（应用数学专业论文）gf（2163）上椭圆曲线密码体制的fpga实现.pdf

摘要 信息技术的不断发展，对信息安全提出了更高的要求。密码技术是保障信 息安全的核心技术。在应用公钥密码体制的时候，对密钥长度要求越来越大， 处理速度要求越来越快。现在广泛使用的r s a 公钥密码体制已很难满足未来人 们对信息高安全性的需求。而基于椭圆曲线离散对数问题的椭圆曲线密码体制， 因其每比特最高的安全性，受到越来越广泛的注意。此外，椭圆曲线密码体制 还具用计算负载小，密码尺寸短，占用带宽少等优点。因而特别适用于计算能 力受限、空间受限、带宽受限和要求高速实现的情况。椭圆曲线密码体制的硬 件快速实现成为一个倍受关注的课题。 本文从实际应用出发，研究了椭圆曲线密码体制算法的f p g a 的实现；以 基本的数学理论，密码学理论为依据，结合一些具体的相关算法和f p g a 的特 点，确定了密码体制的硬件实现方案。采用p 1 3 6 3 推荐的g f ( 2 1 6 上的k o b l i t z 曲线，采用微处理器模式，在f p g a 上实现了抵抗自主选择密文攻击的可证明 安全的椭圆曲线密码体制。文章按照有限域、椭圆曲线、密码体制三方面的内 容依次进行书写，每一部分分别介绍了相应的理论基础及硬件实现。 具体实现中，采用硬件描述语言v h d l ，在a l t e r a 公司出品的o u a r t u s1 i5 0 平台上进行电路设计。设计选用了a l t e r a 公司的s t r a t i xi i 系列器件 e p 2 s 1 3 0 f 1 5 0 8 c 4 。为了硬件实现上的方便高效，有限域o f ( 2 1 6 3 1 上的元素利用 正规基表示，其关键运算乘法运算采用1 4 s m p o 。的算法，利用状态机模式 实现：椭圆曲线上的关键运算标量乘法运算采用m o n t g o m e r y 算法，利用 微处理器模式实现；加密体制采用可证明安全o p t - p s e c - 3 方案实现。程序的 每一部分都结合软件编程验证以保证程序的正确性。 本设计获得了良好的性能指标：最终标量乘法的实现需要8 ，8 3 0 个a l u t 和5 ，5 7 5 个r e ：g i s t e r ，在时钟周期取1 3 n s 时，标量乘法的运行时间为1 8 4 5 2 u s 。 加解密算法的实现需要1 1 ，3 7 2 个a l u t 和6 9 6 3 个r e g i s t e r ，在时钟周期取1 3 n s 时，加密算法的运行时间为3 6 7 6 7 u s ，解密算法的运行时间为1 8 2 6 2 4 u s 。标量 乘法的速度与国内外相同逻辑资源的实现相比有一定的优势：具有可证明安全 的加密方案的硬件实现在我所看到的文献中尚属首次。 关键词椭圆曲线密码体制；标量乘法；可证明安全；f p g a a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , t h ea d v a n c e di n f o r m a t i o n s e c u r i t y i se a g e r l yd e s i r e d t h ec r y p t o g r a p h yi st h ek e yt e c h n o l o g y p u b l i ck e y c r y p t o s y s t e mi sa d o p t e d ，b u tl a r g e rs c a l ek e y sa r er e q u i r e dw i t ht h ec o m p u t i n ga r t s e n h a n c e d r s ac r y p t o s y s t e m ，ap u b l i c k e yc r y p t o s y s t e mb e i n gu s e dw i d e l yt o d a y , s e e m st oh a v ed i f f i c u l t yi nm e e t i n gt h eu s e r s n e e do fh i g hs e c u r i t y h o w e v e r , t h e e l l i p t i cc u r v ec r y p t o s y s t e m ( e c ct h e r e a f t e r ) i sw i d e l yc o n c e r n e dd u et ot h eh i 【g h e s t s e c u r i t yo ft h es a m el e n g t h b i t i na d d i t i o n ，e c ca l s oh a sm a n yo t h e rm e r i t ss u c ha s l e s sc o m p u t a t i o no v e r h e a d s ，s h o r t e rk e ys i z e ，c o n s i d e r a b l eb a n d w i d t hs a v i n g s ，a n d s oo n s ot h ee c ci s ，e s p e c i a l l y , s u i t a b l ef o rs i t u a t i o n sw h i c ha r el i m i t e db y c a p a b i l i t yo fc a l c u l a t i o n ，s p a c e ，b a n d w i d t ha n dr e q u i r e m e n to fh i g hi m p l e m e n t a t i o n t h er a p i di m p l e m e n t a t i o no ft h ee c ch a r d w a r eh a sb e e na p o p u l a rt o p i c i nt h i sp a p e r ，w es t u d yt h ei m p l e m e n t a t i o no ft h ee c ca l g o r i t h mb yt h ef p g a f r o mp r a c t i c a la s p e c t b a s e do nm a t h e m a t i c sa n dc r y p t o g r a p h yt h e o r y ，i n t e g r a t e d s o m es p e c i f i cr e l e v a n ta l g o r i t h ma n df p g a ，w ea s c e r t a i nt h e i m p l e m e n t a t i o no fe c c f o rh a r d w a r e p r o j e c t t h ep a p e r ，w h i c ha d o p t s k o b l i t zc u r v eo n g f ( 2 1 6 3 ) r e c o m m e n d e db yp 1 3 6 3a n dm o d u l eo fm i c r o p r o c e s s o r , p r o v e ss e c u r i t yo ft h ee c ca t f p g a ，t h ea r t i c l e ，w h o s ee v e r yp a r ti n t r o d u c e sr e l e v a n tb a s i ct h e o r ya n dh a r d w a r e i m p l e m e n t a t i o nr e s p e c t i v e l y , i sa c h i e v e db yt h r e ea s p e c t sa sf i n i t yf i e l d ，t h ee c c a n d e n c r y p t i o ns c h e m e s t h ec i r c u i td e s i g ni sa c h i e v e da tt h eq u a r t u si i5 0p r o d u c e db yt h ea l t e r a a d o p t e dt h ev h d l ，a n dc h o o s et h ee p 2 s 1 3 0 f 1 5 0 8 c 4o f s t r a t i xi i p r o d u c e db yt h e a l t e r a i no r d e rt oh i g he f f i c i e n c yo fh a r d w a r e ，e l e m e n t so ft h eg f ( 2 1 6 3 ) a r es h o w e d b yt h en o r m a lb a s i s ，a n di t sk e yc a l c u l a t i o n ，m u l t i p l i c a t i o nc a l c u l a t i o n ，i si n t r o d u c e d b yt h ew - s m p o i 【t h r o u g hi m p l e m e n t a t i o no fm o d u l eo fp r e d i c a m e n t t h ee c c sk e y c a l c u l a t i o n 一s c a l a rq u a n t i t yc a l c u l a t i o na d o p t sm o n t g o m e r y sa l g o r i t h m sa n di s a c h i e v e db ym i c r o p r o c e s s o rm o d u l e c r y p t o g r a p h yi sa c h e v e db yt h eo p t - p s e c - 3 w h o s es e c u r i t yi sa b l et ob ep r o v e d t h ee v e r yp a r to ft h ep r o g r a mw h i c hi sc o m b i n e d w i t hs o f t w a r ep r o g r a m m ee n s u r e st h ec o r r e c t n e s sv a l i d i t yo ft h ep r o g r a m t h i sp r o j e c tr e a c h e st h eg o o dt a r g e to fp e r f o r m a n c e t h e r ea r e8 8 3 0a l u t sa n d i i a b s t r a c t 5 ，5 7 5r e g i s t e r st oc o n s t r u c tt h es t r u c t u r eo fs c a l a rm u l t i p l i c a t i o n ，a n di t sr u n n i n gt i m e i s1 8 4 5 2 u st om u l t i p l yi nt h ec l o c kp e r i o do f1 3 n s a st ot h ec r y p t o s y s t e m ，i tn e e d s 1 1 ，3 7 2a l u t sa n d6 ，9 6 3r e g i s t e r s i fw et a k e1 3 n si nt h ec l o c kp e r i o d ，t h er u n n i n g t i m eo ft h ee n c r y p t i o ni s3 6 7 6 7 u s ，a n dt h a to ft h ed e c r y p t i o ni s1 8 2 6 2 4 u s s p e e do f t h es c a l a rm u l t i p l i c a t i o nt a k e sa d v a n t a g ep o s i t i o nc o m p a r a t i v e l yw i t hs a m el o g i c r e s o u r c ei nd o m e s t i co ra b r o a da tp r e s e n t ，a n dt h ec n c r y p t i n gp r o j e c to fh a r d w a r e i m p l e m e n t a t i o n ，w h i c h i ti sl i k e l yt ob ep r o v e d ，i st h ef i r s ta p p e a r a n c et h a tih a v ee v e r r e a d k e yw o r d s e l l i p t i cc u r v ec r y p t o s y s t e m ；s c a l a rm u l t i p l i c a t i o n ；p r o v a b l e s e c u r i t y ；f p g a u l 广州大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不含任何其他个人或集体已经发表或撰 写过的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律 后果由本人承担。 学位论文作者签名：壬睦日期：沙6 年6 月f 日 广州大学学位论文版权使用授权书 本人授权广州大学有权保留并向国家有关部门或机构送 交论文的复印件和磁盘，允许沦文被查阅和借阅。本人授权 广州大学可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：王日期：2 西年f 月岁i e i 导师签名：夥 日期：2 _ p d 年g 月箩日 第一章绪论帚一早瑁t 匕 1 1 课题研究的背景和意义 随着网络基础设施的不断建立和完善，网络使信息共享、网上交流、网上 交易成为可能。但另一方面，国家或个人的信息也受到非法获取、破坏、篡改 等形式的威胁。人们迫切需要采取措施保障以电子形式保存或传送的数据。 保障信息安全的核心技术是密码技术。加密算法主要分为对称加密算法和 非对称加密算法。两类算法各有优点和不足，各有适宜的应用场合，因此，两 类加密算法将长期共存。 现在通用的非对称加密算法是r s a 算法m 1 ，随着安全需求的增加，r s a 算 法所需要的计算能力和存储空间都显著增加，因此它的应用越来越受到限制。 密码学界一直在寻求一种能在低要求的计算环境中达到高强度加密的算法。椭 圆曲线加密系统是一种基于椭圆曲线上的离散对数问题而设计的非对称加密算 法。 基于椭圆曲线上的离散对数问题要比基于有限域上的离散对数问题的计算 难度更大，其中基于大整数因子分解的难度等同于基于有限域上的离散对数问 题。迄今为止，破解椭圆曲线离散对数问题还没有一般的亚指数时间算法，已 知的最好算法都需要指数时间。这就意味着椭圆曲线密码体制( e c c ：e l l i d t i c c u r v ec r y p t o s y s t e m ) 具有每b i t 最高的安全性。随着计算能力的提高，r s a 的 密钥长度迅速增大，而相比较而言，e c c 的密钥长度增长速率明显低于前者。 因此，可以看到与r s a 算法相比，它具有计算速度快，存储空间占用少，带宽 要求低等特点”1 ，它能够用于许多不适合使用r s a 算法的场合，特别适用于计 算能力和集成电路空间受限的情况，如i c 卡的实现；以及带宽受限，要求高速 实现的情况，如无线通信、计算机网络等；而且e c c 更能适应未来更高的安全 需要：当安全性能需要更长的密钥时，e c c 只需增加很少的系统资源就可以提 供相应的安全服务，大大的降低了成本。因而，e c c 及其安全性分析引起了密 码学家及各界的极大关注与重视，现已成为了研究热点。 1 2 椭圆曲线密码的发展现状 人类从十七世纪就开始研究椭圆曲线了，但真正把其应用到密码学中是 1 9 8 5 年由n e a lk o b l i t z 州( 美国华盛顿大学) 和v i c t o rm i l l e r t ”1 ( i b m 公司) 两 第一章绪论 人单独提出的。他们利用椭圆曲线上的点构造了椭圆曲线密码系统。之后出现 了很多针对椭圆曲线密码系统的研究，主要集中在三个方面。 1 椭圆曲线密码系统的构造：包括有限域的选择和安全曲线的选择以及密 码体制的构造。 2 椭圆曲线密码系统的分析：就是在仅知道由e c c 加密的密文的情况下， 恢复出明文。包括对e c c 的攻击方法的选择、验证等等。 3 椭圆曲线密码系统的快速实现：大体可分为软件和硬件两个方面的快速 实现。 由于椭圆曲线密码体制具有每比特最高的安全性，德国、日本、美国和加 拿大等国的很多密码学研究小组开始了对椭圆曲线密码系统的研究，我国也有 一些密码学者做了这方面的工作。椭圆曲线密码的研究正方兴未艾， a s i a c r y p t o 9 8 上专门开辟了e c c 的栏目。许多标准化组织已经或正在制 定关于椭圆曲线的标准：i e e e 、a n s i 、i s o 、i e t f 和a t mf o r u m 都做了大量 的工作。他们开发的椭圆曲线标准文档有： 1 ，i e e e p l 3 6 3 ，p 1 3 6 3 a 加密、签名、密钥协商机制； 2 a n s i x 9 2 ，x 9 3 椭圆曲线数字签名算法，椭圆曲线密钥协商和传输； 3 i s o i e c l 4 8 8 8 3 椭圆曲线e i g a m a l 体制签名； 4 i e t f 椭圆曲线d h 密钥交换协议； 5 a t mf o r u m 异步传输安全机制； 6 f 1 p s1 8 6 2 美国政府用于保证其电子商务活动中的机密性和完整性的协 议。 这些是技术标准，描述的是以技术支撑为主的椭圆曲线密码体制。另外还 有一些应用标准，掐述的是建议使用e c c 技术的具体应用环境。主要有： 1 i s o i e c l 5 9 4 6 基于椭圆曲线的密码技术； 2 i e t fp k i x 公钥基础设施f x s 0 9 ) ； 3 i e t ft l s 传输层安全协议； 4 w a p w t l s 无线传输层安全协议，包括e c 的d i f f i e h e l l m a n 密钥交换。 同时，由于椭圆曲线密码体制特别适合于集成电路的应用，因而，在硬件 实现方面的研究也是层出不穷。采用硬件方式实现e c c 的报道最早见于文献 1 1 ，文献【1 1 】构造了一块专门用于执行有限域g f ( ( 2 3 1 ) 5 ) = g h 2 1 5 5 ) 上乘法运算 的v l s i ：艺= 片，然后再利用一个高效的可编程控制器实现了基于g f ( 2 ”) 上的 1 2 椭圆曲线密码的发展现状 e c c 。利用这一芯片，标量乘法运算每秒可以计算2 5 6 次，加密速度大致可以 达到4 0 k b s 。2 0 0 0 年，文献【4 0 】介绍了对定义在g f ( 2 1 6 3 ) 上的k o b l i t z 曲线采用 现场可编程门阵列( f p g a ：f i e l dp r o g r a m m a l eg a t e a r r a y ) 方式实现和采用a s i c 方式实现的仿真结果。在0 2 5 u r n 的c m o s 工艺下，a s i c 芯片的规模是1 6 5 万门电路，主频可以达到6 6 m h z 。利用这一芯片，a s i c 设计的标量乘法运算 每秒可以计算1 , 5 3 8 次。2 0 0 0 年，文献 4 1 l j 丕介绍了对定义在g f ( 2 1 6 7 1 上的曲线 利用x i l i n xx c v 4 0 0 ef p g a 芯片的实现结果。这一实现中，芯片的最高工作频 率可达7 6 7 m h z 。这时，完成一次标量乘法运算只需o 2 1 m s 。从而每秒可以完 成4 ，7 6 2 次标量乘法运算。2 0 0 0 年，文献【7 】介绍了g f ( ( 2 8 1 7 ) 1 7 ) 上的，利用8 位处理器模式实现的椭圆曲线标量乘法运算。2 0 0 1 年，文献1 2 9 】介绍了利用多 项式基实现的生成公钥的处理器，可以适应不同的域上的椭圆曲线。2 0 0 2 年， 文献 3 3 1 介绍了g f ( 2 1 6 7 ) 的椭圆曲线的处理器的f p g a 实现。2 0 0 3 年，文献【2 5 】 介绍了定义在g “2 m ) ，m 。 2 5 6 上的任意椭圆曲线的f p g a 实现。采用微处理器 模式，消耗2 0 ，0 6 8 个a l u t 和6 ，3 2 1 个f f ，时钟频率为6 6 4 m h z 时，对于定 义在g f ( 2 ”3 ) 上的n i s t 所推荐的椭圆曲线，每秒可以运算6 ，9 5 5 次标量乘法运 算，对于定义在g f ( 2 1 6 3 ) 上的其它椭圆曲线，每秒可以运算3 ，3 0 8 次标量乘法。 国内在这方面的研究也比较热，2 0 0 4 年，文献【3 】介绍了对定义在g 目2 2 3 3 ) 上的 k o b l i t z 曲线，采用1 e e e s t d l 3 6 3 2 0 0 0 标准中的算法，采用a s i c 方式，a s i c 芯片的规模是1 2 万门电路，主频可以达到1 0 0 m h z ，每秒可以完成4 , 0 0 0 次数 字签名。2 0 0 4 年，文献【1 1 介绍了对定义在g f ( 2 2 3 3 ) 上，结合x i l i n x 的f p g a 的 x c 2 s 5 0 器件，利用v e r i l o g h d l 语言，有限状态机模式，实现利用最佳正舰基 表示的，3 2 个时钟周期完成一次标量乘法，器件工作频率为1 2 7 m h z 。 随着e c c 标准的逐渐完善和理论研究的成熟，一大批公司开始把注意力放 到了e c c 的产品上来。国内外近一两年已有近十种享有专利的椭圆曲线的产 品。m i c r o s o f t 是第一个将椭圆曲线密码系统应用到商业产品的厂家。加拿大的 c e r t i c o m 公司开发出了可使用的椭圆曲线密码体制的集成电路，用来实现加密、 数字签名、验证和密钥管理。3 c o m p a l mc o m p u t i n g 、m o t o r a l a 、v e r i f o n e 、 a t a l l a l o r p 、t e r l i n g c o m m e r c e 、日本m i s t u s h i t a 及n 1 t 实验室、法国t h o m p s o n 、 德国的s i e m e n s 、加拿大w a t e r l o o 大学等都实现了这一体制，实现包括软件和 硬件。国内也有许多公司在做，但是大部分都是软件产品。2 0 0 1 年1 1 月深圳 市明华澳汉科技有限公司与海南信安数据系统有限公司联合推出了( 明华一信 第一章绪论 安) 国内首家e c c 算法的智能卡。 1 3 密码体制的总体设计 e c c 密码体制可以划分为三个层次：一个是有限域上的运算，包括有限域 的加、减、乘、平方、求逆运算；一个是椭圆曲线上有理点构成的阿贝尔群上 的运算，包括点的标量乘法运算，其中标量乘法运算也可以归结为倍点和点加 运算；一个是e c c 密码体制的设计和实现。三个层次的运算紧密相连。椭圆曲 线密码体制的执行效率与密码体制的设计和另外两个层次的运算速度直接相 关。然而，当密码体制选定以后，执行效率的关键就要看标量乘法的性能，而 标量乘法的运算是由有限域上的运算来实现的，特别是其乘法运算的效率是决 定性因素。 论文中选用了具有i n d c c a 2 安全的o t p p s e c 3 密码体制，椭圆曲线则 选用g f ( 2 1 6 3 1 的k o b l i t z 曲线。密码体制的实现采用微处理器模式，首先硬件实 现一个精简指令集的密码处理i p 核，然后利用精简指令集的指令编程实现标量 乘法运算和密码体制。其中标量乘法运算采用m o n t g o m e r y 算法。密码处理i p 核有两个特殊模块：有限域g f ( 2 1 6 3 1 上的乘法运算模块和h a s h 函数模块。有限 域上的元素利用正规基表示，乘法运算模块采用w s m p o z 的算法，利用状态机 模式实现；h a s h 函数模块采用s h a - 1 算法，也是利用状态机模式实现。 1 4 论文的安排 论文主要针对快速和资源受限条件下的应用，侧重于有限域上的乘法运算 以及椭圆曲线密码算法中标量乘法的运算，以及整个椭圆曲线密码体制系统的 实现。本文将按照有限域、椭圆曲线、密码体制的顺序，分以下几个章节来介 绍： 第一章是绪论，主要论述了课题研究的背景和意义、椭圆曲线密码的发展 现状、密码体制的总体设计以及论文的安排。 第二章是有限域上的运算及实现，主要论述了有限域的基本概念、基于正 规基的运算及算法分析、乘法器的硬件实现。 第三章是椭圆曲线上的运算及实现，主要论述了椭圆曲线的基本概念、其 上的运算及算法分析、标量乘法的硬件实现。 第四章是椭圆曲线密码体制及实现，主要论述了基本概念、密码体制的分 4 1 4 论文的安排 析与设计、密码体制的硬件实现。 第五章是总结与展望，主要是对论文的工作做一个总结，同时论述了论文 存在的和未解决的问题，解决问题的方向，以及可以继续改进的地方。 5 第二章有限域上的运算及实现 从本质上来说，椭圆曲线上的点的运算就是通过频繁的调用有限域上的运 算来实现的。e c c 中使用最频繁、对速度影响最大的模块就是有限域运算模块， 因此，要在f p g a 上实现e c c 的标量乘法运算，最重要的就是寻找合适的结构 和算法来实现有限域的运算。下面，从相关概念入手，介绍有限域上的运算的 f p g a 实现。 2 1 基本概念 2 1 1 群和域 定义2 1 如果一个非空的集合g ，对于代数运算0 来说满足以下条件： g 对于运算。是封闭的：对于任意的a , b g ，满足a o b g ； 结合律成立：对于任意的a , b ，c g ，满足( a o b ) o c = a o ( b o c ) ； g 中至少存在一个左单位元e ，对于任意的a g ，满足e o a ：a ； 对于g 中的每一个元a ，g 中至少存在一个左逆元n 1 使a - 1 0 a = e 。 则称g 对于运算。做成一个群。 定义2 2 ”1 如果一个非空集合r ，对于一个称为加法的代数运算。和另一个称 为乘法的代数运算。满足： 尺对于加法运算。构成一个交换群( 加法单位元称为零元) ； 曰中至少含有一个非零元；r 对于乘法运算。封闭，且满足结合律； 有乘法单位元；非零元有乘法逆元； 乘法交换律成立：左右分配律都成立。 则称r 对于该加法和乘法构成一个域。 元素个数有限的域称为有限域。两种常用的有限域是素数域g f ( r ) 永i 特征为 2 的有限域g f ( 2 m 1 。 2 1 2 素数域g f ( p ) 设p 是一个素数，整数集合 o ，1 ，2 ，护一1 ) 构成一个有限域，记为g f p ) 。 g 脚) 的加法运算：设工，y 是g f ( p ) 中的元素，则加法结果为 0 + y ) m o dp 。 2 1 基本概念 加法单位元即零元素：0 。 域元素工的加法逆元为( 一曲m o dp ，即p - - x 。 g f ( p ) 的乘法运算：设x ，y 是g 凡p ) 中的元素，则乘法结果为o 力m o dp 。 乘法单位元：1 。 域元素z 的乘法逆元为y ，其中x y = lr o o dp 。 2 1 3 特征为2 的域g f ( 2 m ) 所有长度为m 的比特串的集合构成特征为2 的有限域o r ( 2 m ) 。 域6 f ( 2 m ) 的力【l 法运算：两个元素的对应比特的异或运算。加法单位元是每 个比特都为0 的元素。一个元素的加法逆元是它本身。 域g h 吵) 的乘法运算：乘法运算与域元素的表示相关。通常选择的表示方 法有两种：多项式基( p o l y n o m i a lb a s i s ) 表示法和正规基( n o r m a lb a s i s ) 表示 法。 多项式基是指 f ”1 ，t 2 , t ，1 ) 。 g f ( 2 m ) d p 每个域元素都可以表示成一个阶数小于m 的g 目2 ) 上的多项式。 域元素0 a 2 口l a o ) 表示成多项式为a 。_ l t ”1 + + 口2 t2 + a i r + a o ，其中a i e g f ( 2 ) 。 g ：h r ) 上的乘法运算与一个多项式p ( t ) 有关，其中p ( f ) 是一个g f ( 2 ) 域上的 m 阶不可约多项式，称为该表示法的域多项式。一 设0 。a 2 n 。a 。) ，( _ 1 b 2 b 。) 是觎2 m ) 中的两个域元素，则他们的乘积 为： c = ( c 。一1 c 2 c l c o ) = q 。- l 。a 2 a l a o ) ( 6 爪一1 b 2 b , b o ) 其中 ( c m _ l t 4 1 + - + c , t + c o ) = ( ( 口。- l t _ 1 + + a l t + a o ) ( 6 卅一1 t ”一1 + - - + b i t + 6 0 ) ) m o d p ( t ) 多项式乘的单位元：( o o o i ) 。 对一个g h 2 ) 上的m 阶不可约多项式p ，如果在模p ( f ) 的条件下，由向量 ( f “，f 2 , t ，1 ) 到向量( f2 ”，t f ，t 2 , t ) 的转移矩阵是可逆的，则称p ( f ) 为正规多 项式。 有限域咧明的正规基是指集合o 1 ，f 2 2t2 ，f ) ，集合中的元素是线性无 关的。有限域g 以) 的域元素0 ，。a 2 n 。n 。) 表示为： a m _ i t2 ”+ + 口t 2 2 + a , t 2 + a o t 第二章有限域上的运算及实现 有限域g f ( 2 n ) 的正规基表示与一个m 阶正规多项式有关，该多项式称为这 个基的域多项式。对于每个正整数m ，都存在g f ( 岁) 的正规基m 1 。 采用正规基表示时，正规基的乘法法则由一个m 行m 列的矩阵来说明，该 矩阵的每个元素都在g f ( 2 忡。 设该正规基的域多项p ( t ) = t ”+ c m _ l t ”1 + + c 2 t 2 + c l t + c o ，求该正规基 下的乘法矩阵的步骤如下： 设在模p 的条件下，由向量( 1 ，t ，f 2 ，t ”1 ) 到向量p ，t 2t ”，t 2 “- i ) 的转移 矩阵为a ，b = 爿。 设矩阵 c = olo o oo1 o 0 o0 1 c o c lc 2 c 卅- 在g f ( 2 ) 上计算d = a c b 。 设鼻，= d h 一，其中0 9 i ，s 所一1 且为整数，下标在模胁的条件下计算。 输出矩阵 、 m ； s o ，o s o a s o , m - 1 s 1 ，0s 1 ，1 。 s 1 ，m 一1 就是所求的矩阵。 设 。a 。a 2 。一) ，( 6 0 b i b ：b 一。) 是g f ( 2 ”) o o 的两个域元素，则其相乘的结 果为c = ( c o c l c ：c ，一1 ) ，其中： c o = ( g o a l a 2 a m _ 1 ) m ( b o b i b 2 b m _ 1 ) 1 ： c 1 = ( a l a 2 a m _ l a o ) m ( b i b 2 k a ) 1 ； c 2 = ( 口2 a m _ l a o a l ) m ( b 2 k 扣1 ) 1 ； c = ( a m _ l a o 口l a m _ 2 ) m ( k 1 b o b a 6 。一2 ) 7 。 2 2 有限域g f ( 2 1 上的基于正规基的运算及算法分析 有限域g f ( 2 “) 用多项式基表示时，乘法运算简单，乘方运算比较困难；而 2 2 有限域g _ f 口m ) 上的基于正规基的运算及算法分析 用正规基表示时，乘方运算简单，只需一次循环移位，而乘法运算一般比较困 难。高斯正规基是一种特殊类型的正规基，它使得乘法和乘方运算都比较容易。 高斯正规基又分不同的类型，用一个正整数丁表示，该数值越小，使用该正规 基时的乘法运算越简单。下面给出在类型为f 的高斯正规基表示下的有限域 g f ( 岁) 的算术运算定义如下( 除乘法外，其他运算对也适用于非高斯正规基) ： 加法：若a = ( 口。a l a 。) 和6 = ( 6 。6 。6 。) 是域g 双2 m ) 上的元素，则 a + b = c 一( c 用- 1 c l c o ) ，其中c i = ( 口。+ b f ) r o o d 2 。即域中加法是按位异 或。 平方：若a = 0 。a a a 。) e g f ( 2 ”) ，则 n 2 = ( 荟叩) 2 。荟叩少12 。2 = a m _ - a l a o a m _ 1 ) 6 因此一个域元素的平方可以通过其向量表示的数串的一个简单的循环移位 而得到。 乘法阁：若p = t m + 1 ( 其中，m 不能被8 整除) ，并且“g f ( p ) ，其阶 为l 定义序列，( 1 ) 以2 ) ，即一1 ) 如下： f ( 2 “m o d p ) 号i ，0 s is ，l 一1 ，0ejs t 一1 。 若a = 0 。口 ) 和b = ( k 岛6 0 ) 是域g f ( 2 m ) 上的元素，则 a b c ( c ，- 1 一c l c o ) 其中 ，一i 。p - 2 n 叩+ 1 ) + 。k ( 小】+ f 若礴偶数； q 一1 乎，。h b f 。，。h + 黧n 。一，k m 。一。+ 。一。_ 1 ) 若哟奇数。 其中0s i5 m 一1 ，并且下标是对m 取模。 求逆：若口是域g 以) 上的非零元，则元素a 在域g f ( 2 ) i - 的逆元为口， 是唯一的元素ce g f ( 2 ) ，使得有4 c = 1 成立。 由此，容易看出利用高斯正规基表示的有限域上的加法、平方和乘法运算 都是比较容易实现的。根据p 1 3 6 3 瞄可知，有限域g f ( 2 1 6 3 1 具有第四类高斯正规 基，因而，其正规基乘法器比较容易实现。因此，我们选择正规基表示来实现 有限域上的运算。由于加法和平方运算比较简单，下面只对乘法和求逆运算做 一个简单的介绍。 第二章有限域上的运算及实现 2 2 1 g f ( 2 1 上的乘法运算及算法分析 m a s s e y 和o m u r a 最先提出了基于正规基表示的g f ( 2 ) 的乘法器”，随后， 一系列乘法器算法相应的被提出。和任何有限域上的乘法器一样，基于正规基 的乘法器的硬件实现可以分为两类：并行和顺序。并行乘法器( 例如：文献 1 6 】， 文献【1 5 】，文献 9 ) 由于消耗的逻辑资源较多而认为不太符合实际。 对于位水平的顺序乘法器，消耗的逻辑资源比较小( 为并行乘法器的1 m ) ， 但是一般每次乘法需要m 次重复。位水平的顺序乘法器又可分为连续输出( 每 次重复产生一位，例如：b e r l e k a m p 提出的对偶基乘法器”1 和m a s s e y ，o m u r a 提出的正规基乘法器”) 和并行输出( 所有的m 位是前面m - - 1 次重复的基础 上由第m 次重复同时产生的，例如：a g n e w e t a l 提出的正规基乘法器”1 和著名 的基于l f s r 的多项式基乘法器”以及a r a s hr e y h a n i m a s o l e h 和m a n w a r h a s a n 提出的正规基乘法器b - s m p o i 和w s m p o i i i l j l ) 。一般的，并行输出要比 连续输出的时钟效率高。 下面，我们首先对b - s m p o 。和w s m p ou 算法做一个介绍，然后把这两种算 法与其他的基于正规基的乘法器算法的性能做一下比较分析。 约定：在本小节中，v = l m 2 i ，6 ，= 卢2 。1 。 、 引理2 1 ”如果a ，b e g f ( 2 ”) ，c t a b ，则 c = m ：卢r 。卢： ? 2 i + 2j 】： 卢2 。+ 2 “ 口2 1 + 2 。 卢2 0 + 2 1 疗2 1 + 2 1 m 为奇数 ( 2 - 1 ) m 为偶数 口2 。+ 2 “ 疗2 1 + 2 “ 卢2 7 一+ 2 “卢2 一+ 卢2 一+ 。 1 0 2 ， 6 工 ，y 旬 萨， 水， 工 工 ，y白“y盘 v 白y 向 + + ， r 口 矗 胁 肌 口 口 孓句y 向 矿v isi1一mv is 0 q+ 口 + 轨 以 = x ： 中明其证 则 卢魄 r 了留 柏昌，i 拈 嘶 ， 口 掣 = 0 矿 “善肚 4 卜 且 示 ， 标 却 基 曰 规 小 正 = 是 c rfg日爿 ， 其 2 2 有限域g f 伫m ) 上的基于正规基的运算及算法分析 令 u = d = 卢2 0 0 p 4 - ：- 0 0 o 0 0 矗1 + 2 i 00 !；。 00 00 8 1 2 啊。2 8 2 + 2 “ ： 0 0 00 00 ： ： ；2 - - , 0 0 卢 口1 + 2 m 4 8 2 + r “ 芦。2 + 2 1 o 则显然有 m ：u + u t + d 所以 c = ax f b 7 口a 【，x b 7 + b u 口7 + a d b 7 将6 ，= 卢+ 1 代入式( 2 3 ) ，可得 u 一 ( 2 - 2 ) ( 2 3 ) ( 2 - 4 ) ( 2 5 ) 将式( 2 2 ) ，( 2 5 ) 代入( 2 - 4 ) ，即得式( 2 - 1 ) 。综上，引理2 1 得证。 令a = 和。n 。a 。一。) ，b = ( b o b l b m 一。) ，是g h 2 m ) 上用正规基表示的元素， c = a b = ( c o c l c “) ，令 互以，曰) a i _ l b i 一。1 3 + z i ，6 ， 其中0g is m 一1 ，z ，= 口i 6 州+ 口也，1 sjsv ，如果m 为偶数，则z = q 6 l + 。 下标的加减法都是模m 的。则我们可得下面的定理。 矿 配一 屯一霹铲 如砰0 文o 0 o 0 0 “ j 砰f o o 砰o 0 0 0 0 o 0 0 o o 0 0 o 0 o 0 0 0 0 第二章有限域上的运算及实现 定理2 1 m 1 如果a ，b e g f ( 2 ”) ，c = a - b ，则 c = ( ( ( e 2 一，+ 一：) 2 + 一，) 2 + + f 1 ) 2 + f 0 ，其中，f 是e 0 丑) 的缩写。 证明： 由引理3 1 ，知 c 2 荟8 j 一，6 j 一卢2 + 荟磊。6 ； 所以 c 。驴 卢+ 荟气 = 罗e 。= ( ( ( 旺。+ l 一：) 2 + r 一，) 2 + + e ) 2 + f 0 箭 综上，定理2 1 得证。 定理2 2 m 1e ，b ) 。瓦+ ，即，b 2 ) 证明： a = ( a o a l a 。一1 ) ，b = ( b o b l 一1 ) 则 a ，= ( 日：，n l 一女，一，口。一一1 ) ，b ”= ( 6 ，6 1 。，一，虬 一，) 所以 e ，曰) = a k + i _ l _ k b k 。一* 卢+ 魄+ “6 ，= e + t 以，b ) 综上，定理2 2 得证。 。 结合前面引理2 1 、定理2 1 、2 2 ，我们有下面算法。 算法2 1b - s m p o i i 算法m 1 ： 输入：a = ( o o a a m _ 1 ) ，b ；瓴q 6 爪一。) 。 输出：c = a b 。 1 初始化：x = ( a o a 。a m _ 1 ) ，y = ( h k 一。) ，d = ( d o d 。d 。) = 0 。 2 f o r i = 0 t o m 2 1d = d 2 + 一1 僻，y ) ； 2 2x ；工2 ，y = y 2 ； 3 c = d 。 利用此算法，我们可以得到乘法器的结构图如下： 2 2 有限域g f