（计算机应用技术专业论文）基于椭圆曲线密码系统的数字签名研究.pdf

湖北工业大学硕士学位论文 摘要 随着信息技术的不断发展和应用，电子信息的安全性问题变得越来越重要。 现在广泛使用的r s a 公钥密码系统己很难满足未来人们对信息高安全性的需求 椭圆曲线密码系统是迄今为止公钥密码系统中最高单位比特安全强度的密码系 统。与其他公钥密码系统相比，椭圆曲线密码系统除了安全性高外，还具有计算 负载小，密钥尺寸短，占用带宽少等优点，因此，椭圆曲线密码系统被认为是下 一代最通用的公钥密码系统。 目l i i 国内对于椭圆曲线公钥的快速实现、智能卡应用等研究较多。由于它 本身的优点也特别适用于无线m o d e m w e b 服务器、集成电路卡等方面，然而， 在现有的研究中它在进行大 t 安全交易的电子商务领域中研究比较有限。随着 网上交易的频繁，这将成为今后研究的热点 本文第一章在查阅大量文献资料的基础上，分析了密码学领域罩的对称加密 体制和非对称体制，并对二者进行了对比，指出了公钥加密体制的优点所在。在 此基础上，提出了几种常用的数字签名算法体制。第二章讨论了椭圆曲线密码体 制的建立，先介绍了椭圆曲线的定义和基本定理：然后讨论了安全椭圆曲线选取方 法：随机选取椭圆曲线的方法，给定椭圆曲线阶的选取方法，w e i l 椭圆曲线选取方 法：最后介绍了应用椭圆曲线密码的加密解密过程。第三章我们首先讨论了传统的 数字签名协议，其次在已有的椭圆曲线数字签名算法的基础上提出了改进算法， 并给出了具有消息恢复的椭圆曲线数字签名算法 关键词：公开密钥椭圆曲线数字签名 湖北工业大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n ta n da p p l i c a t i o no fi n f o r m a t i o nt e c h n o l o g y ，t h e s e c u r i t yp r o b l e mo fe l e c t r o n i ci n f o r m a t i o nb e c o m e sm o r ea n dm o r ei m p o r t a n t t h er s ac r y p t o s y s t e m ，w h i c hi sap u b li c k e yc r y p t o s y s t e mb e i n gu s e dw i d e l y n o w a d a y s ，s e e m st oh a v ed i f f i c u l t i e st om e e tt h eu s e r s n e e do fh i g h e r s e c u r i t y s of a r ，e 1 1i p t i cc u r v ec r y p t o s y s t e mp r o v i d e st h eh i g h e s t s t r e n g t h p e r b i to fa n yp u b l i c k e yc r y p t o s y s t e m s i na d d i t i o nt oi t sh i g h e r s e c u r i t y ，e 1 1 i p t i cc u r v ec r y p t o s y s t e ma l s oh a sm a n yo t h e ra d v a n t a g e s ，s u c h a st h e1 e s sc o m p u t a t i o no v e r h e a d s ，s h o r t e rk e ys i z e ，c o n s i d e r a b l eb a n d w i d t h s a y i n g sa n ds oo n a 1 lo ft h e s em e r i t sh a v em a d ei tt h eb e s tp u b l i c k e y c r y p t o s y s t e 巾t h a ti ss u i t a b l ef o ru s ei nt h ef u t u r e c u r r e n t l y 。t h e r ei sm u c hr e s e a r c ho nr a p i dr e a li z a t i o na n ds m a r tc a r d a p p l i c a t i o no fe 1 1 i p t i c a lc u r v ep u b l i ck e y b e c a u s eo fi t so w na d v a n t a g e s i ta l s oc a nb ea p p l l e dt ow i r e l e s sm o d e m ，w e bs e r v i c e s ，a n di n t e g r a t e d c i r c u i tc a r d sa n ds oo n h o w e v e r ，i no n g o i n gs t u d y ，t h er e s e a r c ho fm a s s s e c u r i t yt r a n s a c t i o h si nt h ea r e ao fe b u s i h e s si ss ol i m i t e d w i t ht h e o n l i n et r a n s a c t i o n sb e c o m em o r ef r e q u e n t t h i sr e s e a r c hf i l e dw i l lb e c o m e h o ts p o t si nf u t u r e t h et h e o r ya n da p p l i c a t i o no fe 1 1 i p t i cc u r v ec r y p t o s y s t e ma r es t u d i e d a sf o l l o w i nc h a p t e r1 ：a c c e s st oal a r g en u m b e ro f1 i t e r a t u r e s t h e s y m m e t r i ca n da s y m m e t r i ce n c r y p t i o ns y s t e mh a sb e e na n a l y z e di n c r y p t o g r a p h yf i e l ds t r u c t u r e a n dac o m p a r i s o nt h a tt h ep u b l i ck e y e n c r y p ti o ns y s t e mh a st h ea d v a n t a g eb e t w e e nt h e mh a sb e e np r o p o s e d o nt h i s b a s i s ，c o m m o n l yd i g it a ls i g n a t u r e sa l g o r it h ms y s t e m sh a v eb e e na d v a n c e d i nc h a p t e r2 ，e 1 1 i p t i cc u r v ea n dt h ea r i t h m e t i co fs e l e c t i n gs e c u r i t y e l l i p t i cc u r v ew a si n t r o d u c e d a st h es a m et i m e t h es y s t e mo fe n c r y p t i n g a n dd e c o dj n gw a sb u i l t i nt h el a s tc h a p t e r ，t h es i g n a t u r eo fe 1 1 j p t i cc u r v e c r y p t o s y s t e mw a sa m e n d e d ，s ot h ec a l c u l a t i o nw a sr e d u c e d d i g i t a ls i g n a t u r e w a sa n a l y s i sa n dt h ep r o t o c o lo fs i g n a t u r ew i t hi n t e r c e s s i o f fw a si m p r o v e d t h e r e f o r et h ep r o t o c o lo fd i g it a ls i g n a t u r ec a nb ei m p l e m e n t e dw it h o u t i n t e r c e s s i o n k e y w o r d s ：p u b l i c k e y ，e 1 1 i p t i cc u r v e ，d i g i t a ls i g n a t u r e n 佩l l 工案火港 学位论文原创性声明和使用授权说明 原创；陛声明 本人郑重声叫：所生交的学位论文，是本人在呼师指导i - ，独i ：进行硼f 究j - 作所i d ( 得的研究成果。除文i 】已经标l 刿引用的内容外，本论文不包含f e f f j j 其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果由本人承担。 学位论文作者签名：互庀日期：2 0 0 7 年，月2 弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 l ：l f i l 国家自_ 天部门或机构送交论义的复印件和i 乜f 版允i ：论文铍盘阅耳i i f 持阋。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名：王庀 日期：z 一7 年，月2 多日 指导教师签名黟麦幺 嗍易矿厂月岁日 湖北工业大学硕士学位论文 1 1 选题背景及意义 第1 章引言 随着计算机网络技术的迅速发展，信息化己成为社会发展的趋势。然而由于 网络本身的丌放性和脆弱性，使得网络信息面临只益严重的威胁和攻击，成为信 息化的瓶颈，信息安全问题也同益严重和突出。而密码学的应用则可以解决这个 问题，因而高效安全的密码系统成为人们研究的热点。 当前国际主流的公钥密码系统是r s a 密码系统。但是，随着分解大整数方法的 进步和完善、计算机运算速度的提高及分布式计算的出现，为了保i 正r s a 的安全性， 其密钥的位数不断增加。密钥位数的增加降低了加解密的速度，也限制了其应用 场合。随着电子商务的普及，人们对加密算法的速度和安全性提出了更高的要求。 而椭圆曲线公钥密码系统的出现符合的人们的要求。椭圆曲线密码系统是建立在 椭圆曲线理论基础上的公钥密码系统，该系统所具有的安全性已经被世界所公认。 在己知的公钥密码系统中，椭圆曲线密码系统在密码强度、加解密的处理速度和 存贮丌销上都由明显的优势。现在，密码学界普遍认为它必将成为计算机网络、 数据通信、电子商务，特别是新一代环境受限系统如移动通信系统和智能卡系统 理想的安全解决方案。 椭圆曲线密码系统以其良好的安全性，曲线选取范围广，在同等长度的密钥 下具有比现在通用的r s a 密码系统更快的加解密速度及更高的密码强度而受到人 们的关注，成为密码学的研究新热点，是很有前途的研究方向。 _ 1 2 密码学基本术语 1 9 4 9 年，s h a n n o n 发表了著名论文保密系统的通信理论，把古老的密码学 置于坚实的数学基础之上。1 9 7 7 年，美国联邦政府正式颁卸了数据加密标准( d e s ) ， 湖北工业大学硕士学位论文 这是密码学历史上的一个创举，由此，过去神秘的密码学逐步走向公丌的学识殿 堂。1 9 7 6 年，w h i t f i e l dd i f f i e 与m a r t i nh e l l m a n 的开创性论文密码学新方向， 首次提出了公钥密码的概念，建立了公钥密码体制基础。 密码学包括两个方面：密码编码学和密码分析学。密码编码学就是研究对数据 进行变换的原理、手段和方法的技术和科学。密码分析学是为了取得秘密的消息， 而对密码系统及其流动的数据进行分析，是对密码原理、手段和方法进行分析、 攻击的技术和科学。密码学的理论基础是数学，其基本思想是隐藏、伪装信息， 使未经授权者不能得到消息的真f 含义 消息称为明文。用某种方法伪装隐藏消息的过程称为加密。被加密了的消息 称为密文。把密文转变成为明文的过程称为解密。图1 1 表明了加密解密的过程。 明文用m 表示，通常是位序列、文本文件、位图、数字化的语音序列或数字 化的视频图象等。对于计算机，m 指简单的二进制数据。m 可以被传送或存储，是 待加密的消息 密文用c 表示，它也是二进制数据，和m 一样大，或比m 稍大，通过压缩和 加密的结合也可比m 稍小些。加密函数e 作用于m 得到密文c ，用数学公式表示： e ( m ) = c 相反的，解密函数d 作用于密文c 产生明文m ： d ( c ) = m 先加密再解密，就恢复出原是明文有下面等式成立： d ( e ( m ) ) = m 图1 1 加密和解密 f i g 1 1e n c r y p ta n dd e c r y p t 湖北工业大学硕士学位论文 鉴别：消息的接受者应该能够j 下确判断消息的来源，消息不是入侵者伪装的。 完整性：消息的接受者应该能够币确判断消息没有经过别人篡改，也不是替代 的假消息。 抗抵赖性：发送者不能否认自己曾经发送过此消息。 密码算法：也叫密码，是用于加密和解密的数学函数。密钥用k 表示，我们每 个用户不可能拥有单独的一个密码算法，用户拥有自己的密钥k ，k 的取值范围称 为密钥空间。加密和解密都依赖于密钥k 。 密码分析学是在不知道密钥的情况下，恢复出明文的科学。密码分析可以发 现密码体制的弱点，恢复出明文或密钥。 密码系统是由算法、明文、密文以及密钥组成的。基于密钥的算法通常可以 分为两类：对称算法和公丌密钥算法。 1 3 对称加密体制 对称加密算法，又称私钥加密算法，就是加密密钥能够从解密密钥中推出来 反过来也成立，在大多数对称算法中，加密解密密钥是相同的。对称加密算法的 典型代表有：d e s ，a e s 等。以d e s 为代表的对称密钥加密算法的设计原则主要基于信 息论的混乱和扩散。混乱指的是密钥和明文及密文之日j 的依赖关系应该尽量复杂， 以破坏分组嘲的统计规律，通常依靠多轮迭代来实现：扩散则应使密钥和明文的每 一位影响密文中尽可能多的位数，这样可以防止逐段破译，并通过s 盒的非线性变 换来实现。实际上，所有的对称密钥加密算法都采用f e i s t e l 网、s 盒及多次迭代 等思想。 对称加密有速度上的优点，用软件实现，对称密钥比非对称密钥快1 0 0 - 1 0 0 0 倍。然而，如果一个消息想以密文的形式传到接收者，我们应该找到一个方法安 全传输密钥。对称加密系统用键长束衡量加密强度，4 0 比特的键长被认为比较脆 弱，1 2 8 比特比较健壮。对称算法的加密和解密表示为： 湖北工业大学硕士学位论文 e x ( 肘) = c d x ( c ) = m 图1 2 对称密钥加密解密 f i g 1 2e n c r y p ta n dd e c r y p tw i t hs y m m e t r i c k e y 1 4 公钥加密休制 1 4 1 公钥密码基本概念 公钥密码概念是由w h i t f i e l dd i f f i e 和m a r t i nh e l l m a n 于1 9 7 6 年提出的，它 是密码学历史上的一个重大成就。公钥密码与以前所有的密码方法都大相径庭：一 是以前的密码算法都基于代换与置换操作，而公钥密码使用数学函数进行变换：二 是公钥密码体制使用非对称的方式，使用两个密钥( 加密密钥与解密密钥) ，而传 统密码算法仅仅使用一个密钥。 公钥密码体制的提出首先是为了解决利用传统密码体制进行密钥分发时遇到 的问题，数字签名也是其重要应用之一。 从1 9 7 6 年起，学者们提出了许多种公钥加密方法，它们的安全性都是基于 复杂的数学难题。根据所基于的数学难题来分类，有以下三类系统目前被认为 是安全和有效的： ( 1 ) 基于大整数因子分解的：r s a 和r a b i n w il li a m s ( 2 ) 基于离散对数问题的：d s a 和e i g a m a l ( 3 ) 基于椭圆曲线离散对数问题的：椭圆曲线密码系统 公开密钥加密算法于对称密钥加密算法相比来说，安全性能更好，密钥管理、 湖北工业大学硕士学位论文 分配都容易实现，其中有些加密算法还能应用在数字签名上，但是它们相对于对 称密钥加密算法运行速度要慢得多，所以不能加密大量的数据。 1 4 2 公钥密码原理 公丌密钥密码理论是1 9 7 6 年美国发表的r s a 算法，它是以三个发明人的名字命 名的，后来又有椭圆算法e c c ，但常用的、成熟的公钥算法是r s a 。它与传统的对 称密钥算法有本质的区别，对称密钥算法常用的是d e s 算法，加解密时用的是同 一个密钥。而公钥算法利用的是非对称的密钥，即利用两个足够大的质数与被加 密原文相乘生产的积来加解密。这两个质数无论是用哪一个与被加密的原文相乘 ( 模乘) ，即对原文件加密，均可由另一个质数再相乘柬进行解密。但是，若想用 这个乘积来求出另一个质数，就要进行对大数分解质因子，分解一个大数的质因 子是十分困难的，若选用的质数足够大，这种求解几乎是不可能的。因此，将这 两个质数称密钥对，其中一个采用私密的安全介质保密存储起来，应不对任何外 人泄露，简称为“私钥”：另一个密钥可以公丌发表，这个密钥称之为“公钥。 公、私密钥对的用法是，当发方向收方通信时发方用收方的公钥对原文进行 加密，收方收到发方的密文后，用自己的私钥进行解密，其中他人是无法解密的， 因为他人不拥有自己的私钥，这就是用公钥加密，私钥解密用于通信；而用私钥 加密文件公钥解密则是用于签名，即发方向收方签发文件时，发方用自己的私钥 加密文件传送给收方，收方用发方的公钥进行解密。 但是，在实际应用操作中发出的文件签名并非是对原文本身进行加密，而是 要对原文进行所谓的“哈希”( h a s h ) 运算，即对原文作数字摘要。该密码算法也 称单向散列运算，其运算结果称为哈希值或称数字摘要，也有人将其称为“数 字指纹”。哈希值有固定的长度，运算是不可逆的，不同的明文其哈希值是不同的， 而同样的明文其哈希值是相同并且是唯一的，原文的任何改动，其哈希值就要发 生变化。数字签名是用私钥对数字摘要进行加密，用公钥进行解密和验证。 公钥证书和私钥是用加密文件存放在证书介质中，证书是山认证服务机构c 所签发的权威电子文档，c a 与数字证书等是公钥基础设施p k i 的主要组成机构和元 湖北工业大学硕士学位论文 素。 公钥密码算法使用两个密钥，其中一个用于加密( 加密密钥) ，另外一个用于 解密( 解密密钥) 。公钥密码算法具有如下特征： ( 1 ) 加密密钥与解密密钥在本质上不通的，也就是说如果仅仅知道密码算法 和加密密钥，而要确定解密密钥，在计算上是不可行的。 ( 2 ) 大多数公钥密码算法的加密密钥与解密密钥具有互换的性质。如r s a 算 法，密钥对中的一个用于加密，另一个用于解密。 1 4 3 公钥密码体制的数学基础 通观公钥密码算法，它们的数学基础是比较狭窄的。大多数公钥密码算法都 是基于以下三种数学难题之一的： 一是背包问题：给定一个互不相同的数组成的集合，要找出一个子集，其和为 n 。 二是离散对数问题：如果p 是素数，g 和m 是整数，找出x 使得g 。；m ( m o d p ) ： 还有一种方法，就是基于椭圆曲线上的离散对数问题。 三是因子分解问题：设n 是两个素数的乘积，则： ( 1 ) 分解n ： ( 2 ) 给定整数m ( 明文) 和c 【密文) 寻找d 满足m 。；c c m o d ) ： ( 3 ) 给定整数e 和c ，寻找m 满足m 。；c ( m o d n ) ： ( 4 ) 给定整数x ，判定是否存在整数y 满足j z y 2 ( m o d n ) 公丌密钥算法用密钥k 加密，用密钥k ：解密表示为：如图1 3 e x , ( 吖) = c d ( c ) = m 6 湖北工业大学硕士学位论文 图1 3 公丌密钥加密解密 f i g 1 3e n c r y p ta n dd e c r y p tw i t hp u b l i c k e y 1 5 椭圆曲线密码的研究现状及本文的主要工作 公开密钥密码的思想是在1 9 7 6 年山w d i f f i e 和m h e l l m a n 首先提出的。 为了克服私钥密码体制的两个主要缺陷一密钥分配效率低且不安全和消息数字签 名的不可靠，相关内容参看文献2 。d i f f i e 和h e l l m a n 为了解决密钥管理问题， 提出了一种密钥交换协议允许在不安全的媒体上通信双方交换信息，安全的达 成一致的密钥。公钥密码的安全性，依赖于数学问题的难解性。公钥密码的思想 与单向函数的概念密切相关。单向函数是这样的函数，计算起来相对容易，但是 反过来，即求逆却很困难。也就是说，己知j 计算函数，( x ) 的值很容易，但已知 厂( j ) ，却难计算出工。现有的椭圆曲线密码体制是从其它群中平移而来，并未产 生新型密码体制，而这种平移主要是对基于离散对数问题的密码体制，a t k i n 和 m o r r a i n 在文献中提出的思想及方法，将离散对数加密体制直接平移到椭圆曲线群 上，得到的密码体制将需要首先把待加密的明文转化为椭圆曲线上的点，而后才 能进行加密，这在实用上较为麻烦，为避免这个麻烦m e n e z e s 和v a n s t o n e 作了修 改，但是怎样把明文转变成椭圆曲线上的点依然是椭圆曲线密码的难题之一。 椭圆曲线密码体制的一个迷人之处在于，基于它的离散对数问题还没有亚指 数时问的攻击，并且由于椭圆曲线具有更小的密钥长度、更小的带宽、而且它的 实现速度更快，使得它更适合于功率和集成电路空问受限的应用场合“。在过去 的十多年里，椭圆曲线离散对数问题e c d l p ( e 1 1 i p t i cc u r v ed i s c r e t el o g a r i t h m p r o b l e m ) 受到全世界前沿科学家的极大关注。目前的研究热点在于如何加快椭圆 曲线上点的运算，特别是标量乘运算的速度，椭圆曲线签名算法运用于特殊签名 7 湖北工业大学硕士学位论文 的方案等。在学术界，1 9 9 7 年1 1 月w a t e r l o o 大学组织了一个专门的学术会议，研 究椭圆曲线离散对数问题，众多著名密码学家及数学家应邀参加。但直到目前， 在密码分析方面仍未取得实质性进展，这种情况持续时问越长，越使人们相信椭 圆曲线密码体制的安全性。“。 在2 0 0 4 年的信息安全国际会议上。曹珍富教授做的“密码理论中的若干问题” 的报告 8 中，介绍了能够代表当前密码学发展的新方向。其中提到公钥密码在信 息安全中担负起密钥协商、数字签名、消息认证等重要角色，已成为晟核心的密 码。 2 0 0 2 年，科技部高技术研究发展项目中，由清华大学微电子研究所丌展了关 于椭圆曲线告诉密码芯片的实现技术和e c c - i p 核关键技术的研究和实现完成了 基于特征2 的椭圆曲线密码芯片的全部设计，以及对给予素数域曲线椭圆曲线密码 的芯片集成技术的深入研究。 2 0 0 4 年底，北京天一集成研制的“w l a n 专用高速椭圆曲线密码算法芯片及i p 核( e c c ) ”项目获得信息产业部和财政部的立项。该项目针对椭圆曲线进行研究， 开发支持1 9 2 2 5 6 6 i t 模p 域上，任意可变曲线的e c c 公钥密码算法芯片系列产品。 这些都表明，我国在椭圆曲线密码体制上的研究和实现已经轰轰烈烈的丌展 起来。 目i j 国外对椭圆曲线密码研究最成功的是c e r t i c o m 公司。1 9 9 5 年开始，以 s c o t i v a n s t o n 。为首的加拿大w a t e r l o o 大学的几位密码学家成立了c e r t i c o m 研究 小组，c e r t i c o m 以推动椭圆曲线密码在商业领域内的广泛应用为主要目标，经过 十多年的研究，c e r t i c o m 开发出了在商业领域内高效、安全、低成本的实现e c c 技 术的方法。 本文第一章主要介绍了密码学术语和椭圆曲线密码体制的研究现状。第二章 讨论了椭圆曲线密码体制的建立，先介绍了椭圆曲线的定义和基本定理：然后讨论 了安全椭圆曲线选取方法：随机选取椭圆曲线的方法，给定椭圆曲线阶的选取方 法，w e l l 椭圆曲线选取方法；最后介绍了应用椭圆曲线密码的加密解密过程。在 第三章我们首先讨论了传统的数字签名协议，其次讨论了椭圆曲线数字签名，在 b 湖北工业大学硕士学位论文 已有的数字签名算法基础上作了改进，并且提出了带有消息恢复的椭圆曲线数字 签名算法 9 第2 章椭圆曲线公钥密码系统 2 1 椭圆曲线的定义及相关定理 关于椭圆曲线的详细理论见文献1 2 6 川2 。i 。在本文中，k 表示一个有限域。 本文中q 元有限域( 有时也用g h 咖表示) 。在密码学中：k 通常指是大素域z ，或特 征为2 的有限域，我们还约定p 总表示一个大于3 的素数，i 表示k 的代数闭包， 量上的射影平面p 2 ( k ) 是彪、 ( o ，o o ) 上的等价关系。”的等价类集合，其中， “”定义为( 五，k ，z ) ( 五，l ，乙) 当且仅当存在“k 使得 ( 五，z ，互) = ( 蟛，l ，以：) 包含( x ，y ，z ) 的等价类记为( j ：，y ：，z ：) 。形如下式的3 次齐次方程称为k 上的w e i e r s t r a s s 方程： y 2 z + a l 腕+ a 3 y z 2 = x + a 2 x 2 z + a x z 2 + 巳z 3 ( 2 1 ) 其中，q k ，i = 1 ，2 ，3 ，4 ，6 a 争f ( x ，y ，z ) = y 2 z + a l 朋眩+ 口3 y z 2 一x + 吗x 2 z + a x z 2 + a o z ，如果对所有满足 f ( x ，r z ) = o 的射影点尸= ( x ：，：z ) p 2 ( i ) ，f 在p 点的3 个偏导数 o f i o x ，o f 8 y ，o f t o z 必不全为0 ，刚称w e i e r s t r a s s 方程( 2 1 ) 是平滑的。为了方 便，常将w e i e r s t r a s s 方程( 2 1 ) 以仿射坐标j = x y ，y = y z 的形式书写为 y 2 + 4 i x y + a ，y = j + a 2 x 2 + 4 x + a o ( 2 2 ) 相应的椭圆曲线e 是方程( 2 2 ) 在仿射平面p 2 ( i ) 中的所有解及无穷远点0 组成的 集合。即 e = ( 五j ，) k 髟，2 + 8 l x y + a 3 y - - - x 3 + 口2 x 2 + a 4 x + a 6 u 。) ( 2 3 ) 以后常用ek 表示k 上的椭圆曲线e 。ek 中两个仿射坐标均属于k 的点及无穷 远点。均称为，置的k 一有理点，e l k 的所有k 一有理点组成的集合记为暑( k ) ，即有： 0 湖北工业大学硕士学位论文 e ( x ) = ( 而y ) k x 膏) ，2 + n l x y + a 3 y = x 3 + a 2 # + a 4 抖口6 e l 。 ( 2 4 ) 如果存在，r ，j ，f 足，h o 使得变量替换( x ，y ) 一似2 x + ，“3 y 十以2 肛+ f ) 将k 上的 两条椭圆曲线e 变为毛。其中 巨：y 2 + 口i x y + a j y = 工+ 口2 j 2 + q 工+ 口6 ( 2 5 ) 丘：y 2 + a t x y + a j y2 ，+ a 2 x 2 + a 4 x + a 6 ( 2 6 ) 则局、易称作是同构的，并记为q k - 兰e 20 ，当k 的特征c 靠矿( 七) 2 ，3 时研j i ： 可在同构意义下化成如下简单形状 e ： y 2 = ，+ “+ 6 ，a , b k ， ( = 一1 6 ( 4 a + 2 7 b 2 ) o ，( = 一1 7 2 8 ( 4 a ) 3 ，( e 其中a ( e 9 是椭圆曲线e 。的 判别式，_ ，( 是椭圆曲线。的j 一不变量。 下面先看一下实数平面上的椭圆曲线 方程y 2 = ，+ 甜+ 6 的所有解( x ，y ) r x r ，加上无穷远点0 ，组成实 数上的平滑椭圆曲线，其中a , b r ，满足4 a 3 + 2 7 b 2 0 。下图2 1 画出 了椭圆曲线y 2 = p 一4 x ，加法运算的凡何图： - 2彳 之2 训 一 - 2 图2 1 实数上椭圆曲线的点加运 f i g 2 1a d d i t i o no fp o i n t so i le l l i p t i cc u r v eo v e rr e a lf i e l d 设p ，q 是椭圆曲线： y 2 = 一+ 甜+ 6 上的两点，j p = ( ，一) ，q = ( ，y ：) 。 无穷远点d 。在e 上定义加法运算，使 为a b e l 群。 湖北工业大学硕士学位论文 l 、p + 0 = p 2 、- - 0 = 0 3 、如果p = ( ，乃) d ，那么一p = ( ，一只) ( 逆元) 4 、如果尸= - 0 ，那么p + o = 0 5 、如果p 0 ，q 0 ，p q 定义p + q = r ，r = ( ，乃) 定义通过p ，q 的直线为：y = 2 x + v ，l 与e 交与第3 点月。月关于x 轴对称的点为 r ，其中r k ( ，一乃) 很容易计算出： 卫= z 出 毛= a 2 一 一t乃= a ( 五一毛) 一y j ( 8 ) 工2 一j - 6 、如果p 0 ，q 0 ，p = q ，假设h 0 ，否则同4 。利用微分知识过p 点的切线 l ：y = a x + v 斜率为 2 y 坐：3 2 2 + 口 a x 咖3 2 2 + 口 凼 2 y 故切线l 的斜率为 a ：坐 2 毛= 五2 2 x j 乃= 五( 玉一而) 一y i 加法运算的有如下性质： l 、加法在集合e 上封闭： 2 、加法是可以交换的： 3 、d 是加法的单位元： 4 、e 上的每个点有关于加法的逆元： 5 ，加法是可结合的。代数证明比较繁杂，用几何结果可以简化证明 1 2 湖北工业大学硕士学位论文 具体证明过程见参考文献 假设有限域c 上的同余方程 y p + a x + b ( m o d ) p 的所有解0 ，y ) ，与无穷远点d ，构成有限域暑上椭圆曲线， 其中口，6 ，r 4 a 2 + 2 7 b 3 o 有限域c 上椭圆曲线加法定义与实 数上的定义相同，只是没有直观的几何解释。定义的加法运算使 仍然是a b e l 群。参见文献”。叫 定理2 1 i z l ：( h a s s e ) 设e 是有限域上的椭圆曲线，毒i # e ( f q ) = q + l - t ，贝i j 2 再，其中群烈艺) 为e ( c ) 的阶。 定理2 2 ：( t a s s e l l s ) 设e 是乙上的椭圆曲线，p 3 的素数，那么存在j 下整数n ，r 1 2 ，使得 e ( 乙) 兰乙乙，其中n 2 1 n ，n 2 i q 一1 定理2 3 ： 对任意h 2 打，to ( m o d p ) ，存在上的椭圆曲线e ( ) ，使得 撑e ( 只) = g + 1 一t 定理2 4 ： 设p 是一个素数，一d 是一个负基本判别式，若整数x ，y 满足4 p = 工2 + 毋2 ，则 臀。对s o m o d p 仅有单根，且全部在z p 中，对其任意根矗，必存在j 一不变量为矗 的椭圆曲线e z 。满足： 4 # e ( z 。) = ( j 一2 ) 2 + d 少2 湖北工业大学硕士学位论文 2 2 椭圆曲线的选取 从现有的椭圆曲线密码攻击理论，我们选择的安全椭圆曲线必须满足恤3 ”。： l 、曲线的阶u 必须被一个大素数r 整除。 2 、曲线的阶u = 撑e ( g ) g ，这类椭圆曲线已经被攻击，称为“反常曲线” 3 、r 不整除q ”一i ，其中l ，= 1 ，2 ，3 1 0 方法i ：随机选取椭圆曲线 1 ，随机选择椭圆曲线方程参数日，b z ，p 3 的素数，验证4 矿+ 2 7 b z 0 ，否则 重新选择参数。 2 、, 用s c h o o f 算法1 ，计算椭圆曲线y = ，+ a x + b 的阶u = 拌e ( z ，) ，如果u = p ，转l 3 ，如果这个阶u 不被一个大素数r 整除，则转l 4 ，验证如果r 整除p 一1 ，i v = l ，2 3 1 0 ，转l 5 ，输出椭圆曲线e 方法2 ：指定阶的椭圆曲线的构造。 方法2 。l 6 l ：输入大素数q 。，g ：的指走二进制长度m ，n 。输出p 和吼q 2 阶椭圆曲 线e 及q ，9 2 1 、任意取定负奇基本判别式一d 使 ( 一d ) 适当小。( 见文献”1 中的表1 ) 2 、确定玉，h ，及而，儿的取值范围，使2 + 砂2 及而2 + 锄2 分别具有长度 m + 2 弗 3 、在第2 步确定的范围中取随机选取奇数玉，咒 4 、令g i = ( 玉2 + 现2 ) 4 ，检测叮i 的素性，若g 不是素数，转第3 步。 5 、在第2 步确定的范围中选取不同奇偶的随机数毛，儿 6 、令q 2 = 而2 + 2 ，检测q ：的索性，若q ：不是素数，转第3 步 7 、计算钾i 口2 = ，+ 毋2 ，其中工= x t x 2 + d y i y 2 ，y = z l 乃一儿 8 、令4 p = o + 2 ) 2 + d y 2 。对p 做素性检测，若p 不是素数，转第3 步。 1 4 湖北工业大学硕士学位论文 9 、计算h d ( j ) 并求出h o ( j ) e 0 m o d p 的一个根d ，厶0 ，1 7 2 8 r o o d p 1 0 、构造以厶为j 一不变量的椭圆曲线：z z p ：y 2 = 一+ 西+ 6 。其中令 k = j d ( 1 7 2 8 一j 0 a = 3 k b = 2 k l l 、任意取不满足椭圆曲线方程研z ，：y 2 = 矿+ 敛+ 6 的一点d ，作为无穷远 点 1 2 、随机选取c z p ，构造椭圆曲线：e z ，：y 2 = ，+ c 2 a x + c 3 6 1 3 、取p e i z ，) ，p 0 ，若吼j p o ，q 2 p o r q i q 2 p = d ，输出p ，吼，g z ，e 。 否则，转第1 2 步 方法2 。2 ： 1 、在【p + l 一2 石，p + l + 2 _ 】中选取一个阶“，“p 2 、如果这个阶被个大素数r 整除则转l 3 、验证如果r 整除- 1 ，转1 4 、计算t = p + l 一“，及d = 4 p f 2 5 、计算 ，d “尸，并求出h o ( j ) = o m o d ，的一个根厶，其中 厶o ，1 7 2 8 m o d p 6 、构造以j o 为j 一不变量的椭圆曲线：可z ，：y 2 = ，+ 似十6 ，其中令 k = j o 0 7 2 s - i o a = 3 k b = 2 k 7 输 n 椭圆曲线e 方法3 ：只上椭圆曲线的选取 利用w e i l 方法，这个方法可以用于选取f 上的椭圆曲线( 当m 被一个小，整除 的时侯，乃包含在( 中) 1 随机选取椭圆曲线e ：y 2 = ，+ 甜+ 6 ，其中b 0 ，r a ，6 乃 2 、计算珊= 捍e ( f ，) ，用穷尽搜索e 上的点的方法 3 、令t = 碍7 + l 一缈且令c = 州，计算递归式序列( 屹j 的第t 项， 湖北工业大学硕士学位论文 = 2 ，巧= f ，= f 屹一- 一2 - 】，月2 令“= 群( c ) = 2 1 + 1 一屹， 4 ，如果u 不被大素数r 整除，转1 5 、验证如果r 整除p v l ，其中i ，= l ，2 ，3 。l o ，转1 6 ，输出椭圆曲线 2 3 椭圆曲线公钥密码系统的建立 椭圆曲线域参数r = ( g ，口，b ，p ，n ) 。其中：整数叮表示个有限域c ：元素 a , b 只：p 表示一个基点：冉为素数且等于点p 的阶。 选取的该椭圆曲线上的一个点d p = q 作为基点，那么给定一个整数d ，计算 d p = q 是容易的但是，要从q 点及p 点推导出整数d ，则是非常困难的，即没有 在多项式时问内求解的算法，这就是椭圆曲线离散对数问题。 系统建立： 选取一个域，一个定义在上的椭圆曲线e 和e 上的一个素数阶n 的点p 。点p 的坐标用( x p ，y ，) 表示。 在使用的时候，先产生密钥a 执行： l 、随机选取整数d 2 、计算点q = d p 3 、 的公钥包含点q 4 、a 的私钥是整数d 椭圆曲线加密体制 加密过程 当b 发送信息m 给a 时，b 执行： l 、查找a 的公钥q 2 、将数据m 表示成域元素m c 6 湖北工业大学硕士学位论文 3 、随机选取整数k 4 、计算点( ，y ) = k p 5 、计算点( 毛，乃) = 坦 6 、判断如果暑= o m o d n ，转3 7 、计算c = 8 、b 把加密数据( ，y 。，c ) 传送给 解密过程 a 接到密文数据( 玉，m ，c ) 后，执行解密过程 l 、用私钥d ，计算点( 五，y 2 ) = d ( 五，乃) 2 、计算所；一，恢复出明文数据n 2 4 小节 本章讨论了椭圆曲线密码体制的建立，先介绍了椭圆曲线的定义和基本定理： 然后讨论了安全椭圆曲线选取方法：随机选取椭圆曲线的方法，给定椭圆曲线阶的 选取方法，w e il 椭圆曲线选取方法：最后介绍了应用椭圆曲线密码的加密解密过 程。 7 湖北工业大学硕士学位论文 第3 章基于椭圆曲线密码系统的数字签名方案 数字签名是密码学的重要问题之一，它是传统文件手写签名的模拟，能够实 现用户对电子消息的认证。数字签名在信息安全，包括身份认证、数据完整性、 不可否认性及匿名性等方面，特别是在大型网络安全通信中的密钥分配、认涯及 电子商务系统中，都具有重要作用。本章主要讨论椭圆曲线密码系统在数字签名 中的应用。并提出三种改进方案。 3 1 数字签名 3 1 1 数字签名的基本概念 现实生活中的很多场合如政治、军事、外交及商业等场合中，都需要使用手 写签名( 或印章) 对所签订的文件、命令，条约等进行确认。当签署文件的双方对文 件的内容发生争执，根据签署文件时留下的签名，第三方可以对签名进行检查以 便对争执进行调解。 随着计算机网络的发展。出现了对类似于数字签名的电子化签名的需求。如： 在电子商务中，某一个用户在下订单时，必须能够确认该订单确实为用户发出。 并且，在用户与商家发生争执时，必须能够为双方关于订单进行仲裁 使用了密码技术的数字签名正是一种类似于传统的手书签名或印章的电子标 记，它可以达到与手写签名类似的作用，即：使用数字签名，在信息通信过程中， 接收方能够对公j 下的第三方证明其收到的信息是真实的，且确实由发送方发送过 来的，同时数字签名还能够保证发送方事后不能根据自己的利益来否认他所发 送过的报文，而接收方也不能根据自己的利益来伪造报文或签名。 湖北工业大学硕士学位论文 手写签名与数字签名的主要差别在于： ( 1 ) 签署文件方面。手写签名是所签文件的物理部分而数字签名则不是，所以 所使用的数字签名方案必须设法把签名“绑”到所签文件上。 ( 2 ) 验证方面。手写签名是通过与真实的手写签名相比较来验证的。而数字签名 能通过一个公丌的验证算法来验证。 ( 3 ) 拷贝方面。手写签名不易拷贝，因为文件手写签名的拷贝易与原文件区别丌 束。而数字签名容易拷贝，因为文件的数字签名的拷贝与原文件一样。这个 特点要求我们必须阻止一个数字签名消息的重复使用一个数字签名方案由 两部分组成：签名算法( s i g n a t u r ea l g o r i t l u n ) 和验证算法( v e r i f i c a t i o n a l g o r i t h m ) 签名者对消息m 使用签名算法记作s i g ( m ) ，为了强调用户a 或所 使用的签名密钥k ，签名算法也记为s ig i ( m ) ，进行签名得到数字签名s = s i g k ( m ) 对消息m 的签名：可以通过验证算法( 记作v e r ( s ，m ) ) ，验证算法返回的结果为 布尔值“真( t r u e ) ”或“假( n a s e ) ”，即 。、l t r u e j = s i g ( m ) 附( ) 2 1 乃居。跑( ：) 在