（计算机应用技术专业论文）基于椭圆曲线密码体制的数字签名算法及其fpga实现.pdf

武汉理工大学硕士学位论文 摘要 随着计算机运算速度的提高和计算机网络的发展，基于离散对数问题和大 整数因子分解问题的数字签名算法越来越不能满足信息安全的需要。为了满足 信息安全的要求，安全性依赖于椭圆曲线离散对数困难问题( e c d l p ) 的椭圆曲线 密码体制是当前密码学界研究的热点之一。现有的求解e c d l p 的算法都是全指 数时间复杂度的算法。由于专用集成电路具有速度快、性能好、安全性高等优 势，使得采用专用集成电路来实现椭圆曲线密码体制已成为主要趋势。因此， 本课题着眼于应用，针对基于椭圆曲线数字签名算法的f p g a 实现进行了较为 深入的探讨与研究。 本课题从实际应用的需要出发，以初等数论、有限域理论、数字签名技术 和椭圆曲线理论为依据，确定了如下基于椭圆曲线数字签名算法的硬件实现方 案：首先，对实现基于椭圆曲线数字签名算法所需的算法和技术进行了剖析和 系统设计。然后，按照层次化、模块化的设计思想，在x i n l i n x 公司的i s e7 1 工具中，采用硬件描述语言v h d l 作为设计输入，对各运算器和控制模块进行 电路设计；采用m e n t e r 公司的m o d e l s i ms e6 2 b 工具对之进行功能仿真，以保 证底层设计的正确性。最后，在确保每个模块的设计正确的前提下，完成电路 的总体设计，再进行总体设计的仿真与测试。 本课题对s c h n o r r 数字签名算法的改进，实现了比未改进前的s c h n o r r 数字 签名算法平均节省三分之一的运行时间。对基于椭圆曲线数字签名算法的设计 也获得了良好的指标：产生签名只需要i r e s 多的时间，验证签名也需要不到3 m s 。 本课题的研究对实现电子交易安全方面有重要的作用，尤其是在密钥分配、电 子货币、电子证券、电子商务和电子政务等领域都有重要的应用价值，其成果 具有广泛的应用前景。 关键词：椭圆曲线密码体制；数字签名；有限域算术；标量乘法；f p g a 武汉理工大学硕士学位论文 a b s t r a c t w i t ht h ei m p r o v e m e n tn f t h em a r r i n gs p e e do f c o m p u t e ra n dt h ed e v e l o p m e n to f c o m p u t e rn e t w o r k s , b a s e do nt h ed i s c r e t el o g a r i t h mp r o b l e m ( d l p ) o rt h ei n t e g e r f a e t o r i z a t i o np r o b l e m ( i f p ) o ft h ed i g i t a ls i g n a t u r ea l g o r i t h mi n c r e a s i n g l yu n a b l et o m e e tt h en e e df o ri n f o r m a t i o ns e c u r i t y t om e e tt h ei n f o r m a t i o ns e c u r i t yr e q u i r e m e n t s , e l l i p t i cc u r v ec r y p t o s y s t e mw h i c hi t ss e c u r i t yd e p e n d so ne l l i p t i cc u r v ed i s c r e t e l o g a r i t h mp r o b l e mi sc u r r e n t l yo n eo fr e s e a r c hb e t si nc r y p t o g r a p h y t h ee x i s t i n g a l g o r i t h mf o re l l i p t i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m ( e c d l p ) i st h ew h o l ei n d e x t i m ec o m p l e x i t ya l g o r i t h m a sa s i ch a st h ea d v a n t a g e so ff a s t e rs p e e d , b e t t e r p e r f o r m a n c ea n dh i g h e rs e c u r i t y ，t h u st h ea s i ct oi m p l e m e n te l l i p t i c c u r v e c r y p t o s y s t e mh a s b e c o m ea m a j o rt r e n d t h e r e f o r e ，t h e i s s u ef o c u so n a p p l i c a t i o n ，a n di m p l e m e n td i g i t a ls i g n a t u r ea l g o r i t h mb a s e do nt h ee l l i p t i cc u r v e i nf p g af o ram o r ei n - d e p t hd i s c u s s i o na n dr e s e a r c h f r o mt h ei s s u eo ft h ep r a c t i c a l a p p l i c a t i o n ，t h e i s s u eh a sd e t e r m i n e dt h e f o l l o w i n gh a r d w a r ep r o g r a m so f e l l i p t i cc u r v ed i g i t a ls i g n a t u r ea l g o r i t h mb a s e do n t h ee l e m e n t a r yn u m b e rt h e o r y , t h ef i n i t ef i e l dt h e o r y , d i g i t a ls i g n a t u r et e c h n o l o g ya n d e l l i p t i cc u r v et h e o r y ：f i r s t , t h ei s s u ea n a l y s i st h ea l g o r i t h m sa n dt e c h n i q u e sf o rt h e d i g i t a ls i g n a t u r ea l g o r i t h mb a s e do nt h ee l l i p t i cc u r v ea n dd e s i g nt h er e q u i r e m e n t s o fw h o l es y s t e m ，s e c o n d l y , i na c c o r d a n c ew i t ht h eh i e r a r c h i c a la n dm o d u l a rd e s i g n i d e a s ，a n di nt h ec o m p a n yx i n l i n x7 1i s et o o l s ，e a c ha r i t h m e t i cu n i ta n dc o n t r o l m o d u l eh a v eb e e nd e s i g n e da sc i r c u i ti n p u ti nv h d l ；t h em o d u l ed e s i g nh a v eb e e n s i m u l a t t a di nf u n c t i o nu s i n gm o d e l s i ms e6 2 bo fm e n t e rc o m p a n i e s t h a tt o e n s u l - et h ec o r r e c t n e s so f t h eb o t t o md e s i g n t h e n , t oe n s u r et h a te a c hm o d u l ed e s i g n i sc o r r e c t , t h ec o m p l e t i o no f t h et o p - l e v e lc i r c u i td e s i g na n ds i m u l a t i o nf o rt h eo v e r a l l f i n a l l y , l o g i cs y n t h e s i s , a n da f t e rl a y o u t ，m u t i n gt i m i n ga f t e rt h ec o m p l e t i o no f s i m u l a t i o n d e s i g nh a sb e e nt e s ta n ds i m u l a t e dw h i c hs e l e c t e dp i e c e si sv e r t e xf i g a s e r i e sx c v l 0 0 0o f i n l i n xc o m p a n y w i t ht h ei m p r o v e m e n tf o rs c h n o r ro f d i g i t a ls i g n a t u r ea l g o r i t h m ，t h i sp a p e rs a v er n 武汉理工大学硕士学位论文 a v e r a g eo n e - t h i r do ft h er u n n i n gt i m ec o m p a r e dw i t hs c h n o r rd i g i t a ls i g n a t u r e a l g o r i t h mh a v e n ti m p r o v e d 日1 ed e s i g no fd i g i t a ls i g n a t u r ea l g o r r h mb a s e do n e l l i p t i cc u r v ei sag o o di n d i c a t o r ：t h ep r o c e s so fs i g n a t u r eo n l yn e e dt oh a v em o r e t h a ni m s t h ep r o c e s so fs i g n e dc e r t i f i c a t i o na l s or e q u i r e sl e g st h a n3 m s t h e r e s e a r c ho ft h ei s s u eh a sp l a y e da ni m p o r t a n tr o l eo nt h es e c u r i t yo fe l e c t r o n i c t r a n s a c t i o n s , e s p e c i a l l yi nt h ek e yd i s t r i b u t i o n , e l e c t r o n i cc u r r e n c y , e - c o m m e r c ea n d e - g o v e r n m e n ta n do t h e rf i e l d s ，a n dt h er e s u r sh a v e b r o a da p p l i c a t i o np r o s p e c t s k e y w o r d s ：e l l i p t i cc u r v ec r y p t s y s t e m ；d i g i t a ls i g n a t u r e ；f i n i t ef i e l da r i t h m e t i c ； s c a l a rn m l t i p l i c a t i o n ；f p g a m 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题的提出及研究的意义 随着计算机和通信网络技术的飞速发展和广泛使用，社会的信息化程度越 来越高，信息共享服务也上升到了一个新的高度，社会对计算机和网络系统的 依赖性也越来越大【。但是，如果计算机网络系统的安全受到危害，不仅会干涉 到我们个人的隐私问题，而且会危及到国家的安全，引起社会的混乱，从而在 政治上和经济上造成巨大的损失。因此，信息安全问题已经成为世人关注的社 会问题，并成为计算机科学技术的研究热点l 如。然而，确保计算机和网络系统的 安全是一个系统工程，必须从整体出发，从多方面着手。就信息安全技术本身 而言，它包括了很多学科分支。比如密码技术、信息隐藏技术、防火墙技术、 入侵检测技术( 有主动与被动) 、蜜罐与蜜网技术以及虚拟专用网技术等1 3 l 。如 果说计算机的硬件结构和操作系统的安全是信息安全的基础，则保护信息的安 全性、真实性、完整性以及不可否认性的密码技术就是信息安全的核心技术【4 】【l 。 数字签名技术是密码技术中的一个分支，主要用于解决伪造、抵赖、冒充 和篡改等安全问题。一般的数字签名算法都是基于公钥密码体制的，在大多数 公钥密码技术中，用得比较多的是基于大整数因数分解困难问题的r s a 数字签 名算法或是基于离散对数困难问题的数字签名算法( 如d s a 数字签名算法) ， 还有一种是基于椭圆曲线离散对数困难问题的数字签名算法( 三类数字签名将 在1 2 节中作进一步讨论) 。后者与前两者相比有许多优点，如椭圆密码机制的 签名算法能提供更好的加密强度、更快的执行效率和更短的密钥长度，具有较 小的资源开销( 所需的计算理量、存储量、带宽、软件和硬件的实现规模等) 和延时( 加密和签名速度快) l i l 。 随着计算机运算速度的提高和计算机网络的发展，求解有限域上的离散对 数问题和大整数因子分解问题的研究得到了长足的进步。为了达到保密安全的 要求，大多数公钥密码体制的密钥也越来越大，如r s a 公钥密码的密钥一般为 1 0 2 4 位，要求较高的密钥为2 0 4 8 位。传统的软件加解密方式已经难以满足速度 和安全的要求，为了满足上百兆到上千兆的加密速率，必须采用硬件实现。与 武汉理工大学硕士学位论文 软件加密相比，硬件加密具有加密速度快、性能好等优势，并且便于物理保护， 安全性好【卯。因此，本课题对基于椭圆曲线密码体制的数字签名算法的硬件实现 方面的研究，具有非常现实的意义。 1 2 密码技术的介绍 密码学的研究与应用已有几千年的历史，但作为一门科学是2 0 世纪5 0 年 代才开始的。目前密码技术已经从外交和军事领域走向公开，且已发展成为一 门综合数学、计算机科学、电子与通信、微电子物理学、生物学等学科和技术 的交叉学科嗍。使用密码技术不仅可以保证信息的机密性，而且可以保证信息的 完整性和确定性，防止信息被篡改、伪造和假冒。s h a n n o n 于1 9 4 9 年提出了保 密通信系统模型【2 l 】。一般说来，按照k e r c k h o f f 原则，系统的保密性不依赖于加 密体制或算法的保密，而只依赖于密钥的安全。也就是说加密和解密算法是公 开的，密码分析者可以知道算法与密文，但由于他并不知道密钥，因此仍难于 将密文还原为明文。根据密钥的使用类型的不同可将现代密码技术分为两类： 一类是对称加密技术，另一类是非对称加密技术门。 加密密钥和解密密钥两者可以相同，也可以不同。当使用的加密密钥与解 密密钥相同时，这类算法称为对称密钥算法，也叫私有密钥算法。不相同时称 为非对称密钥算法或公钥密码算法。 对称密钥算法从加密模式上又可分为序列密码算法和分组密码算法两大类 嗣。在对称加密系统中，由于加解密钥与解密密钥相同，需要通信的双方必须选 择和保存相同的密钥，都必须信任对方不会将密钥泄密出去，这样才可以实现 数据的机密性和完整性。而在公钥密码算法中，加密密钥可以公之与众，谁都 可以使用，但必须保密好解密密钥。 对称密码算法的优点是加解密速度快；其缺点是密钥的分发和管理非常复 杂，无法对信息发送人的身份进行认证并检验信息的完整性，因而很难用于数 字签名。公钥密码算法可以很好地解决这两方面的问题。 自从1 9 7 6 年d i f i l e 和h e l l m a n 提出了公钥密码的概念以来，出现了很多的 公钥密码算法，所有的这些算法的安全性都依赖于相应的数学难题【9 j ： ( 1 ) 整数因数分解闯题( p ) ：如r s a 公钥密码算法。 ( 2 ) 离散对数问题( d l p ) ：如数字签名标准算法s a ) 、e l g a m a l 加密和签名 2 武汉理工大学硕士学位论文 方案、s c l m o t r 数字签名算法和n y b e r g - r u e p p e l 签名算法。 ( 3 ) 椭圆曲线离散对数问题( e c d l p ) ：如椭圆曲线密码o s c c ) ，基于椭圆曲 线的各种数字签名方案( 椭圆曲线版本的d i f f i e - h e l l m a n 和m q v 密钥交换方案， e 1 g a m a l 加密和签名方案，s c h n o 盯和n y b c r g r u e p p e l 签名方案) 。 以上闯题都没有被证明是难解的，只是鉴于目前的技术条件而言是安全的。 因为，这些算法经过全世界的数学家和计算机科学家长年的细致研究，还没有 发现有效的快速算法破解它们。 下面对几个在通信系统中用得最多的公钥密码体制进行简要的分析和比 较。r s a 公钥密码体制是r i v e s t ，s h a m i r 和a d l e m a n 于1 9 7 7 年提出的，它的安 全性是基于大整数因数分解的困难问题。基于离散对数难题的数字签名算法 ( d s a ) 是在e i g a m a l 加密签名方案和s c h n o l t 数字签名方案的基础之上提出来 的。椭圆曲线密码体制是v i c t o rm i l l e 和n e a lk o b i 娩在1 9 8 5 年分别独立地提出 来的p 7 1 田】，它的安全性是基于椭圆曲线上的离散对数难题( e c d l p ) 。相对于公 钥密码算法( g s a ) 和数字签名标准算法回s a ) 等系统，椭圆曲线密码最吸引人的 主要原因是求解其数学难题( e c d l p ) 的己知最好算法也要用完全指数时间，因为 r s a 和d s a 所基于的数学难题( 即因数分解i f p 和离散对数d l p 问题) 都有亚指 数时间算法。这意味着随着长度的增加，求解e c d l p 的难度比求解i f p 和d l p 的难度增加得快得多。因此e c c 仅需要更小的密钥长度就可以提供跟r s a 和 d s a 相当的安全性，具体密钥长度的评估见表1 1 t 1 1 。 表1 1 相同安全强度的r s a d s a 和e c c 的密钥长度 r s r 密钥长度( b i t )d s a 密钥长度( b i t )e c c 密钥长度( b i t ) 5 1 25 1 21 0 6 7 6 8 7 6 8 1 3 2 1 0 2 41 0 2 41 6 0 2 0 4 82 0 4 8 2 2 4 3 0 7 2 3 0 7 22 5 6 8 1 9 28 1 9 23 8 4 1 5 3 6 01 5 3 6 05 1 2 密码系统的安全性能一般通过该系统所使用的算法的抗攻击强度来反映。 本课题研究的椭圆曲线密码体制( e c c ) 和其他几种公钥系统相比，无论从抵抗攻 击能力还是从密钥长度方面，e c c 显然具有绝对的优势。目前应用最为广泛的 是r s a 公钥密码系统，因为r s a 公钥密码算法的原理很简单，用软件和硬件实 3 武汉理工大学硕士学位论文 现都很容易。但是，随着计算机速度和求解大整数因子分解方法的不断完善和 涌现，为了保证公钥密码系统r s a 的安全性，就要相应地增加其密钥的位数， 目前一般认为r s a 系统需要1 0 2 4b i t 以上的字长才有安全保障。但是，密钥长 度的增加导致其加密解密速度大大降低，软硬件实现也变得越来越困难，从而 使得r s a 公钥密码系统应用范围越来越受到制约。从表1 1 中的数据可以看出， 数字签名标准算法( d s a ) 和r s a 公钥密码算法具有相同的安全强度，而椭圆曲 线密码体制( e c c ) 在相同安全的强度下则具有较短的密钥长度。例如，密钥长度 为1 6 0b i t 椭圆衄线密码系统与密钥长度为1 0 2 4b i t 的r s a 和d s a 系统具有相 同的安全强度；密钥长度为5 1 2b i t 椭圆曲线密码系统却与密钥长度为1 5 3 6 0b i t 的l i s a 和d s a 系统具有相同的安全强度。这就意味着带宽要求更低，所占的存 储空间更小，今后椭圆曲线密码系统的使用也更加广泛。 1 3 椭圆曲线密码的研究现状 从1 9 8 5 年以来，椭圆曲线密码( e c c ) 受到全世界密码学家、数学家和计算 机科学家的密切关注。但在当时，他们都认为e c c 的概念仅是数学范畴的，而 其实际实现是不现实的。如今椭圆曲线密码( e c c ) 不仅可以被容易实现，而且成 为己知的效率最高、安全强度大的公钥密码系统。一方面，由于至今没有发现 椭圆曲线密码( e c c ) 有明显的漏洞，使人们充分相信它的安全性；另一方面，在 提高椭圆曲线密码( e c c ) 系统的实现效率上，世界各国也取得了长足的进步，使 得椭圆曲线密码系统成为一种非常重要的公钥密码系统，被广泛地应用于各个 行业，如军事、金融、政府以及电子商务等领域。 在2 0 0 1 年前，在国内由于国家商用密码管理对国外的密码技术也进行管制， 不准使用进口的密码技术和产品，这使得国内对基于椭圆曲线密码体制的数字 签名的开发产品较少，只有武汉大学青年教授陈建华成功开发出一套椭圆曲线 加密软件。如今，武汉大学密码技术中心与海南信安数据系统有限公司进行合 作1 3 0 l ( 以陈建华教授为首的课题组) 开发的椭圆曲线密码芯片已经达到了世界 领先的水平。在2 0 0 1 年初，清华大学微电子学研究所就开始了关于椭圆曲线密 码硬件实现设计的前期研究工作，到2 0 0 4 年前，已研制出了在1 0 0 m h z 工作频 率条件下，每秒能够完成数字签名2 9 5 0 次、签名验证1 6 8 0 次，运算速度达到了 国际先进水平的密码芯片p 2 l 。深圳市明华澳汉科技股份有限公司开发的椭圆曲 4 武汉理工大学硕士学位论文 线算法的e c c - c o s 成功应用在南海c a 等电子政务高安全领域1 3 0 1 。北京天一集 成有限公司设计了“e c c 密码算法芯片及婵核”，该芯片模长1 9 2 2 5 6 位，芯 片运算速度2 0 0 0 0 次，秒，i p 核运算速度5 0 0 次，秒1 3 l 】。上海微科集成电路有限公 司于2 0 0 4 年1 2 月1 5 宣布开发成功的r s a e c c 二合一密码算法协处理器芯片。 该芯片最多可以完成2 5 6 比特的e c c 运算，每秒至少可以完成1 0 0 次e c c 点乘 运算【3 3 l 。( 这些公司都声称：他们设计的产品中所使用的许多技术都达到了世界 的领先水平。) 在国外，也只有少数的几个大公司如加拿大c e r t i c o m 公司、法国 g e m p l u s 公司等掌握了椭圆曲线密码技术阳。特别是加拿大的c e r t i c o m 公司 对椭圆曲线密码体制以及基于椭圆曲线密码体制的各种数字签名算法的研究比 较成熟。采用硬件方式实现椭圆曲线密码的研究最早见于文献【2 4 】。该文献构造 了一块专门用于执行有限域f l 。上乘法运算的v l s i 芯片，然后再利用一个高效 的可编程控制器实现了基于e 。，上的椭圆曲线密码。其加密速度大致可以达到 4 0 k b s ，数字签名的速度大约是每秒1 3 0 次。2 0 0 1 年，德国的i n f i m e o m 公司推 出了一款位宽肼= 1 9 1 的椭圆曲线数字签名算法安全芯片，在5 m h z 的工作频率 下，完成一次签名的产生所需的时间是2 8 5 m s ，完成一次签名验证所需的时间是 5 4 0 m s 。在1 0 m h z 的工作频率下，完成一次签名的产生所需要的时间是1 4 2 m s ， 完成一次签名验证所需的时间2 7 0 m s 。在这一年，m o t o r o l a 公司也推出了一款多 功能安全处理器，这是款功能上几乎做到了包罗万象的芯片，具有实现d e s 、 m d 5 、s h a - 1 、r s a 、e c c 和伪随机数产生等算法的功能。关于e c c 算法功 能，对素数域情况，只要求定义曲线的素数域f 。中的素数p 是一个规模在6 4 比 特到5 1 2 比特之间的素数即可。对特征值为2 的有限域f 情况，也只要求定义 曲线的有限域砸i 中的m 是一个规模在6 4 到5 1 2 之间的数即可。对两种情况下 的椭圆曲线，芯片没有提供任何完整的密码算法或密码协议的实现，只提供了 标量乘法的计算功能和计算椭圆曲线上点加运算和倍点运算的功能【l “。 从总体上来说，我国密码芯片的设计和生产与发达国家相比尚存在很大差 距，还远远滞后于通信技术和计算机网络的发展需求。这可能与我国的集成电 路的生产和设计技术相对落后有关，同时国内对椭圆曲线密码( e c c ) 芯片的设计 和研究起步较晚也有关系。但最近几年来的发展状况还是比较乐观的，己经有 正式的产品面道。 武汉理工大学硕士学位论文 1 4 本课题的内容安排 本课题在深入学习数字签名原理和椭圆曲线密码体制的基础上，对部分数 字签名算法原理和基于椭圆曲线的数字签名进行了深入的理论研究。本课题的 内容安排如下： 第l 章；介绍了课题的提出背景、研究意义以及本课题研究的现状。 第2 章：首先描述了与椭圆曲线相关的数学基础知识，如域和有限域的概念、 二进制域k 和索域e 中元素的表示和运算法则。然后综述了椭圆曲线的概念以 及定义在相应域上的椭圆曲线的运算，最后阐述了减少求逆运算的投影坐标。 第3 章：先叙述了椭圆曲线数字签名安全性所依赖的基础，即椭圆曲线离散 对数问题( e c d l p ) ；然后介绍了椭圆曲线密钥问题和安全哈希函数原理；最后论 述了数字签名原理和基于椭圆曲线的数字签名方案。 第4 章：这一章是论文设计的重点，先描述f p g a 的实现流程。接着对有限 域n 上的基本运算模块进行逐一逻辑设计，然后对椭圆曲线上的运算模块进行 逻辑设计。最后实现基于椭圆曲线的数字签名。 第5 章：总结与展望。 6 武汉理工大学硕士学位论文 第2 章椭圆曲线的理论基础 现代的各类密码技术，都是借助于各类代数结构。基于椭圆曲线的公开密 钥密码系统和数字签名系统也不例外，它是借助于g a l o i s 域代数结构。本章将 介绍椭圆曲线密码算法的数学基础知识。 2 1 数论基础知识 定义2 1 ( 同余) ：令玎n 。令矾b z 为两整数， ( 1 ) 若n 整除b 一口，则称口同余b 模以，记为4 ；b ( m o dn ) ， ( 2 ) 所有与口同余的整数所组成的集合，即 口 = b zl 口b ( r o o dn ) ( 2 一1 ) 称为的同余类。 ( 3 ) 所有同余类所形成的集合，即 z n = 【明1 x z ) ( 2 2 ) 称为同余类集合。 例1 13 ；1 4 一8 ( r o o d1 1 ) ，这时的n = 1 1 ，则 【5 】= ( z z i x ；5 ( m o d1 1 ) ) = 1 6 = _ 6 = 2 7 。 z l l = ( 0 1 ， 1 1 ， 2 1 ， 3 1 ， 4 1 ，【5 】，【6 】， 7 1 ，【8 】， 9 】， 1 0 1 - 在集合上可以进行一些运算，如加法、减法以及乘法，在除法有乘法逆元 素的情况下，也可以定义除法运算。它们的运算都是模运算，可以用同余类的 术语定义如下： ( 1 ) 【口】0 【6 】= 砸0 6 】= x z l x ；a b ( m o dn ) ) ； ( 2 ) 【a l - b 】= 陋- b 】= x z l z z 口一b ( m o dn ) j ； ( 3 ) 【口】0 【6 】= 【口0 6 】= 工z l x = a o b ( m o dn ) ) 。 其中0 ，一，o 分别表示模加法、模减法和模乘法。 定义2 2 ( 交换群) ：对于代数系统( g ，丰) ，其中g 为集合，木为运算，若： ( 1 ) 封闭性：妇、b g 则a * b g ； ( 2 ) 结合律：v 4 、b g 则a * b = b 。口； 7 武汉理工大学硕士学位论文 ( 3 ) 交换律：v a , b 、c g 员( 口 6 ) 牢c = 口 ( b * c ) ； ( 4 ) 存在单位元：v a g ，3 e g 使得c l * e = 口= g s a ； ( 5 ) 存在逆元素：v a e g ，3 b g 有a * b = p = b * a ，其中b 一口一。 当条件( 1 ) 、( 2 ) 、( 4 ) 、( 5 ) 成立时，则称( g ，的为群；当( 1 ) 、( 2 ) 、( 3 ) 、 ( 4 ) 、( 5 ) 都成立时，称( g ，幸) 为交换群，也叫阿贝尔群( k b e l i a ng r o u p ) 。 定理2 1 ( 费马小定理，f e r m a t sl i t t l et h e o r e m ) 令p 为素数，口为与p 互素的整数，则 a p - 1i l ( r o o dp ) 。 ( 2 - 3 ) 定义2 3 ( 原根，p r i m i t i v er o o t ) 若乘法群z 矿中的同余类都可以表示为 g ( g 为整数) 的若干次方，则称g 为乘法群的原根。 由原根的定义可以引出下面的定理： 定理2 2 令g 为z ，矿上的原根，p 为素数，则： ( 1 ) 若工为整数，则fi1 ( m o dp ) x 0 ( m o dp - 1 ) ； ( 2 ) 若i ，j 为整数，则9 1zg | ( r o o dp ) i - j ( m o dp ) 。 定义2 4 ( 域，f i e l d ) ：令f 为一个集合，o 和 为定义在该集合上的两个 运算加法和乘法，当满足下列三个条件： ( 1 ) ( f ，0 ) 对于加法运算构成加法交换群，单位元用0 表示； ( 2 ) ( f ( 0 ) 对于乘法运算构成乘法交换群，单位元用1 表示； ( 3 )且圆对。有分配律： v 仉b 、c f ，a 固( 6 0 c ) = ( 口0 b ) 0 ( a 固c ) 。 则( g ，0 ，o ) 为域。 2 2 有限域 在2 1 节的定义2 4 中，若域f 是有限的集合，则称域为有限域。同样一个 有限域也只有两种运算，即加法运算和乘法运算。对于域元素的减法是用加法 来定义的：对于口，b f ，a b = 口+ ( 一6 ) ，其中一6 是b 的负元素。同样，域元 素的除法是用乘法来定义的：对于口，蚤e f ，b 0 ，a b = 口掌b 一，其中6 。是 的b 逆元素。 有限域的元素的个数称为有限域的阶。存在一个q 阶的有限域f ，当且仅当 g 是一个素数的幂，即q = p ”，其中p 是一个素数，称为域f 的特征，埘是一 8 武汉理工大学硕士学位论文 个正整数。当埘；l 时则称域为素域，用f ，表示；当m 2 时则称域为二进制域 或特征为2 的有限域，用f 2 表示。 2 2 1 素域 设p 是一个素数，以p 为模，则模p 的全体余数的集合 0 ，1 ，2 ，p - l l 关于模p 的加法和乘法构成一个p 阶的有限域，用符号e 表示。此时称p 为f p 的模。 对于任意的整数a ，am o dp 表示用p 除引行得到的余数，0 ，p l ，称 这种运算为求模p 的剩余。素域配中的元素的运算描述如下： ( 1 ) 加法运算：如果a ，b f 。，则加法运算的结果为；c m a + b ( m o dp ) ； ( 2 ) 减法运算：如果口 6 e ，则减法运算的结果为：f = 口一b ( dp ) ； ( 3 ) 乘法运算：如果以6 f 。，则乘法运算的结果为：c = a b ( r o o dp ) ； ( 4 ) 求逆运算：如果q 6 e ，求逆运算的结果为：b - = a - 1 ( r o o dp ) ，即有 a x b ；1 m o d p 其中，加法的单位元为0 ，域元素a 的逆元为( - a ) r o o dp ，即p - a ；乘法 的单位元为1 ，域元素a 的逆元为a - 1 m o dp 。 若令= f ，、 o ) ( 域f ，中的a 零元的集合) ，可以证明在域啄中至少存在一 个元素g ，使得域中任意元素可以表示成g 的方幂，这样的元素称为巳的生 成元( 或本原元) ，即： ：= 9 7 ：0 ，p 一2 ) 例2 1 求素域职，中的元素的运算。 ( 1 ) 加法：5 + 8 2m o d1 1 ，因为1 3m o d1 1 = 2 。 ( 2 ) 减法：5 8 8m o d1 1 ，因为5 8 + 1 1m o d1 1 = - - 3 + 1 1m o d1 1 = 8 。 ( 3 ) 乘法：5 8 = 7m o d1 1 ，因为4 0m o d1 1 = 7 。 ( 4 ) 求逆：5 ；9m o d1 1 ，因为5 9m o d1 1 = 1 。 同时有： 2 0 e lm o d1 1 ，2 1 i 2m o d1 1 ，2 2 e 4m o d1 1 ，2 3 i 8m o d1 1 ， 2 4 i5m o d1 1 ，2 5 e l o m o d1 1 ，2 6 i 9m o d1 1 ，2 7 7r o o d1 1 ， 3m o d1 1 ，2 9 ；6m o d1 1 ，所以： 吒= 2 ：0 _ ，9 ) 。 9 武汉理工大学硕士学位论文 2 2 2 二进制域哆 阶为2 ”的域称为二进制域或特征为2 的有限域。构成域砸l 的方法有两种： 一种是多项式基表示法，另一种是正规基表示法。 2 2 2 1 域砖上的多项式基表示及其运算0 1 域枣上的元素是次数最多为r f l 1 次的二进制多项式，即： k = ( 】，4 + ( i 铲2 】f 扣2 + + 呜，+ q x + ：口i 0 1 ) ，o f s 肼一l 。( 2 - 4 ) 令，( 功为域_ 上的r f l 次不可约多项式： ，( 力= x ”+ 厶】严- + 怃矿+ 石r + 石u 砭，o f j 筇一l ， ( 2 5 ) 即，( 功不能分解为f 2 上两个次数小于m 的多项式的积。显然，对于任意的m ， 这样的多项式是一定存在的，并可以有效的产生。 通常k 域d e 的元素( _ 1 x “+ 口+ 2 z ”2 + 切2 x 2 + a l x + a o ) 用长度为m 的 二进制串和o q 。呸q ) 来表示。 1 加法 当e 域中的元素用二进制串表示时，加法运算很简单，就是两个元素的对 应位的比特异或( x o r ) 运算。 2 乘法 乘法运算与不可约多项式f ( x ) 相关，若v 口，b 虬，且 a = ( 口。q ，2 口2 q 口o ) ，b = k ：屯6 1 玩) ， 乘法结果为： c = ( q ，l c + 2 c a e o ) f _ ，则： 0 1 x 剃+ c 柚x 卜2 + + c 2 x 2 + c w x + c o = o x 州+ 2 广2 + + q x + ) ( x 州+ 广2 + + b x + b o ) m o df ( x ) ， 其单位元表示为：( o o o i ) 。 3 平方 平方运算也与不可约多项式f ( x ) 相关，若v a k ，且 口= ( q 卜：粥) ，则其平方结果为： f 弓卜l x 2 胂4 + + 口i x 2 4 + + q x 2 + a om o d ( x ) = ( c x 。“+ i + 2 】f + 2 + + q r + 喁) 2 r o o d f ( x ) ，o - i - m - i 。 2 2 2 2 域”矿上的正规基表示及其运算乜町 有限域弓的一组正规基是形如： b = 口，口2 ，口2 ，口，盯2 一) ( o f m 1 ) ( 2 6 ) 1 0 武汉理工大学硕士学位论文 的集合。对任意正整数i i l ，凡都有正规基存在。 设a ，o d 2 , 口2 2 ，”二a 为有限域n 的一组正规基，对于有限域i 中的两个元素a = ( a a r _ 。q 。q 口0 ) 和6 = ( ，k ：b ，b 0 ) ， 而 c = ( c + 2 c i c o ) 为各个运算的结果，则： 1 加法 用正规基表示的当砸_ 域中的元素的加法运算，和用多项式基表示的当蛋 域中的元素的加法一样，也是两个元素的对应位的比特进行异或( 聊) 运算； r a - 1h 2 c f f 7 = ( 口f o 匆。， ( 2 7 ) i = o 其中，“o ”表示异或运算。 2 平方 用正规基表示的当k 域中的元素的平方运算，比用多项式基表示的当虬 域中的元素的平方简单，即为域元素对应的比特串循环左移一位的结果： 矿= ( ：一”喁口0 q 。) ( 2 8 ) 3 乘法 设有限域中的两个元素盯= 绯l k ：o i a 0 ) 和b = ( 曩。b p 0 ) 相 乘的结果为c = ( c m - l c m - 2 c l c 0 1 ： m - t m - i c = a 6 = q 咿 一= c k o t 。 ( 2 9 ) 如果称q 6 j 为一个项，则c k 等于若干个不同项之和。记g 0 为c k 中项的个 数。对于任意的m 1 ，有限域砸至少存在一个正规基，且任意的正规基都有 g r 2 n l 。如果g i = 2 n - 1 ，则有限域虬上的正规基就称为优化正规基 ( o p t i m a ln o r m a lb a s e - o n b ) 。 由于只有满足g | = 2 n l 的条件时，有限域q 上才有优化正规基( o n e ) 。 i e f e1 3 6 3 给出检验有限域n 上是否存在o n b 的方法： ( 1 ) p = t n + l ； ( 2 ) 若p 不是素数，则不存在o n b ； ( 3 ) 求七使矿；1 ( r o o dp ) ； ( 4 ) h = t n k ； ( 5 ) 计算h 与即的最大公约数d = g c d 仇力； ( 6 ) 若d = l ，则有限域k 上存在优化正规基( o n b ) ，否则不存在。 武汉理工大学硕士学位论文 其中，t = 1 时为，型正规基，r = 2 时为，型正规基。 若域的元素用优化正规基( o n b ) 表示时，其乘法法则是由一个f 2 上栉甩 的乘法矩阵来表征的，设为肼。对于优化正规基，乘法矩阵膨是一个稀疏矩阵。 乘法矩阵m 中除第一列只有一个1 外，其余各列都只有两个1 ，共有加一1 个l 。 乘法矩阵掰的定义如下： 肘= 口7 口= 口冉2 口o 瑾+ ， 口2 。+ 一 瑾，+ ， ： 盯+ 口2 。+ 一 口，+ 口+ 一 因为c = a x b = 瓴，q ，a m _ 2 ，a 肼1 ) x m x 瓴，q ，二口+ 2 ， ( 岱矿，g ，a 产、口2 2 ，口，4 ( 2 一l o ) 如果设有限域n 的对应的不可约多项式为： ，( 对= 矿4 - 几矿_ 14 - 呸，+ 石x + f 0 e ，0 f s 肼一i ) ，( 2 - u ) 则求该乘法矩阵的运算步骤为： ( 1 ) 设在模，o ) 的条件下，由多项式向量( 口“，a , m - 2 j oo o j 口2 ，口，1 ) 到正规基 向量缸一，口，2 ，”二口2 2 ，口2 ，口) 的转移矩阵为p 。 ( 2 ) 设矩阵q 为： q = o1o ool 0oo c oq 乞 a 吒0 岛a 乞k ，lj1lll 驴矿妒、咖 0，lj1 o o：。 武汉理工大学硕士学位论文 在玛上计算矩阵r = p 一1 q p 。 ( 3 ) 设墨，= 一，其中下标是在模脚下的运算，f l _ o f ，j 研一l 为整数，则 乘法矩阵m 为： f 铀1 m ：i 誓t 气，l l ：l 。 s - z i j 若用口隹，6 耻分别表示口= ( 一i q ，2 q ) 和6 = ( k 2 b , b o ) 循环左移k 位说得的结果，即： = ( 日k 口卅- 2 一ko o o 口2 一q 4 at ) ， b 非= ( 6 _ 4 6 0 i 6 h 6 1