有限域乘法器的设计实现与优化

浙江大学信息科学与工程学院 硕士学位论文 有限域乘法器的设计实现与优化 姓名：梁田 申请学位级别：硕士 专业：电路与系统 指导教师：沈海斌 20080515 浙江人学硕士学位论文一有限域乘法器的设计实现J 优化 摘要 本论文研究的主要内容是有限域算术、椭圆曲线加密算法和有限域乘法器。 椭圆曲线加密算法是目前提供了最短的密钥长度和最优的每比特加密强度的公 钥加密算法。而椭圆曲线加密算法的性能取决于有限域运算的速度，有限域乘法 运算又是有限域运算中其他运算的基础。这使得有限域内的快速运算尤其是二元 括域上的乘法运算成为了近期的研究热点。 本文的重点在于有限域乘法及有限域乘法器的算法设计，尤其是由三项式及 五项式生成的二元域。考虑到目前信息安全系统的有效性，本文所提出的有限域 乘法器结构均为位并行乘法器。 本文基于移位多项式基底( S P B ) 及其弱共轭基底( W D B ) 的有限域乘法器结构 对有限域乘法器的设计实现进行了研究。在由不可约三项式和不可约五项式构建 的有限域中，本文提出的架构在相同的空间复杂度下有着目前最小的时问复杂 度。而且，本文提出的乘法器结构具有很高的规则性，大大降低了硬件电路设计 者对数学知识的要求，为乘法器的快速设计实现提供了极为有利的条件。 进一步的，通过v e r i l o g 硬件描述语言对三项式乘法器设计进行了实现，通 过E D A 软件D e s i g nC o m p i l e r ，P o w e rC o m p i l e r 对设计进行了综合及优化、功耗 分析及优化。研究得到结论，该乘法器架构在相同的空自J 复杂度的前提下实现了 最低的时间复杂度( 最短的关键路径) 。不仅如此，该乘法器架构还以其规范性 易于通过硬件描述语言实现。 关键词：有限域乘法器，位并行乘法器，移位多项式基底，弱共轭基底，三项式，功耗优 化 浙江大学硕士学位论文一有限域乘法器的设计实现o 优化 A b s t r a c t T h ef i n i t e 矗e Ha r i t h m e t i c , e l l i p t i cc u r v ec r y p t o g r a p h y 圆C C ) a n dt h ef i n i t ef i e l d m u l t i p f i e ro r ei n v e s t i g a t e di nt h i st h e s i s E C Ci st h e o n eo ft h ek n o w np u b l i cc r y p t a a r i t h m e t i cw h i c hp r o v i d e st h es m a l l e s tI e ys i z ea n dt h eb e s ts t r e n g t h p e r - b i t T h ec a l c u l a t i o n s M e do v e rf i n i t e 矗e ug r e a t l ya f f e c t st h ep e r f o r m a n c eo fE C Ci m p l e m e n t a t i o n T h i sf a c th a s i n s p i r e dm a n yr e s e a r c h e r st of i n dw a y so np e r f o r m i n gf a s tc o m p u t a t i o n so v e rf i n i t ef i e l d s , e s p e c i a U y o v e r l a r g e f i n i t e f i e l d s o f c h a r a c t e r i s t i c t w o T h ec e n t r a lt h e m eo ft h et h e s i si sa ui n v e s f i g o r i o no ff i n i t ef i e l dc o m p u t a t i o n sa n dt h e i r a r c h i t e c t u r e s , p a r t i c u l a r l yt h ei r r e d u c i b l et r i n o m i a l sa n dp e n t a n o m l a l s A l lt h em u l t i p f i e r a r c h i t e c t u r e sp r o p o s e di nt h i st h e s i sa r eb i t - p a r a l l e lf i n i t ef i e l dm u l t i p l i e r sw h i c he a r i m p r o v et h ee f f i c i e n c yo f e r y p t o s y s t e m ss i g n i f i c a n t 帆 N e ws t r u c t u r e so f b i t - p a r a l l e lm u l t i p l i e rb a s e do nS P Ba n di t sw e a k l yd u a lb a s i sm m B ) o v e rf i n i t ef i e l da r ep r e s e n t e d T ot h ef i e l d sg e n e r a t e db yt r i n o m l a l sa n dp e n t a n o m i a I s , t h e p r o p o s e ds t r u c t u r e sh a v et h es h o r t e s tc r i t i c a lp a t hu pt od a t e 谢t hn e a r l yt h es a m es p a c e c o m p l e x i t y F u r t h e r m o r e , i ti se a s yf o rad e s i g n e rt oi m p l e m e n tt h ep r o p o s e dm u l t i p l i e r si n t o h a r d w a r ef o rt h e i rr e g u l a rs t r u c t u t e l F u r t h e r m o r e ，b yi m p l e m e n t e dt h ep r o p o s a lo fn e ws t r u c t u r eo ff i n i t ef i e l dm u l t i p l i e r u s i n gv e r i l o gH I ) L ，a n da n a 睁z i n gi nd e t a i lt h ep e r f o r m a n c eo fa l g o r i t h m si nf m i t ef i e l da n d t h ep e r f o r m a n c eo ft h ep r o p o s a lu s i n gE D As o f tD e s i g nC o m p i l e r , P o w e rC o m p i l e r ，w eh a v e d r a w nac o n c l u s i o nt h a tt h i sp r o p o s a ls t r u c t u r e sh a v et h es h o r t e s tc r i t i c a lp a t hu pt od a t e w i t hn e a r l yt h es a m es p a c ec o m p l e x i t y F u r t h e r m o r e , i ti se a s yf o rad e s i g n e rt oi m p l e m e n t t h ep r o p o s e dm u l t i p l i e r si n t oh a r d w a r ef o rt h e i rr e g u l a rs t r u c t u r e s W ea l s oo p t i m i z et h e p o w e rc o n s u m p t i o no f t h ep r o p o s a ls t r u c t u r e K c y w o r d s ：f m i t ef i e l dm u l t i p l i e r ；b i tp a r a l l e lm u l t i p l i e r ；S h i f t e dP o l y n o m i a lB a s i s ；W e a k l y D u a lB a s i s ；T r i n o m l a b ；p o w e rc o n s u m p t i o no p t i m i z a t i o n 1 1 一 浙江大学碗上学位论文一有限域乘法器的设计实现i 优化 图目录 图1G F ( 2 m ) 上的M a s t r o v i t o c 乘法器体系结构3 图2I P ( r n ) 的详细结构一3 图3 正规基乘法器实例图6 图4 乘法器结构简图2 0 图5 矩阵乘法运算冈子对应关系简图2 1 图6 三项式乘法器乘法因子迭代运算简图2 2 图7 乘法器空间复杂度分析图2 5 图8 五项式乘法器乘法矩阵简图2 8 图9 五项式乘法器乘法因子迭代运算简图3 0 图1 0v e r i l o g 代码综合出的乘法器结构图( 部分) 3 8 浙江人学硕上学位论立一有限域乘法器的设计实现与优化 表目录 表格1S M I C 3 5T 艺下三项式乘法器复杂度理论值 表格2S M I C 1 8r L 艺下三项式乘法器复杂度理论值， 表格3S M I C 1 31 ：艺F 三项式乘法器复杂度理论值 表格4 三项式乘法器结构的综合优化与功耗分析 舵躬帖 浙江大学硕士学位论文一自限域乘法器的设计实现i 优化 1 1 研究动机及意义 第1 章绪论 随着信息技术产业尤其是电子商务产业的飞速发展，公钥密码加密技术尤其 是椭圆曲线加密算法广发应用于政府、军事、文教、商业、金融等诸多领域，例 如电子政务信息系统、社会公共服务业务系统、证券业务系统、科研数据传输等。 这些系统的推广和J 下常运行，都离不开到加密信息的传输与存储。在这样一个高 速发展的信息化和数字化社会中，计算机的计算速度和网络传输速度的不断提 高，公钥密码势必将扮演越来越重要的角色。 与其他公钥密码体制相比，学界普遍认为，椭圆曲线密码体制将会凭借其 突出优势，成为今后最主要的公钥密码体制。目前已建立或正在建立的各种安全 信息传输和交换系统的安全架构都是基于公钥密码学理论构筑的，离开了这一理 论，就无从谈起它们的安全性。按当前的电子信息化程度，它的应用主要在银行 结算、电子商务和通信领域等，以后必将会扩展到人们社会生活的各个层面。因 此，由椭圆曲线密码理论所发展成的技术必将具有无限的商业价值。 自从N K o b l i t z I l l 和V M i l t e r t 2 分别在1 9 8 6 年和1 9 8 7 年提出E C C 算法以 来，这一算法凭借着密钥长度短、安全性能高等优点而在通信、计算机等领域扮 演越来越重要的角色。而E C C 的一个重要的实现方式就是建立在二元扩域上，这 些域继承了原先在素数域上的多精度算术的优点，因而在诸如财务统计、智能卡、 无线通信等功耗和带宽受限的场合有着极大的应用价值。同时，随着因特网和无 线通信技术的快速发展，越来越多的数字系统开始装备各式各样的密码系统来提 供不同层次的数据安全保护，其中很大一部分密码系统的安全性依赖于极大有限 域上的运算，所以研究并发现在这些域上的快速算法就具有重要的应用价值。 对于一个算法有效性的评价总是根据比特级或是字符级操作的数目决定。在 硬件应用领域，设计的一大需求就是尽量降低逻辑门数目( 空间复杂度) 和门延 时( 时间复杂度) 。这其中，有限域元素的表示方法对算法的时间和空间复杂度 起了决定性作用，特别是对于乘法运算影晌更为显著。 1 2 有限域运算及其应用 有限域运算( 包括有限域加减法、乘法、取模、求逆等运算) 是密码学研究 的重要内容，其在应用密码学、信息安全、数字信号处理( D S P ) 等诸多领域有 着越来越重要的应用。 例如，在近年来学界和业界愈来愈重视的椭圆曲线加密算法的应用上，研究 的焦点便是有限域数乘的快速运算。数乘运算的快速实现又基于有限域加减法、 乘法、取模、求逆( 除法) 等运算的高效算法。 此外，有限域运算还广泛应用在编码理论、超大规模集成电路设计( V e r y L a r g eS c a l eI n t e g r a t i o n ，V L S I ) 、数字签名算法( D S A 等) 、公钥加密R S A 和E 1 G a m a l 浙江大学顾七学位论文一有限域乘法器的设计实现I 优化 算法等不同领域。 在m 次二元扩域的基本运算中，加法很容易通过m 个二输入异或门实现，而 乘法运算则需要更多的门数和更大的运算延时，其他有限域上的复杂运算如指数 运算、求逆( 除法) 运算和取反运算等都可以通过多次乘法实现。因此，在二元 域上的快速乘法运算便成为了研究的焦点和热点。 1 3 有限域乘法器研究现状及成果 1 3 1M o n t g o m e r y 乘法器 目前最为学界熟知和广泛研究的有限域乘法器是M o n t g o m e r y 算法乘法器。 M o n t g o m e r y 算法是1 9 8 5 年由M o n t g o m e r y 发表在著名的“M o d u l a r M u l t i p l i c a t i o nw i t h o u tT r i mD i v i s i o n ”一文中【3 J ，由于它用乘法运算替代 运算复杂度高的乘逆运算，大大降低了除法的复杂度，因而受到了广泛的应用。 早期设计的M o n t g o m e r y 乘法器沿用了经典的M o n t g o m e r y 乘法的定义，只针对素 数域。1 9 9 6 年，K o c 和A c a r 成功地将M o n t g o m e r y 乘法算法移植到二元域上。 这以后，大量高效的二元域上M o n t g o m e r y 乘法和指数运算的软件实现被提出来， 同时利用稍稍对K o c 和A c a r 方法加以扩展的位并行乘法器和平方器也被设计得 到，主要针对某一类特殊的有限域。一种可伸缩的标准化的并且同时支持二元域 运算和有限域运算的乘法器结构也在2 0 0 0 年时被提出”。这里的改进主要是针 对K o c 和A c a r 的算法，事实证明，在恰当选取域元素r ( x ) 使之与不可约多项式 中第二项幂次相同后，就能得到一个有效的乘法器和乘方器架构，具有较低的应 用复杂度。 1 3 2M a s t r o v i t o 乘法器 二元域并行多项式基底乘法器由B a r t e e 和S c h n e i d e r 首先提出。基于不可 约多项式，这一应用需要m 3 一m 个异或门。由于如此高的电路复杂度和结构上的 低规则性，使得早期并行结构的乘法并不具有优势。 M a s t r o v i t o 接着提出了一种算法和乘法器结构( 后来被称为M a s t r o v i t o 算 法乘法器) 用于P B 乘法“1 。该乘法器由f - n e t w o r k 和I P ( m ) 两部分构成，其对 应的硬件体系结构见图一和图二。因为f ( x ) G F ( 2 ) x ，所以f - n e t w o r k 的复杂 性与使用的不可约多项式有关，因此我们仅根据B S P 模型分析I P ( m ) 部分的空间 复杂性和时间复杂性。在I P ( m ) 部分，首先是6 ，和4 ( J = o ，m - 1 ) 相乘，需要 m 个与门在一个L 时间步内完成，其中乃表示一个与门的时间延迟：接着用( 旷1 ) 个异或门在p o g ，m q 步内完成m 个乘积的加法，该计算过程的计算时间为 l o g ：m C ，其中，疋表示一个异或门的时间延迟。 - - 2 - - 浙江大学硕十学位论文一有限域乘法器的设计实现优化 A B 图1G F ( 2 m ) 上的M a s t r o v i t o c 乘法器体系结构 b O 图2 I P ( m ) 的详细结构 S u n a r 和K o c 提出了一种新的在三项式域上计算M a s t r o v i t o 算法的公式，整 个并行乘法器仅需要坍2 1 个异或门和m 2 个与门”1 。H a l b u t o g u l l a r i 和K o c 总结 了S u n a r 和K o c 的方法，并且发现了一个构建适用于任意M a s t r o v i t o 多项式乘 法器的方法”。这种方法既考虑了通常的情况，又考虑了特殊形式不可约多项式 的情况，如三项式、A O P 、E S P 等。在当时，他们的方法针对特殊形式不可约多 项式的情况下拥有最低的异或门数量和最低的延时。 Z h a n g 和P a r h i 提出了一种系统性的方式来构造M a s t r o v i t o 乘法器”1 。进一 步的，他们还改进了先前提出的系统性改进M a s t r o v i t o 乘法器的设计，并比较 了两类不可约五项式M a s t r o v i t o 乘法器的复杂度。 二元域M a s t r o v i t o 位并行乘法器的运算基于多项式基底，包含晰个相同的 一3 一 浙江大学颅十学位论文一有限域乘法器的设计实现j 优化 内积和一个额外的耿模操作，这个设计依赖于有限域的生成多项式。在 M a s t r o v i t o 乘法器被提出来之前，位并行M a s s e y O m u r a 乘法器一度被认为是最 适合7 L S I 实现的并行乘法器，因为它包含了m 个相同的模块。但是事实证明 M a s t r o v i t o 乘法器只需要大约M a s s e y O m u r a 一半的逻辑门数。考虑到它的高规 则性和低的资源使用，M a s t r o v i t o 乘法器结构因此被认为是非常适合包括R S 编 码器在内的各类密码学应用的结构。 和M a s t r o v i t o 方法不同的是，二元域乘法也呵以由一个直接的多项式乘法 和一次模规约得到。这种方法常常在各种文献中被提及。如w u 在取不可约三项 式作为域多项式时曾经提出了一个方法使得二元域乘法能够通过( w 一1 ) ( m 1 ) 位 加法得到，这里W 代表不可约多项式的H a n m i n g 重量。“。在硬件实现时，这个方 法需要m 2 个与门和( m 一1 ) 2 + ( w O ( m 一1 ) 个异或门。近期R o d r i g u e z H e n r i q u e z 和K o c 提出了特殊形式不可约五项式的P B 乘法器，并且计算得到了它的延时和 门数“。虽然他们也将这种方法称为M a s t r o v i t o 乘法器，但是这一结构已经和 最初的M a s t r o v i t o 乘法器有一定区别，因为他们的方法需要两个独立的步骤来 完成乘法。 1 , 3 3K a r a t s u b a 乘法器 大多数有限域上的乘法运算算法都是两步完成：第一步是多项式乘法，第二 步是取模运算。即假设一( x ) ，B ( x ) G F ( 2 “) ，首先计算多项式乘法： c ( x ) = B ( x ) ( x ) = ( 。m - I 叫) ( = 叫) ( 1 1 ) 接下来计算： C ( x ) = C ( x ) r o o d P ( x ) ( 1 2 ) 第一步通常采用经典( C l a s s i c ) 的多项式乘法算法，K a r a t s u b a 算法，以及二 者的混合运用算法。第二步通常采用的取模多项式有：等距多项式 ( E q u a ll y s a p c e dP o l y n o m i a l ) ，三项式和五项式。 K a r a t s u b a 算法由K a r a t s u b a 在1 9 6 2 年提出，它是第一个能够在低于O ( m 2 ) 个操作内完成的多项式乘法，其时间复杂度为O ( m 1 0 8 2 ) ，其基本思想为： 假设 爿( 功= ：q 一= ：，：q 一+ 竺q x ( 1 3 ) = 一2 竺+ 掣q x 。= 一2 A ”+ 一。 B ( x ) = V L 1 ”i = 0 1 i 一= ：，：b x j + ? 叫 ( 1 4 ) = X m 2 竺一b 。+ m 1 2 一+ 竺。以= ”B ”+ 萨。 d 浙江人学碗1 学位论文一有限域乘法器的设计实现1 i 优化 则 c 】：? i ? 4 1 B ”+ ( 爿“B ”+ 爿B L + ( 4 ”+ A ) ( 曰”+ B ) ) x m ”1 + A B 。( 1 5 ) = C “+ C 。 最好的结果是结合经典算法和K a r a t s u b a 策略而得到，该P B 乘法器的空间 复杂度和时间复杂度如下： X O R g a t e s ( m ) 1 ；( R 2 + 6 r t - - 1 ) 一8 研+ 2 A N D g a t e s ( 竺) 1 0 9 ；刀2 T i m e D e 劬+ ( 1 0 9 2 n + k ) 其中m = 2 k n 1 3 4 正规基乘法器 在域元素的正规基表示下，域元素的平方运算仅需对该元素的坐标进行简单 循环移位即可，在硬件实现平方运算时，其开销可以忽略不计，因此，基于正规 基表示的乘法运算及其乘法器设计得到了大量研究“。 一般的， A = ( a o ，q ，a m 一，) ，q 表示A 的第i 个座标。 另瓦= 【，q ，a m I 】和i = 【6 0 ，岛，屯一。】分别对应域元素4 = ( 嘞，q ，口。) 和曰= ( 6 0 ，岛，6 卅一1 ) 的行向量，C = ( ，C I ，c 卅一。) G F ( 2 ) 表示它们的乘积，则 c = A B = ( = 口，y 2 ) ( ：0 厂2 7 ) ( 1 6 ) = 砷矿( 1 7 ) 其中，矩阵肘可通过f 次循环右移和璁定循环下移矩阵M ( o ) ：M 得到】( 【， 矿表示i 的转置。 一5 一 浙江大学硕十学位论文一有限域乘法器的设计实现j 优化 图3 正规基乘法器实例图 一6 一 浙江大学硕土学位论文一有限域乘法器的设汁实现1 ，优化 1 4 有限域乘法器应用现状 在安全通信领域，由于数据的传输途径在很大程度上是开放式的，发送方和 接收方为了保证数据的安全，必须对数据进行加密操作，而接收方在接收到数据 后进行相应的解密操作，获取有用的信息。这样，在通信中就需要有相应的密码 算法支持，以达到安全通信的目的。而这些密码算法的选择根据相应的应用场合， 必须符合一定的条件，比如目前应用广泛的对称加密算法( 私钥加密算法) ，由 于其运算强度小，吞吐率高而在民用通信等低强度安全通信领域被广泛使用。但 在高强度安全通信领域，如航空航天、军事领域等，传统的私钥加密算法已经越 来越不能满足现实需要，很多时候只好求助于公钥密码算法。 但公钥密码算法在带来高强度安全性的同时也产生一个严重的问题，就是运 算量相对于私钥加密算法而言太大，无法应用于高速实时通信领域，这一问题一 直困扰着众多从事密码学研究的科技人员。目前对这一问题的处理存在着回避和 强行解决两者方法，采用回避方法的专家们一般倾向于使用双钥密码算法，即对 数据采用私钥密码算法，而对私钥的传输、储存、交换采用公钥算法，这个方法 的缺点是需要在不同算法间进行切换，当传输的数据量较小，或是在突发式传输 领域，开销过大。而采用强行解决的专家们则逐渐分成两个派系：是选择安全 强度高而运算量小的公钥密码算法，如用E l l i p t i cC u r v eC r y p t o g r a p h y ( E C C ， 椭圆曲线密码算法) 来代替传统的R S A 公钥算法“4 ”“1 ；二是研究低复杂度高速度 的运算单元( 即高性能的密码算法核) ，这方向上的研究考虑了密码学中运算 的特殊性，目前主要集中在乘法器的设计上“。有低复杂度高速度乘法器的支持， 就能使公钥密码算法克服自身运算量太大的缺陷，从而在通信领域获得更广泛的 应用。 1 浙江人学硕上学位论文一有限域乘法器的设计实现j 优化 第2 章有限域运算的数学基础 2 1 有限域算术 2 1 1 有限域定义 域是对常见的数系及其基本特征的抽象。定义给定的一个非空集合G 及两 种运算加法( + 表示) 和乘法( 表示) ，同时满足以下三项算术特性1 1 7 】： ( 1 ) ( G + ) 对于加法运算构成加法交换群，单位元用0 表示； ( 2 ) ( G O ) ，) 对于乘法运算构成乘法交换群，单位元用1 表示； ( 3 ) 分配率成立：对于所有口，b ，c G ，都有( a + 6 ) c = a c + 6 c 。 若集合G 是有限集合则称域为有限域。 简言之，就是有限域具有封闭性、交换律、结合律、单位元、逆元。 2 1 2 素数域和二元扩域 令P 是一个素数，则 O ，1 ，P 一1 ) 组成一个有限域，称为素域，记为G F ( p ) 。 有限域的元素个数称为有限域的阶，阶为2 “的域称为二元域，记作G F ( 2 4 1 。构 成二元域G F ( 2 ”) 的一种方法是采用多项式基表示法，即域G F ( 2 ”) 的元素是次数 最多为m 一1 次的二进制多项式，系数取自G F ( 2 ) = ( O ，1 ) I t s ： G ( 2 ) = 一1 z ”1 + 口z ”2 + + a l z + a o ：q o ，1 ) ) = = q ，4 o ，1 ) ( 2 1 ) 从而可以用m 维向量( ，q ，a i ，) 来表示二元括域上的任一元素。 选择二元域上的m 次既约多项式f ( z 1 。域元素的加法是两个多项式系数的模 2 相加，域元素的乘法是两个多项式相乘后取模f ( z ) 。 2 2 有限域的基 定义2 1 有限域F ( q ”) 可以看作是域F ( q ) 上的一个向量空间。其向量是域 F ( q ”) 的元素，标量是域，( g ) 的元素，向量的加法运算是域F ( q “) 上的加法运算， 标量与向量的乘法是域F ( g ) 的元素与域F ( q ”) 的元素在域F ( 矿) 上的乘法运算。 这个向量空间的维数是”，有许多基底。 一R 一 浙江人学硕L 学位论文一有限域乘法器的设计实现1J 优化 定义2 2 有限域G F ( 矿) 上的一组具有疗个元素的向量表 口，口q “ ，其 中口为有限域上某一个特定的元素，这时我们称 口，盯q “ 是有限域 G F ( q ”) 上基于生成多项式f ( x ) 的正规基底( N o r m a lB a s i s ，N B ) 。 ( 1 ) I 型最优正规基的构造 定义2 3 假设m 1 是素数，2 是模m + l 的一个原根( 即，2 的幂模( m + 1 ) 生成 1 m 中的元素) ，则G F ( 2 ) 上肌个非单位元的( 所+ 1 ) 次单位根是线性无关的，且 组成G F ( 2 “) 到G F ( 2 ) 上的一组最优正规基， 记 N = 缸2 1 f = o ，m - l = 缸7 I ，= 1 ，哪，其中口是一个( m + 1 ) 次本原单位根 ( i e 口1 ( 1 i m + 1 ) ) ，称N 是G F ( 2 ”) 到G F ( 2 ) 上的一组I 型最优正规基。 ( 2 ) I I 型最优正规基的构造 定义2 4 令G F ( 2 “1 是含2 “个元素的有限域。如果2 m + l = P 是素数，且下 面两个条件之一成立：2 是模P 原根；或P = 3 ( m o d 4 ) ，且2 模P 的次数为m ，则 ，= + 卢1 生成一个G F ( 2 ”) 至J O F ( 2 ) 上的一组最优正规基，其中是( 2 m + 1 ) 次 本原单位根。记= ，y 2 ， = + ，2 + ，“+ ”) ，称N 是 G F ( 2 ”) 到G F ( 2 ) 上的一组I I 型最优正规基。 定义2 5 令口为有限域G F ( 矿) 内的一个元素，有限域G F ( 矿) 的生成多项式 为厂( 力，若d 在有限域G F ( q ”) 内相对于( 砷的最小次数为”，即有限域的次数， 这样口的一组幂 1 ，口，口2 ，口“) 就构成了有限域的多项式基底( P 。l y n o m i a l B a s i s ，P B ) 。 定义2 6 令v 是一个整数，有序组M = 缸I O i m 一1 ) 是二元域上的一个 多项式基底。则有序组口M ：= x “9 1 0 i 聊一1 ) 被称为相对于M 的移位多项式基 底( S P B ) 。 在由三项式f ( x ) = X ”+ + l 生成的有限域中，P B 和相应的S P B 分别表示为 M = 虹1 0 i m - l 和口一M # x l O j m 一1 ) ，其中O v m 一1 ，盯是满足 一9 一 浙江人学硕一卜学位论文一有限域乘法器的设计实现j 优化 f ( a ) = 0 的根。文献 1 9 证明了当v 取k 或k 一1 时乘法器具有最低的复杂度。在 设计三项式乘法器时，我们取v 等于k ，而相应的S P B 为 口4 M # 4I o i m 一1 ) 。这样，和多项式表示方法类似，有限域上的每一个 元素都能由移位多项式基底独一无二地表述，即任意有限域元素爿均可唯一地表 示为A = m - I - ”q + ，。 文献 1 9 也同时证明了在不可约三项式生成的有限域中，有限域元素在P B 和S P B 之间的相互转换，在并行计算的情况下仅需要v 个二输入异或门和一个单 位的异或门延时( 1 巧) 。 在I I 类乘法算法中，S P B 上的乘法与P B 上的乘法一致，只有第二步约减时 利用以下两个公式来完成： 一= ，”+ x 1 ，其中m v i 2 m 一2 2 v ( 2 2 ) x = x ”w + x “。， 其中2 v i 一( v + 1 ) 定义2 6 已知有限域G J F ( 矿) 及其生成多项式( x ) 。则两组有限域上基于 ，( x ) 的基底 ，q ，o r 一) 和 屁，届，鼠一一 若是满足以下公式则被称为互为共 轭基底，其中I f ，J n ： 她驴船乞 对于二元域上的元素口G F ( 2 ”) ，它的二元域上的迹函数( t r a c ef u n c t i o n ) 可表示为n ( 口) = ：口。 定义2 7 2 0 令慨) 和 屈 是二元域上的两种基底，取任意非零元素 y G F ( 2 ”) 。这样，如果满足条件丹( 心乒) = 磊，i ，j = o ，1 ，2 ，埘一1 则称两种基 底互为弱共轭，其中T r ( ) 为迹函数，瓯为K r o n e c h e rd e l t a 函数，这一函数的 值仅在i = j 时等于1 ，其余情况下等于0 。 提示2 1 1 0 对于任意一个非零的，G F ( 2 “) ，每一类基底都有其相应的 基于y 的弱共轭基底。 相对于共轭基底的定义，弱共轭基底中引入了，这个参量。由于，可以取到 浙江人学硕 ：学位论文一有限域乘法器的设计实现1 优化 非零元素以外的所有其他值，极大地扩展了共轭基底的选择。以多项式基底为例， 任意多项式基底的共轭基底是确定且唯一存在的，而存在的弱共轭基底的数目为 2 ”一1 ，如此多弱共轭基底对的存在为有限域乘法的设计提供了很大的帮助，因 为从众多的基底中选取几种易于硬件实现的结构相对于原先共轭基底没有备选 方案的情况，在硬件实现上更为有利。 基于S P B 的W D B 以不可约三项式f ( x ) = X “+ + l 生成的有限域上移位多项 式基底来获得它的弱共轭基底并得到相关的性质。如果S P B 由 ，q ，一。) 表 示，同时令不可约三项式，( x ) 的根为口，我们很容易得到吒+ ，= ，其中 一V - - f 茎m l v 。假定 屁，届，成一) 为 ，q ，一，) 的弱共轭基底。 对于二元域上的元素4 ， m - l - vm - l - vm - l - v 4 = q + ，q 。= q + ，口= 瓦，取，( 2 4 ) 一v i f f i - v i = - V 其中a i 和蠢，一v i n q 一1 - v ，分别表示了在S P B 和W D B 表示时元素爿的系 数。根据定义2 7 ，可以得到 m - I 一” T ，( r a 4 ) = r r ( z a 7 吐，属+ ，) m 一1 一” = 丹( 玛+ ，层+ ，) 文， ( 2 5 ) i f f i - v = 口：+ ，一v 兰J m - l - v 从( 2 5 ) 中可以发现，对多项式基底的某一个元素一和基底口，的乘积进行迹 函数值的计算可以得到相应的弱共轭基底的参数，这就给出了多项式基底与其弱 共轭基底之间的代数关系，同时也给出了两种基底之间相互转化的关系。而如何 利用这个关系进行乘法器结构的设计，降低乘法器的复杂度，提高乘法效率就成 了工作的重点。 2 3 有限域各种基底的转换 2 3 1 正规基与多项式基 设厂O ) = 矿+ 厶。X ”1 + 石x + 石是是G F ( 2 ) 上次数为坍的不可约多项式，把 f ( x ) 作为约化多项式可定义有限域为G F ( 2 4 ) ： G F ( 2 “) = 一l X ”1 + a l x + a o I q o ，1 ) ) 一1 l 一 浙江人学硕卜学位论文一有限域乘法器的设计实现1J 优化 设= ，q ，一，) 是G F ( 2 ”) 到G F ( 2 ) 上的一组基，如果存在 G F ( 2 ) ，使得= p ，O s j m - 1 ，则称N 为一组多项式基。如果存在 ，G F ( 2 ”) ，使得q = 广，o s i m 一1 ，则称N 为一组J 下规基。当取定一组基 后，可以把G F ( 2 ”) 的元素+ q q + + a m I 一l 与G F ( 2 ) 上m 维向量 ( 嘞，a I ，a m 一。) 等同起来。 下面两个基集合 M = f l + f l - , f 1 2 + 卢。2 ，卢，1 + 。“) 与 = 妒+ 卢一，卢2 + p - , - - - , , a ”+ 卢“) 是等价的，假设口2 钕。m ， 关于基M 和N 的表示分别为 十，q ，铴) 和 一- ，呸，“，则可得到q 。a i ，其中 I k ( k 【1 ，m 】) 。 【( 2 坍+ 1 ) 一k ( t 【m + l ，2 州】) ，七= 2 “( m o d 2 m + 1 ) ( i ：1 ，二 2 )( 2 - 3 ) 。利用 此式便可以将域元素的正规基表示和多项式基表示进行相互转换。 2 3 2 多项式基转换为共轭基 以G F ( 2 8 ) 域生成多项式为f ( x ) = x 8 + 工4 + 矿+ x 2 + l 为例。从迹函数的定义可 以得到如下等式：T r ( 1 ) = 0 ，T r ( a ) = O ，T r ( a 2 ) = 0 ，T r ( a 3 ) = O ，T r ( a 4 ) = 0 ， T r ( a5 ) = 1 ，T r ( a 6 ) = 0 ，T r ( a 7 ) = 0 ，其中o r 满足等式f ( o t ) = 0 。一个元素Z 由 多项式基底表示为z = ：；。在共轭基底中可以表示为z = ：= o z ：五，其 中 ：- = T r ( Z c t ) = 乃( ( 毛t 。+ z - 口+ 2 7 2 + 毛口3 _ 口4 + 毛口5 + Z 6 口6 + 口7 ) 口) ( 2 ，4 ) = z o T r ( a ) + z l T r ( a “1 ) + z 2 T r ( a + 2 ) + z f r ( a ) + z 4 T r ( a 。+ 4 ) + 弓7 ，( 口。+ 5 ) + z 6 乃。( 口+ 6 ) + 乙乃( 口+ 7 ) n ( ) ，0 蔓七1 4 ，已知情况下，实现多项式基底向共轭基底的转化。 2 3 3 共轭基转换为多项式基 采用上节提到的有限域和生成多项式，共轭基底表示的元素Z 可以表示为 z = ：；。z 。五。在多项式基底情况下，令它表示为z = ：；。从轨迹函数 的定义可以得到如下等式： 一1 2 浙江大学硕I ：学位论文一有限域乘往器的设计实现j 优化 z k = T r ( Z 五) ：黪淼麓兹乏湍瑟- b 托Z j 5 糍 地) ( 2 = z ；乃( 凡五) + z 。n ( 五五) + z ：乃( 五五) 7 ，( 五磊) + ：4 乃( 五 ) + z ，n ( 五矗) + z j n ( 五五) + z ，n ( 五) 若共轭基底已经确定，上面公式中的轨迹函数值已经被计算得到，从而完成 共轭基底向多项式基底的转化。 2 3 4 迹函数求解 多项式基底和共轭基底之间相互转化时，迹函数的值是转化的一个关键，如 何快速求解轨迹函数的值可以加快密码系统中各类基底的转化，提高密码系统的 效率“。 这里介绍一种快速计算域元素迹函数值的算法。利用迹函数的定义，对于 ，2 G F ( 2 “) ，有 乃( p 2 ) 5 萎( 2 ) r = f 1 2 + 卢2 2 + + ( 2 6 ) t = 0I ，6 ) = + 2 + + 2 ”1 = T r ( y ) 因此，如果已知乃( ) ，就能直接知道舟( 卢2 ) 的值而无需计算。 鉴于每一个二元扩域上的元素都能用基底忙o ，0 I 口2 ，a 3 口4 ，口5 ，口6 ，口7 ) 来表 示，则可以表示成为= 屁+ 届一+ 屈口2 + 屈口3 + 局口4 + 肛口5 + 成口6 + 岛口7 。 从迹函数的性质可以得到 丹( ) = 属n ( d o ) + 届乃 1 ) + 岛乃 2 ) + 屈n 幢3 ) r 。7 、 + 肛乃以4 ) + 屈乃5 ) + 屁乃位6 ) + 岛乃 7 ) 因此只需计算口o ，a 1 ，口2 ，矿，a 4 , 口5 ，矿，口7 的迹函数值即可，其他的值可以很 容易地通过这些基底表示即可得到。 一1 3 一 浙江人学硕士学位论文一有限域乘法 的设计实现1 优化 2 4 椭圆曲线加密算法 将椭圆曲线用于公钥密码学的思想是1 9 8 5 年由V i c t o rM i l l e r 和N e a lK o b l i t z 共同提出的。其理论基础是定义在有限域上的某一椭圆曲线上的有理点可构成有 限交换群。如果该群的阶包含一个较大的素因子，则其上的离散对数问题是计算 上难解的数学问题【2 0 J 。 现已证明，除了某些特殊的椭圆曲线之外，目前已知的最好的共计算法也是 完全指数级别的。就密钥安全性强度而言，密钥长为1 6 3 b i t 的椭圆曲线密码体制 ( 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 C ) 相当于1 0 2 4 b i t 的R S A 的密钥强度。这样， E C C 对于存储空间、传输带宽、处理器处理速度的要求就较低。这使得E C C 成 为很有前途的公钥密码体制【2 l 】。 定义3 1 有限域G F ( 2 1 上的椭圆曲线是指由W e i e r s t x a s s 方程： Y 2 + x y = x 3 + a x 2 + 6 口，b G F ( 2 ”) ，b 0 ( 3 1 ) 若a G F ( 2 ) b = 0 则称为K o b l i t z 曲线。 定理3 1 令E 为有限域卯( 2 ”) 上的椭圆曲线，令P = ( 一，y O 为E 上的点，则 一P = ( X t ，X t + M ) 。如果P = ( x 2 ，北) 也为E 上的点且O P ，则P + Q = ( x 3 ，见) ， 其中 为= 五2 + A + 一+ 屯+ 口 ( 3 2 ) Y 3 = 2 ( x l + x 3 ) + x s + 咒( 3 3 ) 肚+ ( 3 4 ) 如果Q = P ，