西南交通大学硕士学位论文椭圆曲线密码体制的研究及DSP实现姓名：赖晖申请学位级别：硕士专业：密码学指导教师：唐小虎20070301西南交通大学硕士研究生学位论文第1 页摘要在二十一世纪，数字通信已经成为人们生活中的重要组成部分然 而，在信息的价值不断提升的同时，信息的安全性也遭受着日益严重的 威胁因此，在信息社会中，人们强烈要求有一种技术用于保护信息以 及信息系统，公钥密码势必将扮演越来越重要的角色 M i l l e r 和K o b l i t z 在上个世纪8 0 年代提出了椭圆曲线密码体制 ( E C C ) E C C 作为一种新的公钥密码体制，因为有着比其他公钥体制 无法替代的优点( 更高的安全性、更高的实现效率、更省的实现代价1 ， 所以从提出后到现在近二十年的时间里，得到世界各地数学家和密码学 家的密切关注和快速发展，并被广泛的应用于实践中 本文围绕着椭圆曲线密码体制展开讨论和研究，回顾了椭圆曲线的 发展历史和应用实现，介绍了椭圆曲线密码系统基础理论然后较全面 的分析了实现椭圆曲线快速点乘算法的几个因素，提出了一种快速不定 点乘算法经过分析，证明了该算法是一个高效可行的快速点乘算法， 并且需要更少的存储空间。
最后给出了在D S P 芯片上建立和实现椭圆曲 线密码体制的全过程，同时结合T I 公司T M S 3 2 0 C 6 4 x 系列芯片的特点 对程序进行了迸一步的优化，形成了一个基于有限素域的椭圆曲线加密 算法的底层算法函数库，并评估了实现效率经过对比分析，本文的域 运算具有更高效的实现效率关键字：椭圆曲线；有限素域：点乘；D S P西南交通大学硕士研究生学位论文第1I 页A b s 仃a c tI n2 1 s tc e n t u r y , d i g ：i t a lc o m m u n i c a t i o nh a sb e c o m eo n ei m p o r t a n tp a r to fO U rl i v e s ．W i t ht h er i s eo fi n f o r m a t i o nv a l u e ．t h ei n f o r m a t i o ns e c u r i t yf a c e si n c r e a s i n g l ys e r i o u sm e n a c e s ．C o n s e q u e n t l y , t h e r em u s tb es o m e e 伍c i e n tt e c h n o l o g yt op r o t e c tt h es e c u n t yo fi n f o r m a t i o n , a n dp u b l i ck e yc r y p t o g r a p h yw i l lp l a yam o r ea n dm o r ei m p o r t a n tr o l e ．M i l l e ra n dK o b l i t zp r o p o s e dE l l 诂t i ca , ．1 r v ec r y p t o s y s t e m ( E C C ) i n1 9 8 0 s ．A san e wp u b l i ck e Ys y s t e m ．E C Ci sb e t t e rt h a no t h e rp u b l i ck e ya l g o r i t h mi nt e r m so fs a f e t y , t i m ea n dc o s t ．功ⅡSi nt h el a s t2 0y e a r s ji td e v e l o p l e df a s t ．a t t r a c t e da r e n t i o nf r o mm a t h e m a t i c i a n sa n dc r y p t o g r a p h i s t s o f t h ew o r l d ．a n db e e nw i d e l yu s e di nt h es o c i e t y ．T h i sP a o e ri sm a i n l ya b o u tE C Cs y s t e m ．F i r s t l y , t h eh i s t o r yo f E C Ca n di t sa p p l i c a t i 0 1 1i m p l e m e n t si Sr e v i e w e d ．a n dt h eb a s i ct h e o r yo fE C Ci si n t r o d u c e d ．T h c a ，t h ek e yf a c t o r sf o rr e a l i z a t i o no ff a s tp o i n tm u k i p l i c a t i o no ne l l i p t i cc u r v ea r ea n a l y z e di nd e t a i la n dan e wf a s tp o i n tm u l t i p l i c a t i o ni sp r o p o s e d ．A f t e ra n a l y s i s ．i ts h o w st h a tt h en e wa l g o r i t h mi Sh i g he 艏c i e n t ．f e a s i b l e ．a n dn e e dl e s ss t o r a g em e m o r y ．L a s t l y , 也ew h o l er e a l i z i n gp r o c e s so fE C Cs y s t e m0 1 1D S P si Sg i v e ni nt h eP a p e r ’m e a n w h i l e ，c o m b i n i n gw i m t h ec h a r a c t e r i s t i c so fT M $ 3 2 0 C 6 4 xc h i p s ．t h ep r o g r a mi sd e e p l yo p t i m i z e d ． A sar e s u l t ，ab a s i cf u n c t i o n sl i b r a r yo fE C Cb a s e do nf i n i t ep r i m en u m b e rf i e l di Sf o r m e da n di t se f f i c i e n c yi Se v a l u a t e d ．B yc o n t r a s t i n g ．t h ee 茁c i e n c yo ff i e l do p e r a t i o n si n 血i sP a p e ri sf a s t e rt h a nO t l l e r s ．K e yw o r d s ：e l l i p t i cc u r v e ；f i n i t ep r i m en u m b e rf i e l d ；p o i n tm u l t i p l i c a t i o n ； D S P西南交通大学硕士研究生学位论文第1 页第1 章绪论1 9 7 6 年D i f f i e 和H e l l m a n t ’饶出公钥密码思想以来，国际上提出了 许多种公钥密码体制的的实现方案。
一些已经被攻破，一些被证明是不 可行的目前，只有3 类公钥密码体制被认为是安全有效的，按照其所依据的数学难题划分为： 1 ．基于大整数分解问题( I F P ) ，典型例子是著名的R S A 体$ I j t - , J 和 R a b i n 体制嘲 2 ．基于有限域离散对数问题( D L P ) ，典型例子是D i f f i e —H e l l m a n体制和E I G a m a l 体制【4 】、S c h n o r r 体制 3 ．基于椭圆曲线离散对数问题( E c D L P ) ，典型例子是椭圆密码体制 椭圆曲线密码体制最早是由N e i lK o b l i t z 睛】和V i c t o rM i l l e r 【6 J 两位学 者分别于1 9 8 5 年首先提出，即将椭圆曲线离散对数问题来代替一般有 限域的离散对数问题大多数的椭圆曲线密码系统是在模P 或F 此密码系统仍是存有与R S A 或E 1 G a m a l 相同的常见弱点( 例如：同 模数攻击、低指数攻击1 R S A 与E I G a m a l 系统中需要使用长度为1 0 2 4 位的模数，才能达到足够的安全等级，而E C C 只需使用长度为1 6 0 位的模数即可，且传送密文或签名所需频宽( b a n d w i d t h ) 较少，并已正式列 入I E E E1 3 6 3 标准【7 1 。
本文将围绕着椭圆曲线密码体制展开讨论，介绍椭圆曲线的研究背 景与应用现状，椭圆曲线密码系统的基础理论，根据椭圆曲线密码体制 己有的点乘算法，分析实现椭圆曲线快速点乘算法的几个要素，给出了 在D S P 芯片上建立和实现椭圆曲线密码体制的全过程同时结合T I 公 司T M S 3 2 0 C 6 4 x 系列芯片的特点对程序进行了进一步的优化，形成了一 个基于有限素域的椭圆曲线加密算法的底层算法函数库，并评估了实现 效率最后展望了椭圆曲线密码体制的进一步研究的方向 本章简要叙述群椭圆曲线的研究背景与应用环境，介绍本文的组织 结构和研究成果，并给出文中使用的数学符号1 ．1 椭圆曲线的研究背景与现状在本节中，我们将首先来回顾一下椭圆曲线密码体制、目前的应用 现状和研究椭圆曲线密码的意义1 ．1 ．1 椭圆曲线密码的优点椭圆曲线密码体制与目前广泛应用的R S A 、D S A 相比，具有以下优点： 1 ．安全性能更高加密算法的安全性能一般通过该算法的抗攻击强度西南交通大学硕士研究生学位论文第2 页来反映E C C 体制和其他几种公钥系统相比，其抗攻击性具有绝对的 优势它所依赖的椭圆曲线离散对数问题至今没有亚指数时间的求解方 法。
下表1 ．1 [ 6 】是在同等安全条件下对不同体制所需密钥长度的比较， 可见，E C C 的安全性远远优于R S A 和D S A ，且在同等安全条件下，安 全要求越高，其“短密钥”的优势越明显目前，1 6 0 b i t 的密钥长度便 足以保证E C C 的安全性 表1 - 1E C C 和R S A ／D S A 在相同安全条件下所需的密钥长度( 单位为b i t ) M I P SR S A ，D S AE C C 密R S A 和E C C 年数密钥长度钥长度密钥长度比1 0 45 1 21 0 65 ：11 0 87 6 81 3 26 ：l1 0 1 11 0 2 41 6 07 ：11 0 2 02 0 4 82 1 0l O ：l1 0 7 82 1 0 0 06 0 03 5 ：l2 ．计算量小，处理速度快虽然在R S A 中可以通过选取较小公钥的方 法提高公钥处理速度( 即提高加密和签名验证的速度) ，使其在加密和 签名验证速度上与E C C 有可比性，但在私钥的处理速度上( 即解密和 签名) ，E C C 比R S A 、D S A 快的多 3 ．存储空间占用小。
E C C 的密钥长度和系统参数与R S A 、D S A 相比 要小得多，意味着它所需要的存储空间要小的多这对于加密算法在l C 卡上的应用具有特别重要的意义 4 ．带宽要求低当对长消息进行加解密时，三类密码系统有相同的带 宽要求，但应用于短消息时E C C。