公钥加密体制的理论与实现论文

1、 本科生毕业论文（设计）题目 公钥加密体制的理论与实现 姓名 李瑶 学号 2012417017 院系 信息科学与工程学院 专业 软件工程 指导教师 马旭 职称 讲师 2016 年 5 月 21 日曲阜师范大学教务处制目录摘要3关键词3Abstract3Key Words31 前言31.1研究背景41.2加密算法的研究现状42 密码学基础知识52.1数学问题52.2公钥加密模型62.3安全性定义63经典加密算法73.1 ELGamal算法73.1.1 ElGamal算法思想73.1.2 ELGamal算法描述73.3.3 ELGamal方案的安全性73.2 Rabin加密算法83.2.1 Rab

2、in算法思想83.2.2 Rabin算法思想83.2.3 Rabin密码体制的安全性83.3 RSA密码算法83.3.1 RSA算法思想83.3.2 RSA算法描述93.3.3 RSA方案的安全性94算法的实现105 总结126致谢12参考文献13 公钥加密体制的理论与实现软件工程专业学生：李瑶指导教师：马旭1 摘要：本文主要论述研究背景及相关的研究现状：密码学中初等加密算法是对称密码，各发送方和各接收方之间都只存在一种密钥。初等加密算法的密钥管理复杂，而且安全性较差。因此引入了高级加密算法，非对称密码。然后介绍了密码学基础知识，其中涉及数学困难问题，包括陷门单向函数问题、整数分解问题、离散对

3、数问题等。然后介绍了典型的加密算法，如ELGamal算法，它基于的困难问题是群中的离散对数问题；RSA算法，它基于大整数分解问题，与ELGamal算法一样既可以进行数据加密也可以数字签名。然后是利用Eclipse软件开发工具实现了ELGamal算法的截图，最后对本文进行了总结。关键词：公钥密码 信息安全 密码学 Design and Implementation of Public Key CryptographyStudent Majoring in Soft Engineer: Yao LiTutor Name:Xu MaAbstract：Mainly discusses the rese

4、arch background of this paper and the related research status of elementary encryption algorithm in cryptography which is a symmetric cipher between the sender and the receiver is only one key. The key management of elementary complex encryption algorithm, and poor safety. Therefore the introduction

5、 of advanced encryption algorithm and asymmetric cryptography. Then introduces the basic knowledge of cryptography, which involves the problem of mathematical difficulties, including the trapdoor one-way function problem, integer factorization problem and discrete logarithm problem. Then introduces

6、the typical encryption algorithms, such as ELGamal algorithm, which is based on the difficulty of the problem is the discrete logarithm problem in the group; the RSA algorithm, which is based on the integer factorization problem, like ELGamal the algorithm can encrypt the data can also be a digital

7、signature. Then the ELGamal algorithm is implemented using Eclipse screenshot software development tools, finally summarized in this paper. Key Words: Public key ; Information Security ; Cyrptography;Cryptography 1 前言 互联网时代里，人们的生活到处都围绕着网络，比如：广泛使用的腾讯的QQ、微信；阿里巴巴的支付宝、淘宝、蘑菇街；360的浏览器以及网易的各种业务，它们的产生和发展冲击着

8、社会的变迁，给人们的生活带来了巨大的变化。它们带来了很多方便的同时也存在很多隐患。在网络安全问题上已经出现很多的恶意、犯罪事件，例如，5月4日，据每日邮报报道，知情人士爆料称，在未经患者同意下，谷歌已经获得160万份私人医疗记录，用以研发帮助监控肾病的应用。随着有关我们的信息被越来越多的共享，在很多情况下，民众根本不知道谁在使用他们的信息。我们经常看到数据在未经同意或正确理解的情况下被分享，这会产生巨大影响。这就催生出了新的科学即网络安全。网络安全的发展为网络信息安全共享和为人们服务的安全、方便、快捷提供了可能。当然，网络安全的核心技术-密码学显得尤为重要。1.1研究背景 从整体上来说，密码学

9、经历过人工密码，到机械密码，到电子计算机密码的发展历程。近代密码时期的密码技术常常是凭直觉和信念来进行密码设计和分析，而不是推理证明。因此，也有学者将古典、近代密码时期划分为一个阶段。现代密码时期密码学时期，密码学越发成熟。 随着信息社会的发展，信息的安全成为一个需要解决的关键问题。信息安全采用了信息论、计算机科学和密码学等方面的知识，其主要任务是研究计算机系统和通信网络中信息的保护方法，以及实现系统和网络中信息的机密性、完整性、认证性、不可否认性、可用性等目标，其中密码学是实现信息安全目标的核心技术。密码学研究实现信息安全各目标的相关的数学、方法和技术。密码学是数学、计算机科学、电子与通信等

10、交接在一起的一门交叉的学科。 先出现的对称加密算法的特点是算法公开、计算量小、加密速度快、加密效率高。不足之处是，交易双方使用同样钥匙，安全性不能保证。而且，用户每次使用对称加密算法时，都需要使用其他人不知道的惟一钥匙，这会使得发收信双方所拥有的钥匙数量巨大，密钥管理就成为了用户的负担。还有就是对称加密算法在分布式网络系统上使用较为困难，因为密钥管理困难，导致成本较高。但是对公开密钥加密算法来说，对称加密算法能够提供加密和认证但是没有签名功能，使得使用范围有所缩小。 公钥密码的安全性更好，私钥密码的通信双方使用相同的秘钥，如果一方的秘钥遭泄露，那么整个通信就会被破解。而且非对称加密使用一对秘钥

11、，一个用来加密，一个用来解密，而且公钥是公开的，秘钥是自己保存的，不需要像对称加密那样在通信之前要先同步秘钥。公钥密码的缺点是加密和解密花费时间长、速度慢，只适合对少量数据进行加密。 密钥分发问题，使用对称密钥体制进行保密通信时，通信双方需要事先通过安全信道传递密钥，但是安全信道不易实现。因此，对称密钥的分发问题一直困扰着密码专家。 密钥管理问题，由于对称密码体制的密钥量过于大。例如如果有个用户在通信网络中，都想和其他个用户进行通信，则必须使用个密钥，那么系统的总密钥量就是 。也就是说当较大时，就会产生、保存、使用、销毁庞大的密钥量，这样操作就会变得很复杂，也会存在安全隐患。不可抵赖性是对称密

12、钥体制的局限，但实际应用的需求急需一种新密码体制的出现。即非对称密码密钥密码体制也就是公开密钥密码体制。1.2加密算法的研究现状 我们已知私钥密码和公钥密码各有其特点，但公钥密码的适用性以及其优越性，使得对它的研究越来越多。其中根据其基于的数学问题不同可分为： MH背包公钥密码，在背包公钥密码算法的基础上，结合Rabin算法，使得原先的密码体制变得更为灵活。改进后的算法不但能在性能上保持高效率，而且还将原先的密钥变为公玥，可以根据用户需求动态地改变公钥，成倍提高安全性能。 RSA算法， RSA公开密钥加密算法自20世纪70年代提出，现在在电子安全领域的各方面已经形成了较为完备的国际规范。RSA

13、在硬件方面，应用在技术成熟的IC应用各种消费电子产品。RSA在软件方面的应用，在Internet上取得了很多的应用。 NTRU公约密码系统 NTRU具有很多优良特性，如密钥生成、加密/解密速度快，运算简单等，还可以广泛应用于通信、嵌入式系统等领域。 ELGamal算法， ELGamal签名方案，是基于离散对数问题且主要是为数字签名而设计的，是继RSA之后最著名的数字签名方案。在金融系统中，广泛地使用到ELGamal签名体制，同时在通信系统中，也大量使用基于ELGamal签名算法的认证和通信协议。 椭圆曲线公钥密码算法， ECC技术的更强安全性、更高效率和更好的性价比，使其在实际中得到了更为广泛

14、的应用。国际上，Scott-Vanstone博士和他的同事在1985年成立了Certicom研究小组，并成功实现和推广了ECC技术及产品；2005年3月2日，美国政府部分正式采用ECC用于数字签名和密码交换的排他性的公钥密码技术；夏普将M-System 加密技术并入安全性半导体产品；SET的发展商Globeset公司计划将ECC用于付费中，将此技术并于基于芯片的产品和服务当中；Entrust提供一系列全面的软件产品，包括Entrust Authority、TruePass和Entelligence使PKI可以用于多种应用；Sun公司计划推出支持ECC7.0版的Sun Java系统服务器等。国内

15、，我国已经拥有了自主知识产权的ECC算法标准-SM2，完整实现ECC国家标准算法的芯片已经研发成功；2003年5月12日，我国颁布的无线局域网国家标准GB15629.11中采用了ECC算法，并包含了全新的WAPI；ECC技术已经用于我国第二代身份证；基于ECC的可信计算、电子政务、数字电视CA等，正在建设或者已经建设完成。这些都表明ECC在我国正得到越来越多的重视，其应用也必将越来越广泛。2 密码学基础知识 在密码学中，常用的一种方法是基于已知的数学难题构造安全的密码方案。而公钥密码体制是保障信息安全的重要方法，它除了安全还很高效。目前成熟的公钥密码算法很多都是基于整数分解和离散对数等数学难题

16、的。本章首先讲述了密码学基于的7种数学困难问题，通过对这些数学问题的研究可以更清楚的理解加密的本质；继而又讲述了公钥加密模型，至此你可以了解到加密解密的过程。2.1数学问题(1)陷门单向函数与“可交换”单向函数 单向函数：就是满足下列条件的函数： 1）给定，计算是容易的； 2）给定,计算使得是困难的。 在密码学中常用的单向函数：一是单向陷门函数；二是单向散列函数。其中陷门单向函数即满足下列条件的函数： 1）可计算性：给定，计算是容易的； 2）单向性即：给定,想要得到使得，很困难； 3）陷门性：存在，已知，对给定的任何，若相应的存在则计算使是容易的。 简言之，知道陷门信息后，函数就不是单向函数了

17、。为陷门信息。通常为加密函数，可公开，相当于公开了加密密钥。需要保密，它是解密密钥，即私钥。当使用陷门单向函数构造公钥加密时，陷门信息也许就是私钥，也许是某种方法。可交换的单向函数即具有“可交换”特性的单向函数。(2)整数分解问题，任何大于1的正整数都可以分解成如下质因数分解式： ，其中，为质数，为正整数。(3)离散对数问题，设为素数的模循环群的原根，对任意的，计算：是容易的。反过来，给定计算满足式中的是困难的，称为以为基的对数。因为均为整数，不像实数那么“连续”，故称离散对数。（其中都属于模的循环群）(4)二次剩余问题 若的最大公约数为1记为，m整除记为有解，则称为模的二次剩余（或平方剩余）

18、； 否则，称为模二次非剩余（或平方非剩 二次剩余余）。(5)椭圆曲线问题 椭圆曲线是域上亏格为1的光滑射影曲线，它的(仿射)方程，通常称为维尔斯特拉斯方程，可以写成 如果这个域的特征不等于2和3，则可以改写成或，。(6)欧拉定理问题 一个关于同余的性质，欧拉定理表明，若为正整数，且互质。(7)费马定理 它断言当整数时，关于的方程没有正整数解。2.2公钥加密模型 公共密钥加密方案是一个元组的概率多项式时间算法，满足以下： 1）算法需要输入一个安全参数和输出一对密钥。我们称第一个为公钥，二是私钥，每个的长度至少为。而可由确定； 2）算法需要一个公钥和一段明文。然后根据输出密文； 3）算法Dec需要

19、一个密钥和一段密文，输出明文或乱码。我们假设没有损失的一般性，Dec是确定的，并写为：。2.3安全性定义(1)语义安全性 语义安全性是密码学中的术语。戈德瓦塞尔和米卡里在1982年首次提出语义安全性的概念，后来又证明了语义安全和另一性质密文不可辨别性是等价的。(2) CPA (Chosen-Plaintext Attack) 选择明文攻击（CPA）其公共密钥加密方案具有相同的加密：，在选择明文攻击（或CPA安全）中，攻击者可以事先任意选择一定数量的明文，让被攻击的加密算法加密，并得到相应的密文： 。步骤如下：是运行得到的密钥；然后A得到用于访问然后输出一对消息；随机选择，算出密文，发送给A，我

20、们称为密文，A继续访问；A输出；如果实验结果为1，否则为0。(3) CCA（Indistinguishability Chosen Ciphertext Attack） 不可区分选择密文攻击（IND-CCA）一个基于身份的加密方案，如果对任意的概率多项式时间攻击者A的攻击下，都有，就称该方案是可以抵抗泄漏的CCA安全加密方案。步骤如下：初始设置：生成系统的主私钥和主公钥；密钥产生，对身份为ID的用户生成对应的公钥和私钥；解密和泄漏查询：攻击者A可以进行私钥查询，给定一个ID，挑战者会产生一个对应的返还给攻击者，并且攻击者给定ID，可以进行相应泄漏查询，泄漏可以看成是私钥的一个函数，挑战者返回,

21、其输出总长记为L；另外也可以自适应进行解密查询，攻击者给定密文，挑战者输出对应的消息；解密查询：攻击者A可以自适应进行解密查询，给定密文，挑战者输出对应明文；输出：A输出，则称A赢。3经典加密算法 经典的密码学是关于加密和解密的理论，主要用于通信保密。在今天，密码学一得到了更深入、广泛的发展。其内容已不再是单一的加密技术，已被有效、系统地用于电子数据的保密性、完整性、真实性和不可否认性等各个方面。本章详细介绍了ELGamal加密算法、Rabin加密算法和RSA加密算法。3.1 ELGamal算法3.1.1 ElGamal算法思想 ELGamal是一种较为常见的加密算法，基于1984年提出的公钥

22、密码体制和椭圆曲线加密体系。ELGamal密码体制基于的困难问题是群中的离散对数问题。离散对数问题是在密码学中有着广泛应用的问题。ELGamal密码体制的构造方法可推广到一般的循环群中，如基于有限域和椭圆曲线的ELGamal面加密方案。ELGamal的特点是加密是概率的，即不同的明文加密后具有不同的密文。3.1.2 ELGamal算法描述 ELGamal加密其实是利用DH密钥交换思想，产生随机密钥加密，然后传递生成随机密钥的“部件”，接收方利用该“部件”和自己的私钥生成随机密钥进行解密。ELGamal密码体制可以在任何离散对数问题难解的有限群中实现。密钥生成，选择一个合适的循环群，设其阶为，生

23、成元为；随机选取整数，使得,计算y=；公开公钥，保持私钥。加密算法，假设发送者B想把明文加密发送给接受者A，B先选择合适的可逆映射，使得G,并获取A的公钥，再选取随机数r，,然后计算c=,.密文。 解密算法，A收到密文后，利用私钥计算:。然后利用的逆映射求出明文。所谓合适的循环群，是指上的群运算容易计算，求解上的离散对数问题是计算不可行的。通常包括如下一些群： 1）大素数取模的乘法群； 2）的阶子群，其中是的大素数因子，是的唯一的阶子群； 3）有限域上的乘法群，其中,为素数； 4）有限域上的椭圆曲线上的点构成的群。3.3.3 ELGamal方案的安全性 ELGamal加密方案基于的安全问题 E

24、LGamal加密方案的破解是指：给定，能够得出。如果能破解，则可以来得到,于是在给定，的情况下，得到了，从而解决了DHP。另一方面，如果能够解决DHP，则可以在给定，的情况下，计算，然后来得到，从而破解了DLP问题。 基本的参数要求 前面提到加密不同消息必须使用不同的随机数r。假如同一个r加密两个消息,结果为，由于。如果已知，则很容易计算出来。比特安全性，敌手能够观察到密文和。如果是二次剩余。当且仅当是偶数，因而敌手可以根据密文来确定的奇偶性。从公钥是否是二次剩余，可以确定的奇偶性。从而可以计算的奇偶性。于是可以确定是否是二次剩余。加上可以确定是否为二次剩余，于是从可以确定m是否为二次剩余。因

25、此，加密泄露了是否为二次剩余这一信息。因此不是语义安全的。即明文m是否为二次剩余这一比特信息不安全。求解离散对数问题 与RSA问题中因子分解攻击方法类似，方案的破解的一个直接方法是求解离散对数问题。这是一种完全攻破，即给出公钥，可以求私钥。3.2 Rabin加密算法3.2.1 Rabin算法思想 目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。大整数因子分解问题：给定一个正整数，找到它的素因子分解，即将写为=，这里是不同的素数，且。3.2.2 Rabin算法思想 密钥的生成 随机生成两个大的素数和,满足,计算。为公钥，作为私钥。加密算法 c=解密算法 解密就是求c模n的平

26、方根，即解，该方程等价于方程组 由于p=q=3mod4,可容易地求出c在模p下的2个方程根 和c在模q下的两个方程 两两组合联立，可得4个方程组： 求得4个，其中必有一个为明文。3.2.3 Rabin密码体制的安全性 Rabin密码体制的破解等价于大整数因子分解。由于大整数因子分解被公认是困难的，故Rabin密码体制不能破解。因此它是第一个可证明安全的个月密码体制。Rabin方案的可证明安全性：Rabin方案的攻破将会导致解决一个公认的困难问题。所谓“方案的攻破”，就是说给定Rabin方案密文，可得到明文。即拥有一个解密函数，给定y,返回y的4个平方根中的1个。3.3 RSA密码算法3.3.1

27、 RSA算法思想 公钥加密算法是1977年由罗纳德李维斯特、阿迪萨莫尔和伦纳德阿德曼一起提出的。1987年首次公布，当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。 RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。3.3.2 RSA算法描述 RSA的安全性基于大整数的因子分解，其基础是数论中的欧拉定理。因子分解可以破解RSA密码系统，但是目前尚无人证明RSA的解密一定需要分解因子。 密钥生成，1）选取两个大素数；2）计算乘积,，其中为n的欧拉函数；3）随机选择整数,要求满足,

28、即与互素；4）用扩展的Euclidean算法计算私钥，以满足,即。得到：公钥为和,是私钥。 加密过程，明文先转换为比特串分组，使每个分组对应的十进制数小于,即分组长度小于,然后对每个明文分组作加密运算，具体过程： 1）获得接收公钥；2）把消息M分组长度为的消息分组；3）使用加密算法,计算出密文。 解密过程，将密文按长度L分组得。1）使用私钥和解密算法计算；2）得明文消息。3.3.3 RSA方案的安全性 共模攻击，设两个用户的公钥中的模相同，虽然加密解密不同，但仍然是不安全的。设模为，公开的加密密钥分别为和,通常很可能和是互素的，明文消息为，密文是。敌手截获和后，可通过如下方法恢复：利用扩展的E

29、uclidean算法求出满足的两个整数和,其中必有一个为负数，不妨设是。再次利用扩展的Euclidean算法求出,于是，因此公钥中每个实体的参数不要相同。 低加密指数，对于加密指数的选择，通常建议。原因的解释要从计算模密的快速算法说起。其实RSA的加密和解密就是计算模密，因此，寻求快速求模密的算法对RSA的加密解密效率至关重要，于是平方乘算法被提出来。由于平方乘算法的循环中模乘的次数等于加密指数的二进制表示中1的个数，故选择二进制表示中1较少的那种将会加快加密的速度，例如，,在平方乘算法的循环中只有2次模乘。 低解密指数攻击，为了提高解密速度，希望选用小的,但是有研究表明，利用格攻击方法在且时

30、，攻击者可以成功攻击RSA。另外，M.Wiener提出一种攻击，可以成功地计算出解密指数，前提是当不够大时，即满足条件,如果n的二进制表示为l比特，那么的二进制表示的位数小于,且和相距不太远时攻击有效。为安全起见建议，和有大的素数因子，设在模下阶为k,由得（为抵御循环攻击，的选择应保证使很大,所以,即,为满足上式的最小值。又当与互素时，,为使大，就应该大，且应有大的素因子。 不动点，满足条件的称为不动点。显然，不动点对RSA的安全性有一定的威胁，因此，应尽量减少。 因子分解攻击，对RSA最直接的攻击就是因子分解。如果能够分解得到和，便可以得到。4算法的实现 本章演示了使用Eclipse实现的ELGamal算法。该算法采用文件输入输出形式读取英文的输入，然后输出加密解密的结果。以下是已完成的部分截图：图1 实现ELGamal算法图2 ELGamal加解密界面图3 加解密的结果5 总结 本文重点讲解了公钥密码的设计与实现，其中还涉及了数学困难问题。在对公钥密码学的学习以及本文设计的重点中有以下总结：尽管MH背包公钥密码体制的弱密钥问题在强大的计算机攻击下显得不堪一击，但是由于其生成密钥效率高，加密/解密速度快，因此在大量