（应用数学专业论文）基于椭圆曲线密码算法的代理签名体制.pdf

西南交通大学硕士研究生学位论文 第l 页 摘要 代理签名体制在电子商务中的应用很广泛，目前的代理签名体制安全性 主要是基于求解大数因子分解问题的疆难性或求解离散对数问题豹困难性。 随着大整数分解和并行处理技术的进展，公钥密码体制使用的密钥长度随着 增长，这将使其运算速度变慢，密码系统更加复杂。同时，目前也存在许多 针对大整数分解密码体制和离散对数密码体制的攻击算法。 本文简要介绍了代理签名体制概念与性质，并对其中比较典型的两种代 理签名体制进行分析，指出其在密钥长度，处理速度，安全性能等方面存在 着缺点。 本文还对椭圆曲线密码体制和r s a 及基于离散对数问题的密码体制进 行分析比较，明确了椭圆曲线密码体制在安全性能、密钥长度、处理速度、 系统参数、带宽要求等方面具有独特优势。本文正是利用椭圆曲线密码算法 的这些优势，构造出椭圆曲线代理签名体制，并对该体制进行分析论证。该 体制的安全性基于椭圆盛线离散对数问题的难解性，它与前面两种代理签名 体制相比，具有安全性高、密钥长度小、处理速度快、系统参数小、带宽占 用低等优点。 现有的代理签名体制都是假设通信信道安全。其实，在实际应用中，通 信信道并不总是安全的，本文为了解决这个问题提出了种新的身份识别体 制，该体制的安全性基于椭圆曲线离散对数问题的难解性，同时还具有零知 识证明的特性，同般的身份识别体制相比，它具有安全性能更高，密钥长 度小，处理速度快，系统参数小，带宽占用低等优势。该体制也可独立出来 用于解决一般的身份认证问题。 关键词：代理签名：离散对数问题：公钥密码；零知识证明 西南交通大学硕士研究生学位论文第1 l 页 a b s t r a c t p r o x ys i g n a t u r es y s t e m sh a v eg r e a ta p p l i c a t i o n si ne - b u s i n e s sw h o s es e c u r e t y i sb a s e do nt h ed i f f i c u l t yo fi n t e g e rf a c t o r i n go rt h ed i f f i c u l t yo fs o l v i n gt h e c o m m o nd i s c r e t el o g a r i t h mp r o b l e m ，a st h ed e v e l o p m e n to fi n t e g e rf a c t o r i n ga n d t h ep a r a l l e lc o m p u t i n gt e c h n o l o g y , t h ep u b l i ck e yc r y p t o g r a p h i e su s e dt o d a yh a v e t oe n l a r g ek e y s i z ew h i c hs l o w st h e i rs p e e da n di n c r e a s e st h e i rc o m p l e x i t y a l s o ， t h e r ea r em a n ya t t a c k i n gm e t h o d st os o l v et h eg e n eo fa b i gi n t e g e ra n dt h ec o r n m o nd i s c r e t el o g a r i t h mp r o b l e m t h i st h e s i si n t r o d u c e st h ec o n c e p ta n dt h ep r o p e r t yo fap r o x ys i g n a t u r es y s t e r n ，w ea n a l y s et w oc o m p a r a t i v e l yr e p r e s e n t a t i v es y s t e m sa n df i n dt h a tt h e r e e x i s ts o n i cd i s a d v a n t a g e si nt h el e n g t ho ft h e i rk e y s ，t h es p e e do f d a e i rd i s p o s a l a n dt h e i rs e c u r i t y t h i st h e s i sa l s oc o m p a r e sr s aa n dt h ec r y p t o s y s t e mb a s e do nd i s c r e t el o g a r i t h mp r o b l e mw i t he c c ( e l l i p t i cc u r v ec r y p t o s y s t e m ) ，f r o mt h ec o m p a r i s o nw e c a r ld r a wac o n c l u s i o nt h a te c ch a sap a r t i c u l a ra d v a n t a g ei nt h es e c u r i t y , t h e l e n g t ho fk e y ，t h es p e e do fd i s p o s a l ，t h es y s t e mp a r a m e t e ra n dt h ed e m a n do f b a n d w i d t h t h et h e s i sm a k e su s eo ft h o s ea d v a n t a g e sa n dc o n s t r u c t st h ep r o x y s i g n a t u r es y s t e mb a s e do ne c c w ea l s oa n a l y s ea n dd e m o n s t r a t et h es y s t e m w h o s es e c u r i t yi sb a s e do ne c d l p ( e 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 ) c o m p a r i n gw i t ht h et w of o r m e rs y s t e m s ，o u rs y s t e mh a st h em e r i t so fi m p r o v e d s e c u r i t y , m u c hl e s sk e y l e n g t h ，f a s t e rs p e e do fd i s p o s a l ，m u c hl e s ss y s t e mp a r a m e t e ra n dm u c hj e s sd e m a n do fb a n d w i d t h a l lo ft h ee x i s t i n gp r o x ys i g n a t u r es y s t e m ss u p p o s et h ec o m m u n i c a t i o n sc h a n n e lm a i n t a i ns e c u r ei nt h e i rs y s t e m s i nf a c t ，t h ea b s o l u t es e c u r ec h a n n e l d o e s n te x i s t t os o l v et h es e c u r i t yp r o b l e m ，w ep r e s e n tan e wa u t h e n t i c a t i o n p r o t o c o lw h o s es e c u r i t yi sb a s e do nd c d l p a tt h es a m et i m e ，t h es y s t e mh a st h e c h a r a c t e r i s t i co fz e r ok n o w l e d g ep r o o f c o m p a r ew i t ht h eo t h e rs y s t e m s ，t h e s y s t e mh a st h em e r i t so fi m p r o v e ds e c u r i t y , m u c hl e s sk e y l e n g t h ，f a s t e rs p e e do f d i s p o s a l ，m u c hl e s ss y s t e mp a r a m e t e ra n dm u c hl e s sd e m a n do fb a n d w i d t h t h es y s t e ma l o n ec a l la l s ob ea p p l i e dt or e s o l v et h en o r m a la u t h e n t i c c a t i o n p r o b l e m k e y w o r d s ：p r o x ys i g n a t u r e ；d i s c r e t el o g a r i t h mp r o b l e m ；c r y p t o g r a p h y 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 本文工作研究背景和意义 网络的应用日益普及，其应用涉及政府、军事、文教、商业、金融等诸 多领域。如商业经济系统、政府机关信息系统、银行业务系统、证券业务系 统、科研数据传输等，这些系统都涉及到机密信息的传输与存储。 如何保证这些机密不泄露，就是网络安全研究工作需要解决的问题。网 络安全应当满足以下性质：身份真实性、信息机密性、信息完整性、服务可 用性、不可否认性、系统可控性、系统易用性、可审查性等等。数字签名技 术是网络安全的重要手段之一，它可以保证信息的完整性，鉴别发送者身份 真实性与不可否认性：再运用数字签名本身的基础技术如加密技术，就可以 保证信息机密性；如再运用审计日志的方法，则可完成可审查性的功能。 数字签名是当前网络安全领域的研究热点。特别是在电子商务、电子银 行、电子政务等应用领域，数字签名是其关键技术之一，在社会生活的各个 领域也有极其广阔的应用前景。美国、欧盟分别在2 0 0 0 年前后，正式颁布了 数字签名法律。 1 9 9 6 年，m a m b o 、u s u d a 和o k a m o t o 提出了代理数字签名的概念，并给 出了解决这个问题的一种方法。代理签名是数字签名中的一种特殊的签名形 式，由于它在实际应用中起着重要作用，所以一提出就受到了广泛的关注， 国内外许多学者对其进行了深入的探讨与研究。迄今为止，人们已经提出了 多种代理签名方案，这些代理签名方案安全性都是基于大整数因子分解的困 难性或基于离散对数问题的难解性。借助不断提高的计算机技术，人们经过 不懈的努力，目前对这两类数学问题的求解能力较过去有了很大的提高。这 迫使r s a 【7j 体制中使用的模数和基于有限域上离散对数问题的公钥密码体制 中有限域的大小越来越大。对这两类密码体制，过去5 1 2 比特大小的密钥己 足够安全，但现在就不能保证它的安全性。为了保证足够的安全性，目前一 般不得不使用1 0 2 4 比特或2 0 4 8 比特大小的密钥。如此以来，安全性基于前 二者的代理数字签名体制就必须进一步增长密钥长度，这将使安全性基于这 两种数学问题的代理签名体制的运算速度更慢，系统也更加复杂。 西南交通大学硕士研究生学位论文第2 页 椭圆曲线密码体制，即基于椭圆睦线离散对数问题的各种公钥密码体制， 最早于1 9 8 5 年由k o b l i t z t 8 】和m i l l e r t 9 1 分别独立地提出，它是利用有限域上的 椭圆凹线有限循环群代替基于离散对数问题密码体制中的有限循环群所得到 的一类密码体制。 在椭圆曲线密码体制中，1 6 0 比特长的密钥所具有的安全性和前两类体 制中1 0 2 4 比特长的密钥所具有的安全性相当，2 1 0 比特与2 0 4 8 比特相当等。 我们在后面的章节中，可以看到椭圆曲线密码体制的诸多优点。 目前，人们普遍认为，椭圆曲线密码体制将会成为2 1 世纪最主要的公钥 密码体制。就目前这种快速发展的电子信息时代，要对它的价值做出估计， 只需看一下整个公钥密码理论在这个时代所发挥的作用就可以了。它的应用 主要在银行结算、电子商务和通讯等领域，以后必将会扩展到人们社会生活 的各个层面。因此，由椭圆曲线密码理论所发展成的技术必将具有无限的商 业价值。 本文利用椭圆曲线密码算法的优点，提出了一种新的代理签名体制，它 由两个协议组成，第一个协议主要针对只有一个代理签名者和一个原始签名 者鲶情形而设计的，第二个协议针对有许多个代理签名者和一个原始签名者 的情形而设计的，用户可以根据实际情况选择符合自己要求的方案。本文提 出的体制更符合当前网络环境的要求，同时由于椭圆曲线资源丰富，同一个 有限域上存在着大量不同的椭圆曲线，这就为该体制的安全性增加了额外的 保证，也为软、硬件实现带来了方便。 椭圆曲线具有丰富的群结构和多选择性，并可在保持与r s a d s a 体制 同样的安全性能的前提下缩短密钥长度，网络传输中占用带宽小，因此本文 提出的代理签名方案在无线网络、集成电路卡、w e b 服务器等方面的应用具 有广阔的前景。 现有的代理签名体制都是假设通信信道是安全的，可是在现实生活中， 绝对安全的信道是不存在，这就对代理签名方案的实现构成一个威胁，本文 针对这个问题，提出了一个新的身份识别方案，它除了使用前面介绍的椭圆 曲线算法工具，还使用了零知识证明工具。椭圆曲线密码算法的应用，使得 我们提出的身份识别方案与其它的身份识别方案相比f 现有的身份识别体制 安全性都是基于大整数因子分解的困难性或基于离散对数问题的难解性1 ，具 有了安全性高、计算量小和处理速度快、存储空间占用小、带宽要求低等优 点；同时零知识证明的应用，很好地符合了本文代理签名体制的要求，即要 求代理签名人和原始签名人的身份不能暴露，我们提出的身份识别方案在示 西南交通大学硕士研究生学位论文第3 页 证者( 在我们提出的代理签名方案中，他还扮演着代理签名人的角色1 在向验 证者( 在我们提出的代理签名方案中，他还扮演着原始签名人的角色) 证明自 己的身份时，并没有向验证者泄露任何有关自己身份的任何有用的信息，这 就很好地满足了代理签名方案的要求。 本文提出的方案由两个协议组成，第一个协议是串行协议，第二个协议 是并行协议，用户可以根据不同的网络环境来确定使用哪个协议。 本文提出的身份识别方案也可以独立出来用于一般的身份认证问题，同 时由于椭圆曲线具有丰富的群结构和多选择性，并可在保持与r s a d s a 体 制同样的安全性能的前提下缩短密铜长度，网络传输中占用带宽小，因此本 文提出的身份认证方案在无线网络、集成电路卡、w e b 服务器等方面的应用 具有广阔的前景。 1 2 本文研究方向和主要研究内容 代理签名在商业中有着非常重要的应用，所以它日益引起人们的关注， 国内外许多学者对其进行了深入的研究，提出很多的方案，但如何使其更好 地满足当前不1 可网络环境的要求，这也是急需解决的问题，由于现有的代理 签名体制，安全性都是基于大整数分解的困难性或离散对数问题的难解性， 随着大数分解技术和并行处理技术的进展，基于这两类数学问题的公钥密码 体制就必须增长密钥长度以保证足够的安全性，如此一来，也带来了处理速 度变慢，系统更加复杂等缺点，基于这两类密码体制的代理签名方案也就不 能很好地满足当前网络环境对安全性高，处理速度快，带宽占用低等方面的 要求。 本文主要的研究工作：保证原有代理签名体制的安全性不降低的情况下， 提高其运算速度，降低其密钥量，降低系统的复杂性。本文首先对e c c 、r s a 、 基于离散对数问题的公钥密码体制进行比较分析，在比较分析中我们了解到 e c c 是目前已知的公钥密码体制中能够提供最高比特安全强度的一种公钥 密码体制。它在保证与后两者具有同样安全的条件下，具有计算量更小和处 理速度更快、存储空间占用更小、带宽要求更低等优点，然后本文利用这些 优点，提出了一种新的代理签名体制并对其进行分析论证，它与前两种体制 相比，具有密钥量小，安全性高，私钥密钥对生成快等优点，而且它对带宽 的要求低，这就使得它在无线网络领域具有更加广泛的应用前景。 本文还针对现有的代理签名体制存在的安全信道问题，提出了一种解决 方案，它主要是通过身份认证的方式来解决，我们提出的身份认证方式，与 西南交通大学硕士研究生攀位论文第4 页 一般的身份认证方案相比，具有计算量更小和处理速度更快、存储空间占用 更小、带宽要求更低等优点。 本论文由六部分组成。第一章是绪论，介绍有关研究背景及国内外研究 现状：第二章介绍代理签名体制的概念及性质，并对两种比较典型的代理数 字签名体制进行分析。指出其不足，提出应用椭圆曲线密码算法进行改进的 思路：第三章简要介绍椭圆曲线密码体制( e c c ) ，并把e c c 、r s a 以及安全 性基于离散对数问题难解性的密码体制进行比较分析，指出e c c 比后两者在 安全性，密钥长度，处理速度，带宽占用等方面具有更大的优势：第四章主 要是结合代理数字签名和椭圆曲线密码体制二者的特性，提出了椭圆曲线代 理数字签名体制，并给出了该体制鲍具体实现过程，该体制与前两种体制相 比，具有安全性更高，密钥量更小，处理速度更快，系统参数更小，带宽要 求更低等优点。第五章主要是结合零知识证明理论和椭圆曲线密码体n - - 者 的特性，提出了椭圆曲线身份识别协议，这部分内容主要是为了解决现有的 代理数字签名体制通信信道存在的安全性问题而提出的，该协议与一般的身 份认证协议相比，具有安全性更高，密钥量更小，处理速度更快，系统参数 更小，带宽要求更低等优点。最后是结论部分，对本文的研究工作进行总结， 并对今后进一步的研究工作提出一些建议 1 3 本文主要研究成果 本文主要在以下方面进行了研究并取得了相应的成果： f 1 1 结合椭圆曲线密码算法的特性及代理签名的特点，设计了一种安全的 椭圆曲线代理数字签名体制。本文提出的代理数字签名体制与安全性建立在 求解大整数因子分解的困难性或求解离散对数问题的困难性之上的代理数字 签名体制相比，具有安全性能更高，计算量小和处理速度快，存储空间占用 小，带宽要求低等优点。该体制还节省存储空间，节省处理时间，能够适应 未来更高安全的需求，而且生成私钥公钥对很方便。另一方面，椭圆曲线资 源丰富，同一个有限域上存在着大量不同的椭圆曲线，这就为该体制的安全 性增加了额外的保证，也为软、硬件实现带来了方便。 ( 2 ) 作者还结合零知识证明的特点，提出了一种新的椭圆曲线身份识别协 议。现有的代理签名体制都是假设通信信道是安全的，我们知道，在实际生 活中，绝对安全的通信信道是不存在的针对这种情形，作者根据零知识证 明的特点，同时利用椭圆曲线密码算法的优点，提出了安全性建立在求解椭 西南交通大学硕士研究生学位论文第5 页 圆曲线离散对数问题困难性之上的零知识证明身份识别体制，该体制也可独 立出来用于解决一般的身份识别问题。与一般的身份识别体制相比，该体制 具有计算量更小和处理速度更快，存储空间占用更小，带宽要求更低等优点。 同时椭圆曲线具有丰富的群结构和多选择性，并可在保持与r s a d s a 体制 同样的安全性能的前提下缩短密钥长度，网络传输中占用带宽小，因此本文 提出的身份认证方案在无线网络、集成电路卡、w e b 服务器等方面的应用具 有广阔的前景。 西南交通大学硕士磺究生学位论文第6 页 第2 章代理数字签名 2 1 数字签名的概念 目前，通信双方在网络上交换信息时，如何防止伪造和欺骗已经成为头 等重要的课题，特别是随着电子商务、电子货币的推广应用，如何解决这一 问题就显得更加迫切。公钥加密或私钥加密只能用来保护通信双方免受第三 方的攻击，然而它们无法防止通信双方的互相攻击。签名起到了认证、核准 及生效的作用，传统上都采用手写签名或印鉴。随着信息时代的发展，人们 希望通过数字通信网进行迅速的、远距离的贸易合同的签名，于是数字签名 法便应运而生，并开始用于商业通信系统，诸如电子邮件、电子转账、办公 自动化等系统。 数字签名与传统的手写签名的主要区另4 在于： ( 1 ) 签署文件方面一个手写签名是所签署文件的物理部分，而一个数字 签名并不是所签署文件物理部分，所以所使用的数字签名方案必须设法把签 名“绑”到所签文件上。 ( 2 ) 验证方面 一个手写签名是通过和一个真实的手写签名相比较来验 证的，这种方法不是一种很安全的方法。相对而言比较容易伪造。而数字签 名畿透过一个公开的验证算法来验证，这样任何人都能验证一个数字签名。 安全的数字签名方案能够阻止伪造签名的可能性。 ( 3 ) “拷贝”方面一个手写的签名是不容易拷贝的，因为一个文件的手 写签名的拷贝通常容易与原文件区别开来。而一个数字签名容易拷贝，因为 一个文件的数字签名的拷贝与原文件一样。这个特点要求必须阻止一个数字 签名消息的重复使用，一般通过要求消息本身包含诸如日期等信息来达到阻 止重复使用签名的目的。在某种意义上，数字签名比传统的手写签名或印鉴 更为有效。因为当手写签名的文件很长时，很难保证每页内容均不会被改动 或替换，而数字签名则能保证这一点。 一个签名方案至少应当满足以下三个条件： ( 4 ) 签名者事后不能否认自己的签名： 西南交通大学硕士研究生学位论文 第7 页 ( 6 ) 接收者能验证签名，而任何其他人都不能伪造签名； ( c ) 当双方关于签名的真伪发生争执时，第三方能解决双方之间发生的争 执。 数字签名是对以电子消息存贮的消息进行签名的一种方法。公钥密码体 制的诞生为数字签名的研究和应用开辟了一条广阔的道路。根据接收者验证 签名的方式可以将数字签名分为直接数字签名和仲裁数字签名两大类【1 0 】。从 计算能力上来分，可以将数字签名分为无条件安全的数字签名和计算上安全 的数字签名。现有的数字签名大部分都是计算上安全的，诸如r s a 数字签名 、e 1 g m a l 数字签名【1 2 j 等等。所谓计算上安全的数字签名是指任何伪造者 要想伪造签名者的签名是计算上不可行的。无条件安全的数字签名1 1 3 ) 在理论 上篚代替计算上安全的数字签名，但在实际应用中由于效色巳太低而不鹾被应 用。从签名者在一个数字签名方案中所能签的消息数来分，可以将数字签名 分为一次数字签名和非一次数字签名【“】。一次数字签名方案只能签一个消 息，如果签两个或两个以上不同的消息。伪造者就能伪造签名。一次数字签 名方寨类似于一次一密密码方案的情况，它往往具有很强的安全性。根据数 字签名方案中的验证方程是隐式或显式。可以将数字签名分为隐式数字签名 和显式数字签名。现有的数字签名方案大部分是显式数字签名。也可以根据 数字签名的功能将数字签名分为普通数字签名和具有特殊性质的数字签名等 等。 一个数字签名方案包括两个部分：签名算法和验证算法。通信者a l i c e 能够使用一个( 私有的) 签名算法s i g 来为消息x 签名，签名结果s i g ( x ) 能使用 一个公开的验证算法v e r 得到验证。给定数据对0 ，y ) ，验证算法根据签名是 否有效而返回该签名为“真”或“假”的结果。 下面给出签名方案一个正式的定义。 定义2 1 一个签名方案是一个满足下列条件的五元组( 尸4 j ，功： 1 p 是由所有可能的消息组成的一个有限集合。 2 一是由所有可能的签名组成的一个有限集合。 3 k 为密钥空间，它是由所有可能的密钥组成的一个有限集合。 4 对每一个七k ，有一个签名算法s i g k s 和一个相应的验证算法v e r t v 。对每一个消息x p 和每一个签名y 爿，每一个s i g k ：p 爿和v e t t ： p x a - - - + t r u e j a l s e 都是满足下列条件的函数： 西南交通大学硕士研究生学位论文 第8 页 v 吨加 淼；：黧 由z 尸和y c a 组成的数据对0 ，y ) 称为签名消息。 对每一个七斯讯和v e r k 应该是多项式时间函数。”“是公开的函数， 而s i g k 是保密函数。给定一个消息，除了签名者a l i c e 之外，任何人去计算 使v e r ( x , y ) = t r u e 的数字签名y 应该是计算上不可行的( 注意，对给定的z ，可能 存在不止一个y 满足要求，这要看函数v e r t 是如何定义的) 。如果敌手o s c a r 能够计算出使得v e r 0 , y ) = t r u e 的数据对0 ) 而事先又没有被a l i c e 签名，则签 名y 称为伪签名。非正式地，一个伪造的签名是由a l i c e 之外的其他人产生 的一个有效签名。 渣息签字与泄息加密有所不同，消息加密和解密可鹾是一次性的，它要 求在解密之前是安全的；而一个签字的消息可能作为一个法律上的文件，如 合同等，很可能在对消息签署多年后才验证其签字，且可能需要多次验证签 字。因此，签字的安全性和防伪造的要求更高些，且要求证实速度比签字速 度还要快些，特别是联机在线实时验证。 随着计算机网络的发展，过去依赖于手书的签字的各种业务都可以用电 子数字签名代替，它是实现电子贸易、电子支票、电子货币、电子购物、电 子出版及知识产权保护等系统安全的重要保证。 关于数字签名的一些比较好的综述性文章可参看文献1 6 1 ，f 1 7 1 2 2 数字签名和h a s h 函数 签名方案几乎总是和一种非常快的h a s h 函数( 哈希函数) 结合使用。所谓 哈希函数h a s h ( 也称杂凑函数，文中我们用胃来表示) ，其实就是满足下列性 质的函数： ( 1 ) h 能用于任何大小的数据分组输入： ( 2 w 能产生定长输出； ( 3 ) 对任何给定的工，日0 ) 要相对容易计算； ( 4 ) 对任何给定的散列码h ，寻找使得朋伍) = i l 在计算上是不可行的，这称 为哈希函数的单向性。 有时，还需要哈希函数h 具有下列性质： ( 5 ) 对任何给定的分组x ，寻找不等于工的y ，使得h 0 ) = 胁) 在计算上是 不可行的，此性质称为弱抗碰撞( w e a kc o l l i s i o nr e s i s t a n c e ) 。 西南交通大学硕士研究生学位论文 第9 页 ( 6 ) 对任何的0 ) 对，使得坼) = 勘) 在计算上是不可行的，此性质称为强 抗碰撞( s t r o n gc o l l i s i o nr e s i s t a n c e ) 。 ( 7 p = 坼) ，y 的每一比特都与工的每一比特相关。 将哈希函数应用到数字签名中可带来下列一些好处： ( 1 ) 可破坏数字签名方案中的某种数学结构，诸如同态结构。 ( 2 ) 可提高数字签名的速度。当签名者想签一条消息石时，他首先构造一 个消息摘要z = 卸，然后计算签名y = s i g k 0 ) 。使用哈希函数的数字签名方案参 见图2 1 。 图2 - 1 使用h a s h 函数的数字签名方案 ( 3 ) 无需泄漏签名所对应的消息，可将签名泄漏，比如对消息z 的签名是 y = s i g k 仁) ，其中z = h 仁) ，可将往，y ) 公开，而工保密。 ( 4 ) 可将签名变换和加密变换分开来，允许用对称密码体制实现保密，而 用非对称密码体制实现数字签名。在i s o 的开放系统互联参考模型中，这种 分离的一个优点是可在不同层提供消息的完整性和机密性。哈希函数除了可 用于数字签名方案之外，还可以用于其他方面，诸如消息的完整性检测，消 息的起源认证检测等。例如，文件的所有者为了保障一个文件的完整性，即 咀止对文件的非法改变，他首先获得一个文件的h a s h 值，自己保存这个文 件的h a s h 的一个拷贝，然后将文件存贮在可公开的地方，每当他使用文件 时，他计算存贮的文件的h a s h 值，然后与他自己保存的拷贝进行比较，如 果相等，说明文件是完整的，没有被改动；否则，说明文件已经被改动。 从理论上来讲，安全的h a s h 函数的存在性依赖于单向函数的存在性， 文献 1 8 】讨论了如何利用一个给定的单向函数来构造一个安全的h a s h 函数。 目前已经设计出了大量的h a s h 函数。诸如r a b i nh a s h 方案【1 9 l 、m c r k l c 西南交通大学硕士研究生学位论文第1 0 页 h a s h 方案1 2 0 i 、nh a s h 算法【2 1 , 2 2 、m d 4 算法【2 3 1 、m d 5 算法【“1 、s h a 算法等等 p 】。想全面了解现有的h a s h 算法，可参阅文献【1 8 】，【2 6 】，【2 7 】。 2 3n is t 数字签名标准 1 9 9 1 年8 月3 0 日，美国国家标准与技术研究所( n l s t ) 提出了一个数字 签名标准( d s s ) 1 2 8 i ，在正式采用之前征求各方面的意见，目的是为需要签名 的美国各政府机关提供一个标准。该方案于1 9 9 4 年5 月1 9 日在联邦记录( f r ) 中公布，同年1 2 月1 日被正式采纳。实际上，n i s t 数字签名标准( d s s ) 就是 当q 毪 ? 如 ? ；j 。 - p 一1 j 一 j f ： 图3 一l ( 2 ) 设，是连接尸，q 的直线，r 是f 与e 的第三个交点，则p + q = - r ，特 别地，如果p = q ，则j 成为切线。如图3 2 i i j 。 ； l -矗7 香 ： 2 1 3 飞0 3 ， o6 sl ：d 新 ： r 。l 一l j 。 jl 、 图3 2 3 2 椭圆曲线群的阶 我们已经知道椭圆曲线上的点集可以构成一个a b e | 群。而将要讨论的密 码体制就是在这个群上进行的，所以，这个群的结构和阶对密码体制的安全 西南交通大学硕士研究生学位论文第2 1 页 性是至关重要的。研究这个群的结构和阶满要更力【i 深刻、复杂的群理论基础。 这里仅给出几个重要的定理和结论。 定理3 2 ( h a s s e 定理) 令艇( 即) = 口+ 1 - t ，则h z 4 q 。 定义3 5 如果p i t ，则称椭圆曲线是超奇异的( 简称超奇的) ，否则称为 非超奇异的。 定理3 3 ( w e i l 定理) 设是定义在有限域b 上的椭圆曲线，令 t = q + l 一托( 唧) ，贝j j # e ( f q 2 ) = 矿+ 1 m 十矿，其中口，p 满足：1 - t t + q t z = ( 1 一a d ( 1 - ) 。 应用这个定理，可以计算许多椭圆曲线群的阶。 一般说来，给定了椭圆曲线，我们可以计算它的阶，但是要用在加密方 面，还要对其安全性进行分析，因此通常采取给定椭圆曲线的阶，再来构造 椭圆胁线，关于这方面的论述可以参阅文献 3 8 1 。 定义3 6 设g 是一个( 加法) 群，p e g ，则如果存在正整数k 使得k g = o ， 则称点p 的阶为有限阶，如= r a i n k k p = o ，七 称为点p 的阶。否则称p 是无 限阶的，记拓= 8 。如果g 的每一个点都有有限阶，则称g 是一个挠群。g 陋1 = p i b = 露，p g 是所有矗阶点组成的集合，可以证明它是g 的一个子群，称为 g 的，l 阶挠子群 定理3 4 设三【k 】= e ( 兄) i n 】，那么：若n ，碍互素，则e n 】= 乙毋z 。；如 果e 是超奇异的，则e p l = d ，否则e p 。】= 乙。 3 3 椭圆曲线上的基本运算 3 3 1 有限域b 有限域，p ( 也记为g f p ) ) 由整数集合 0 ，1 2 ，1 组成，每个这样的整数 可以用一个长度恰为r = ，d g 妒1 ( 其中k 1 表示不小于工的最小整数) 的二进制表 示，该表示由整数的二进制表示及在其左边添加适当个数的0 组成。r 中元 素的算术运算如下： 加法如果a ，b r ，则+ 6 = r ，其中r 是d + 6 被p 除所得的剩余， o 3 是一个素数，a ，b 兄满足4 a 3 + 2 7 b 2 o ，由参数a 和b 定义的 f p 上的一个椭圆曲线是方程 y 2 = z 3 + e z x + 6( 3 3 ) 的所有解o ) ，工昂，y e 昂连同一个称为“无穷远点”( 记为d ) 的元素组成 的点集合。e ( ) 的点数用托( ) 表示。由h a s s e 定理可知： p + 1 2 p 带目q 0 ) p + 1 + 2 p 点集合e ( 日) 对应下面的加法规则构成一个群，即 ( 1 ) d + d = d ： ( 2 ) 对所有0 ，y ) e e ) 10 卜d = 扛，y ) ； ( 3 ) 对所有0 y ) 互( 舀) ，0 ) + 仁，哆) = o ( 即点0 ，y ) 的逆为 ，亨) ) ； ( 4 ) ( 两个不同且不互逆的点加法法则) 令仁l i ) e ) ，2 ) e ( f 日) 是满 足x 1 舟2 的两个点，则0 l 1 ) + 0 2 2 ) = 她3 ) ， 卜巳- a 2 一x 1 一x 2 i _ ) ，= a “一而) 一y 。 其中兄：堑塑。 1 7 2 一 ( 5 ) ( 倍点规则) 令0 l 1 ) e ( ) 是一个点，) ，l o ，则2 ( xx , y 1 ) = g 3 肋) ， f 工3j a 2 2 毪 i y 3 一a ( 葺一而) 一y 1 其中丑。莓兰。 二y l 群e ) 是a b e l 群，即对e 眠) 中所有的点p 和q ，p + q = q + p 。如果 把( ，g ) 叩+ 1 ，则称曲线为超奇异的，否则称为非超奇异的。 西南交通大学硕士研究生学位论文第2 3 页 3 3 3 有限域g f ( 2 ”) 有很多构造元素个数为素数方幂的有限域的方法，在这里我们介绍一种 利用多项式的加、乘、除和剩余来构造有限域的方法。 令搀) ”砺p 尸1 + 可彝2 扛1 砺诉，2 ，o 连用一1 ) 是f 2 上次数为所的不 可约多项式，即触) 不能分解为f 2 上两个次数小于m 的多项式的积。有限域 g f ( r ) 由r 上所有次数小于m 的多项式组成，即 g f ( 2 州) = 口用1 z 州1 + 口卅2 x 限2 + + a l x + a o ：a i e 0 ，1 ) 域元素红珥1 + 口。蓼”2 。- i - d l l x - i - a o ) 通常用长度为m 的二进制串 0 + 1 a r 幻) 表示，使得 g f ( 2 ) = 口。1 a 。2 a l a o ：a f 0 ，1 西此g f ( 岁) 中的元素可以雨所有长度为m 的二进制的集合来表示。 域元素的加、乘运算如下： 域加法- 1 a l a o ) + ( 6 b 1 6 0 ) = ( c + 1 c l c o ) ，其中c i = a i + b ir o o d2 ，即 域加法是按分量形式进行的。 域柔 去和剃钎船) ( b 1 厶t 占仃) = ( h 1 r l f 毋，其中多项式 1 m 岱”1 + r 一f “+ “+ r l x + r 0 是多项式 ( 口m ，1 卫m 一1 + 口m 2 x 限2 + + a t x + a o ) ( 6 用一i x 删1 + 6 州2 x m 2 + + 6 1 工+ 6 0 ) 在f 2 上被舡) 除所得的剩余。 这种表示g f ( 2 4 ) 的方法称为多项式基表示。 注意到g f ( 矿) 恰好包含2 “个元素。令( f 2 “) 表示g f ( r ) 中所有非零元素 的集合，则可证明至少存在一个元素g g f ( 2 “) ，使得g f ( 2 1 ) 中任意非零元 素可以表示成g 的一个方幂。这样的一个元素占称为如“的生成元( 或本原元) 。 即 g 以扩) = ：o f r 一1 ) a = g ( f ，) 的乘法逆是 4 1 = 占一g ( 一) 舶耐( 2 用1 ) 。 更一般地，域g f ( 2 “) 可以表示成为f 2 上的一个维数为r t l 的向量空间， 也即g f ( 2 “) 中存在一个由肌个元素a o ，a l ，d ，z 组成的集合，使得每个a g 以吵) 可以写成如下形式，即 西南交通大学硕士研究生学位论文第2 4 页 a = a 0 伽+ 口l o l 十+ a m 1 c 1 其中口， o ，1 ) 。可以将口表示成0 ，1 向量0 0 i ，口棚，口剃) 。域元素的加法 由元素的向量表示按位异或来进行。 一般地，g f ( 矿) 在疋上有很多不同的基。g f ( 罗) 在基域疋上的一组正 规基是形如户拶2 ，卢”，卢2 ( ”_ 1 的一组基，其中f l e g f ( 2 “) ，可以记n ：亨q ， 倒 其中a i e 0 ，1 ，o i 小一1 。由于平方在g f ( 2 “) 中是一个线性运算，有 a 2 = 卢一= 弘p 垂嘲山砘钆：) 指标用模约简，因此f 2 卅用正规基表示时，平方一个元素可以通过向量表 示的一个简单循环移位来完成，这是在硬件中非常容易实现的运算。 g f ( 2 m ) 中的元素还可以用一种特殊的正规基一最优正规基( o n b ) 来表 示。o n b 只对某些m 的值，在g f ( 2 “) 中存在。有两种o n b ，称为i 型o n b 和i i 型o n b 。这两种o n b 的差别在于定义中所采用的数学公式不同。 当采用o n b 表示时，g 以矽) 中元素的乘积很容易用硬件实现。 3 3 4g f ( 2 m ) 上的椭圆曲线 g f ( 2 “) 上由参数a ，b g f ( 2 “) ，b o 定义的一个非超奇异椭圆曲线e ( f 2 ”) 是方程 y 2 + x y = x 3 + a x 2 + 6 ( 3 4 ) 的解集合旺，_ ) ，) ，x g f ( r ) ，y e g f ( 岁) ，连同一个额外的“无穷远点”0 组 成的点集合。e ( r ”) 中的点数表示为舾( f 2 “) 。由h a s s 定理可知