（计算机应用技术专业论文）基于椭圆曲线的公钥密码系统的研究与实现.pdf

南开大学硕士学位论文2 0 0 3基于椭圆曲线的公钥密码系统的改计与实现 摘要 基于椭圆曲线的密码系统是目前主流的密码系统之一，并且被认为是经典的r s a 系统的 最佳替代者。密码系统的安全性、密码协议和关键算法的研究是密码系统实现中的关键问题， 本文就以上问题进行了研究，并实现了一个基于椭圆曲线的密码原型系统。 现代的公钥密码系统大多数是基于数学上的难题，这样的难题目前还没自找刽有效的算 法解决。例如：大整数分解问题、离散对数问题和椭圆曲线上的离散对数问题。特别是椭圆 曲线e 的离散对数问题还没有亚指数阶的算法，基于它的密码系统的安全性很高。 通过对e l 前研究现状的分析表明椭圆曲线密码系统的安全性是很高的。最有效的攻击方 法也必须面对指数阶的运算量，这在实际中是不奏效的。椭圆曲线密码系统已经成为众多国 际标准中规定使用的密码系统。本文给出了椭圆曲线密码系统实现的整体框架和类结构，并 定义了系统的接口和应用模式。椭圆曲线密码系统的系统参数的选取对系统的安全性和实现 效率都有着至关重要的影响，因此本文对系统参数的选取进行了研究，给出了有限域的选取、 曲线的选取和基点的选取方法。 在系统实现中，对系统实现效率影响最大的部分是系统使用的密码协议和底层关键算法。 本文对密码协议的使用和关键算法的实现进行了仔细的研究，并研究了优化系统实现的方法。 通过测试得到的实验数据显示我们实现的系统是相对高效的。 本文晟后对椭圆曲线密码系统的发展前景进行了一定的展望和预测，并对未来需要进一 步开展的工作进行了说明。 关键词：密码学加密解密椭圆曲线系统 椭圆曲线上的离散对数问题数字签名 信息安全有限域 南开大学硕i 。学位论文2 0 0 3幕于椭圆曲线的公钥密码系统的设计与实现 a b s t r a c t ： t h ec r y p t o s y s t e mb a s e do ne l l i p t i cc u r v ei so n eo ft h em a i ns t r e a mc r y p t o s y s t e m sa n di th a s b e e n r e g a r d e da st h eb e s tr e p l a c e ro f r s a - ac l a s s i c a lc r y p t o s y s t e m t h es e c u r i t yo f c r y p t o s y s t e m ， p r o t o c o la n dk e ya l g o r i t h mi st h em a i np r o b l e m i ni m p l e m e n t i n gac r y p t o s y s t e mt h e s ep r o b l e m s h a v eb e e nr e s e a r c h e di n m yt h e s i s ，a n d w eh a v ei m p l e m e n t e da p r o t o t y p e o fe l l i p t i cc h i v e c r y p t o s y s t e m i nm o d e mt i m e s ，p u b l i c k e yc r y p t o s y s t e m s a r eb a s e do nd i f f i c u l tm a t h e m a t i c a lp r o b l e m s t h e s ep r o b l e m sh a v en o tb e e ns o v l e de f f i c i e n t l y , s u c ha s i n t e g e rf a c t o r i z a t i o np r o b l e m ( i f p ) ， d i s c r e t el o g a r i t h mp r o b l e m ( d l p ) ，a n de l l i p t i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m ( e c d l p ) e s p e c i a l l yt h es u b e x p o n e n t i a la l g o r i t h mt h a tc a l ls o v l ee c d l p h a sn o tb e e nf o u n d y e t t h r o r i 曲t h ec a r e f u l r e s e a r c ha n da n a l y s i s ，w eh a v em a d eac o n c l u s i o nt h a te l l i p t i cc u r v e c r y p t o s y s t e mi ss e c u r e t h eb e s ta t t a c km e t h o di se x p o n e n t i a lo r d e ra n di n f e a s i b l e e l l i p t i cc u r v e c r y p o t o s y s t e mh a v eb e e ns e l e c t e db yl o t s o fi n t e r n a t i o n a ls t a n d a r db e c a u s eo fi t s s e c u r i t ya n d p e r f o r m a n c e w eh a v ed e s i g n e dt h em a i nf r a m e w o r ko fe c c a n dc l a s ss t r u c t u r ea n dh a v ed e f i n e d t h ei n t e r f a c eo f c r y p o s y s t e m a n d a p p l i c a t i o nm o d e t h es y s t e mp a r a m e t e r si sv e r yi m p o r t a n tf o rt h e s e c u r i t ya n dp e r f o r m a c eo fc r y p t o s y s t e m s oi nm yt h e s i s ，w eh a v er e s e a r c h e dh o w t os e l e c tt h e s y s t e mp a r a m e t e r s ，i n c l u d i n gt h es e l e c t i o no f f i n i t ef i e l d ，t h es e l e c t i o no fc u r v e sa n dt h es e l e c t i o no f b a s ep o i n t t h em o s ti m p o r t a n tt h i n g si st h es e l e c t i o no fp r o t o c o l sa n dl o wl e v e lk e ya l g o r i t h m si n i m p l e m e n t i n gc r y p t o s y s t e m w eh a v er e s e a r c h e d i t c a r e f u l l ya n dh a v ed o n e l o t so ft h i n g st o o p t i m i z et h es y s t e m i th a s b e e ns h o w ni no u rt e s td a t at h a to u r s y s t e mi sr e l a t i v eh i g hp e r f o r m a n c e i i lt h el a s tp a r to f m y t h e s i sig i v es o m ef o r e c a s ta b o u tt h ef u t u r er e s e a r c ha n dt e l ls o m et h i n g a b o u tt h ef u t u r ew o r k k e yw o r d ： c r y p t o l o g ye n c r y p t d e c r y p 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 ) e l l i p t i cc u r v e d i s c r e t el o g a r i t h mp r o b l e m ，( e c d l p ) d i g i t a ls i g n a t u r e i n f o r m a t i o ns e c u r i t yf i n i t ef i e l d l l 南开大学硕士学位论文2 0 0 3 基于椭圆曲线的公钥密码系统的设计与实现 1 、1 应用密码学简介 第一章绪论 密码学( c r y p t o l o g y ) 包括密码编码学( c r y p t o g r a p h y ) 和密码分析学( c r y p t a n a l y s i s ) 。密 码学是一个古老的学科，早在古罗马时期就已经出现了有关密码学的应用记载，当时凯撒 ( j u l i u sc a e s a r1 0 0 - 4 4b c ) 在军事和外交中使用了一种简单的替换密码( s u b s t i t u t i o n c i p h e r ) 来保证通信的保密。早期的传统密码学基本上都是对称密码( s y m m e t r i cc i p h e r ) ，即用来加秘 的密钥和解秘的密钥相同或者可以很容易地互相推出。在密码学早期的数千年的应用中，大 部分时间是被当政者控制用于军事行动，几乎看不到在民间的个人或者商业上的应用。 现代密码学是随着计算机的出现而发展起来的。1 9 7 6 年w h i t f i e l dd i f f i e 和m a r t i ne h e l l m a n 首次提出了公开密钥密码学( p u b l i c k e yc i p h e r ) 的概念 w e 7 6 1 ，同时r a l p hm e r k l e 也独立地提出了公钥密码学的概念 r 7 8 。值得一提的是，1 9 9 7 年英国政府宣称早在1 9 7 0 年 j a m e s h e l l i s 已经提出并由c l i f f o r d c c o c k s 实现了一个公钥密码系统，但英国政府对这些研 究成果进行了保密，当时并未公开。在1 9 7 8 年r o n a l dl r i v e s t ，a d is h a m i r 和l e o n a r da d l e m a n 设计出了第一个基于大整数分解问题( i n t e g e rf a c t o r i z a t i o np r o b l e m ，i f p ) 的公钥密码系统 一r s a 。随着现代密码学和计算机的发展，密码学的研究不但对政府和军方举足轻重而且在 民间个人和商业上的应用也日益重要。在军事、政府部门中，数据安全的重要性不言而喻， 一旦数据安全受到破坏，直接威胁到国家的安全，在保护数据的安全中，密码学扮演着很重 篮的们色，这方而的著名案例就是二次大战期f i j 图灵( a l a nt u r i n g ) 领导的蜒川研究, j , t l 【诎 解德国的e n i g m a 密码机，德方因此损失惨重。在商业上，随着互联网的发展，信息技术的 进步和各行各业的信息化，信息( 数据) 的价值越来越大，快速准确地获取信息是成功的关 键，但一旦自己的重要数据被非法地攫取，损失也是非常巨大的。个人方面，人们越来越重 视对自己隐私的保护。作为信息安全重要手段之一的密码学因此越来越受到关注。有关密码 学的更详细介绍和入门学习资料参见文献 m o v 9 6 s 9 6 1 。 1 、2 公钥密码学 密码学有两个主要研究方向：对称密码和公钥密码。对称密码的主要特点和优势是加解 密速度较快，密钥相对较短，算法实现相对简单，而其主要的问题在于密钥的分发管理困难， 而在网络时代，大用户量系统中这个问题表现得尤为严重，公钥密码在这方面有着先天的优 势，因此在实际应用的密码系统中往往是结合使用这两种密码体制。 对称密码又分为流密码( s t r e a mc i p h e r ) 和分组密码( b l o c kc i p h e r ) 。在计算机出现以前的 密码体制主要是流密码。与对称密码体制不同，公钥密码体制的加解密密钥互不相同，并且 在已知公钥( 加密密钥，可以公布出去，任人皆知) 的情况下推出私钥( 解密密钥，必须保 密，加密信息的安全全赖于此) 有实际上的不可操作性。现代主流的公钥加密系统均以数学 特别是数论方面的难题作为基础。1 7 t 前主流的公钥密码系统主要基于三种数学难题：1 f p ，离 南开大学硕士学位论文2 0 0 3基于椭网曲线的公钥密码系统的设计与实现 散对数问题( d i s c r e t el o g a r i t h mp r o b l e m ，d l p ) 和椭圆曲线上的离散对数问题( e l l i p t i cc u r v e d i s c r e t e l o g a r i t h mp r o b l e m ，e c d l p ) 。这些难题都有一个共同的特点，即函数的( 陷门) 单向 性，也就是说，函数的正向计算比较容易，但逆向计算如果没有相应的陷门信息就非常困难， 至少是在计算上有实际的不可操作性。如大整数分解问题，给定两个大整数求其积是很容易， 但到目前为止还未找到计算上可行的多项式时间复杂度的算法可将任意一个大整数分解为它 的若干因子。这些数学上多年悬而未决的难题是公开密钥加密系统的安全保证，基于这些难 题设计出的公开密钥加密体制的加密解密过程的计算相对容易，但不知道特定陷门信息( 例 如：解密密钥) 的破译者进行破译时，由于没有相应的解决这些难题的算法，使得破译具有 实际的不可操作性，从而保证了加密信息的安全。 整数分解算法和解决离散对数问题的算法在不断取得进展，目前的i n d e x c a l c u l u s 方法已 经达到亚指数阶( s u b e x p o n e n t i a la l g o r i t h m ) ，5 1 2 位( b i t ) 的r s a 算法在1 9 9 9 年己经被攻 破，并且随着计算机的运算速度不断提高，可以被分解的大整数和可以被解决的离散对数问 题的位数还会不断提高，从而要求密码系统中使用的密钥越来越长，然而密钥长度的增长势 必带来a n 解密计算的复杂性的提高，加密解密需要的计算能力的增加，存储和传输密钥需要 的资源的增加，这些问题将限制这样的加密系统的广泛应用，并且整数分解和离散对数问题 的数学背景相对狭窄，面对数论研究的进展，这些系统的安全性受到威胁。面对这些问题， 基于椭圆曲线的密码系统应运而生。 1 、3 椭圆曲线密码系统 椭圆曲线是代数几何的重要分支，对椭圆曲线进行的纯数学研究已经进行了很多年，并 且取得了丰硕的成果，例如：费玛( p i e r r ed ef e r m a t ) 大定理( f e r m a t s l a s tt h e o r e m ) 就是利 用椭圆曲线方法得到证明的，椭圆曲线也被应用在素数测试 a m 9 3 k 9 0 和整数分解中 l 8 7 。 椭圆曲线被应用到密码学中是v i c t o r m i l l e r 和n e a l k o b l i t z 在1 9 8 5 年提出的 n 8 7 v 8 6 ，随 着这种想法的提出，基于椭圆曲线的公钥密码系统越来越受到密码学者的注意，如今已经发 展成了公钥密码系统研究的最活跃的领域之一。 椭圆曲线公钥密码系统被广泛地研究是出于该系统在安全和性能上的优势。在安全性方 面，非特殊的椭圆曲线上的离散对数问题目前还没有找到亚指数阶解决算法，以公式 上。( v ，c ) = e x p ( c ( 1 0 9 p ) v ( 1 0 9 l o g p ) t v ) 衡量一个算法的计算复杂度，当v = l 时，算法是指数阶的， 当v = 0 时，算法是多项式阶的，当l v 0 时，是亚指数阶算法( 其中c 是一个常数，p 输入问 题的大小) 。目前解决非特殊的椭圆曲线上的离散对数问题( e c d l p ) 最好的p o l l a r dr h o 算法的 计算复杂度是工。( 1 ，c ) ，而解决离散对数( d l p ) 或整数分解问题( i f p ) 最好的数域筛算法( n u m b e r f i e l ds i e v ea l g o r i t h m ) 的计算复杂度是l 。( 1 3 ，c o ) ( 其中c 。= ( 6 4 9 ) ma 1 9 2 ) ，也就是酷解决 ( d l p ) 和( i f p ) 有亚指数阶算法，而解决( e c d l p ) 的算法目前还是指数阶的。公式 n = b n t + 3 ( 1 0 9 ( n l 0 9 2 ) ) 2 3 ( b = 2 c 。( 1 0 9 2 ) 2 3z 4 1 9 ) 反映了在相同安全级别下e c d l p ( n ) 公钥 南开大学硕士学位论文2 0 0 3基于椭圆曲线的公钥密码系统的设计与实现 系统和i f p 、d l p ( n ) 公钥系统的密钥长度关系 i g n 9 9 。下表给出各种不同算法在相同安全级 别下需要的密钥长度比较。 对称密对称密r s a 密 f ( p 忡 f ( 2 | l t ) 中 当f ( q m ) 中的q 是3 2 位时m 的位数 钥位数码算法钥位数 p 的位数 m 的位数 8 0s k j p j a c kj 0 2 4】9 2j 6 35 1 1 2 t r i p l e d e s 2 0 4 82 2 42 3 37 i2 8 1 2 8 b i t a e s3 0 7 22 5 62 8 3 i l 1 9 21 9 2 b i t a e s7 6 8 03 8 44 0 9 1 3 2 5 62 5 6 一b i t a e s1 5 3 6 05 1 25 7 11 9 表1 、不同算法在相i 司安全级别f 斋要的密钥长度比较 由表1 可以看出，同其它公钥算法相比，基于e c d l p 的密码系统可以使用相对较短的密 钥。短密钥使得密码系统实现中对处理单元的计算能力，需要的存储空间的大小，网上传输 公钥需要的带宽等资源的需求相对较小，从而由安全优势带来系统性能上的优势。 椭圆曲线密码体制有着广阔深邃的数学背景，一方面这种特点使人们对椭圆曲线系统的 安全性更有信心，对攻击者来说这种数学背景使得攻击首先必须站在一个较高的起点上并且 面对当今世上最困难的难题之一，从而使攻击之路更加艰难，另一方面，复杂的数学问题使 得密码设计实现人员也同样面临很大的挑战，设计实现者必须对整个系统原理有一定的了解， 从而降低软件实现中漏洞的可能性。避免人为地降低系统的安全性。 从更深层次上来说，e c d l p 比p 和d l p 问题更加广阔的数学背景，使得我们可以在很 多不同类型的有限域上建立曲线，在同一个有限域上可以有非常多的曲线可供选择建立密码 系统，这样一旦某种类型的有限域或者曲线被证明不适合用来建立密码系统我们还有很多其 它的选择，不像i f p 和d l p 问题，一旦数学上找到因式分解算法则整个密码体系彻底崩溃， 并且三次曲线在数学上是很难被完全掌握弄清的曲线，虽然经过多年的研究但是目前人们对 三次曲线的认识还很不充分。从这点上来说，椭圆曲线在安全性保障和发展前景上比其它系 统更有优势。下图给出r s a 和e c c 的安全比较。 其中纵屯标是密钥长度，横坐标是需要的破解时问。m i p sy e a r s 是指每秒运行一百万条 指令的计算机计算一年的计算量。带方形的曲线是r s a 的，三角的是e c c 的。 蔓堑茎兰堡兰兰竺堕二塑一 墨王塑堕些堡塑坌塑童旦墨竺堕堡生皇壅里 c o m p a r i s o no fs e c u r i t yl e v e l so t e c ca n d r s a & d s a t i m e t ob r e a kh e y i m i p s y e a r s l 图1 、r s a 和e c c 的安全性比较，该图取自 c e r t 0 0 下面给出有限域上椭圆曲线的定义。 定义1 ：在域f 上的椭圆曲线e 是满足w e i e r s t r a s s 等式的平滑曲线。 设f ( x ，y ) = y 2 + 口l x y + a 3 y x 3 一a 2 x2 一c 1 4 x 一1 2 6 ) f f ，( x ，y ) ，2 e ( f ) = ( y ) 1 f ( x ，y ) = 0 ) u o ) 。其中o 是人为定义的无穷远点，该点的定义是为了使 全部椭圆曲线上的点形成一个a b e l 群，o 就是群的幺元( i d e n t i t y e l e m e n t ) 。 平滑曲线的意思是在e ( f ) o 中没有点( x ，y ) 满足善= 婴：0 ，亦即曲线上没有奇异点 似 c y ( s i n g u l a r p o i n t ) ，或者说该曲线的三次方程没有重根。 上面对椭圆曲线的定义对任何域都适用，但在密码学中我们只对有限域上的椭圆曲线有 兴趣，例如：，( p ) 、，( 2 m ) 或，俨m ) ，其中p 是奇素数。在定义的曲线上用“弦切法” ( c h o r d a n d - t a n g e n t ) 定义点的加法，则曲线上点和其上点的加法构成一个a b e l 群，基于椭 圆曲线的公钥密码系统就是建立在这个有限群上的。 定义2 ：设k 是一个整数，pe e ( f ) 是曲线上的一个点，则点p 的标量乘( s c a l a r m u l t i p l i c a t i o n ) k p 被定义为k 个点p 相加。 定义3 ：已知p 和q 是椭圆曲线e ( f ) 上的点，q = ”( 其中k 是整数) ，椭圆曲 线上的离散对数问题( e c d l p ) 就是已知q 和p ，求k 。 南开大学硕士学位论文2 0 0 3 基于椭圆曲线的公钥密码系统的设计与实现 基于椭圆曲线的公钥密码系统就是以e c d l p 的难解性作为基础的。椭圆曲线密码系统入 门介绍见文献 s a m 9 8 l d 0 0 x l 9 9 。有关椭圆曲线的系统全面的介绍见m e n e z c s 的文献 m 9 3 ，有关公钥密码学和椭圆曲线系统的数学基础请参见文献 y 0 2 k 9 4 1 、4 研究现状 1 、4 、1 e c d l p 的攻击现状 当前对e c d l p 问题的研究是椭圆曲线系统研究中最重要也是最基础的。多年来众多的理 论数学家和密码学家对这个问题进行了广泛深入的研究 1 ) 穷举攻击 原始的穷举攻击最坏情况时间复杂度为o ( n ) ，改进的穷举攻击方法( b a b y - s t e p 厂_厂- g i a n t s t e p i ) 需要存储”个点和o ( ”) 的时间复杂度，穷举攻击在实际中并不有效。 2 ) p o h l i g h e l l m a n 攻击 p h 7 8 1 这种攻击依靠对点p 的阶( o r d e r ) n 的分解，将求解k 的问题转变为求解k 模每个 n 的因子的问题，之后k 可以通过中国剩余定理求解。当所求问题中的点p 的阶是平滑 的时候，这种攻击十分有效。 3 ) p o l l a r d 类攻击 p o l l a r d 在提出了一种随机的b a b y - s t e pg i a n t s t e p 算法( p o l l a r dr h o 算法 p 7 8 1 ) ，该算 法时间复杂度为o f 册2 ) ，但需要很少的存储空间。 w i e n e r 和z u c c h e r a t o 将该算法时间复杂度改进为o ( 4 , t o r t 2 ) w z 9 9 1 。p o l l a r d r h o 算法可以并行实现，线性提高运行速度，使用r 个处理器的运行时间大概是 o ( m 2 r ) o w 9 9 。p o l l a r d 提出的l a m b d a 算法在所求k 位于 o ，b ( b 2 ，因此硬件攻击在实际中并不奏效。 2 0 0 0 年4 月4 日，一个国际研究小组宣称解决了c e r t i c o m 的e c c 第1 级2 k 1 0 8 c h a l l e n g e c e r 0 0 ，但目前使用的密钥至少有1 6 0 位，因此这并不能对椭圆曲线系统构成威胁。 由目前的对e c d l p 攻击的研究情况看，椭圆曲线密码系统目前还是相当安全并有着很光 明广阔的发展前景。 1 、4 、2 系统实现方面的研究现状 目前关于椭圆曲线密码系统实现研究的文章很多，国内最近几年这类文章尤其之多，这 南开大学硕士学位论文2 0 0 3基于椭圆曲线的公钥密码系统的设计与实现 些文章大体集中在三个方面：椭圆曲线的选取或构造，底层算法研究，系统架构描述或者某 种应用描述。基本上国内在这方面的研究处于跟踪国外研究的水平。目前国外有关系统实现 方面的文章大多数都集中考虑系统的底层算法优化，例如文献： a m v 9 3 l d 9 8 ( w b v g v 9 6 【g p 9 7 】【k m h 0 1 】【a o i g l v 0 1 q a 都是介绍系统实现中的底层算法的优化实现。 在 b h l m 0 1 1 h l m 0 0 忡介绍了n i s t 推荐曲线的软件实现方法。关于曲线的选取和构造的文 献见 b b 0 0 s o o 】 f g h 0 0 】。 c e r t i c o m 拥有很多有关椭圆曲线密码算法的专利，并且该公司是目前世界上最优秀的提 供椭圆曲线密码产品的公司，有关该公司参见h t t p ：w w w c e r t i c o m c o r n 。加拿大f 1 1 w a t e r l o o 大学的应用密码学研究中心在椭圆曲线方面也做了大量的研究，该中心每年都会举行一个椭 圆曲线的会议( w o r k s h o p o ne l l i p ! i cc u r v ec r y p t o g r a p h y ) ，代表了研究椭圆曲线密码系统的最前沿， 参见h t t p ：l l w w w c a c r m a t h u w a t e r l o o c a 。 值得一提的是，w e id a i 的一个免费的c + 十类库，其中实现了众多的密码学算法，该类库 的一个主要问题是类库过大，造成一定的效率问题。参见： h t t p ：| | n p e s k i m o c o r r g - w e i d a i c r y p t l i b h t m l n 本文属于软件实现方面，与以往工作不同之处在于本文将系统阐述整个椭圆曲线密码系 统：系统框架设计一系统参数选择一密码协议选择与实现一底层算法实现一系统应用架构。 本文是现代密码学和计算机科学与应用技术结合的产物，旨在利用计算机辅助密码学走出神 秘圣坛。在系统实现细节部分将在遵从国际标准的前提下进行尽可能的优化与改进。 在硬件实现方面，在 w p s o u 中介绍了在p a l m o s 设备上实现椭圆曲线。在 w b p 0 0 q h 介 绍了在智能卡上实现椭圆曲线。在 o p o o 中介绍了一种可配置的椭圆曲线协处理器。一些文 章讲述了关于底层算法的硬件实现，例如：【b p 0 1 g b k p 0 1 。总的来说，目前椭圆曲线系统 在硬件方面的实现比较多，尤其是在资源受限的硬件设备中，这是因为椭圆曲线系统对计算 能力和存储能力要求较少的原因。 1 、4 、3 关于e c c 的国际标准 目前椭圆曲线密码体制已经成为各种信息安全标准的重要组成部分，例如i e e ep 1 3 6 3 和 p 1 3 6 3 a 中将椭圆曲线密码体制作为重点讨论内容之一。美国国家标准局授权的金融业标准委 员会( a n s i ) 也制订了相关的签名标准x 9 6 2 及密钥交换及传递标准x 9 6 3 。其它一些标准如： n i s t 的f i p s ( 1 8 6 2 ) 、i s o i e c1 5 9 4 6 ( 1 4 ) 、p k c s # 1 1 、p k c s # 1 3 等。其它一些面向信息安全 应用的标准中也都相继规定了使用e c c ，例如：x 5 0 9 、t l s 、i p s e c 、w a p w t l s 、s n 以蹦e 等。这些标准的制定标志着椭圆曲线已经成为继r s a 之后的新一代主流公钥密码系统。 1 、5 本文的组织结构 本文第二章将给出设计的椭圆曲线密码系统的整体架构，包括系统框架、类结构和接口 定义。在第三章将重点讨论椭圆曲线密码系统的参数选取与生成问题，介绍如何选取安全的 南开大学顶士学位论文2 0 0 3基于椭圆曲线的公钒密码系统的设计与实现 系统参数。在第四章将对系统中使用的密码协议、算法进行讨论，并给出系统的优化方案。 最后一章是本文的结论，在其中介绍了对未来工作的展望，提出了本文设计实现的原型系统 需要改进和进一步完善的方向，并对椭圆曲线密码系统的应用和前景进行展望。 1 、6 本章小结 本章是全文的绪论，主要工作是对椭圆曲线系统的研究现状进行研究，查找、收集、整 理、阅读大量相关文献，并对这些文献进行了分类和组织，使得工作可以在前人的基础上向 前展开，并对系统的安全性有一个理智的认识。在本章中引用了大量文献，对h 后工作有一 定指导帮助作用。为了论述完整，在c h a p t e r l 、l 、c h a p t e r1 、2 和c h a p t e r l 、3 小结对阅读本 文需要的基础知识进行了简要说明，其中给出了基础的和经典的参考文献。在c h a p t e r i 、5 给 出了本文的组织结构。 南开大学硕士学位论文2 0 0 3基于椭圆曲线的公钥密码系统的设计与实现 第二章系统整体架构 2 、1 系统的整体框架 本文实现的系统将提供现代密码学中最基本的四种功能服务：保密性( c o n f i d e n t i a l i t y ) 、 身份验证( a u t h e n t i c a t i o n ) 、数据完整性( i n t e g n t y ) 和不可否认性( n o n r e p u d i a t i o n ) 。系统将 通过三个密码协议提供最基本的四种密码服务。所有高级的密码协议和服务都将建立在这四 个基本服务基础之上。这三个协议分别是： 11 密钥协商( k e ye s t a b l i s h m e n t ) 使用密钥协商协议可以使用户通过不安全的信道安全地建立共同拥有的密钥，用户之后 的通信就可以使用共同的密钥保护通信内容。在本系统中将提供e cd h 和e cm q v 两个密 钥协商协议。e cd h 协议是著名的d i f f i e h e l l m a n 算法 d h 7 6 ：l i j 椭圆曲线上的平移，该协议 不能抵抗中间人攻击( m a ni nm i d d l ea t t a c k ) ，但协议比较简单高效。我们同时提供一个可以 抵抗中间人攻击但是相对复杂的协议e c _ m q v ，向用户提供安全与高效的选择。 2 1 保密传输( e n c r y p t i o n ) 保密传输可以使用户通过不安全的信道安全地传输敏感数据。因为公钥密码较对称密码 的效率低、安全性差，因此实际应用中很少用公钥密码直接加密数据，一般是使用一种叫做 混合( h y b r i d ) 密码的方法，使用公钥密码加密对称密码的会话密钥( s e s s i o nk e y ) ，而使用 对称密码加密用户数据，这样既可以发挥公钥密码的密钥分发优势又可以得到对称密码的高 效安全。本文使用混合加密方法，公钥加密使用e c e i g a m a l 协议，该协议是e i g a m a l e 8 5 】 协议到椭圆曲线上的平移。 3 ) 数字签名( d i g i t a ls i g n a t u r e ) 数字签名可以向用户提供的服务有：身份验证、数据完整性、不可否认性。e c d s a 已 经成为众多国际标准中的签名协议，例如：i s o1 4 8 8 8 - 3 、i e e ep 1 3 6 3 、a n s ix 9 6 2 和f i p s 1 8 6 2 。e cd s a 是离散对数域的数字签名协议d s a n i s t 9 4 至t 椭圆曲线的平移。为与国际标 准兼容，本系统将使用e cd s a 协议。 下图给出系统整体结构： 南开大学硕 学位论文2 0 0 3基于椭圆曲线的公钥密码系统的设计与实现 上层应用程序或高层密码协议系统 例如：电子商务、电子政务应用程序、保密通信程序、数据安全应用程序等。 随机数 生成服务 系统参数 生成服务 其它辅助 功能服务 提 供 密 码 服 务 的 密 码 系 统 整个公钥系统向上层提供服务的接口 密码协议层服务 曲线上点的基本运算服务 大整数运算服务 对称密钥 密码服务 数据散列 算法服务 2 、2 系统的整体类结构 图2 、椭圆曲线密码系统整体结构图 下面给出系统实现中的主要类结构： 大整数类： c l a s sb i g i n t e g e r p u b l i c ： b i g i n t e g e r o ； ，一族构造函数 向外提供用于大整数计算和操纵的函数族 ，用于格式转换输入输出的辅助函数族 p r i v a t e ： 用于类内部的辅助函数 u n s i g n e di n t u f ：用于存储大整数数据的存储区 b o o ls i g n ；存储大整数的符号 i n ts i z e ；：i 每储大整数的位数长度 ) 椭圆曲线上点的类： c l a s se c p p o i n t o 南开大学硕十学位论文2 0 0 3 基于椭圆曲线的公钥密码系统的设计与实现 p u b l i c e c p p o i n t 0 ； 一族构造函数 向外提供用于曲线上点计算和操纵的函数族 ，用于格式转换输入输出的辅助函数族 p r i v a t e ： 用于类内部的辅助函数 s t r u c tp o i n 点的横纵坐标，两个坐标都是零表示无穷远点 b i g i n t e g e rx ，y ； ) ) 椭圆曲线系统参数类： c l a s se c p p a r a m e t e r p u b l i c ： e c p p a r a m e t e r 0 ； 一族构造函数 用于参数生成和验证的一族函数 ，参数的输入输出函数 p r i v a t e ： 用于类内部的辅助函数 b i g i n t e g e ra ，b ； b i g h n e g e rn ：曲线的阶 e c p p o i n tg ；i = | 扫线的基点 b i g i n t e g e rp ；，有限域的大素数 i n th ；协因子 i n tf r ：暂时未用，有限域元素的表示方法 南开大学硕士学位论文2 0 0 3 基于椭圆曲线的公钥密码系统的设计与实现 u n s i g n e df l e l d s i z e ； 密钥类：( 抽象类) c l a s sk e y p u b l i c ： k e “) ) 一族构造函数 有关密钥的共同操作 p r o t e c t e d ： 密钥拥有的相同数据 e c p p a r a m e t e re c p a r a ；系统参数 ) ； 公钥类： c l a s sp u b l i c k e y ：p u b l i c k e y p u b l i c ： 有关公钥的操纵函数 p r i v a t e ： e c p p o i n t p u b k e y ；公钥点 ) 私钥类： c l a s ss e c r e t k e y ：p u b l i ck e y p u b l i c ： 有关私钥的操纵函数 p r i v a t e ： b i g i n t e g e rs e c k e y ；h 公钥点 ) 南开大学硕士学位论文2 0 0 3 基于椭圆曲线的公钥密码系统的设计与实现 密钥生成器 c l a s sk e y g e n e r a t o r p u b l i c ： k e y g e n e r a t o r ( ) 一族构造函数 有关密钥生成提取的函数 p r i v a t e ： p u b l i c k e yp u b k e y ； s e c r e t k e ys e c k e y ； e c p p a r a m e t e r e c p a r a ； ) ； 注：完整的类定义参见本文附录。 2 、3 系统的接口定义 本系统使用c + + 语言开发，可以利用组件技术向不同用户提供不同层次的服务。本文中 接口为示意性定义，旨在更清楚说明问题，可能与实际接口定义不相一致。系统接口主要由 以下几个部分组成： 系统服务接口 这是本系统最上层的接口，向上层应用提供对数据的d h i 解密，签名验证等高层接口服务 i n t e r f a c ei c r y p t o d a t a e n c r y p t d a t a ( i n d a t ai n d a t a ， i n p u b l i c k e y , o u t d a t ao u t d a t a ) ：数据加密 d e c r y p t d a t a ( i n d a t ai n d a t a ， i n s e c r e t k e y , o u t l d a t ao u t d a t a ) ；数据解密 v e r i f y d a t a ( i n d a t ai n d a t a ， i n p u b l i c k e y , o u t d a t ao u t d a t a ) ；数据验证 s i g n d a t a ( 【i n d a t ai n d a t a ， i n s e c r e t k e y , o u t d a t ao u t d a t a ) ；数据签名 ) 密码协议接口 向系统服务接口提供密码协议服务支持。 i n t e r f a c ei e c p r o t o c o l 南开大学硕上学位论文2 0 0 3基于椭圆曲线的公钔密码系统的世计与实现 e c d h ( i n p u b l i c k e yp k _ o f _ b ， i n s e c r e t k e ys k _ o c a ， o u t e c p p o i n t ) ；e c d h 协议 e c m q v ( i n p u b l i c k e yp k _ o f _ a ， i n s e c r e t k e ys k _ o f - a ， i n p u b l i c k e y t p k o f a ， i n s e c r e t k e yt s k _ o f - a ， i n p u b l i e k e y p ko fs ， i n p u b l i c k e y t p k o f b ， o u t e c p p o i n t ) ；m cm q v 协议 e ce i g a r n a l e n c r y p t ( i n p u b l i c k e y , i n d a t ai n d a t a ， i n s y m m e t r i c c i p h e r , o u t d a t a o u t d a t a ) ；e ce i g a m a l 协议加密 e c e i g a m a ld e c r y p t ( i n s e c r e t k e y , i n d a t ai n d a t a ， i n s y m m e t r i c c i p h e