（信息与通信工程专业论文）高性能有限域乘法器的研究与实现.pdf

浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 摘要 密码技术在诸如通信和计算机系统等领域日渐广泛的应用使得越来越多的 学者开始寻找有限域上快速计算的方法，特别是次数较大的二元域更是研究的 重点。本论文的中心思想就是探索高效的有限域计算方法和实现结构，研究主 要针对由不可约三项式和不可约五项式构建的二元扩域。同时，为了满足现代 密码系统的性能要求，文中所研究和探讨的都是位并行有限域乘法器。 本文首先提出的高性能有限域乘法器利用了非平衡模规约算法。当有限域 的生成多项式( 力= ，+ 丁o ) 满足d e g 【r o ) 】册时，这种算法有着极高的运算 效率。在二元域椭圆曲线密码系统( e c c ) 中，国际密码标准( s e c ) 推荐的 几类不可约多项式均满足这个特点。因此，非平衡模规约算法与其它主流算法 相比运算速度提高了l o 3 0 倍，而非平衡模乘算法可以提高e c c 点乘算法 4 0 0 , - 5 0 的性能，且该方法无需预计算。 文中另外一种乘法器基于移位多项式基底( s p b ) 。当有限域生成多项式为 等比三项式时，移位多项式基底与k a r a t s u b a - o f m a n 方法结合使用。这里，s p b 的应用降低了乘法器的延时而k a r a t s u b a - o f m a n 方法的应用则降低了乘法器空 间复杂度。这样设计的乘法器结构与其它乘法器结构相比有着相同的延时而逻 辑门数量下降了1 4 。 同时本文还提出了基于移位多项式基底及其弱共轭基底( w d b ) 的有限域 乘法器结构。在由不可约三项式和不可约五项式构建的有限域中，本文提出的 架构在相同的空间复杂度下有着目前最小的时间复杂度。而且，本文提出的乘 法器结构具有很高的规则性，大大降低了硬件电路设计者对数学知识的要求， 为乘法器的快速设计实现提供了极为有利的条件： 关键词：有限域计算，位并行乘法器，移位多项式基底，非平衡模乘算法，三 项式，五项式 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 a b s t r a c t t h ei n c r e a s i n gu s eo fc r y p t o g r a p h yt e c h n i q u e si i lv a r i o u sc o m m u n i c a t i o n a n dc o m p u t e rs y s t e m sh a si n s p k e dm a n yr e s e a r c h e r st of i n dw a y so up c l t o r m i n g f a s t c o m p u t a t i o n s o v e rf i n i t e f i e l d s ，e s p e c i a l l y o v e r l a r g e f i n i t ef i e l d so f c h a r a c t e r i s t i ct w o t h ec e n t r a lt h e m eo ft h et h e s i si sa ni n v e s t i g a t i o no ff i n i t ef i e l d c o m p u t a t i o n sa n dt h e i ra 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 d p e n t a n o m i a l s a l lt h em u l t i p l i e ra 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 l f i n i t ef i e l d m u l t i p l i e r s w h i c hc a ni m p r o v et h e e f f i c i e n c y o fc r y p t o s y s t e m s s i g n i f i c a n t l y t h ef i r s tp r o p o s a lo f h i g hp e r f o r m a n c ef i n i t ef i e l dm u l t i r l i e ri sb a s e do n u n b a l a n c e dm o d u l a rr e d u c t i o na l g o r i t h m t h i sa l g o r i t h mc a na c h i e v e h i g he f f i c i e n c y w h e nc o m p u t i n go nac e r t a i nc l a s so ff i n i t ef i e l d sg e n e r a t e db yf = + t 嗡 w h e r e d e g 【r ( x ) 】m i nt h e f i e l do fe 1 l i t ，t i cc u r v ec r y p t o s y s t e m ( e c c ) o v e r g f ( 2 ”) ，t h er e d u c t i o np o l y n o m i a l sr e c o m m e n d e db ys e c ( s t a n d a r d sf o re f f i c i e n t c r y p t o g r a p h y ) f u l f i l lt h ep r o p e r t ym e n t i o n e da b o v e t h ep r o p o s e da l g o r i t h m sc a l l s p e e du pm o d u l a rr e d u c t i o nb y1 0 3 0t i m e so v e i g f ( 2 ”) a n ds p e e du pe c c p o i n t m u l t i p l i c a t i o nb y4 0 - 5 0 w i t h o u tp r e - c o m p u t a t i o nw h e nc o m p a r e dt oo t h e rm a i n s t r e a mm o d u l a rm u l t i p l i c a t i o nm e t h o d s t h es e c o n dp r o p o s a li sb a s e do ns h i f t e dp o l y n o m i a lb a s i s ( s p b ) w h e n u s e di nf i n i t ef i e l dg e n e r a t e db ye q u a l l ys p a c e dt r i n o m i a l ( e s t ) ，s p bi sc o m b i n e d w i t hk a r a t s u b a - o f i n a nm e t h o d t h eu s eo fs p bs i g n i f i c a n t l yr e d u c e st i m ed e l a yo f t h ep r o p o s e dm u l t i p l i e ra n da lt h es a l n et i m ek a r a t s u b a - o f r a a nm e t h o dd e c r e a s e s p a c ec o m p l e x i t y a sar e s u l t , w i t ht h es a m et i m ec o m p l e x i t y , a p p r o x i m a t e l y3 4 g a t e so f p r e v i o u sm u l 石p t i e r sa r eu s e di np r o p o s e dd e s i g n a l s o n e ws n u c n l i so fb 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 y d u a lb a s i s ( w d 8 ) 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 y t r i n o m i a l sa n dp e n t a n o m i a l s , t h ep 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 h u pt od a t ew 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 ra d 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 oh a r d w a r ef o rt h e i rr e g u l a r s t r u c t u r e s k e y w o r d s ：f i n i t ef i e l da l g o r i t h m , 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 l b a s i s ，u n b a l a n c e dm o d u l a rm u l t i p l i c a t i o n , t r i n o m i a l s ，p e n t a n o m i a l s 一1 l 一 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 图目录 图1 公钥密码加速器架构1 7 图2s m i c 3 5 工艺下三项式乘法器的关键路径4 8 图3s m i c 1 8 工艺下三项式乘法器的关键路径 图4s m i c 1 3 工艺下三项式乘法器的关键路径 5 0 5 1 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 表目录 表一非平衡模规约算法与其它模规约算法的性能比较1 4 表二非平衡模乘算法与其他模乘算法的性能比较1 6 表三几种三项式乘法器的复杂度比较 表四各种有限域乘法器复杂度的比较，其中域生成多项式为 f ( x ) = j ，+ j 南+ 工屯+ j b + l ，0 岛 屯 毛m 2 ) 3 3 表五各种有限域乘法器复杂度的比较，其中域生成多项式为 。r ( 曲= ，+ r + 2 + r + 1 + ，+ l ，其中1 n 1 ) ，该设计则大大降低乘法器的复杂度m 。 与之对应的是，在多项式基底的有限域乘法器领域，所有应用已有最新技 术的有限域乘法器中，低的空间复杂度和时间复杂度的乘法器都是构建在e s p 或三项式上。遗憾的是，不可约的e s p 相当少，在次数小于1 0 2 4 的有限域中， 只有8 1 个域存在不可约的e s p 1 8 】。 另一方面，不可约的三项式也不是每个次数的有限域上都存在的。事实上， 在次数小于1 0 2 4 的有限域中，有4 6 8 个不存在不可约三项式【2 6 1 。因为在特征 为2 的有限域中，一个不可约多项式中必须包含奇数个非零的参数，所以第二 个选择就是使用不可约五项式。而i e e e 的i e e es t a n d a r ds p e c i f i c a t i o n sf o r p u b l i c - k e yc r y p t o g r a p h y 3 7 也推荐使用不可约五项式来替代不可约三项式当不 可约三项式在某些次数的域中不存在时候。这个推荐相当必要而且实用，因为 在幂次为2 1 0 0 0 0 的有限域中，不可约的三项式或五项式必然存在【2 6 l 。因此， 设计基于不可约五项式的乘法器就具有了很强的实用意义，特别是对于密码学 应用。 - - 4 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 在研究基于某些特殊不可约五项式的域上的乘法器的时间和空间复杂度 时，两种特殊类型的不可约五项式被提出来，并且得到了充分的验证。这两种 不可约五项式分别被命名为i 型和型，具体表述如下所示： t y p e i ：，+ x ”1 + ，+ x + 1 ，w h e r e2 n _ l m 2 j - 1( 1 2 ) t y p e ：j ，+ j ”2 + 耳”“+ ，+ l ，w h e r el n l - 2 j 一1( 1 3 ) 从充裕程度看待这两种五项式有着很强的现实意义，因为在很多幂次的有 限域中这两种形式的不可约五项式存在：在幂次小于5 1 5 的域中有4 1 6 个幂次 存在i 型不可约五项式；在幂次小于5 2 6 的域中有3 0 4 个幂次存在型不可约 五项式【2 6 1 ，即i 型和型的五项式在数量上是充分的，已有文献证明这两种类 型的五项式能分别为m a s t r o v i t o 和共轭乘法器的设计提供有利的条件【1 8 1 。 1 2 3m 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 乘法 2 5 1 。s u n a r 和k o c 提出了一种新的在三项式域上计算m a s t r o v i t o 算法的公式，整个并行乘法器仅需要n 1 2 一1 个异或门和肼2 个与门i s l 。 h a l b u t o g u l l a r i 和k o e 总结了s u n a r 和k o e 的方法，并且发现了一个构建适用于 任意m a s t r o v i t o 多项式乘法器的方法【1 9 l 。这种方法既考虑了通常的情况，又考 虑了特殊形式不可约多项式的情况，如三项式、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 7 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 位并行乘法器的运算基于多项式基底，包含m 个相同的 内积和一个额外的取模操作，这个设计依赖于有限域的生成多项式。在 m a s t r o v i t o 乘法器被提出来之前，位并行m a s s e y - o m u r a 乘法器一度被认为是最 适合v 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 a - o v i t o 方法不同的是，二元域乘法也可以由一个直接的多项式乘法 和一次模规约得到。这种方法常常在各种文献中被提及。如w u 在取不可约三 一5 一 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 项式作为域多项式时曾经提出了一个方法使得二元域乘法能够通过 ( w 一1 ) ( 埘一1 ) 位加法得到，这里w 代表不可约多项式的h a m m i n g 重量【2 2 】。在硬 件实现时，这个方法需要聊2 个与门和( m 一1 ) 2 + ( w 一1 ) ( 肼一1 ) 个异或门。近期 r o d r i g u e z h e n r i q u e z 和k o c 提出了特殊形式不可约五项式的p b 乘法器，并且 计算得到了它的延时和门数【1 8 】。虽然他们也将这种方法称为m a s t r o v i t o 乘法器， 但是这一结构已经和最初的m a s t r o v i t o 乘法器有一定区别，因为他们的方法需 要两个独立的步骤来完成乘法。 1 2 4m 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 r i l i c a t i o nw i t h o u tt r i a ld i v i s i o n ”一文0 e t 2 引，由于它用乘法运算替代运算复 杂度高的乘逆运算，大大降低了除法的复杂度，因而受到了广泛的应用。早期 设计的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 乘法算法移植n - - 元域上【3 1 】。 这以后，大量高效的二元域上m o n t g o m e r y 乘法和指数运算的软件实现被提出 来，同时利用稍稍对k o c 和a c a r 方法加以扩展的位并行乘法器和平方器也被 设计得到，主要针对某一类特殊的有限域。一种可伸缩的标准化的并且同时支 持二元域运算和有限域运算的乘法器结构也在2 0 0 0 年时被提 2 0 j 。这里的改 进主要是针对k o c 和a c a r 的算法，事实证明在恰当选取域元素，( 曲使之与不 可约多项式中第二项幂次相同，就能得到一个有效的乘法器和平方器架构，具 有较低的应用复杂度。 1 1 3 有限域乘法器在安全通信领域的应用 在安全通信领域，由于数据的传输途径在很大程度上是开放式的，发送方 和接收方为了保证数据的安全，必须对数据进行加密操作，而接收方在接收到 数据后进行相应的解密操作，获取有用的信息。这样，在通信中就需要有相应 的密码算法支持，以达到安全通信的目的。而这些密码算法的选择根据相应的 应用场合，必须符合一定的条件，比如目前应用广泛的对称加密算法( 私钥加 密算法) ，由于其运算强度小，吞吐率高而在民用通信等低强度安全通信领域被 广泛使用。但在高强度安全通信领域，如航空航天、军事领域等，传统的私钥 加密算法已经越来越不能满足现实需要，很多时候只好求助于公钥密码算法。 但公钥密码算法在带来高强度安全性的同时也产生一个严重的问题，就是运算 量相对于私钥加密算法而言太大，无法应用于高速实时通信领域，这一问题一 直困扰着众多从事密码学研究的科技人员。目前对这一问题的处理存在着回避 和强行解决两者方法，采用回避方法的专家们一般倾向于使用双钥密码算法， 一6 一 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 即对数据采用私钥密码算法，而对私钥的传输、储存、交换采用公钥算法，这 个方法的缺点是需要在不同算法间进行切换，当传输的数据量较小，或是在突 发式传输领域，开销过大。而采用强行解决的专家们则逐渐分成两个派系：一 是选择安全强度高而运算量小的公钥密码算法，如用e 1 l i p t i cc u r v e c r y p t o g r a p h y ( e c c ，椭圆曲线密码算法) 来代替传统的r s a 公钥算法【6 】【2 3 1 ；二 是研究低复杂度高速度的运算单元( 即高性能的密码算法核) ，这一方向上的研 究考虑了密码学中运算的特殊性，目前主要集中在乘法器的设计上1 3 4 1 。有低复 杂度高速度乘法器的支持，就能使公钥密码算法克服自身运算量太大的缺陷， 从而在通信领域获得更广泛的应用。 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 第2 章有限域乘法中的数论知识 2 1 有限域基底 有限域中各个元素的表示一般基于三类基底，分别被命名为多项式基底 ( p o l y n o m i a lb a s i s ，p b ) ，正规基底( n o r m a lb a s i s ，n b ) 和对称基底( d u a l b a s i s ，d b ) 。这几类基底各自的定义如下【2 2 】： 琵义2 1 l 令俚为存眼域g f 时、内的一个元素套限域g f 崤、的生成 多项式为l l 心若在有限域g f l 蕾、内指对于l 旺1 的最小次数为n 鄂有限 域的次数，这样伍的一组幂次u 。【玉，o p 就构成7 菊限域的多项式基底 ( p o l y n o m i a lb a s i s ，p b ) 。 是艾2 2 有限域g f ( q “、上的一组具有n 令元素的向量表 口，口一 ，菇乒口为方用域上祟一个劳启；q 元荣，越蔸刃移 c l , 毋。矿是宥限域g f ( q 1 、上基于生成多项式 l x 、的正规基底( n o r m a l b a s i s n b ) ， 良艾2 3a 知有限域g f 时、及其生战多项式f t 砼。黜两组考限域上基 于f 的基底k o 。俚、，旺。0 和k 氏，改，。p 若是满足以下公式奶被称为互 为共轭基底其中、s i , j n ： 打( 吒，) ：彤? 2 2 各类基底之间转化关系 多项式基底是现实应用中最为实用且最容易直观认识的一种基底，大部分 的密码系统从顶层的角度来看，其最初的输入和最终的输出都是通过多项式基 底表示的，而密码系统中的运算模块一乘法器又往往根据应用的场合和使用 的算法的不同而采用多种类型的基底，如正规基底，共轭基底等。于是各类基 底之间的转化也是密码系统的设计者需要考虑的一个问题，以下的几个小节介 绍了几种常用基底之间的相互转化方法。 2 2 1 多项式基底转化到共轭基底 这里介绍了一种将有限域元素从多项式基底表示转化到共轭基底表示的方 法【2 n 。以g f ( 2 8 ) 域生成多项式为厂( 曲= 算。+ x 4 + ，+ ，+ l 。从迹函数的定义可 以得到如下等式：t r o ) = 0 ，乃( 盯) = 0 ，r r ( a 2 ) = 0 ，r r ( a ) = 0 ，t r 4 ) = 0 ， 一8 一 浙扛大学硕士学位论文一高性能有限域乘法器的研究与实现 乃位5 ) = 1 ，r r ( a 6 ) = o ，t r 7 ) = o ，其中口满足等式f ( o e ) = o 。一个元素z 由 多项式基底表示为z = ：，。z k a 在共轭基底中可以表示为z = 乙z ：五， 其中 z ：= t r ( z a ) 羔：j：荔荔2+弘3麓盯4+z5cc5+。z，6zotr(a) + z 2 t r ( a ) + z 3 t r ( a 叩1 矿 = ) + z 1 乃( 盯“1 “2 “3 ) 、。 z 4 y r ( a “4 ) + z s t r ( a “5 ) + z 6 t r ( a “6 ) + z 7 t r ( a ”) 因此，一旦乃似) ，0 k - 1 4 ，都已知的情况下，从多项式基底向共轭基底 的转化就完成了。 2 2 2 共轭基底转化到多项式基底 这里介绍了一种将有限域元素从共轭基底表示转化到多项式基底表示的方 法【2 1 】。依旧采用上节提到的有限域和生成多项式，共轭基底表示的元素z 可以 表示为z = 乙z ：五在多项式基底情况下，令它表示为z = ：。4 。从 轨迹函数的定义可以得到如下等式： = 乃( z 五) ：a z t o 警淼麓兹之澎t r 搿麓袅搿托7 劲= 乃( 凡五) + z ：7 ，( 五) + z ：( 五五) + z ：z ，( 五五) 、 + z j 2 ，( 五五) + z ：2 ，( 五五) + z ：z ，( 五五) + z ；乃( 乃五) 因此，如果共轭基底已经确定，上面公式中的轨迹函数值已经被计算得到， 从共轭基底向多项式基底的转化就完成了。 2 2 3 求解迹函数的值 在上面的论述中我们发现，多项式基底和共轭基底之间相互转化时，迹函 数的值是转化的一个关键，如何快速求解轨迹函数的值可以加快密码系统中各 类基底的转化，提高密码系统的效率伫1 1 。 这里介绍一种快速计算域元素迹函数值的算法。利用迹函数的定义，对于 ，2 g f ( 2 4 ) ，有 n ( d 2 ) 2 荟- - u 够2 ) 一= 2 + 2 2 + + 2 i( 2 4 )ti 二- t ， = + 户2 + + 声2 “= 7 ，( ) 因此，如果已知r r ( p ) ，就能直接知道1 r ( p 2 ) 的值而无需计算。 鉴于每一个二元扩域上的元素都能用基底缸o ，口2 ，g 3 , ，口7 来 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 表示 ， 则 可以表 示成为 = 屁口o + 屈+ 屈盯2 + 屈矿+ 屈矿+ a a 5 + 屈口6 + 岛口7 。从迹函数的性质可以 得到 乃( ) = 成n 。) + a r r 1 ) + 压乃 2 ) + 压丹 3 ) ( 2 5 ) + 屈t r ( a 4 ) + 尼乃 5 ) + 尼t r 6 ) + p ：r ( a 7 ) 、7 因此只需要计算扩，口2 ，矿，矿，口6 ，口7 的迹函数值即可，其他的值可以 很容易地通过这些基底表示即可得到。 2 3d t w h e 公式 为了使文章证明充分，这里将会定义有限域上的迹、离散域w i c n e r - h o p f 等式( d t w i - i e ，d i s c r e t et i m ew i 昏h o p f e q u a t i o n ) 和共轭基底的数学概念【帅】。 令4 为一个素数幂次，m 为一个正整数。 定义2 4 p 、是g f ( q “、上豹一组m 个线性独立元素。 令，是g f ( q 8 ) 上任意元素。 定义2 5 y k ) ，o 七聊一i ：g g f ( q ”) 上钐_ 级鲞赢叫广 ，o 七埘一l 兹 称为经典( 多项式) 基底， 定义2 6g f ( q “、上豹元素8 豹孰迹定义麴下： m - i 驴( ) = 7 ( 2 6 ) i = o 迹函数有如下性质： 1 ) t r ( p + 力= f r ( ) + f r ( ，) ， 2 ) l r ( 历取到g f ( q ) 上的每一个值， 3 ) t r ( f 1 9 ) = t r 够) 9 = t r ( f 1 ) ， 4 ) f r ( 1 ) e m ( m o d q ) 定义2 两令域沁、幂i 、峨如果满是以下条传蚋互为共轭 f r 五) = 1 , i = k 七。 定义2 8 离散域w i c n c r - h o p f 等式是一个由包含，个未知变量 吩o = o 1 ，f 1 ) ，2 t - 1 个不全为0 的常系数墨o = 0 ，1 , - - - , 2 t - 2 ) ，r 个常数 b a i = 0 ，1 ，t - 1 ) 组成的t 个等式的系统，如下所示： 一1 0 一 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 屯f - 2 f - 3 以- t s 2 t 4 屯“ s , - 2羽= 6 f - 1 包一2 6 0 ( 2 7 ) 当q o = 0 ，1 ，t - 1 ) ，s a i - - o ，l ，2 t - 2 ) 和岛( f = o ，1 ，t - 1 ) 都属于g f ( q ) 时，上式被称为g f ( q ) 上t 次d t w h e 公式。 一1 l 一 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 第3 章非平衡有限域位并行乘法器 有限域乘法器高效的v l s i 应用对于各类密码系统非常重要。在这个方向 上，各种算法和相应的硬件结构在各类文献中被提出来。在已有的算法和结构 中，多项式基底相对于其他基底，如正规基底、共轭基底等应用更加广泛。 对于使用多项式基底的二元域位并行乘法器的硬件实现，基本上可以归纳 为两类方法： i 类：两个次数小于等于聊一1 的多项式相乘，然后进行模规约运算，依据次 数为历的不可约多项式厂( 力。 类：构造一个依赖于一个输入和不可约多项式的m 肌矩阵，然后由矩阵 和另一个输入相乘得到输出。 对于乘法c = a b ，其中彳，b a v ( 2 4 ) ，无论使用多项式基底还是移位多项 式基底，i 类和类方式计算得到的输出和输入都是用相同基底表示的。同时 存在的还有被称为m o n t g o m e r y 乘法的一种乘法方式，在这种方式中，当输入 为a 和占时，输出a b r r o o d f ( x ) ，这里r 表示一个精心挑选的域元素五的倒数， 这种形式的乘法被称为m o n t g o m e r yf r o m ( m f ) 。已有的大部分m f 算法都是 i 类的，仅有少数的m f 算法的类形式1 9 1 。 在这两类方法中，类方式适用于当不可约多项式确定或者是从一小组多 项式中选取的情况。在二元域e c c 算法中，各大机构纷纷制定了各自的标准和 相应的有限域生成多项式，如s e c l t 2 9 1 中，就推荐了他) = 一“十，+ 一+ 一+ j ， f b 西= f ”+ 一+ i ，f o o = f + ) 严+ l， f q i 、= t 螂+ x l 铺+ l ， f = p 2 + 叠2 + 叠+ f + l ，f = + + l tf = f 引+ 0 0 + f + + l 等七个 不可约三项式和五项式。这就为类方法的使用提供了极大的便利条件，在这 一章中，我们针对s e c i 中所推荐的有限域多项式设计了高性能乘法器结构， 为e c c 算法的商用提供了极大的便利。在设计中我们利用了这些多项式自身的 特点，提出了非平衡算法的概念，大大降低了乘法器的延时，而且整个乘法器 的输入输出均是用多项式基底表示的有限域元素，能嵌入到现有大部分密码系 统中，而无需额外的基底变换开销。在智能卡、嵌入式应用等领域，密码算法 的安全强度往往是和面积、功耗等现实条件相折中的产物，这样，选用固定的 有限域多项式是这些应用的一个必然实现形式。同时，为了降低空间开销，利 用有限的空间资源，存储器的容量受到了很大的限制，因此，能够直接利用输 入数据而无需转化的运算单元是非常合适的选择，输出也是如此。于是，一中 利用多项式基底，针对某一类特殊类型多项式的有限域乘法器应运而生。 一1 2 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 3 1 非平衡模规约算法介绍 模规约算法是模乘等运算的基础，提高模规约算法的速度是决定整个e c c 点乘运算的关键，也决定了e c c 算法核的整体性能。所以首先研究高效的模规 约算法以及由此延伸的模乘算法，并最终将这一算法应用到e c c 点乘操作中， 设计出高性能的e c c 算法核。 根据国际密码标准s e c ( s t a n d a r d sf o re f f i c i e n tc r y p t o g r a p h y ) ，e c c 中 g f ( 2 4 ) 域上的不可约多项式厂( 功= ，+ 丁o ) 的选取要求r ( 力的次数相对于m 尽量小。 一个次数大于或等于，( 曲次数m 的多项式c ( 力，可表达成如下的形式： c ( 茗) = g o ) ，+ c j ( 力 ( 3 1 ) 将c ( 力对- r ( 力取模，并推导得： c ( 功= c ；( j ) r ( j ) + q ( x ) m o d f ( x )( 3 2 ) 逐步使用( 3 2 ) ，直到q ( 曲= o 。算法的描述如下： 算法一二元域非平衡指数模规约算法 i n p u t ： c ( ，厂( 功 o u t p u t ： c ( 力m o d f ( 力 d o p a r t i t i o n c ( 力i n t og ( 力 a n dg w i t hd e g r e e m ： c ( z ) = g 【力x m + g ( 力 ) w h i l e ( g o ) r e t u r nc ( x ) 非平衡指数模规约算法的基本性能如下： 假设a 工) = ，+ 口。4 r 4 + + n 。，+ 口，4 工8 4 + ，r = ，+ + 1 ， 厂( 力= j ，+ r ( 力，则 c ( 力= g r ( 力+ q ( 曲m o d 厂( 力 = ( 工肿”+ a n 1 x “碍4 + ) ( ，+ + 1 ) + ( 口。i 矿。+ 一) m o d f ( x ) 一1 3 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 可以看到，最高项的次数从疗变为雄m + 七，即每次迭代，c o ) 最高项的次 数减少值卸= m - k ，因此，当c ( 工) 经过三次迭代后变为0 时，意味着： 上是满足以下( 3 3 ) 、( 3 4 ) 条件的整数： n 一三_ 肇m l( 3 3 ) n 一( l 1 ) 肇m - 1( 3 4 ) 即三是满足0 - m + o ( m k ) 三( 万一k ) ( m k ) 的整数。易证明，区间 【一m + 1 ) ( m j i ) ，一k ) ( m 一七) 】内只包含一个整数。 由于k 远小于m ，一般情况下仅需2 次迭代即可收敛，而以目前s e c 标准 中m 、k 最接近的厂( 工) = 工”+ 工“8 + 1 为例，也仅需3 次迭代。且每次迭代主要 为二元域的乘法运算，速度较高。 对非平衡指数模规约算法进行了进一步的测试，我们选取了b a r r e t t 模规 约算法【2 4 】和m o n t g o m e r y 模规约算法嘲作为比较对象，并遍历选取了s e c 标准 中所有的二元域不可约多项式作为测试基准，以非平衡指数模规约算法复杂度 为基准，结果如下： 表一非平衡模规约算法与其它模规约算法的性能比较 测试向量长度及测试域( 遍历了所有 b a r r e t t m o n t g o m e r y s e c 推f ( x ) )算法性能算法性能 3 1 61 6 3 长度n = 3 2 0 b i t sf 2 一域 b a = t 8 + t + t t + l 3 0 41 7 5 长度n = 4 4 8 b i t s f 2 一域 f ( x 、= # ”+ x 7 + l 长度n = 4 4 8 b i t sf z 一域 3 1 81 9 8 ，( 曲= 】9 + 工埘+ j 长度n = 4 4 8 b i t sf 2 m 域 1 7 21 0 7 b c 、= x 2 j 9 七t “七l 长度n = 5 4 4 b i t sf 2 一域 4 9 52 8 4 f q c 、= 铲”七t 2 + t + t l 1 4 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 长度n 2 8 0 0 b i t sf 2 一域 5 8 43 1 5 f = + f 7 + l 长度n 2 1 1 2 0 b i t s f 2 一域 1 0 6 45 7 1 f o o = # 矾+ x - 。+ f + + l 可见，非平衡指数模规约算法在进行二元域e c c 模规约算法时，通常情况 下，相对于m o n t g o m e r y 模规约算法，综合性能可改进2 0 5 0 倍，即使在极端情 况下( “x ) = x ”+ 一”+ j ) ，也可改进1 0 倍。相对于b a r r e t t 模规约算法，性 能可改进3 0 “1 0 0 倍，即使在极端情况下( f ( x 1 = x 一+ 一”+ j ) ，也可改进1 7 倍。 3 2 非平衡模乘算法 如上节所述，我们提出的非平衡模规约算法可以大大提高模规约算法的运 算速度，但是实际密码系统应用中，完整的模乘算法才是构成关键路径的一部 分，在这一节中，模规约算法被推广到了模乘算法上，具体算法如下所示： 算法二二元域非平衡指数模乘算法 i n p u t ： 彳( 功，曰( 力，o ) o u t p u t ： a ( x ) b ( x ) r o o d 嫡 c ) = 4 ( j ) 曰( 力： d o p a r t i t i o nc ( x ) i n t og ( 工) a n dg ( 工) w i t hd e g r e e m ： c ( 工) = c j ( 工) 石”+ g ( 力 w h i l e ( g 0 ) r e t u r nc ( 曲 我们可以用类似的方法来获得非平衡模平方算法。 同样的，选取s e c 标准中的二元域不可约多项式作为测试基准，将非平衡 模乘算法应用到二元域e c c 点乘算法中，同样以b a r r e t t 模乘算法和 m o n t g o m e r y 模乘算法作为比较对象，各类算法性能比较如下表所示： 一1 5 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 表二非平衡模乘算法与其他模乘算法的性能比较 测试向量长度及测试域 b a r r e t t m o n t g o m e r y ( 遍历了所有s e c 推荐f ( x ) )算法性能算法性能 长度n = 3 2 0 b i t sf 2 一域 1 9 21 4 5 ，( j f ) = 工1 甜+ ，+ ，+ ，+ j 1 9 2 1 4 1 长度n 2 4 4 8 b i t sf 2 一域 b i 、= x t m 七圣i + l 长度n 2 4 4 8 b i t sf j 一域 l 7 71 4 7 f 幻o = f 。+ f ”+ i 长度n 2 4 4 8 b i t sf 2 一域 1 7 31 4 4 f 幻0 = # ”+ 0 ”+ l 长度n 2 5 4 4 b i t sf 2 一域 1 8 61 4 7 b a = p 。+ 譬2 + t + t + l 长度n 2 8 0 0 b i t s f 2 一域 1 9 01 4 8 = 妒+ + l 长度n 5 1 1 2 0 b i t sf 2 一域 1 9 21 4 9 于0 0 = f + 0 0 + # + # + l 可见，二元域e c c 点乘算法在应用非平衡指数模规约算法时，通常情况下， 综合性能可改进1 4 5 倍左右( 相对于应用m o n t g o m e r y 模规约算法) ，1 9 倍左 右( 相对于应用b a r r e t t 模规约算法) 。 3 3 非平衡乘法器的实现与应用 观察算法二，我们可以发现非平衡算法的主要运算部件还是普通不带模规 约功能的二元域乘法器，如果纯粹用硬件电路实现算法二中的条件判断，会造 成控制逻辑开销过大，进而影响整个乘法器的面积和性能，所以我们直接结合 乘法器的最终应用场合，将非平衡指数模规约算法作为二元域e c c 点乘算法的 核心嵌入在高速的公钥密码加速器中，这样密码处理器的控制单元就能完成非 一1 6 一 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 平衡算法的判断转移功能。设计实现的公钥密码加速器结构如图l 所示。 图i 公钥密码加速器架构 一1 7 浙江大学硕士学位论文一高性能有限域乘法器的研究与实现 第4 章基于s p b 及其w d b 的并行乘法器 4 1 新型基底s p b 及其w d b 的介绍 为了更好地表示二元域上的各个元素，一种基于多项式基底的新型基底移 位多项式基底( s h i f t e dp o l y n o m i a lb a s i s ，s p b ) 被提出来。就像名称所表示的 那样，对于任意整数v ，有序组缸“1 0 i 删一1 ) 就是移位多项式基底。基于 s p b 的二元域乘法也和基于p b 的类似，分为i 类和类。这个方法在三项式 乘法领域获得了极大的成功，并很快被其他学者扩展到了其它几类多项式乘法 领域，这一章中我们的设计也是对基于s p b 乘法的推广。 4 1 1s p b 的概念 移位多项式基底( s h i f t e dp o l y n o m i a lb a s i s 。s p b ) ，最早由h f a n 在“f a s t b i t - p a r a l l e lg f ( 2 n ) m u l t i p l i e