《椭圆曲线求阶算法的研究》由会员分享，可在线阅读，更多相关《椭圆曲线求阶算法的研究（67页珍藏版）》请在金锄头文库上搜索。
1、中南民族大学 硕士学位论文 椭圆曲线求阶算法的研究 姓名：张波 申请学位级别：硕士 专业：计算机应用技术 指导教师：余启港 20080520 中南民族大学硕士学位论文 I 摘 要 1985年，Neal Koblitz和Victor Miller分别独立地提出了利用椭圆曲线设计 公钥密码体制。 此后关于椭圆曲线密码安全性和有效实现的大批研究成果被发表 出来。在众多的公钥密码体制中，椭圆曲线公钥密码以其独特的优势成为公钥密 码研究中的热门。但是相对于其它公钥密码体制来说，如何选取安全的椭圆曲线 参数这一问题目前还是一件困难的事情。对于这个问题，我们需要求得给定椭圆 曲线的阶，并将其作为判断一条椭圆
2、曲线是否安全的重要依据。所以本文以椭圆 曲线公钥密码体制（ECC）为研究对象，内容包括与椭圆曲线公钥密码相关的数 学概念、加密解密算法以及椭圆曲线求阶算法。 论文的主要工作如下： 本论文详细介绍了椭圆曲线的求阶算法 Schoof 算法及其改进 SEA 算法。将 袋鼠算法和大步小步法用于对 Schoof 算法的加速。实验结果表明，这两种加速 算法能使 Schoof 算法的运行时间大大降低。而在 SEA 算法中，讨论了它的两种 实现方法，实验结果表明当仅使用 Elkies 素数的时候，SEA 算法运行时间更短。 关键词：Schoof 算法；SEA 算法；BSGS 算法；Kangaroo 算法；安全
3、的椭圆曲线； 椭圆曲线求阶算法的研究 II Abstract In 1985,Neal Koblitz and Victor Miller independently proposed the elliptic curve cryptosystems(ECC).after that, lots of paper about the secure and implementation of elliptic curve public key cryptography was published. Among the public key cryptosystems, Elliptic curve
4、 cryptography became the hotspot with its own advantage. Compare to the other public key cryptography, how to choose secure parameter of an Elliptic curve used for encrypt and decrypt is still a tough work. We need to know the points of a given elliptic curve which is important to judge whether the
5、given curve is secure. So, in this paper I take Elliptic curve cryptography as my research object. It include to introduce related mathematic conception,encrypt and decrypt algorithms and the algorithm to counting the points of a given elliptic curve. The main research of this paper as follows: This
6、 paper is mainly discuss the Schoof algorithm and SEA algorithm, and take the Kangaroo algorithm and BSGS algorithm as the accelerate method to Schoof algorithm. The experiment shows that the acceletate method can short the running time of Schoof algorithm greatly. To SEA algorithm, I discussed the
7、two implement method of it, when only use Elkies prime, the running time of SEA algorithm is shorter. Key Words： Schoof algorithm; SEA algorithm; BSGS algorithm; Kangaroo algorithm; Secure Elliptic Curve; 中南民族大学中南民族大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任
8、何其 他个人或集体已经发表或撰写的成果作品。 对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查 阅和借阅。 本人授权中南民族大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1、保密，在_年解密后适用本授权书。 2、不保密。 （请在以上相
9、应方框内打“” ） 作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日 中南民族大学硕士学位论文 1 第一章 绪论 1.1 引言 1976年，Diffie和Hellman发表了New DirectionsinCryptography一文， 第 一 次 提 出 了 公 钥 密 码 的 概 念 。 所 谓 的 公 钥 密 码 体 制 （PublicKey Cryptography）是基于某个难以解决的数学难题，在该数学难题的基础上通过某 种公开的算法将加密密钥（公钥）和解密密钥（私钥）相联系起来。加密密钥和 解密密钥是不一样的，加密密钥可以公开而解密密钥必须保密，从加密密钥得到 解密密
10、钥非常困难同时计算过程仅仅在理论上可行而实际上是不可能的。 公钥密码学开创了密码学的新领域，在后来的三十多年中，公钥密码这一 概念得到了数学家、密码学家和业余爱好者的追捧。不断的有新的公钥密码模型 被提出，但是其中的绝大部分要么被有效的破解，要么由于太复杂而难以实现。 现在， 被公认为既安全又能有效实现且具有代表性的公钥密码仅有为数不多的几 种，下面将予以简要介绍： 一、一、RSA公钥密码体制 它是由Ron Rivest、Adi Shamir和Leonard Adelman于1978年提出的。其 理论是基于费马小定理，安全性是基于大整数的素分解的难解性。尽管目前尚未 在理论上严格证明因子分解问
11、题一定是难解的，但是经过长期的研究，迄今尚未 找到一个有效算法的事实使得因子分解问题成为众所周知的难题。 这是RSA公钥 密码建立的基础。 二、Elgamal公钥密码体制 Elgamal公钥密码体制是由.T Elgamal于1985年提出的。 它至今仍然是安全 性能良好的公钥密码体制之一。Elgamal密码体制的安全性是基于有限域上的离 散对数问题，这也是一个公认的难题。关于有限域上离散对数问题，人们进行了 椭圆曲线求阶算法的研究 2 许多深入的研究，取得了许多重要的成果。但是到目前为止，还没有找到一个有 效的多项式时间算法来计算有限域上的离散对数。这是Elgamal公钥密码建立的 基础。 三
12、、三、椭圆曲线公钥密码体制 它是在1985年由Neal Koblitz 1和Victor Miller2分别独立提出的。它是利 用有限域上椭圆曲线有限群代替基于离散对数问题密码体制中的有限循环群所 得到的一类密码体制。这也是一个目前没有解决的数学难题，它是椭圆曲线公钥 密码建立的基础。严格的说，椭圆曲线密码不是一种新的密码体制，它只是已有 的密码体制在椭圆曲线上的一种新的实现。 但是它又具有原有的密码体制不具备 的新特征，因此可以被认为是一种不同于原有的离散对数问题的新的密码体制。 在以上三种公钥密码体制中，RSA公钥密码和Elgamal公钥密码由于实现 简单且易于理解，所以被进行了较为透彻的
13、研究。他们是当今使用最为广泛的公 钥密码。但是正是由于它们的广泛使用，引起了人们对大数分解问题和离散对数 问题的极大的兴趣。值得注意的是，大数分解问题和离散对数问题的求解在本质 上具有一致性 3 。目前人们对这两类问题的求解能力有了较大的提高，这使得人 们要求所使用的安全密钥的长度越来越长。 比如RSA， 目前人们认为安全的密钥 长度从先前的512bit增加到了现在的10242048bit。密钥长度的增加使得加密 解密所需的时间也越来越长，这又反过来制约了它的使用。相反地，人们对椭圆 曲线离散对数求解方法进行的研究在近10年里却没有什么大的进展。现在，长 度为160bit的椭圆曲线密码的安全性
14、相当于1024bit的RSA的安全性。于是，椭 圆曲线密码体制的优点就显现出来了， 在这种背景和椭圆曲线公钥密码体制逐渐 走向成熟的情况下，椭圆曲线公钥密码成为了当前人们研究的一个热门。 1.2 选题背景和意义 椭圆曲线公钥密码体制是以有限域上椭圆曲线理论为基础的。人们对椭圆 中南民族大学硕士学位论文 3 曲线公钥密码的研究仅仅才二十几年时间， 而对椭圆曲线的研究却有上百年的历 史。尽管椭圆曲线公钥密码仅仅是椭圆曲线理论中的一个小的分支，但是它在密 码学这一领域所带来的影响却是相当大的。甚至有人预言它将成为RSA的替代 者。 椭圆曲线公钥密码与其它公钥密码体制相比较，其优势主要有以下几个方 面
15、： 1. 更高的安全性 2. 更小的带宽需求 3. 更快的计算时间 4. 更小的存储空间需求 总的说，椭圆曲线公钥密码体制的这些优点正是基于对密钥长度和安全的综合 虑。下表给出了相同安全性的RSA公钥密码和椭圆曲线公钥密码密钥长度的对 比： MIPS 年数 RSA 或 DSA 密钥长度ECC 密钥长度RSA 和 ECC 密钥长度比 4 10 512 106 5:1 8 10 768 132 6:1 11 10 1024 160 7:1 20 10 2048 210 10:1 78 10 21000 600 35:1 表. 相同安全性的 RSA 和椭圆曲线密钥长度的对比 相对于RSA和Elgam
16、al这些成熟的技术，椭圆曲线则是有待完善的。目前人 们对它的研究主要集中在以下两个方面： 1. 安全椭圆曲线的选取。 本人认为这是阻碍椭圆曲线公钥密码进一步发展 的关键问题所在， 现有的选择方法过于复杂从而使得选择安全椭圆曲线 椭圆曲线求阶算法的研究 4 的时间过长。如果能使安全椭圆曲线的选取时间更短，在实际应用中将 会是非常的大的突破。 2. 椭圆曲线快速算法。尽管椭圆曲线公钥密码加解密的时间比RSA要快 得多，但相对于对称密码（如DES）其速度还是太慢，人们仍然在寻求 更快更有效的加解密算法。 这些同时这也是制约了椭圆曲线公钥密码进一步商业化的主要问题。可以说 正是因为椭圆曲线在实用过程中的这些缺陷才使得人们对它如此地感兴趣。在 此，我选择如何选取安全的椭圆曲线这一问题来作为研究课题。 1.3 论文安排和主要的研究成果 本论文共分六章，其中第一章为绪论，简要的对公钥密码进行了介绍，以及 选题的背景和意义。 第二章介绍了椭圆曲线的数学基础，包括群、环、域、有限域等概念和相关 的性质。这些都是和椭圆曲线公钥
