（计算机应用技术专业论文）椭圆曲线密码系统多点乘算法研究与实现.pdf

椭圆曲线密码系统多点乘算法研究与实现 摘要 椭圆曲线密码系统( e c c ) 的安全性依赖于椭圆曲线离散对数问题( e c d l p ) 的难解性。与整数因子分解问题( i f p ) 和一般离散对数问题( d l p ) 不同，目前求解 e c d l p 的算法都是全指数时间复杂度的算法，而对前两个问题的求解存在子指 数时间复杂度的算法。在相同安全强度条件下，椭圆曲线密码体制具有较短的 密钥长度，较少的计算量、存储量、带宽等优点。因此，椭圆曲线密码系统被 认为是下代通用的公钥密码系统。 本文主要研究椭圆曲线密码系统的多点乘算法。全文共分6 章叙述。其中， 第一章概括地介绍了椭圆曲线密码研究的背景、意义、现状和本文的内容安排。 第二章给出了椭圆曲线的基本概念和基本理论。第三章着重研究椭圆曲线密码 系统。第四章深入研究椭圆曲线密码体制的关键算法：点乘算法及多点乘算法。 在分析研究已有算法的基础上，在4 4 和4 5 节提出了两个新的多点乘算法，这 两个算法由于对标量的编码均能从左到右实现，所以编码和主计算阶段合并， 节省了存储空间，因此特别适用于现在广泛使用的计算能力较弱、存储空间受 限的设备( 如s m a n 卡等) 上使用。第五章用s u a lc + + 实现了新的多点乘算法。 第六章对全文进行总结以及对下一步工作进行展望。 关键词：椭圆曲线密码系统：点乘算法：多点乘算法；加密解密；数字签名： a b s t r a c t t h es e c u r i t yo fe l l i p t i cc u r v ec r y p t o 乒印h y ( e c c ) r e s t so n 也ed i 筒c u l t ) ，o f s o l v i n gt 1 1 ed i s c r e t el o g a r i 也mp r o b l e mo v e rp o i n t so na 1 1e l l i p t i cc u r v e c u 仃e n t l yt h e b e s ta l g o r i t l l mk n o w nf o rs o i v i n gt h el u l d e r l y i n gm a t l l e m a t i c a l p r o b l e mi ne c ct a l ( e s f u l l ye x p o n e n t i a lt i m e ，i nc o n 虹a s tt om es u b e x p o n e n t i a l t i m ea 1 9 0 r i t h m1 ( 1 l o w nf o rm e i n t c g e rf a c t o r i z a t i o np r o b l e ma n dt h ed i s c r e t el o g a r i m mp r o b l e m t h i sm e a n st h a t s i g n i f i c a n t l ys m a i l e rp a m m 酏粥c a i lb eu s e di ne c ct h a ni no m e rp u b l i ck e ys y s t e m s s u c ha sr s aa n dd s a ，b u t 谢t he q u i v a l e ms e c w i t yl e v e l 1 1 1 es h o n e rk e ys i z e g c n e r a l l yl e a d st oi m p r o v e dc o m l ) u t a t i o n a le 伍c i e n c i e sa t l ds m a l l e rs t o r a g ea n d b a n d w i d t hr e q u i r c m e n t s h e n c et l l ee l l i p t i cc u r v ec r y p t o g r a p h ys e e m st ob et h ef u t u r e s t a n d a r do f p u b l i ck e y c 巧甲t 0 舒a p h y n l em a i nf o c u so ft l l em e s i si st h em u l 却l ep o i mm u l t i p l i c a t i o na l g o r i t h mo f e l l i p t i cc u r v ec r y p t o g m p h yi tc o n s i s t so fs i xc h a p t e r s i nc h a p t e ro n e ， s o m e i n 删u c t i v em a t e r i a l sa r ep r e s e n t e d ，i n c l u d i n gt h em o t i v a t i o n sa 1 1 dt h ed e v e l o p m e n t s o ft l l ee l l i p t i cc u r v ec r y p t o s y s t e m s ，t h ei n t e n t i o n so ft h er e s e a r c hw o r k ，m em a i n c o n t e i l t so ft h ep a p e ri nc h 印t e rt 、o ，s o m en e c e s s a r ya n db a s i cm a t e r i a l so ft 1 1 e e m p t i cc u r v e st h e o r ya r ei n _ 【r o d u c e d i nc h a p t c rt h r e e ，t h ee l l i 面cc u r v ec r y p t o g r a p h y i ss 叫i e d t h ek e ya i g o r i t h m si n c l u d i n gp o i n tm u n i p l i c a t i o na l g o r i t h m sa n d m u l t i p l e p o i mm u l t i p l i c a t i o na l g o r i 恤m so fe c ca r e 胁h e ri r l v e s t i g a f e di nc h a p t e rf o u li n4 4 a n d4 5 ，t w om u l t i p l ep o i n tm u l t i p i i c a t i o na l g o r i m m sa r ed e s i g n e do nm eb a s i so f a r i a l y s i sa n dr e s e a r c ho fk n o w na l g o r i t 塔t h er e c o d i n go ft h es c a l a rcanb e p e f 白r m e df r o mt h em o s ts i g l l 沁c a mb i t ( i e f b ml 硪t or i 曲t ) h e n c er e c o d i n ga 1 1 d e v a i u a t i o n s t a g e c a l lb e m e 唱e d t h e s e t 、v o a l g o r i t l l i t l sa r ep r e f e r a b l eo n m e m o r y c o n s t r a i n ta r dl i m i t e d - p r o c e s s i n g - p o w e rd e v i c e ss u c ha ss m a r t c a r d i n c h a p t e rf i v e ，t h en e wm u l t i p l ep o i n tm l l l t i p l i c a t i o na l g o r i t l 瑚i si m p l e m e n t e du s i n g v i s u a lc + + a tl a s tc h 印t e rs i xs 眦衄a r i z e s 1 ew h o l ep a p e ra 1 1 dp r e v i e w st h e 如t h e r d e v e l o p m e n t so f m ew o r k k e yw o r d s ：e l l i p t i cc u r v ec r y p t o g r 印h y ；s c a l a rm u l t i p l i c a t i o na l g o r i t l l m ；m u l t i s c a l a r m u l t i p l i c a t i o na l g o r i t h m ；e n c r y p t i o n d e c r y p t i o n ；d i g i t a ls i g n a t u r e ； 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学 硕士学位论文质量要求。 主席： 委员： 答辩委员会签名 丝z 房中删定撇 导师： f 乒奸z 芝矗 r 夕寥l f 攻孜 | 别疹後 剥硌张 l 图2 1 图2 2 图4 1 图4 2 图4 3 图4 4 图4 5 插图清单 椭圆曲线上点加运算( r = p + q ) 的几何描述 椭圆曲线上倍点运算( r = 2 p ) 的几何描述 简单的s h 锄i r 多点乘 快速的s h 8 m i r 多点乘一 s h a n l i r - n a f 多点乘- j s f 多点乘- 不同窗口宽度下预计算表尺寸 1 5 1 5 3 7 3 7 3 8 3 9 4 5 表2 一lf 2 4 中元素的表示 表格清单 表4 - l 不同坐标系统下椭圆曲线定义及对应的仿射坐标 表4 2 不同坐标系统下点加及倍点性能比较- 表5 - 1 新的算法与点乘后求点加效率比较 8 3 1 3 1 5 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果也不包含为获得 盒魍互些态堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名一，乍 签字日期：砂万年l 为划白 学位论文版权使用授权书 本学位论文作者完全了解盒妲王些太堂有关保留、使用学位论文的规定有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盒 蟹至些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 “杲密的学位论文在解密后适用本授权书) 学位论文作者签名：乎一乇 签字日期二簖年- 月曲日 7 口霄 ， ” 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 仆锗l t 签字日期；冲厂月“日 电话： 邮编： 致谢 本人在三年的硕士研究生课程学习和撰写学位论文的过程中，自始至终得 到了我的导师侯整风副教授的悉心指导，无论从课程学习、论文选题，还是到 收集资料、论文成稿，都倾注了侯老师的心血，由衷感谢侯老师在学业指导及 各方面所给予我的关心以及从言传身教中学到的为人品质和道德情操，老师广 博的学识、严谨的治学作风、诲人不倦的教育情怀和对事业的忠诚，必将使我 终身受益，并激励我勇往直前。 同时，真诚感谢计算机学院的全体老师，他们的教诲为本文的研究提供了 理论基础，并创造了许多必要条件和学习机会；感谢课程班的同学，在我课程 学习和论文撰写期间，给予我的大力支持。 感谢所有关心、帮助我的人。 作者：程一飞 2 0 0 5 年5 月日 l - l 论文的研究背景和意义 第一章绪论 在计算机网络深入普及的信息时代，信息本身就是时间，就是财富。信息 的传输通道是脆弱的公共信道，信息存储在“不设防”的计算机系统中，如何 保护信息的安全使之不被窃取及不至于被篡改或破坏，已成为当今普遍关注的 重大问题。密码是有效而且可行的办法。 密码学的发展中有两个重要的里程碑：1 9 4 9 年s h a i 】o n 的“保密通信中的数 学理论”和1 9 7 6 年d i 伍e 和h e l l m a n 的“密码学的新方向”。s h a n o n 的理论 使对密码学的研究变成具有一定理论体系的科学；“密码学的新方向”一文提出 了公钥密码的思想，开创了公钥密码学的新纪元。公钥密码提出后，立刻受到 了人们的普遍关注。从1 9 7 6 年以来，人们提出了大量公钥密码体制的实现方案， 所有这些方案的安全性都是基于求解某个数学难题的。到目前为止，既具有一 定安全性又能比较容易实现的密码体制按照所基于的数学难题分类，可分为如 下三类： 1 、基于大数分解问题( i r l t c g e rf a c t o r i z a t i o n p m b l e m ) 的公钥密码体制，如r s a 体制； 2 、基于有限域上离散对数问题( ( d i s c r e t el o g a r i t h mp m b l e m ) 的公钥密码体 制，其中主要包括e l g 锄a 1 类加密体制和签名方案，d i 伍e h e l i m a l l 密钥交换方 案等； 3 、基于椭圆曲线离散对数问题( e l l i p t i cc u r v ed i s c r e t el o g 础t 1 1 mp r o b l e m ) 的公钥密码体制，其中主要包括椭圆曲线型的d i 蚯e h e l i l n a n 密钥交换方案、椭 圆曲线型的m q v 密钥交换方案和椭圆曲线型的数字签名算法等。 椭圆曲线密码体制( e l l i p t i cc u r v ec r y p t o 伊印h ye c c ) ，即基于椭圆曲线离散 对数问题的各种公钥密码体制，最早是1 9 8 5 年分别由v s m i l l e r 【2 j 和n e a l k o b l i t z 3 】独立提出的。它是利用有限域上椭圆曲线的有限点群代替基于离散对 数问题密码体制中的有限循环群所得到的一类密码体制。与其他公钥密码系统 相比，椭圆曲线密码体制有着以下技术优势：安全性更高、计算量小、处理速 度快、存储空间占用少、带宽要求低。另外利用椭圆曲线建立密码体制具有两 大潜在的优点：一是有取之不尽的椭圆曲线可用于构造椭圆曲线有限点群；二 是不存在计算椭圆曲线有限点群的离散对数问题的亚指数算法。因此椭圆曲线 密码系统被认为是下一代最通用的公钥密码系统。 当前，国际上主流的公钥加密技术仍然采用的是r s a 密码体制。但是，先 进的椭圆曲线公钥密码体制已经得到了世界上广泛的认可。安全的电子商务协 议一s e t ( s e c u r ee l e c t r o n i ct r a l l s a c t i o n s ) 的制定者已经把椭圆曲线密码体制作为 下一代s e t 协议中默认的公钥密码算法，几个国际标准化组织也把椭圆曲线密 码体制作为新的信息安全标准。我国也已经将椭圆曲线密码体制作为“十五” 期间的重点研究课题。尽管美欧发达国家在密码技术的理论和应用研究上都处 于世界领先地位，并且已经有了基于椭圆曲线公钥密码体制的密码类产品面世， 但是有关国家对我国采取禁运的政策以及我国在密码管理上实行专控不准使用 进口技术和产品的要求。因此进行椭圆曲线密码体制的理论与应用研究就有着 重要的现实意义。 1 2 椭圆曲线密码体制的研究现状 目前，国外已有用e c c 进行加解密和数字签名的的产品出现在市场上。美 国n e x tc o m p u t e r 公司己开发出快速椭圆曲线加密( f e e ) 算法，其密钥为容易记 忆的字串。加拿大c c r t i c o m 公司也开发出了用于e c c 的集成电路，可实现高效 加密、数字签字、认证和密钥管理等，并已经应用于许多领域。日本m i t s u s h i 诅、 法国n l 呲p s o n 、德国s i e m e i l s 、加拿大w 乱e r l o o 大学等也都在实现这一体制。 这些产品被广泛应用于保密通信、网络安全、电子商务等方面。国内也有几家 公司和研究机构正在研究e c c 的实现，不过还未发现有比较成功的产品出现： 随着e c c 研究的不断深入，e c c 的标准化工作也在紧锣密鼓地进行中。e c c 己被纳入i e e e 公钥密码标准p 1 3 6 3 1 6 】中，包括加密、签名、密钥交换机制等。 同时，a n s i 也在制定椭圆蓝线的相关标准，其中包括椭圆曲线数字签名算法 ( e c d s a ) 标准a n s ix 9 6 2 【崎口椭圆曲线密钥共享和传输协议标准a n s ix 9 6 3 【8 】 等。此外，i s o 【9 】 ” 等组织也在对椭圆曲线的应用制定相关标准。 近几年来，对椭圆曲线密码技术而言，域操作算法已研究得比较成熟，e c c 的安全性也已得到人们的普遍认同。但对e c c 的研究并没有停止，依然是密码 学研究中的热点领域。基于研究现状，其方向主要集中在以下几个方面： ( 1 ) 加快点乘的运算速度 在e c c 系统中，椭圆曲线点乘运算是最耗时间的运算，它决定了整个e c c 系统的性能。因此，进一步加快计算点乘k p 和多点乘k p + l o 的速度，从而提高整 个e c c 系统的性能正成为一个热门的研究领域。点乘运算分为：底层运算( 即 有限域上的算术运算) 和上层运算( 即椭圆曲线有限点群上的各种点运算) 。而 有限域上的算术运算已研究得相当成熟，这里主要是指对椭圆曲线有限点群上 各种点运算的研究。 ( 2 ) 选取合适的椭圆曲线，快速产生椭圆曲线域参数 选取合适的椭圆曲线，即确定椭圆曲线域参数d = ( m ，f f x l ， a ，b ，g ， n ， h ) 。要使用椭圆曲线密码系统，首先需要确定系统的各个参数，这是建立 e c c 系统最花时间的一个步骤，其关键是求椭圆曲线的阶拌( e ( f q ) ) 。虽然可以以 离线的方式产生椭圆曲线域参数，并且一旦产生了一条安全的椭圆曲线后，以 后就可一直使用该曲线来建立椭圆曲线密码系统，但如何快速地以在线的方式 产生可用于密码学的安全的椭圆曲线域参数是密码学者一直在谋求解决的问 题。 ( 3 ) 椭圆曲线密码系统的实现 e c c 的特点使得它特别适合于在计算能力弱的环境( 如w a p 和i c 卡) 下实 现。如何在计算能力弱的环境下实现e c c ，特别是如何充分利用e c c 的计算量 小、占用存储空间少、安全性高等优势，在不增加成本的前提下，在i c 卡上实 现e c c 系统，同时提高i c 卡的实用性，是目前学术界和工业界都在积极考虑 的问题。i c 卡与e c c 的结合不仅可提高i c 卡的安全性、降低i c 卡的成本，而 且还会为i c 卡带来新的用途。 ( 4 ) 设计硬件结构加速e c c 的计算效率 如同r s a 一样，能用硬件实现e c c 系统，那么用e c c 加解密数据的效率 将大大提高，因此如何设计有效的硬件结构来实现e c c 也是人们正在研究的一 个方向。 ( 5 ) 椭圆曲线密码协议的设计 要推广椭圆曲线密码技术的应用，就必须要有基于椭圆曲线密码技术的椭 圆曲线密码协议的支持，目前支持椭圆曲线技术的密码协议还很少，因此设计 新的基于椭圆曲线密码系统的密码协议是学者们现在和将来的一项任务。 1 ：3 论文的研究重点及内容安排 1 3 1 论文的研究重点 在椭圆曲线数字签名e c d s a 协议的签名验证过程中，需要多点乘计算。 多点乘计算在其他密码协议中也经常出现，例如基于椭圆曲线密码体制的密钥 协商( k c ya g r e e m e n t ) ，各种多方协议( m u l t i _ p a r t i e sp r o t o c 0 1 ) 等等。多点乘是椭圆 曲线密码应用中的核心计算。一般的多点乘形如：k i p l + k 2p 2 + t + k tp t ，其中 k i 是整数，p i 是椭圆曲线上的点。它的运算速度关系着许多密码应用的效率。 因此，对它的研究有着非常重要的意义。本文着重研究点乘算法及多点乘算法， 并提出了二个新的多点乘算法：窗口m o fi m e r l ea _ “雌多点乘算法和f r a c t i o n a l w m o fi n t e r l e a v i n g 多点乘算法，它们都非常适合内存受限环境下使用。 1 3 2 论文的内容安排 第一章引言。问题的提出，研究背景，现状和意义。 第二章椭圆曲线密码体制的基本理论。介绍了有限域、有限域上基本运算、 椭圆盐线、椭圆曲线上的有限点群及其运算、椭圆曲线离散对数问题。 第三章基于椭圆曲线的密码学协议研究。主要介绍椭圆曲线域参数、密钥 生成、椭圆曲线密钥交换体制、椭圆曲线加解密、椭圆曲线数字签名、椭圆曲 线盲签名以及椭圆曲线代理签名。 第四章椭圆曲线密码关键算法的研究。充分研究主流的点乘算法及多点乘 算法，并提出了新的多点乘算法。 第五章算法的实现。给出新算法的实现环境、实验结果以及分析。 第六章总结及展望。对全文进行总结以及对一步工作进行展望。 第二章椭圆曲线基础理论研究 1 9 8 5 年n e a lk o b l i t z 和v s m i l l e r 把椭圆曲线的研究成果应用到密码学中， 分别独立提出在公钥密码系统中使用椭圆曲线的思想。这种思想的基础是定义 在有限域上的椭圆曲线点集可以构成a b e l i a n 群，由此可以定义其上的离散对 数，即椭圆曲线离散对数。求解椭圆曲线离散对数是非常困难的，所以通信双 方可以据此构造公钥密码体制椭圆曲线密码体制。 本章描述椭圆曲线密码学的基本数学原理。2 1 节介绍群、域、有限域，2 2 节给出有限域f 2 ”中的元素在多项式基表示下的运算算法，2 3 节描述椭圆曲线 相关概念、椭圆曲线点基本运算及椭圆曲线离散对数问题。 2 1 数学基础【1 1 2 1 1 群和域的概念 1 ) 群的定义与性质 定义2 1 1 1 ：如果一个非空的集合g ，对于二元代数运算0 来说满足以下 条件： g 对于运算0 是封闭的：对任意的a ，b g ，满足a o b g ； 结合律成立：对任意a ，b ，c g ，满足( a o b ) 0 c = a o ( b o c ) ； 存在单位元e ：即存在e g ，对任意a g ，恒有e o a - a o e = a ； 存在逆元素：对任意a g ，恒有b g ，使a o b _ b o a _ e 。元素b 称 为a 的逆元素，用a - 1 表示，即b = a - 1 ； 则称 为群。 定义2 1 1 2 ：若对于v a ，b g ，有a o b _ b o a ，则称群g 为阿贝尔( a b e l i a l l ) 群或交换群。 定义2 1 1 3 ：设g 是群，v a g ，n z ，则a 的n 次幂 kn = 。 d “= d ”1 乜 n o i f 日) ” n 0 ，n m 易知：a m o a n = a ”“。 元素a 的阶m 定义为使a m = e 成立的最小正整数m 。 定义2 1 1 4 ：如果集合g 中只含有限多个元素，则我们称 为有限 群，此时集合g 中元素的个数称为有限群g 的阶。 定义2 1 1 5 ：设 是一个群，如果群g 中存在一个元素o ，使得对 群g 中任意元素b 都存在一个整数i 使得b = a 1 ，则称g 是一个循环群。元素a 称为g 的一个生成元。 2 ) 域的定义与性质 设f 是至少含有两个元素的集合，对f 定义两种二元运算“+ ”和“，并 且满足以下三条件的代数系统 ，称为域。 i f 的元素关于“+ ”运算构成一个网贝尔群，设其单位元为o ； i i f o 关于咻”运算构成一个阿贝尔群； i i i 对于v a ， b ， c f ，分配律成立。即： a 木( b + c ) = ( a + b ) + ( a + c ) ，( a + b ) + c = ( a + c ) + ( b 4 c ) 。 如果域f 中元素的个数有限，则称f 为有限域或伽罗瓦( g a l o i s ) 域，定义f 上元素的个数为f 的阶，记为撑f 。 2 1 2 有限域 一个有限域由一个有限集合f 和定义在f 上满足某种算术属性的两个二元 操作+ 和构成。域上元素的个数称为有限域的阶。当且仅当q 是一个素数幂时， 存在阶为q 的有限域，并且当q 是素数幂时，仅仅存在一个阶为q 的有限域， 表示为f q 或g f ( q ) 。对于f 日上元素的表示方法有许多种，其中一些表示使得 域上的算术运算在硬件或软件上能更有效地实现。 如果q = p “( p 是一个素数，m 是一个正整数) ，那么p 称为的f q 特征，m 称为的f 。扩展次数，该有限域元素阶为q = p “。在椭圆曲线密码体制中，两种 常用的有限域是素数域r 和特征为2 的有限域f 2 m 。 2 1 3 素数域f p 设p 是一个素数，整数集合 o ，1 ，2 ，p 1 ) 构成一个有限域，记为 f d ( 1 ) f p 的加法运算：设x ，y 是f p 中的元素，则加法结果为( x 十y ) m o d p 。加 法单位元即零元素：0 。域元素x 的加法逆元为( 一x ) m o dp ，即p x 。 ( 2 ) f p 的乘法辱算：设x ，y 是f p 中的元素，则乘法结果为( x y ) m o d p 。乘法 单位元：1 ； ( 3 ) 除法( 求逆) ：若a 是f 。上的非零元，a 的模p 逆，记为a 1 ，是唯一整数 c ，其中c r ，并且a c = 1 ( m o d p ) 。 2 1 4 特征为2 的有限域f 2 “ 有限域f 2 称为特征为2 的有限域或二元有限域，是二元域f 2 的m 次扩域， 其中f 2 的元素为o 和1 ，可以理解为f 2 上的m 维向量空间。在f 2 ”中存在m 个 元素oo ，ol ，om 1 的集合，使f 2 “中的每一个元素a 均可唯一表示成如 h i 一1 下形式：a - q 口。，其中a ( o ，1 ) ，集合 o ，l ，。1 称为f 2 上f 2 m ，= 1 的基。给出一组基，则域元素a 可以表示为长度为m 的二进制位串( a o ，a l 。， a f r i 1 ) 。域元素的加可由其向量表示串按位异或得到，域元素的乘法规则需根据 所选择的基而定。在f 2 ”上有许多种不同的基可供选择，但在f 2 上算术运算的 软件或硬件实现上，其中一些基比其它基更有效。例如，a n s ix 9 6 2 允许两种 基：多项式基和正规基。下面介绍多项式基及多项式基算术运算。 多项式基： 多项式基( p o i y n o m i a lb a s i s ) 也称标准基( s t a l l d a r db a s i s ) ，是形如 ( 1 ，1 ， n ，a ) 的基，这里n 是f 2 上某个不可约多项式的一个根。 多项式基是描述有限域最直观的方式。设f ( x ) = x “+ f m 1 x ”1 + + f l x + 晶( 其中 丘 o ，1 ) ，i - o ，1 ，m 一1 ) = x 斗t ( x ) 是f 2 上m 次不可约多项式( i r r e d u c i b l e p 6 l y n o m i a l ) 。那么有限域f 2 可以看成是f 2 上所有次数小于m 的多项式集合： f 2 。生 a m 1 x 丌卜1 + + a l x + a 0 陋 o ，l 。 域中的元素a f n i x ”1 + + a l x + a 0 一般用长度为m 的二进制串( a m l a l a 0 ) 表 示。因此f 2 n 1 _ a l n 1 x ”l + + a l x + a o l a o ，1 j 就是所有长度为m 的二进制数串 的集合。不可约多项式f ( x ) 称为的有限域f 2 “归约多项式( r e d u c t i o n p o l y n o m i a l ) 。 有限域f 2 中的元素在多项式基表示下的运算： 设f 取) 为归约多项式，a = ( a m 1 a l a o ) ，b = ( bm 1 b l b o ) ( 1 ) 加法：a + b = c = ( c 。1 c l c o ) ，其中c i - ( a i + b i ) m o d2 。即域中的加法是按位异 或。 ( 2 ) 减法：减法运算同加法运算。 ( 3 ) 乘法：a b = c = ( c m 小c l c 0 ) ，其中c ( x ) = ：1 c ，x 。，是多项式( 三q x 。) ( ：b 工7 ) 除以归约项式f ( x ) 的余式。即 ( c m j x m 1 + + c i x + c o ) = ( a m i x m 。1 + + a l x + a o ) ( b m 1 x m 。1 + + b i x + b o ) m o df x ) ( 4 ) 平方： ( p m 1 x m 1 + + c l x + c o ) = ( a m 1 x m - 1 + + a l x + a o ) ( a m 1 x m 。+ + a l x + a o ) m o d f 辑) 我们把它作为两乘数相同的乘法运算。 ( 5 ) 乘法逆运算： 在多项式基表示下，域乘法运算可以看作是模不可约多项式乘法。 因为定义多项式f ( x ) 不可约，所以对任意一个非零元素e f 2 ，对应的多 项式e ( x ) ，都有 g c d ( f ( x ) ，e ( x ) ) = 1 g c d ( ) 表示求最大公因式。于是存在多项式s ( x ) 和t ( x ) ，使得 f ( x ) s ( x ) + e ( x ) t ( x ) _ 1 所以e ( x ) t ( x ) = 1 ( m o df ( x ) ) “x ) 对应的元素t = e ，称为非零元素e 的逆。 从另一角度看，f 2 可以被看作是f 2 上的m 维向量空间。在多项式基表示 下，这个向量空间的基向量就是( 1 ，a ，a ) ，a 是f ( x ) = o 在f 2 上的一 个根。那么f 2 “中任何一个元素都可以用这组基唯一地表示。 每个有限域f q 至少有一个元素称为本原元( p r i m i t i v ee i e m e m ) ，它的阶为 q 1 ，如果f ( x ) = o 的任何一个根a 均是f q 的一个本原元，那么f ( x ) 称为生成多项式。 如果f ( x ) 是生成多项式，那么f q 所有q 个元素可表示成o 以及a 的l 到q 一1 次幂的集 合，即可表示成如下形式： 0 ，q ，q ，n ”1 = l l 例( 有限域f 2 4 上的多项式基表示) 令取) = x 4 + x + l 是生成多项式，如果a 是 f ( x ) = o 的一个根，那么f ( a ) = d 。+ a + 1 = 0 ，而对于二元有限域，减法运算等同 于加法运算，于是n = a 1 = n + 1 。那么这1 6 个元素可以表示成如下表2 。1 的 形式： 表2 1f 2 4 中元素的表示 f 2 4 中的元素多项式表示坐标表示 oo( 0 0 0 0 ) ad ( 0 0 1 0 ) 22 a n( 0 1 0 0 ) 3 3 q ( 1 0 0 0 ) 4 q+ 1 ( 0 0 1 1 ) 52 aa+a ( 0 1 1 0 ) 632 q+ ( 1 1 0 0 ) 7 o3 + 2 + l ( 1 1 0 1 ) d 8 a2 + 1 ( 0 1 0 1 ) d 93 qn+a ( 1 0 1 0 ) 1 0 q q + a + 1( 0 】1 1 ) l l32 qd+a+d ( 1 l l o ) 1 2 q3 + q2 + d + 1 ( 1 1 1 1 ) 】332 a d + a + 1( 1 1 0 1 ) 1 4 q3 + 1 ( 1 0 0 1 ) q 1 5 q 1( 0 0 0 1 ) 2 2 有限域f 2 ”中的元素在多项式基表示下的运算算法1 1 3 1 2 2 1 域元素表示 在软件实现中，我们通常用一个数组来存贮元素a ，设计算机的字长为3 2 位，则需要t = 3 2 个数组元素，每个数组元素是一个3 2 位二进制数的数组 a = ( a 【t - 1 】，a 【2 ，a f l 】，a o 】) 来表示，其中a 【o 的最右位是a 0 ，且a 【 - l 】 的最左s = 3 2 t 唧位未用，将其置o 。 2 2 2 加法运算 加法：加法即对应二进制位异或 算法2 1 ：有限域f 2 “加法 输入：a _ ( a m 1 a i 勘f 2 m ，b = ( b m - i - b i b o ) f 2 “ 输出：c = a + b = ( c m 小c l c o ) 1 f o r j 行o m0 t o t - 1d o s e tc d 】一a 【j 】0 b 【j 】a d 】0 b j 】表示对应位异或 2 r e t u m ( c ) 2 2 3 模约简运算 模约简：根据乘法定义，多项式乘法或平方的结果必须规约一个m 次不可 约多项式f 酝) 。当f ) 是三项或五项式时，约简操作效率特别高。以下算法通过 减少a ( x ) 次数直到小于等于m 计算x ) m o df ( x ) 。 算法2 2 ： 输入：a _ ( a 2 。“a l a 。) ，仁( f m f m _ 1 f l f 0 ) 输出：c = a m o d f 1 f o r i 丘o m 2 m - 2 t o m d o f o r j 行o m o t o m 一1d o i f 0 ot h e na j i t i + j + 一a i m 十j + a i 2 r e t 哪( c 一( a m i 8 1 a 0 ) ) 当f ( x ) 是三项或五项多项式时，约简运算效率更高，一次可以处理一个字。 例如，生成多项式f ( x ) = x 1 6 3 + x 7 + x 6 + x 3 + 1 ，则由该多项式生成的有限域f 2 1 6 3 中任 何一个元素次数都小于等于1 6 2 ，故任何二个元素相乘或任何一个元素的平方次 数都小于3 2 4 ，则在3 2 位处理器上，需要用1 1 个元素来表示。下面观察c ( x ) 的第九个元素c 【9 】m o df ) ： x 2 8 8 ：x 1 3 2 + x 1 3 1 + x 1 2 8 + x 1 2 5m o d 盯x 1 x 2 8 9 = = x 1 3 3 + x 1 3 2 + x 1 2 9 + x 1 2 6m o df f x l ； x 3 1 9 = x 1 6 3 + x 1 6 2 + x 15 9 + x 1 5 6m o df r x l 观察上面同余式，可知约简c 9 可通过将c 【9 】加四次到c 中，具体见算法 2 ，3 ： 算法2 3 ：模约简( o n e w o r da t a t i m e ) 输入：一：元多项式c ( x ) ，最高次数不超过3 2 4 输出：c ( x ) m o df ( x ) ，其中f ( x ) = f ( x ) = x 1 6 3 + x 7 + x 6 + x 3 + l 1 f o r i 厅o m1 0 t o6d o ，约简c i m o d f ( x ) 1 1 t c 脚 1 2c i 一6 c i 6 】0 ( t 2 9 ) l 3c i 5 c i - 5 】0 ( t 4 ) 0 口 3 ) 1 4c i 一4 】c i 卅0 ( t 2 8 ) 0 ( t 2 9 ) 2 t c 【5 a n d0 x 毋葡髓清除c 5 】的第o ，1 ，2 位 3 c 【o - c 【o o ( t 4 ) o ( t 3 ) 4 c 【1 c 1 o ( t 2 8 ) o ( t 2 9 ) 5 c 【5 c 5 a 1 1 do x o o 0 0 0 0 0 7 清除c 【5 】的未用的位 6 r e t u m ( ( c 5 】，c 4 】，c 【3 】，c 2 】，c 【1 】，c o ” 算法2 3 可以很容易移植到其它三项或五项多项式模约简。由于目前选择 生成多项式，常选用三项或五项多项式，而对于生成多项式是三项或五项时， 算法2 3 比算法2 2 快。 2 2 4 平方运算 平方：“x ) 2 = ( 芝口，x 。) 2 = 芝口；x 2 j 算法2 4 ： 8 1 9 输入：a = ( a 。小a l a o ) ，仁( f m f m 1 f j f 0 ) 输出：b = a 2 m o d f 1 p r e c o m p u t a t i o n ：对一个字节v = ( v 7 ，v 1 ，v o ) ，计算1 6 位的数 t ( v ) = ( 0 ，v 7 ，0 ，v 1 ，o ，v 0 ) 2 f o r i f b m0 t o t - ld o a i 】= ( u 3 ，1 1 2 ，u 1 ，u o ) c 2 i 】一( t ( u 1 ) ，t ( u o ) ) ，c 【2 i + 1 一口( u 3 ) ，t ( u 2 ) ) 3 计算b c ( x ) m o df 礅) ，用算法2 - 2 4 r e t i l m ( b ) 算法2 4 第一步预计算每一个8 位二进制( v 7 ，v 1 ，v o ) 对应的1 6 位( o ， v 7 ，o ，v 1 ，o ，v o ) 形式，将结果用2 5 6 个元素数组t 来存贮；第二步内循 环首先将每一个字分成4 个字节u 3 ，u 2 c 【2 i 】， ( t ( u 3 ) ，t ( u 2 ) ) 赋值给c 【2 i + 1 】， 2 2 5 乘法运算 u 1 ，u 0 ，并将( t ( u 1 ) ，t ( u o ) ) 赋值给 第三步采用算法2 2 对c 进行约简。 移位加方法是基于以下事实： a b = a 们，l x m 。1 b + + a l x b + a o b 由此，我们可以先计算x i b m o df ( x ) ，然后判断a i 是否为1 ，若为i 则将x l b m o d f ( x ) 累加到c 中，否则c 不变。x 飞是把b 向量左移i 位，计算x l b m o df ( x ) 的方 法很简单，首先把表示b 的向量向左移一位( 即先计算x b 的值) ，然后判断b 。= 1 是否成立，若成立则表示计算结果是m ( 已大于m 1 ) 次多项式，需进行约简。 约简的方法是把移位后所得的结果与r ( x ) 相加即可( 因为x ”m o df ( x ) = r ( x ) ) 。下 面给出移位相加法算法( 算法2 5 ) ，它用移位相加法计算域乘，所以该算法称为 称移位相加。 算法2 5 ：从右到左移位加算法 输入：a = ( a f n “a l 呦f 2 “，b = ( b 。1 - b l b o ) f 2 输出：c = a bm o df ( x ) = ( c m i - c l c o ) 1 i f a 0 = l 也e nc b ；e l s ec o 2 f o r i 丹o m l t o m 一1d o 2 1b b x m o d f 取) 2 2i f a = 1n l e nc c + b 3 r e t u r n ( c ) 如果已经计算出x - b ，i o ，3 1 】，则x i + 3 2 j b 只需在x b 右加上j 个内容为。 的数组元素。记c = ( c 【t - 1 ，c 2 】，c 【1 】，c o ) ，c j ) - ( c t 一1 】，c d + 】 ， c d 】) 。于是有以下算法： 算法2 6 ：从左到右梳状乘法 输入： a ( x ) ，b ( x ) f 2 “ 输出：c ( x ) = a ( x ) b ( x ) m o d f ( x ) 1 c 一o 2 f o r k f r o m3 1t ood o 2 1 f o r jf r o mo t o t 一1d o i f a j 】的第k 位= 1t h e nc m = c j + b 2 2i f k 0 t h e n c c x 3 jc c m o d f (