（计算机软件与理论专业论文）椭圆曲线密码系统研究与eccsp的构建.pdf

东北大学硕士学位论文 摘要 椭圆曲线密码系统研究与e c c s p 的构建 摘要 1 9 7 6 年d i f f i e 和h e l l m a n 提山了公钥密码的概念，信息安全产业由于这一概念的引 入得到了迅猛的发展。目前应用最广泛的公钥密码是基于大整数分解问题的r s a 算法 和基于离散对数问题的e i g a m l 算法，椭圆曲线密码系统由k o b l i t z 和m i l l e r 在1 9 8 5 年独立提出，经过十多年的安全性论证，于本世纪初开始步入应用领域。随着人们对公 钥密码系统分析的深入和计算能力的提升，大整数的难分解性和离散对数的难解性都受 到了威胁，这就迫使以它们为基础的密码系统使用更长的密钥，而与此同时，椭圆曲线 离散对数问题的求解却几乎毫无进展。因此在相同的安全级别下，椭圆曲线密码系统可 以使用更短的密钥，这就意味着史快的运算速度和更小的窀间消耗，这也使其特别适用 于传输带宽或计算能力受限的环境，例如无线网络、智能卡等。 本文以椭圆曲线密码系统的实现算法和协议为研究重点。椭圆曲线可以定义于各种 域上，但只有定义于二元域和大素数域上的适用于计算机密码学，因此文中对这两种域 上的基本运算算法作了细致的探讨，同时给出实现椭圆曲线点加、点乘的典型算法。文 中解决了二元域上的明文嵌入问题，将明文嵌入算法应用到椭圆曲线点的变换上，节省 了大约一半的存储空间和传输带宽。椭圆曲线可以应用在各种基于离散对数问题的安全 协议中，文中对此作了分析，并将e c e l g a m a l 加密协议加以改造，提出了r a m b o 会话 密钥交换协议，新的协议简化了通信双方交换会话密钥的过程。文中对实现椭剧曲线密 码系统各功能模块的典型算法均作了性能分析，给出实验数据，并以之为参考，选出效 率最高的算法，开发了二元域上的椭圆曲线密码函数库。在此基础上，按照w m d o w sc s p 的框架，将此系统和对称加密、哈希功能集成，构建了一个基础密码函数库，称为 “e c - c s p ”。测试数据表明，“e c - c s p ”主要功能函数的速度要优于w i n d o w s 白带的两 种主流c s p ( r s a 和d s s ) ，且运行稳定，可以支持上层应用程序的调用。 关键词：椭圆曲线密码系统：二元域；明文嵌入；r a m b o 会话密钥交换协议：e c c s p i i r e s e a r c ho fe l l i p t i cc u r v ec r y p t o s y s t e m sa n d t h ec o n s t r u c t i o no fe c c s p a b s t r a c t d i 伍ea n dh e l l m a np r o p o s e dt h ei d e ao fp u b l i ck e yc r y p t o s y s t a m s m1 9 7 6 f b rt h e a d o p t i o no fw h i c ht h ei n f o r m a t i o ns e c u r i t yi n d u s t r yg o tt r e m e n d o u sd e v e l o p m e n t st h cm o s t p o p u l a rp u b l i ck e yc r y t o s y s t e m sa r er s a a l g o r i t h mb a s e do nt h ed i f f i c u l t yt of a c t o r i z eb i g i n t e g e r sa n de 1 1 3 a n l a la l g o r i t h mb a s e do l lt h ed i f f i c u l t yt oe x t r a c td i s c r e t e1 0 9 a r i t h i n s e l l i p t i c c n l w ec r y p t o s y s t e m sw e r ep r o p o s e db yk o b l i t za n dm u l e ri d1 9 8 5 a n da f t e rt h es e c u r i b a r g u m e n t a t i o n so f d o l et h a nt e ny e a r s ，i ts t a r t e ds t e p p i n gi n t oi n d u s t r i a la p p l i c a t i o n sa tt h e b e g a l no ft h i sc e n t u r ya st 1 1 ed e v e l o p m e n t so f r e s e a r c ho np u b l i ck e yc r y p t o s y s t e m sa n dt h e i m p r o v e m e n t so fc o m p u t a t i o n a lp o w e r , b o t hf a c t o r i z a t i o no fb i gi n t e g e r sa n de x t r a c t i o no f d i s c r e t el o g a f i t h m sf a l lu n d e rt h r e a tw h i c hc o m p e l st h ec r y p t o s y s t e m sb a s e do nt h e mt oa d o p t l o n g e rk e y sb u ta tt h es a m et i m e ，t h er e s e a r c ho fe 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 i np r o b l e m s p r o c e e d ss l o w l y t h e r e f u r e ，e l l i p t i cc u r v ec r y p t o s y s t e m sr e q u i r es h o r t e rk e y sa tt h es a e i e v e lo fs e c u r i t y , w h i c hi m p l i e st h ef a s t a rc o m p u t a t i o n a ls p e e da n dt h el e s ss p a c e c o n s a n l i 【1 9 a n dw h i c he n a b l e st h e ms u i t a b l ef o rt h es e t t i n gr e s t r i c t e dw i t hb a n d w i d t ha n dc o m p u t a t i o n a l p o w e rs u c ha ss m a r tc a r d sa n dw i r e l e s sn e t w o r k s t h et h e s i ss t r e s s e so nt h em g o f i t h r n sa n dp r o t o c o l st o i m p l e m e n te l l i p t i ec u r v e c r y p t o s y s t e m se 1 i i p t i co t l v a sc a nb ed e f m e do v e rv a r i o u sf i e l d s ，b u to n l yo v e rb i n a r yf i e l d s a n dp r i m ef i e l d st h e yh a v em o r ee a s yr e a l i z a t i o n s ，s ot h ea t g o r i t h m so v e rt h e s et w ot y p e so f f i e l d sa r ec a r e f u l l ys t u d i e di nt h et h e s i sw h i l et h ea t g o r i t h m st oi m p l e m e n te l l l p t i ec u r v ep o i n t a d d i t i o na n dp o i n tm u l t i p l i c a t i o na r ep r e s e n t e dt o o t h ep r o b l e mo f p l a i n t a x te m b e d d i n go v e r b i n a r yf i e l d si ss o l v e di nt h et h e s i s ，m a dw ea p p l yt h ep l a i n t e x te m b e d d i n ga l g o r i t h m st o t r a n s f o r m a t i o n o f e l l i p t i cc u r v e p o i n t s w h i c hr e s u l t s i n t h es a v i n go f h a l l o fs t o r a g es p a c e a n d t r a n s m i s s i o nb a n d w i d t h t h ee l l i p t i cc u r v e sc a nb ea p p l i e dt oa t lk i n d so fp u b l i ck e v c r y p t o s y s t a m sb a s e do nd i d c l e t al o g a r i t h m s ，a b o u tw h i c hw em a k eap r e c i s ed e s c r i p t i o nt o g of u r t h e r , w er e c o n s i d e rt h ee c e 1 g a m a le n c r y p t i o np r o t o c o la n dp r o p o s e “r a m b os e s s i o n k e ye x c h a n g ep r o t o c o l ”w h i c hs i m p l i f i e st h ep r o c e s so fe x c h a n g i n gs e s s i o nk e y s t h e p e r f o r m a n c e so fw p i e a la l g o r i t h m st oi m p l e m e n te l l i p t i cc h r ec r y p t o s y m e m so r ea n a l y z e di n t h et h e s i sa n dw ep r e s e n te x p e r i m e n t a ld a t af o rt h e m h a s e do nw h i c hw ec h o o s et h em o s t e f f i c i e n to n e sa n dc o n s t r u c te l l i p t i cc u r v ec r y p t o g r a p h i ef u n c t i o nl i b r a r yo v e rb i n a r yf i e l d a n dt h e nw ei n t e g r a t ei tw i t hs y m m e a i ce n c r y p t i o na n dh a s hf u n c t i o na n dc o n s t r u c ta f u n d a m e n t a l c r y p t o g r a p h i cl i b r a r y , n a m e d “e c c s p ，a c c o r d i n gt ot h ef r a m e w o r ko f w m d o w sc s ee x p e r i m e n t a ld a t as h o w st h a t e c c s p ”h a saf a s t e re x e c u t i o nt h a nt h et w o m a i nc s p ( r s aa n dd s s ) c a r r i e db yw i n d o w sa n dh a sas t a b l ep e r f o r m a n c e ，w h i c he n a b l e s i tt ob ec a l l e db yu p p e ra p p l i c a t i o n p r o g r a m s k e yw o r d s ：e l l i p t i cc u r v cc r y p t o s y s t e m s ；b i n a r yf i e l d s ；p l a i n t a x te m b e d d i n g ；r a m b os e s s i o n k e ye x c h a n g ep r o t o c o l ；e c c s p i i i - 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同忐对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：犹虽 签名日期：佗刃、2 、j 留 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和偌阅。本人授权东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：写铯军 签名日期：伽g 2 j 移 导师签名： 签名日期：j 翳的 东北大学硕士学位论文 第一章绪论 1 1 现代密码学的发展 第一章绪论 密码学的发展已经有上千年的历史了，但在计算机网络出现之前，密码学对于公众 来说是很神秘的，因为只有在军事上、或者其它涉及重大机密的领域内，才有密码学的 用武之地。训算机网络出现之后。随着网络通信量及对在公网内传输安全信息需求的增 长，密码学的应用越来越广泛，像f e i s t e l 密码结构、d e s 算法等都是在这个时期出现 的。但随着应用的拓展，传统密码学的不足之处越发明显。在这些密码系统中，消息的 发送方和接收方使用相同的密钥，通信的一方既可以加密消息，也可以解密消息，因此 它们统称为“对称密码系统”。在对称密码系统中，通信双方可以选择通过另外一条比 较安全的信道( 比如在电话中告知对方通信中要使用的密钥，或者写e - m a i l ) 来交换密 钥，然后用这个密钥来加密和解密信息，但是在没有这样的安全信道的情况下，我们应 该怎样做呢? 对称密码系统遇到的另一个难以解决的问题是密钥的管理问题。比如在 个由一个用户组成的网络中，要使每个用户都能与其他用户进行安全通信，则总共最少 需要n ( n 1 ) 2 个密钥。可以看出，随着”的增长，这样庞大的密钥数据是难以管理的。 考虑密码学要解决的舅一个问题一认证，对于解决身份的认证问题，对称密码系统尚能 起到”一定的作用，但对于解决消息的认证问题，即如何以完全电子的形式代替现实中的 手写签名，对称密码系统似乎是无能为力的。公铜密码概念的提出，不仅解决了上述问 题，它对现代信息安全的影响，更是超出了人们的稳象。 二十世纪7 0 年代早期，有的文章中已经出现了公钥密码思想的萌芽 3 1 。1 9 7 6 年， d i 伍e 和h e l l m a n 在他们的文章 ( n e w d i r e c t i o n s i nc r y p t o g r a p h y ) ) 【4 j 中明确提出了“公钥 密码”的概念，现代密码学由此发展起来。d i f f i e 和h e l l m a n 使用了由数学公式构造“单 向函数”的思想，这种函数只有在某些信息( 解密密钥) 未知的情况下才是单向的，如 果获得了这些信息，便可以很容易地计算出经函数作用前的明文，因此这类函数也可以 叫做“陷门函数( t r a p d o o r f u n c t i o n ) ”。在出这类数学公式构造的密码系统中，一个人将 一些信息设定为“私钥”，即“陷门”，再以这些信息为基础生成“陷门函数”，然后将 “陷门函数”公开，作为“公钥”。可以看出，“公钥”中隐含了“私铡”的信息( 这是 必然的) ，如果攻击者想通过“公钥”恢复出“私钥”，在理论上虽然可行，在计算上却 是不可行的。如果某个人想给这个人发消息，他可以通过公共信道得到这个人的“公钥”， 然后将明文和“公钥”作用，在合理的时间内生成密文，发送给接收方。接收方得到密 文后，用自己的“私钥”和密文作用，在合理的时间内得到明文。 可以看出，d i 伍e 和h e l l m a n 设计的公钥密码系统解决了传统密码系统遇到的困难， 即所有的通信都可以在公共信道内完成，而不需要另外的“安全”信道来交换密钥，这 东北大学硕士学位论文第一章绪论 与现代网络通信的需求是吻合的。因为这种密码系统的加密和解密密钥是不同的，所以 为了和传统的密码系统对比，我们称之为“非对称密码系统”。虽然他们提出的思想很 完美，但如何构造“公开密钥体制”所需的数学函数，d i f f i e 和h e l l m a n 并没有明确给 出。1 9 7 7 年，r o nr i v e s t ，a d is h a m i r 和l e na d l e m a n 提出了基于r s a 算法口1 的公钥密 码系统，这种算法使用的数学公式很简单( 仅使用了模指数运算) ，运算速度快，算法 安全性的数学依据是大整数的难分解性，这一问题已经经过了上千年的研究，被认为是 很牢固的。r s a 提出后，迅速应用到了信息安全领域。白此之后，公钥密码的思想得 到普遍的认可，许多新的应用也随之发腱起来，这包括： ( 1 ) 认证，用来验证用户的身份或权限； ( 2 ) 鉴别，证明消息未被窜改及柬源的可靠性； ( 3 ) 不可抵赖，保证用户执行某些动作后，有证据能证明这些动作发生过； ( 4 ) 密钥交换，用户使用公共倍道交换用来执行对称加密的密钥； ( 5 ) 电子现金，保证消费者的匿名性； ( 6 ) 电子选举，保证选票的可信性和有效性。 三十年来，人们提出了大量的数学难题来实现公钥密码系统，但能经受得住时间考 验的只有三种：火整数的分解、离散对数的求解和椭圆曲线离散对数的求解。基于大整 数分解的典型公钥密码系统是r s a ，基于离散对数求解的典型公钥密码系统是e l g a m a l 密码系统畔j ，椭圆曲线密码系统的使用尚处于初期阶段。由于公钥密码的引入，信息安 全产业获得了突飞猛进的发展，可以这么讲，没有公钥密码学，便没有现代的信息安全 产业。但自从公钥密码这一思想提出的那时起，对它的批评便没有停止过。众所周知， 公钥密码系统的安全性依赖于某些数学难题，像大整数分解、离散对数求解等，但根本 没有人能证明这些问题确实是“困难”的，人们只是在经过很长时间的努力后，仍然没 有解决这些问题，便认为它们是“困难”的，但谁能说将来仍然没有人能解决这些问题 呢? 拿r s a 来讲，不仅大整数的难分解性不能得到证明，而且到现在人们仍然不能证 明破解r s a 的困难度确实与分解大整数相当。因此，以数学家的眼光来看，整个公钥 密码学是脆弱的，它就像瓶子里的魔鬼，迟早有一天会出来伤人。但如果以一个计算机 科学家的角度来看待这个问题，虽然“绝对安全”这个概念让我们身心舒畅，但我们没 有必要为达到这个目标而空耗精力，“最大可能的安全( p r o b a b l es e c u r i t y ) ”已经足够了， 我们没有必要为现在加密的信息在数十年之后被破解而担心。为了取得“最大可能的安 全性”，计算机科学家们也是报慎重的，一种公钥密码算法提出后，大约要经过1 5 年的 安全性论证，才可以被国际组织认可。基于“背包问题”的公钥密码系统1 6 便在提出几 年后被攻破了，椭圆曲线密码系统经过了二十年的分析，其安全性是可以保证的。 值得一提的是，在公钥密码系统的基础上，s h a m i r 于1 9 8 4 年提出了一种“基于身 份的密码系统( i d c a f i t y - b a s e dc r y p t o s y s t e r r t s ) 1 5 0 1 - 。众所周知，在公钥密码系统中，每 个用户可随即地生成一个私钥公钥密码对，一个可倍的目录负责收集所有用户的公钥 并提供查询服务。若用户b o b 想与a l i c e 进行安全通信( 发送消息或者验证签名) ，他 2 东北大学硕士学位论文第一章绪论 必须向目录询问：“a l i c e 的公钥是什么? ”得到答案后，他才可咀执行上述过程。而在 “基于身份的密码系统”中，这样的目录是不需要的。若b o b 想与a l i c e 进行安全通信， 他叫1 以直接使用“a l i c e ( 身份) ”，除此之外，不需要任何信息。每个用户拥有一个相 对于自己身份的密钥，这个密钥用来生成签名或者解密消息，但这个密钥并不是由用户 自己生成的。比如d a v i d 想加入网络，他把自己的详细资料交给一个密钥生成中心 ( k g c ) 审核，若审核通过，k g c 根据自己掌握的一个主密钥( m a s t e r - k e y ) 和“d a v i d ” 生成卟密钥然后通过安全的渠道把它发给d a v i d 。可以看到，一旦用户加入网络后， 他就可以直接与其他用户进行安全通信，而不需要任何第三方提供的服务。基十身份的 密钥系统沿用了公钥密码系统的思想，仍然属于“非对称密码系统”的范畴，相对于公 钥密码系统而言，它有两个弱点：m - 5 如果主密钥泄漏，则整个系统就会瘫痪；二，用 户的个人密钥更新是很匿难的，因为更新个人密钥必然伴随着个人身份的更新，这将带 来一系列的问题，所以每个用户必须谨慎地保护自己的密钥。s h a m i r 在他的文章中建 议将个人密钥和所有的安伞通信协议封装在一个智能卡里，这样既保护了密钥，又增加 了对上层用户的透明度。很多学者对这种密码系统进行了研究，比较典型的是文献【”1 的结果。下面三幅图就现行的三种密码系统作了比较。文献h 6 1 对近代公钥密码学的发展 作了详细的分析，并介绍了若干种新型的尚处于理论研究阶段的公钥密码系统，如超椭 圆曲线密码系统、双线性对密码系统等，建议读者奄看。 m e s s a g e 图1 1 对称密码系统 f i g 1 1s y m m e t r i cc r y p t o s y s t e m 图12 公钥密码系统 f i g t2p u b l i ck e yc r y p t o s y s t e m 。3 m e s s a g e 随机种子 m e s s a e e 酗1 3 基丁身份的密码系统 f i g 1 3l d e n t i t y b a s e dc r y p l e s y s t e m 1 2 椭圆曲线密码系统 m e s s a g e 随机种子 椭圆曲线密码是一种新兴的公钥密码系统，于1 9 8 5 年由k o b l i i ：z i l l 和m i l l e r 2 独立提 出。二十年来，人们对这种密码系统进行了大量的研究，结果表明，与其他几种广泛应 用的公钥密码系统比起来，具有速度快、难破解、数学背景丰富等优点。椭圆曲线密码 系统也是基于离散对数问题的，它用有限域上的椭圆曲线有理点群代替了大素数域上的 乘法群，所以严格来讲，椭圆曲线密码系统并不是一种新的公钥密码系统。1 9 8 5 年将 有限域上椭圆曲线有理点群应用到公钥密码系统中这思想提出后，人们的反应并不是 很积极。首先，当时并没有有效的方法计算有限域上椭圃曲线的有理点的个数，这使得 人们在选曲线时遇到了无法克服的障碍；其次，椭圆曲线上的点加过于复杂，实现起来 很困难。而当时r s a 算法已提出将近十年，技术上趋于成熟，执行效率也很高。就当 时分解大整数的能力而吉，只需选择不太大的模数，r s a 的安奎l 生就可以得到保证， 但是，一些钟爱理论的科学家没有放弃对椭圆曲线密码系统的研究。1 9 9 0 年，m e n e z e s 使用了一类特殊的曲线一超奇异椭圆曲线1 1 7 1 ，这种曲线有理点群的阶可以很容易的得到 并且实现速度也很快。但是到1 9 9 3 年，m e n e z e s 本人和他的两个合作者发现了对这种 曲线的一种有效的攻击方法，称为“m o v 攻击口1 ”，这手中方法可以把椭圆趋线离散对数 问题化约到某个次数较低的扩域上，从而在多项式时问内求解。但与此同时，椭圆曲线 上有理点个数的计算问题得到了很大的突破。1 9 8 9 到1 9 9 2 年问，a t l k i n 和e l k i e s 对1 9 8 5 年提出的s c h o o f 算法作出了重大改进，到1 9 9 5 年，人们在这一问题上取得的成就已经 达到密码学上的实用标推了。另外，由于这一时期计算机软件和硬件技术的突飞猛进， 椭圆曲线点加也可以很容易的实现了。1 9 9 8 年以后，a n s i 、 e e e 、i s o 、n i s t 等国际 组织陆续地将椭圆曲线密码系统列为标准 8 q 2 1 。2 0 0 0 年，k o b l i t z 、m e n e z e s 和v a n s t o n c 等大师对椭圆曲线密码系统的整体发展状况做了客观的分析 l ，为其商业应用打下了坚 实的基础。 与r s a 和离散对数密码比起来，椭圆曲线密码系统的诱人之处是在安全性相当的 前提下，可以使用较短的密钥，而这意味着运算空嘞的节省和运算速度的提升。一般 a 4 东北大学硕士学位论文 第一章绪论 为，当椭圆曲线基域长度为1 6 0 比特时，其安全性相当于使用1 0 2 4 比特模数的r s a ， 所以在某些计算能力和存储空间受限的环境下，比如智能k 、p c 卡、无线设备等，椭 圆曲线密码系统的优势是很明显的。由于椭圆曲线上的一次点加运算最终化为其背景 域上不超过1 5 次的乘法运算，因而便于软件实现，且在速度的提升上有很大的活动空 间。如果我们使用类称作k o b l i t z 的特殊曲线，其运算速度要比r s a 快很多。在安全 性方面，自从1 9 7 8 年r s a 算法提出后，人们对分解大整数产生了很大的兴趣，一些具 有特殊形式的和位数较低的大整数，陆续地被分解。1 9 8 5 年e 1 g a m a l 公钥密码系统提 出后，人们对离散对数的求解问题进行了大量的研究，结果表明，大整数的分解与离散 对数的求解在本质上具有一致性，即如果其中的一种得到解决，另一种也随之解决。另 外，随着计算机运算能力的提高，位数较低的大整数已经不安全了。过去，5 1 2 比特的 密钥空剧已经足够安全，现在要达到同等的安全性，密钥的长度至少为1 0 2 4 比特，在 菜些安全性要求较高的应用中，密钥的长度甚至要2 0 4 8 比特。而另一方面，近二二十年 来，对椭圆曲线离散对数问题的求解几乎毫无进展，人们只是找到了一些特殊曲线的破 解方法，对于一般的椭圆曲线，到现在仍然没有亚指数时间级的破解方法，其优势越发 明显。加拿大的c e r t i c o i n 公司对椭倒曲线密码系统和r s a 的安全性做了详细的比较， 下袭1 14 j 是他们得出的结果： 表1 1r s a d s a 与e c c 密钥长度比较 t a b l e1 1c o m p a r i s o n o f k e y l e n g t h b e t w e e n r s a d s a a n d e c c m i p s 年数 r 茗富嚣a密蒹度 两者长度比 椭圆曲线密码系统是以椭圆曲线理论为基础的，后者的研究已经有上百年的历史 了。以前，椭圆曲线只是种纯粹的数学理论，深奥，抽象，没有什么应用价值，数学 家们研究它，只是出于对纯粹理论的偏爱。椭圆曲线密码理论提出后，越来越多的人着 手研究椭圆曲线及相关的数学理论，这无疑促进了它的发展。近年来，椭圆曲线理论在 编码理论、伪随机数的产生、大整数分解等领域也相应获得了应用。基于对椭圆曲线安 全性的信任，人们普遍认为它将会成为二十一世纪最主要的公钥密码系统，而现代的信 息安伞系统是靠公钥密码学理论支撑起来的，可以预见的是，椭圆曲线密码系统带给未 来的应用价值足巨大的。 本文以椭圆曲线密码系统为研究目标，下面对论文的篇章结构作一描述。第二章引 入了椭圆曲线的一些基本数学概念和定理，推导出密码学上常用的公式，为后续的工作 打下基础。第三章讲述实现椭圆曲线密码系统所需的备种算法，包括二元域和大素数域 东北太学硕士学位论支第一章蜡论 上的基本运算、点加、点乘和明文嵌入问题等，并以实验数据为基础，分析了它们的执 行效率。第四章分析了椭圆曲线密码在各种加密、签名协议中的应用，提出r a m b o 会 话密钥交换协议，并对上述协议的安全性问题作了探讨。第五章首先引入w i n d o w zc s p 的概念和相关知识，接着详细描述了本文构建的基于二元域上椭圆曲线的基础密码函数 库“e c c s p ”。第六章总结了本文的工作，并对后续的工作作出展望。 6 东北大学硕士学位论文苹= 章基本数学理论 第二章基本数出：- t - ：理论 弟一早：荃今鳅璀了匕 椭圆曲线的研究来源于椭i 到积分，即计算椭圆上任意一段弧的长度。这样的积分不 能用初等函数来描述，为此引入了椭圆嗨线的概念。椭圆曲线理论的研究已经有上百年 的历史了，它是一门交叉学科，涉及到代数几何、群论、域论、数论等多方而的知识。 椭圆曲线理论本身深奥、抽象，研究起来相当耗时，本章只介绍应用于密码学理论的一 些基本概念和定理，以便于开展进一步的讨论。读者若欲了解更多本章相关的内容，可 参见文献1 5 , 1 6 。在本章中，我t f k 表示域，i 表示k 的一个代数闭域，茁表示的 扩域。 21 仿射空间与射影空间 本节只给出仿射空间与射影空间的定义。 定义2 1 ：k 上的n 维仿射( 揽n e ) 空间是如下n 元组的集合： a ”= a “( 世) = ( x i ，) l t k ) 同理，中的足一有理点集合是： a “( 茁) = ( ，) 4 4 l j ，k 。 定义2 2 ：j ! ( 上的 维射影( p r o j e c t i v e ) 空间记为p r r 或者p ( i ) ，是月元组 ( ，) 肿1 ( 至少有一个x 不为零) 模上等价关系 ( x o ，) c ( 虬，n ) 所构成的集合，这个等价关系需满足列于所有的i ，存在 夏+ 使得t = 砂。一个等 价类 ，一触。) 记为k ，】，因此中k 一有理点集合是： p ”( ) = f 矗，x n 】e p ”薯 数学上的空间可以分为两类：仿射空间和射影空间。仿射空问是我们用的最多的空 问，也最接近于我们的直觉。仿射空间也可以理解为向量空间，我们在其中引入线性变 换平移，于是仿射空间、仿射空间的映射、仿射空间的子空间，都成了线性代数中的 结论在某种程度上的翻版。射影空间是抽象意义上的，我们的直觉是空间有无数的点组 成，点是我们研究的基本单位，而在射影空间中，空间的的基本组成单位是线，一簇平 行线在无穷远处交于一点。 行线在无穷远处交于一点。 。7 。 东北大学硕, - t - 学位论文 第二章基本数学理论 2 2w e i e r s t r a s s 方程 在代数儿何种，亏格为1 的曲线称为椭圆曲线，亏格大 _ _ l 的曲线称为超椭圆曲线， 本章只研究前者。由r i e m m a n - r o e h 定理可知，任意一条椭圆曲线总可以用一个i 次方 程来表示，这个方程称为w e i e r s t r a s s 方程。下面我们在这个方程的基础上，给出椭圆曲 线的定义。 定义2 3 ：对于w e i e r s t m s s 方程 y 2 z + a 1 x y z + 码y z 2 = x3 + a 2 x 2 z + q 船2 + d 6 z3 ( q 芭k ，【x ，y ，z 】p 2 ) ( 2 1 ) 假设其满足j a c o b i 条件，即方程组 a f f 镊= 0 ofar20(z-z) a f a z = 0 f ( z ，r ，z ) = 0 在足上无解，则定义于置上的椭圆曲线是 e = y z 】e ，1i x , y ，z 】是( 2 - 1 ) 的解) ( 2 3 ) 若z 0 ，令x = x ，z ，y = y z ，则方程( 2 1 ) 可以化为 y 2 + 盯1 x y + a 3 y = x 3 + a 2 x 2 + d 4 r 十砘( 研足) ( 2 - 4 ) 若z = 0 ，则j ，_ 0 ，】，为任意的值，此时 置z l 表示一个点，e p 0 ，1 ，0 1 。这个点映射到 仿射坐标系中，即为无穷远点，方向是y 轴。这时，占可以用方程( 2 4 ) 的所有解再加 上一个无穷远点来表示，即 e = 0 ，) e l & ，一为( 2 4 ) 的解) u 0 ( 2 5 ) 山于直观的考虑，下面给出r 仿射坐标系下定义于实数域上的几种椭圆曲线的图像： r j k j ： i 一4 0t 2 1olzjq ；1 国123 5 1 - 2 3 + 4 5、 东北大学硕士学位论文第二章基本数学理论 厂、i ! u 0、1z - 。i y 2 = x 3 一x 扩= ， 圈2l 仿射坐标系下定义于实数域上的几种椭圆曲线的捌像 f i g21i m a g e si na f f i n ec o o r d i n a t eo f c u l p t i cc u r v e so v e rr e a ln u m b e rf i e l d 设f z e e ，若存在口ek + ，使得【墨a y , n z = 瞄，r ，z ，这里，r ：z 1e p e ( k ) ， 则称i x , y 2 为k _ 有理点，所有这样的点组成的集合记为e ( k 3 。e ( 目表示椭圆曲线上 的所有丘一有理点。 若方程组( 2 - 2 ) 有解，则称e 是一条奇异椭圆曲线：否则，称e 是非奇异椭圆曲线， 或者光滑椭圆曲线。由图2 1 可以看出，方程少= ，表示的曲线为奇异椭圆曲线，奇异 点为( 0 ，0 ) 。由方程n ( 2 2 ) ，我们可以推导出五的判别式d ( 勘。令 b 2 = 4 i2 + 4 4 2 b 4 。4 1 4 3 + 2 a 4 乏：=。a。j：2+。+4a6b a 4 a ：a 。一a l o ，a 。+ a z a ，一。： c ze ， 8 = 口1 26 +26 34 +3 2 一d 4 i 。4 = b 2 2 2 4 b 4 c 6 = - b 2 3 + 3 6 6 2 b 4 2 1 6 b e 则“切= - b 如一8 6 3 2 7 玎+ 9 6 2 6 。6 s ，f 的广不变量，( e ) 2 壶茜a 可验证 4 b b = b 2 b 6 一b 4 2 且1 7 2 8 a ( e ) = c 4 3 一吒2 。 当且仅当( e ) = 0 ，方程( 2 1 ) 表示的曲线为奇异椭圆曲线。 定义2 4 设e 的仿射方程如( 2 4 ) 所示，e 的仿射方程为： y ”+ 疗。l 石，l 卜d 3 ，= j 。+ 日2 x 1 2 + 口j x * + a t 6 ( 瞳i 田 9 东北太学砸士学位论t第二章基本数学理论 若存在“，r ，s ，te k ，m 0 ，使得 r1 x = “：。+ 7 ( 2 7 ) i y3 “。y + “+ f 成立，则称椭圆曲线五与e 在域置上是同构的。 可以看出，由( 27 ) 规定的映射为一一映射。若e 与e 同构，则两者的性质是相同 的，我们可以选取一簇同构曲线中的一种作为研究对象。根据e 的j 一不变量，可以对 椭圆曲线做同构分类。 定理2 , 1 两条椭圆曲线在k 上i 刊构的充要条件是它们具有相n j - 不变量。 由定理2 1 可知，两条在k 上同构的椭圆曲线一定具有相同的，一不变量，具有相 同，一不变量的两条椭圆曲线一定在丘上同构，具有相同，不变量的两条椭圆曲线不 一定在世上同构，但肯定存在拦的一个扩域，使得两条椭圆曲线在k 上同构。 根据椭圆曲线同构的性质，我们总可以将形如( 2 4 ) 的曲线化为更简洁的曲线，下面 我们根据域的特征值c h 叫蜘，对曲线进行化简。 ( 1 ) c h a r ( k ) 2 ，3 时，令 则方程( 2 4 ) 叫”以化为如下形式： y 2 = p + 血+ b( 2 8 1 此时( e ) = 一1 6 ( 4 a3 + 2 7 b 。_ j ( e ) = 一1 7 2 8 ( 4 4 ) 3 a ( e ) 。要使e 为非奇异椭圆曲线，必 须4 爿3 + 2 7 8 2 0 。 ( 2 ) c h a r ( 固= 2 时，根据，c 目的取值分两种情况进行讨论。 】) j ( 日0 ，即a l o ，令 x = d 。2 x 1 + 旦 吗 2 ，= q 3 _ y + 塑李生 a i 则方程( 2 4 ) 可以化为如下形式： y 2 + x y = x 3 + a x 2 b ( 2 9 ) 此时( 点) 宣b ，( 点) = i 1 。显然，b 。 2 ) ，( 净o ，即a l = 0 ，令 1 0 o l 一3 一 )屯 ，一佗 一 也 仁 ，uq一2 一 一 p p = = x y 东北大学硕士学位论文 第二章基奉数学理论 卜= x + 啦 【y = ， 则方程( 2 - 4 ) 可化为如下形式： y 2 + a 3 y = x 3 + a 4 x + a 6 r 2 - 1 0 、 此时( e ) = 口，4 ，( e ) = 0 ，显然，a s o 。 ( 3 ) c h m - ( 柳= 3 时，同样根据“d 的取值两种情况讨论。 1 ) ( 毋o ，令 则方程( 2 - 4 ) 可化为如下形式 0 1 日4 + d2 口3 z 口， y 2 = x 3 + a x 2 + b i f 6 时a ( e ) 一夙邶) 一鲁，显然，a * o 且b * o 。 2 ) ，( 毋- 0 ，令 f z = x y = y 一导( 口，x ，+ a ，) 则方程( 2 4 ) 可化为如下形式： v ：= z3 + a 工+ b 此时a ( e ) = 一a ，j ( e ) = 0 ，显然，一0 。 2 3 椭圆曲线点群 23 1 点群的定义及基本陛质 ( 2 1 1 ) ( 2 1 2 ) 任一椭圆曲线的元素之问，存在着一个自然的群运算法则。设t 尸2 是一条直线， 因为e 的w e i e r s t r a s s 方程的度是3 ，所以与五必交于三点，设为p ，p ，r 。注意到 若与e 相切，则此三点中的两点或三点重合。根据上述性质，我们给出如下的组合 法则，记为o ： 设p 、q e e ，三是过j d 、9 的直线( 如果p = q ，则l 为切线) ，r 是l 与e 的第三 个交点。设是过月与0 的直线，则p o q 表示上与e 的第三个交点r 。 为了使结果比较直观，在这里我们设k 为实数域，下图揭示了。的原理： x口 生凡一2 + l y = l 【 x y j，、【 ， 、4 巴 l 箩 勋慷 1 1 。l 23 八 0 一2 3* ：l 产 西 0 】j 3 4 j1 _ 4 图22 组台法则。不意图 f i g 2 2d e m o n s t r a t i o no f c o m b i n a d o nr u l eo 组合法则。有如下的性质： ( 1 ) 如果线交e 于p ，q ，r 三点( 可能有重合点) ，则妒。q ) 。r = 0 ； ( 2 ) 对于所有的p e ，p $ o = p ： ( 3 ) 对于所有的p ，qe e ，p o q = q 毋a ( 4 ) 设d e 五，ee 存在一点q ，使得p o q = 0 ； ( 5 ) 设只q ，r 正，则俨毋9 0 r p 。( q 由五) 。 由以上性质可以看出，在组台法则。的作用下，e 二所有点构成一个a b e l 群，这个群 以0 为零元素。在此基础上，我们还_ j 以得到 ( 6 ) e 啦) ( e 上所有的置一有理点) 存$ 的作用下构成e 的子群。 证明：设p ，q 是耳目中的两点则p ，q 的坐标值在k 中，从而穿过p ，q 的直 线的系数在k 中。因为e 定义于k 上，所以与f 的第三个交点的坐标是三与e 的 某种有理组合，即第三个交点的坐标值在足中，从而性质(