（电路与系统专业论文）椭圆曲线密码算法及芯片实现方法研究.pdf

浙江大学博士学位论文摘要 摘要 椭圆曲线密码( e c c ) 是19 8 5 年提出的一种公钥密码算法。在保证 相同安全强度下，e c c 与另种公钥密码算法r s a 相比，所需的密钥 长度更短、存储信息更少、硬件实现效率更高。因此，具有广阔的应 用情景。在许多安全标准如i p s e c 、w a p i 中，都包含了e c c 的使用。 e c c 的研究主要包括安全和实现效率两方面。安全的问题在理论上 主要围绕离散对数问题、椭圆曲线参数的选取及攻击算法研究等，而 在工程上则涉及时间分析攻击、功耗分析攻击、电磁分析攻击和差错 分析攻击等。实现效率的问题主要是标量乘ko p 的计算问题( k 为一 个大整数而p 为椭圆曲线上的一个点) ，研究的领域包括椭圆曲线标量 乘算法研究、有限域运算研究、软硬件体系架构设计和硬件底层数据 通路优化等。 作为2 1 世纪前后热门研究领域之一，e c c 的研究取得了重多的成 果，理论上的安全问题已基本得到澄清，现有研究多是针对提高实现 效率和在工程上防止攻击等问题而展开。论文在简短回顾e c c 研究领 域的既有成果基础之上，主要针对特征为2 有限域e c c 的标量乘实现、 有限域乘法器和安全扫描链设计展开了研究，并给出了详实的数据， 也对e c c 相关技术作了探讨。在前人成果的基础上，主要做了以下的 工作并获得了一些成果： 1 提出了非平衡模归约算法。基于非平衡模归约算法，设计了一种 e c c 的可配置加速器。加速器采用类c p u 的流水线设计，使用有 限状态机产生指令以控制整个算法的流程；采用基于分段运算的域 可扩展设计的方法设计运算单元，支持多种不同有限域的运算。 2 提出了一种在特征为2 有限域上的并行快速实现e c c 标量乘运算 的方法。该方法利用硬件动态指令调度技术，同时采用指令级并行 和线程级并行，提高并行运算的性能。 浙江大学博士学位论文 摘要 3 提出一种针对一类椭圆曲线密码的硬件实现的攻击方法，并相应提 出一种防止该类攻击的简单有效的密码芯片的安全扫描方法，使得 在保持高测试覆盖率的同时，并不降低芯片的安全性。 4 提出一类有限域乘法器的归一化设计架构并进行复杂度分析。架构 可实现参数化的部分并行乘法器，分析结果为应用时的参数选取提 供参考。 关键词：椭圆曲线密码；标量乘：并行运算；有限域运算；指令集体 系结构 浙江大学博士学位论文a b s t r a c t a b s t r a c t e l l i p t i c c u r v ec r y p t o g r a p h y ( e c c ) i so n eo ft h e p u b l i ck e y c r y p t o g r a p h i e sp r o p o s e di n19 8 5 c o m p a r e dw i t hr s a ，i th a ss m a l l e rk e y l e n g t h ，l e s ss t o r ei n f o r m a t i o na n dm o r eh a r d w a r ei m p l e m e n t a t i o ne f f i c i e n c y ， w i t ht h es a m es e c u r i t yl e v e l t h u s ，i th a sb r i l l i a n tp r o s p e c ti na p p l i c a t i o n i n f a c t ， i th a sb e e na d o p t e db ym a n ys e c u r i t ys t a n d a r d s ，s u c ha sip s e ca n d w a p i ，e t e t h er e s e a r c ha b o u te c cm a i n l yi n c l u d e st w oa s p e c t s ：s e c u r i t ya n d i m p l e m e n t a t i o ne f f i c i e n c y r e s e a r c ho ns e c u r i t yi sd e v e l o p e dt h e o r e t i c a l l y w i t ht o p i c ss u c ha sd i s c r e t e l o g a r i t h mp r o b l e m ，p a r a m e t e rs e l e c t i o no f e l l i p t i c c u r v ea n da t t a c k a l g o r i t h m m e a n w h i l e ，i t i s d e v e l o p e d i n e n g i n e e r i n gw i t ht o p i c ss u c ha st i m i n ga n a l y s i sa t t a c k ，p o w e ra n a l y s i s a t t a c k ，e l e c t r o m a g n e t i s ma n a l y s i sa t t a c ka n df a u l ta n a l y s i sa t t a c k ，e t c r e s e a r c ho ni m p l e m e n t a t i o ne f f i c i e n c yi sm a i n l ya b o u tt h ec a l c u l a t i o n a b o u ts c a l a rm u l t i p l i c a t i o no f kop ，w h e r e a ski sab i gi n t e g e ra n dpi sa p o i n t o n e l l i p t i c c u r v e i ti n v o l v e st h er e s e a r c hf i e l d so fs 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 ，f i n i t ef i e l dc a l c u l a t i o n ，s o f t w a r ea n dh a r d w a r e s y s t e ms t r u c t u r ed e s i g na n d h a r d w a r ed a t a p a t ho p t i m i z a t i o n ，e t c a so n eo ft h eh o t t e s tr e s e a r c ha r e a si nt h e21s tc e n t u r y ，e c ch a s o b t a i n e dm a n ya c h i e v e m e n t s t h ep r o b l e mo ft h e o r e t i c a ls e c u r i t yh a sb e e n c l a r i f i e di ns u b s t a n c e n o wm o r er e s e a r c hi sa i m e da ti n c r e a s i n ge f f i c i e n c y a n dp r e v e x i s t i n g e n t i n ga t t a c k sl a u n c h e di ne n g i n e e r t h ep a p e rr e v i e w e db r i e f l yt h e a c h i e v e m e n t so n e c c ，t h e n ，t a r g e t e dr e s e a r c hm a i n l y a b o u t h a r d w a r ei m p l e m e n t a t i o no ft h es c a l a rm u l t i p l i c a t i o n ，f i n t ef i e l dm u l t i p l i e r a n ds e c u r es c a nc h a i n d e s i g n ，g i v i n g t h ed e t a i l e d r e l e v a n td a t a m e a n w h i l e ，t h eo t h e rr e l a t e d t e c h n i q u e s w e r ed i s c u s s e d t h em a i n a c h i e v e m e n t so ft h i sp a p e ra r el i s t e da sb e l o w ： 浙江大学博：b 学位论文 p r o p o s e da nu n b a l a n c e dm o d u l a rr e d u c t i o nm e t h o di nf i n i t ef i e l d b a s e d o nt h em e t h o d ，a ne c cc o n f i g u r a b l ea c c e l e r a t o rw a sa d v i s e d t h e a c c e l e r a t o ra d o p t e dp i p e l i n ed e s i g nl i k ec p u ，c o n t r o l l e do p e r a t i o nw i t h i n t e r ni n s t r u c t i o n sg e n e r a t e db yf i n i t es t a t em a c h i n e m e a n w h i l e ，af i e l d f l e x i b l em e t h o db a s e do ns u b s e c t i o no p e r a t i o nw a sa d o p t e d ，t h u s ，m a n y d i f f e r e n tf i e l d sw e r es u p p o r t e d ap a r a l l e lc o m p u t a t i o nm e t h o df o re c cs c a l a r m u l t i p l i c a t i o no v e r c h a r a c t e r i s t i c2f i n i t ef i e l d sw a sp r o p o s e d t h em e t h o dm a d eu s eo f h a r d w a r ed y n a m i ci n s t r u c t i o ns c h e d u l et e c h n i q u ew h i c ha p p l i e db o t h i n s t r u c t i o nl e v e lp a r a l l e l i s ma n dt h r e a dl e v e lp a r a l l e l i s mt oi m p r o v et h e p a r a l l e lc o m p u t a t i o np e r f o r m a n c e a na t t a c km e t h o dw a sp r e s e n t e di na l l u s i o nt oak i n do fh a r d w a r e i m p l e m e n t a t i o no fe l l i p t i cc u r v ec r y p t o g r a p h y t h e na ne a s ya n dv a l i d s e c u r es c a nm e t h o dw a sp r o p o s e da g a i n s tt h ea t t a c k i tm a i n t a i n e dh i g h t e s tf a u l tc o v e r a g ea n dw o u l dn o tc o m p r o m i s et h ec h i ps e c u r i t y an o r m a l i z e df i n i t ef i e l dm u l t i p l i e rw a sp r e s e n t e dw h i c hc a nr e a l i z e p a r t i a lp a r a l l e lm u l t i p l i c a t i o na c c o r d i n gt oac h o s e np a r a m e t e r t i m e c o m p l e x i t ya n ds p a c ec o m p l e x i t yw a sa n a l y z e d t h ea n a l y z e dr e s u l tc a n g u i d et h ed e s i g np a r a m e t e rs e l e c t i o n k e y w o r d ：e l l i p t i cc u r v ec r y p t o g r a p h y ；s c a l a rm u l t i p l i c a t i o n ；p a r a l l e l o p e r a t i o n ；f i n i t ec a l c u l a t i o n ；i n s t r u c t i o ns e ta r c h i t e c t u r e i v l 乙 王 t 浙江大学博士学位论文表格索弓 表格索引 表格1 1 ：r s a 和e c c 安全模长的比较3 表格1 2 ：r s a 和e c c 的实现速度比较3 表格1 3 ：不同坐标映射下的点加倍点的操作数6 表格2 1 ：自左自右扫描位标量乘算法2 0 表格2 2 ：n a f 扫描位标量乘算法2 l 表格2 3 ：窗口n a f 标量乘算法2 2 表格2 - 4 - m o n t g o m e r y 标量乘算法2 3 表格2 - 5 ：射影m o n t g o m e r y 标量乘算法2 3 表格2 - 6 ：固定基窗口标量乘算法2 4 表格2 7 ：固定基混合标量乘算法2 5 表格2 8 ：标量乘的运算代价估计( m = 1 6 3 ) 2 6 表格3 1 ：s e c 2 中推荐的各g f ( 2 肌) 的不可约多项式2 8 表格3 2 ：费马小定理求解模逆的数据存储3 2 表格3 3 ：非平衡模归约算法与其它模规约算法的性能比较3 4 表格3 - 4 ：非平衡模归约算法与其它模乘算法的性能比较3 4 表格3 5 ：加速器内部指令设计3 7 表格3 - 6 ：g f ( 2 1 9 3 ) 下的模乘运算实现步骤3 9 表格3 7 ：相关设计的速度性能比较4 1 表格3 8 ：各有限域下的标量乘运算时钟周期数4 2 表格3 9 ：素数域m o n t g o m e r y 模乘算法一4 4 表格3 1 0 ：修改后的素数域m o n t g o m e r y 模乘算法4 5 表格3 1 1 ：扫描位为1 时的数据调度5 2 浙江大学博士学位论文 表格索弓 表格3 12 ：相关设计的速度性能比较5 5 表格4 1 ：用一般方法得到的乘法器的复杂度5 9 表格4 2 ：k a l a t s u b a 乘法器的复杂度6 0 表格4 3 ：不同方法下得到的复杂度比较6 0 表格4 4 ：l2 8 位k a l a t s u b a 乘法器的理论与实际复杂度6 2 表格4 5t 典型三项式有限域乘法器复杂度比较一6 3 表格4 6 ：典型五项式有限域乘法器复杂度比较6 6 表格5 1 ：工作模式分配表7 7 表格6 1 ：参数化s c m 算法8 4 表格6 2 t6 4 位精度实现结果8 6 表格6 3 ：6 4 位精度归一化实现结果8 7 表格6 4 ：s h a 2 5 6 算法实现性能比较9 2 i x 浙江大学博士学位论文 图索弓 图索引 1 1 ：椭圆曲线密码系统的研究领域5 l 一2 ：硬件设计的三个维度8 3 一l ：基本网络通信模型2 7 3 2 ：标量乘实现的基本架构2 9 3 3 ：e c c 加速器系统架构一3 5 3 4 ：密码运算处理器流水线结构3 6 3 5 ：运算单元结构框图3 7 3 - 6 ：模乘运算的仿真波形( 部分) 4 1 3 7 ：相关设计的速度性能比较4 2 3 8 ：硬件动态指令调度5 0 3 - 9 ：标量乘运算系统架构图5 1 3 1 0 ：运算部件流水线5 l 3 1 l ：数据相关性分析5 3 3 12 ：求模运算的实现5 4 4 1 ：二元域多项式乘法实现的一般方法5 8 4 2 ：彳( x ) x m o d f 3 ( x )算实现电路一6 4 4 3 ：彳( x ) x m o d 石( x ) 运算实现电路6 4 4 4 ：彳( x ) 色m o d f 3 ( x ) 运算实现电路6 5 4 5 ：彳( x ) b ( x ) m o d 六( x ) 运算实现电路6 6 4 6 ：彳( x ) x m o d f s ( x ) 运算实现电路6 7 4 - 7 ：彳( x ) x 7m o d 石( x ) 运算实现电路6 8 4 - 8 ：彳( x ) 最m o df s ( x ) 运算实现电路6 8 4 - 9 ：彳( 工) b ( x ) m o d 六( x ) 运算实现电路6 9 4 1 0 ：g f ( 2 肼) 串行乘法运算单元7 0 5 1 ：扫描寄存器7 3 x 图图图图图图图图图图图图图图图图图图图图图图图图图 浙江大学博士学位论文 图索引 图5 2 ： 图5 3 ： 图5 4 ： 图5 5 ： 图6 1 ： 图6 2 ： 图6 3 ： 图6 4 ： 扫描链测试7 4 寄存器排除流程图7 6 安全扫描d f t 架构7 7 s c a nm a s k 产生电路7 8 利用混沌密码系统生成随机数7 9 锯齿混沌映射8 1 代价与分段数目关系图一8 6 s h a 2 5 6 主运算模块9 1 x l 第1 章绪论 1 绪论 1 1 椭圆曲线密码的研究背景和意义 19 7 6 年斯坦福大学的m e h e l l m a n 、w d i f f i e 和r m e r k l e 联合发 表了密码学的新方向一文，使密码学发生了一场变革【l 】。论文提 出了一种密钥交换协议，允许通信双方在不安全的媒体上交换信息， 安全地达成一致的密钥。在此新思想的基础上，很快出现了公钥密码。 公钥密码基于单向陷门函数。所谓单向陷门函数，指的是有一个秘 密陷门的一类特殊单向函数，它的一个方向易于计算而反方向却难于 计算。但是，如果知道那个秘密陷门，就很容易反方向计算这个函数。 在公钥密码当中，加密是容易的方向，任何人都可使用公钥来完成信 息加密；而解密是困难的方向，若不知道私钥( 即陷门) ，通常使用最 快的计算机用几百万年的时间都不能解开加密信息。 与传统的对称密码相比，公钥密码能解决两类对称密码所不能解决 的问题：1 ) 通信双方在不安全的媒体上可以安全地达成一致的会话密 钥，并进而用对称密码算法来实现信息的加密：2 ) 对信息发送人的身 份进行认证以及对信息的完整性进行检验。 自从d i f f i e 和h e l l m a n 提出公钥密码的观点之后，大量公钥密码被 陆续提了出来，如m e r k l e h e l l m a n 背包公钥密码【2 ，”、r s a 公钥密码【4 1 、 m c e l i e c e 公钥密码、e i g a m a l 公钥密码1 5 和椭圆曲线公钥密码( e c c ) 1 6 ，7 】等。所有这些公钥密码的安全性都是基于某个数学问题的难解性。 3 0 年来，许多曾经提出的公钥密码已经被攻破了，也有很多被证明是 不实用的。迄今为止，比较流行的和被人们认可的公钥密码主要有两 浙江大学博士学位论文：椭圆曲线密码算法及芯片实现方法研究 类：1 ) 基于大整数因子分解问题，其中最著名的代表是r s a 公钥密码； 2 ) 基于有限域上离散对数问题，其中主要包括e 1 g a m a l 公钥密码和影 响比较大的椭圆曲线公钥密码。 目前被广泛应用于实际系统的是r s a 公钥密码1 4 】。它在l9 7 7 年由 r r i v e s t ，a s h a m i r 和l a d l e m a n 三位教授提出( r s a 的取名就是来 自于三位发明者的姓的第一个字母) 。r s a 的安全性是基于数论中的一 个事实：将两个大的素数合成一个大数很容易，而相反过程则非常困 难。由此可见，r s a 的安全性依赖的是作为公钥的大数刀的位数长度。 根据摩尔定律，随着集成电路设计的集成度和复杂度的提高，处理 器的运算能力也日益增强，分解大整数的能力也随之不段提高，这对 r s a 公钥密码的安全带来了一定的威胁。与之相应的是，r s a 公钥密 码必须选择越来越长的模长( 即大数的位数) 。l0 2 4 位模长已经不足以 保证系统的安全性，2 0 4 8 位甚至更多位模长将成为必然的选择。增大 模长带来的后果是实现代价的提升：运算速度的限制及耗费的资源令 r s a 公钥密码越来越难以适应形势的发展。 相对r s a 公钥密码，e c c 有着突出的优势：第一，安全强度更高。 r s a 中存在着一般数域筛( n f s ) 方法 8 1 攻击使得其安全强度为亚指 数级，而即使使用目前国际上公认的有效攻击方法p o l l a d p 算法1 9 】， e c c 的安全强度仍然为指数级。第二，在同等安全强度下，e c c 的密 钥长度比r s a 短很多( 见表格1 1 ) l 加j ，这使得e c c 特别适合无线环 境以及存储资源有限的环境。第三，计算速度快。在现代分布式网络 中，由于服务器的瓶颈效应，使得快速的认证成为了一种迫切的需求。 比如一个w e b 服务器，如果认证速度太慢，将导致服务效率降低，并 影响用户访问热情。e c c 由于其最底层的有限域规模较小，以及相关 研究的深入，使得其计算速度大大高于r s a ( 见表格1 2 j ) 。 第l 章绪论 表格1 2 ：r s a 和e c c 的实现速度比较 在电子商务、电子政务、电子邮件和其他的各种应用当中，都有使 用密码技术来提供保密性、完整性、不可否认性和认证服务的可能。 使得这些普遍的安全服务成为可能的技术是公钥密码，将它组合在公 钥基础设施中，使得在大范围内进行这些服务成为可能。可见，公钥 密码的研究和使用将对解决现实生活中所遇到的安全问题起着极其重 要的作用。而鉴于e c c 所具有的上述优点，e c c 受到了国际上广泛的 关注。在不久的将来，e c c 极有可能取代r s a 成为应用当中的主流公 钥密码。 实际上，目前的形势已经逐步地证明了这一趋势。e c c 已被多个组 织所标准化，包括椭圆曲线数字签名标准e c d s a ( a n s ix 9 6 2 ) m 2 l ， 浙江大学博士学位论文：椭圆曲线密码算法及芯片实现方法研究 i e e epl3 6 3 ，i s o i e cc d l4 8 8 8 3 等。e c c 也被各种协议所使用，如 i p s e c l l 3 i k e f l4 1 、w a p i l l5 1 、w t l s t l 6 、s s h 、s s l 和s e t 等。而多种 安全产品也使用了e c c 加密技术，包括：v p n 网关、防火墙、安全网 关、安全路由器、w e b 服务器、基于e c c 的移动终端、s i m 卡数字 签名模块、无线p o s 机等。 1 2 椭圆曲线密码的研究现状 椭圆曲线密码最早于l9 8 5 年由k o b l i t z l 6 】和m i l l e r l 7 1 分别独立地提 出，它利用有限域上的椭圆曲线有限群代替基于离散对数问题密码体 制中的有限循环群，从而得出一类具有显著特点的公钥密码体制。历 经2 0 余年的发展，e c c 已经获得了广泛的关注和认可，已经从纯数学 理论的研究转向被各类标准所采纳的公钥密码算法。在过去的这些年， e c c 经受住了大量的密码分析和攻击，显示了强大的生命力。 本着让椭圆曲线密码走进实践应用的想法，国内外的研究者主要就 安全性和实现效率两个方面展开了研究。安全的问题在理论上主要围 绕离散对数问题、椭圆曲线参数的选取及攻击算法研究等，而在工程 上则涉及时间分析攻击、功耗分析攻击、电磁分析攻击和差错分析攻 击等。实现效率的问题主要是标量乘ko p 的计算问题( k 为一个大整 数而p 为椭圆曲线上的一个点) ，研究的领域包括椭圆曲线标量乘算法 研究、有限域运算研究、软硬件体系架构设计和硬件底层数据通路优 化等。研究内容按抽象程度的不同分层次如图1 1 表示。其最高层次 为协议和标准层，而最低层次则涉及基本的布尔逻辑运算。 4 第1 章绪论 效 塞 安全性 图1 - 1 ：椭圆曲线密码系统的研究领域 在算法协议和标准层次，包含了椭圆曲线参数的选取、椭圆曲线上 的点与字符串之间的相互转换，以及签名算法、密钥建立方案、加解 密方案等。要解决椭圆曲线的选取问题，首先要对椭圆曲线离散对数 问题有一个清晰的认识。在这方面作出较大贡献的有s h a n k s 的大步小 步算法【17 1 、p o h l i g h e l l m a n 演化类求解算法【18 1 、p o l l a d p 算法1 19 1 、i n d e x 算法【2 0 1 和x e d n i 算法【2 。其次还要研究有效计算椭圆曲线有理点个 数的算法，在这方面最初由s c h o o f 在19 8 5 年提出的计算椭圆曲线有 理点个数的算法1 22 1 ，l9 8 9 年到l9 9 2 年之间，a t i k i n 2 3 , 2 4 和e l k i e s l 2 5 l 对其作出了重大改进，而后又在c o u v e r g n e s ，m o r a i n 等人的完善下， 到19 9 5 年时人们己能够较容易地计算出满足密码要求的任意椭圆曲 线有理点的个数了f 2 6 1 。而与这个过程相伴的是一些攻击算法的提出， 其中值得关注的有m o v 约减攻击 2 7 1 、s m a r t a r a k i s a t o h s e m a e v 攻击 f 2 8 1 和w e i ld e s c e n t 攻击【2 9 1 等。这些研究结果从根本上影响了现实应 用中的协议和标准的曲线选择。比如，m o v 攻击使得超奇异椭圆曲线 被排除在应用之外。到目前为止，关于椭圆曲线的选取问题已不再是 5 浙江大学博上学位论文：椭圆曲线密码算法及芯片实现方法研究 椭圆曲线密码实用化的主要障碍了。实际上，正如前面所介绍的，各 类协议和标准已经相继出台。 在椭圆曲线运算层次，主要研究的是在点的运算层次上如何让椭圆 曲线的标量乘运算效率更高的算法。这当中比较著名的有n a f 位扫描 标量乘算法 3 0 , 3 1 】、窗口n a f 标量乘算法1 3 1 1 、m o n t g o m e r y 标量乘算法 3 2 , 3 3 l 、固定基窗口标量乘算法【3 4 1 和固定基混合标量乘算法1 3 5 】等。在这 些算法当中，对于不需要预计算( 即不需要额外的存储数据) 的要求 而言，射影m o n t g o m e r y 标量乘算法具有最快的运算速度，而其点加数 和倍点数是等同的这一特点，可以有效抵抗各类边信道攻击【5 4 】。 在有限域运算层次，利用不同有限域中的元素的表示方法及不同的 坐标系能改变运算的复杂度。有限域中元素的表示常基于两类基底， 分别被命名为多项式基底( p o ly n o m i a lb a sis ，p b ) ，正规基底( n o r m a l b a sis ，n b ) 引。多项式基底是现实应用中最为实用且最容易直观认识 的一种基底，它不需要基转换电路，单元的结构比较规整，易于扩展， 是使用得最多的一类基底；而以正规基底表示元素的一个优点就是元 素的平方运算仅相当于元素的一次循环移位。关于不同的坐标系统下 的换算，研究得比较多的是射影坐标，包括标准射影坐标、雅可比射 影坐标和射影坐标等，并有如表格l - 3 所示的结果，其中，代表模逆 操作，m 代表模乘操作。 表格1 3 ：不同坐标映射下的点加，倍点的操作数 对于标量乘运算影响较大的模乘和模逆等，也有大量的研究1 3 7 1 。 对于模乘运算，最早的二元域并行多项式基底乘法器由b a r t e e 和 6 第l 章绪论 s c h n e i d e r 提出。依赖不可约多项式，这一应用需要m 一m 个异或门。 由于如此高的电路复杂度和结构上的低规则性，使得早期并行结构的 乘法并不具有优势。后来，m a s t r o v i t o 提出了一种算法以及相应的结构 ( 后来被称为m a s t r o v i t o 算法乘法器) 用于多项式基乘法【38 1 。s u n a r 和k o c 提出了一种新的在三项式域上计算m a s t r o v i t o 算法的公式，整 个并行乘法器仅需要m 2 1 个异或门和m 2 个与门【3 9 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 多项式乘法器的方法【4 0 1 。这种方法既考虑了通常的情况， 又考虑了特殊形式不可约多项式的情况，如三项式、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 乘法器【4 1 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 t r o v i t o 方法不同的是，二元域乘法也可以由一个直接的多项 式乘法和一次模归约得到。这种方法常常在各种文献中被提及。如w u 在用不可约三项式作为域多项式时曾经提出了一个方法使得二元域乘 法能够通过( w 1 ) ( 朋一1 ) 位加法得到，这里w 代表不可约多项式的 h a m m i n g 重量【3 6 】。在硬件实现时，这个方法需要加2 个与门和 浙江大学博士学位论文：椭圆曲线密码算法及：占片实现方法研究 ( 肌一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 乘法器【4 2 1 ，并且计算得到了它的延时和 门数。虽然他们也将这种方法称为m a s t r o v i t o 乘法器，但是这一结构 已经和最初的m a s t r o v i t o 乘法器有一定区别，因为他们的方法需要两 个独立的步骤来完成乘法。 对于模逆运算，主要是基于欧几里德( e u c l i d e a n ) 算法和费马( f e r m a t ) 定理。而欧氏求逆算法经过改进又提出了新的算法，包括扩展欧氏求 逆算法( e x t e n d e de u c l i d e a na l g o r i t h m ，e e a ) ，二进制欧氏求逆算法 ( b i n a r y e u c l i d e a na l g o r i t h m ，b e a ) 和准求逆算法( a l m o s ti n v e r s e a l g o r i t h m ，a i a ) 1 4 3 】。 布尔逻辑运算层次将关注的目标指向椭圆曲线密码的硬件实现领 域( 图1 2 ) 。硬件实现主要指的是经由集成电路设计的手段，借助电子 设计自动化工具，将e c c 密码体制的全部运算或核心运算以专用集成 电路( a s i c ) 或现场可编程门阵列( f p g a ) 的形式实现。它是建立在上两 层的椭圆曲线运算和有限域运算的基础之上，着重对硬件的体系架构 进行研究，并对底层的运算单元进行优化以实现提高运算效率的目的。 对于硬件的体系架构，主要提出了加速器设计，协处理器设计和超标 量协处理器设计等。 图1 2 ：硬件设计的三个维度 第1 章绪论 关于公钥密码及e c c 的更多的研究进展情况，可参考文献 【4 4 ，4 5 ，4 6 ，4 7 ，4 8 ，4 9 】。 1 3 研究思路 基于椭圆曲线的密码系统的设计包含了很多的挑战，包括了多种要 素的权衡。 一方面，由于处理能力、功耗、面积、存储器容量等彼此互为依赖、 互为制约，如何在各种不同的应用场合当中就实现的效率和安全级别 ( 安全性) 之间取得恰当的平衡成为了一个重要的课题。不同的应用 将要求不同的设计方案，这样的一个课题涉及到了e c c 研究领域的各 个设计层次。从协议和标准，到椭圆曲线方程的选择，到点加、倍点 实现算法的考虑，到有限域算法的实现等等。 另一方面，密码芯片作为以推向市场为目标的产品，是以应用需求 为导向的，必须分析现实的环境来决定各类设计指标，必须考虑下列 各对矛盾。 1 ) 运算速度v s 安全性( 安全级别) 。通常，安全级别越高，运算速度越 慢。因此，产品的选择并非关注其中之一要素即可，而应两者综合 考虑。理想的设计应能支持各种安全级别，并给出相应的速度性能 比较以供选择参考。 2 ) 运算速度v s 芯片面积需求。芯片面积越大，运算单元( 其主要部件 通常是有限域乘法器) 可占据越多的资源，支持越宽的输入字长， 从而有利于运算速度的提高。但一方面，芯片面积的增加必须是在 可承爱的范围之内，另一方面，运算单元输入字长的增加也往往会 导致时延的增加，必须综合考虑。 3 ) 运算速度v s 灵活性。通常情况下，应用环境会时过境迁，其对安 全强度的需求并不总是一成不变，此时，若想使芯片能持续发挥作 9 浙江人学博士学位论文：椭圆曲线密码算法及芯片实现方法研究 用，必须能够支持各种安全级别的椭圆曲线；而为保证与本设备互 连以实现安全功能的对象的有效通信，进行正确的加解密运算，也 要求芯片能支持不同椭圆曲线参数，包括不可约多项式的选取等。 但灵活性总是要付出代价，就速度性能而言，支持特定椭圆曲线及 不可约多项式的密码芯片往往拥有快得多的速度性能。 4 ) 芯片开发速度v s 稍纵即逝的机会。应用情境的差异需要异彩纷呈 的各类芯片以突出不同的需求。加速器、协处理器、增强其它密码 算法的芯片产品等等都要求在尽可能短的时间内开发完成。 5 ) 芯片的测试v s 产品的安全性及成本。芯片推出到市场上必须经过 测试，与普通芯片的测试不同的是采用成本相对低廉的普通扫描链 设计会损坏密码芯片的安全性能。而使用内建自测试( b i s t ) 的d f t 设计方法则又会增加芯片的成本 鉴于以上1 ) 4 ) 点的考虑，论文力求提出一种架构，要求： 1 ) 架构具有极强的归纳性。一方面，从设计定位上，将其归类为加速 器，另一方面，它又要有协处理器的内涵，即拥有独特的指令集， 拥有指令发射，指令译码，指令执行等类c p u 的流水线设计。该目 标促生了由有限状态机生成内部指令，由运算单元完成指令执行的 加速器设计方法。 2 ) 在运算单元方面，具备灵活的选择可能。一方面，可以牺牲灵活性 而采用针对特定有限域和不可约多项式的有限域乘法器，以极大的 提升运算的性能。另一方面，也可以用不同字长的对称或非对称的 有限域乘法器来支持多种有限域和任意椭圆曲线参数的运算。在满 足灵活性需求的同时，可以调整字长来权衡速度与面积、速度与安 全级别的权衡。 基于上述两点思想，可进一步展开研究。一方面，在有限状态机生 成指令时，可由硬件来进行动态的指令调度，展开并行运算，以防止 数据停顿导致的性能损失，提高运算性能；另一方面，对于运算单元 1 0 第l 章绪论 中的关键部件有限域乘法器，也要进行深入的研究，分析时间和空间 的复杂度，以利于设计时的选择。 针对密码芯片的测试问题，将针对e c c 密码芯片提出一种经由扫描 链进行攻击的方法，实证扫描链设计所带来的危害。在能进行与普通 芯片同样的测试且不增加或略微增加芯片成本的前提下，开发保证芯 片安全的可测性设计方法。 1 4 论文结构安排 基于1 3 节的研究思路，论文的结构安排如下： 第1 章为绪论。首先介绍了椭圆曲线密码的产生背景及对信息安全 所产生的重要影响；其后对椭圆曲线密码领域的研究进展作了介绍； 最后站在e c c 密码芯片的开发角度阐述了考虑因素，并提出研究思路。 第2 章给出了论文研究的背景知识。首先给出了一般椭圆曲线的概 念和基本特性；然后给出特征为2 的有限域上椭圆曲线的基本理论； 最后对离散对数问题和基本的应用协议作了介绍，并着重分析比较了 标量乘运算的代表性算法。 第3 章以射影m o n t g o m e r y 标量乘算法为基础，设计了一种归纳性 极强的具有典型性的e c c 加速器结构。在设计加速器之前，先提出了 非平衡模归约算法，以提高运算的效率。随后，基于该算法，介绍一 种e c c 可配置加速器，着眼于应用的灵活性，可供速度、面积和安全 强度等选择权衡。最后，介绍了一种基于硬件动态指令调度技术的并 行快速e c c 加速器，通过采用指令级并行和线程级并行，提高并行运 算的性能。 第4 章着重讨论了实现标量乘运算时所采用的运算单元中对性能 有很大影响的有限域乘法器。将有限域乘法器分为两类，一类是先乘 法运算再求模运算，可针对任意的有限域和不可约多项式；另一类是 浙江大学博士学位论文：椭圆曲线密码算法及芯片实现方法研究 乘法运算和求模运算同步完成，仅支持特定的有限域和特定的不可约 多项式。对每一类乘法器作了复杂度分析，以有助于设计加速器时运 算部件的选择。 第5 章是关于密码芯片的安全测试。在介绍密码芯片的一般攻击方 法之后，针对芯片通常采用扫描链设计以实现其可测性的特点，提出 了一种根据扫描链信息攻击e c c 加速器芯片的方法，并进而提出一种 新的安全扫描方法。 第6 章对椭圆曲线密码应用协议中所涉及的相关技术作了一定的 补充。首先考虑了用混沌映射来生成随机数