RSA公钥加密算法的设计与实现

《RSA公钥加密算法的设计与实现》由会员分享，可在线阅读，更多相关《RSA公钥加密算法的设计与实现（33页珍藏版）》请在文档大全上搜索。

1、RSA公钥加密算法的设计与实现28 / 33RSA公钥加密算法的设计与实现论文摘要RSA公钥加密算法是目前最有影响力的非对称加密算法，为ISO的推荐的加密标准。而非对称加密因其安全性、开放性以与在数字签名技术中的重要性，在我们的生活中被使用得越加频繁。RSA的安全性建立在大整数的分解困难上，其基本原理是初等数论中的欧拉定理。在工业实现上，为了保证加密的安全性，通常要求密钥对大于1Kbits，然而计算机的整型变量为32bits，这构成一个矛盾。此外，RSA密钥的生成需要产生随机的大素数，这也是本文需要解决的问题。关键词RSA；非对称加密；素数The design and implementati

2、on of RSA public key encryption algorithmABSTRACTRSA public key encryption algorithms are the most influential dissymmetrical encryption algorithms, the recommended encryption standard to ISO. And dissymmetrical encryption is used more and more frequently in our lives because of its security, openne

3、ss and the importance in digital signature technology.RSA's security is built on the difficulties of big integer factorization, whose basic principle is the Euler's theorem in elementary number theory. In order to ensure the security of encryption, when it comes to industry, we often require

4、 the key pair is greater than 1Kbits. However, the integer class of computers occupies 32bits, which constitutes a contradiction. In addition, RSA's key-generation needs a random large prime number, which is also a problem to be solved.Keywords RSA; dissymmetrical encryption; prime number目录RSA公钥

5、加密算法的设计与实现IThe design and implementation of RSA public key encryption algorithmI目录II一前言2（一）引论2（二）背景知识21. 密码技术的发展22. 密码学的主要任务23. 密码系统的安全性24. 对称与非对称密码的区别25. 公钥：RSA密码体制2二、实验部分2（一）实验目的2（二）实验环境2（三）实验步骤21. 大整数类22. 快速模幂运算23. 快速产生随机素数24. 扩展的欧几里德算法2（四）代码设计21. 大整数类22. Rsa类23. 关键代码2三、结果与讨论2（一）程序展示21. 程序主界面22.

6、RSA密钥产生23. 加密解密展示2（二）RSA分析21. RSA的安全性22. RSA效率2（三）小结2注释2参考文献2致2一前言（一）引论从公元前5世纪，古希腊斯巴达人用木棍和带子进行换位密码，到现在的网上购物、网上银行，密码学在我们生活中占着越来越重要的地位。如同我们寄信会把信纸放入信封并在封口签名，以免他人获知信件容以与在投递过程中被更改丢失原意，使用密码是为了保证信息的秘密性、不可更改性等。密码学真正得到革新，是在计算机的广泛传播之后。1977年，DES（the Data Encryption Standard，数据加密标准）被美国政府正式采纳 (1)。同年，RSA公钥加密算法由Ro

7、n Rivest、Adi Shamirh和Len Adleman在美国麻省理工学院开发，是目前最有影响力的公钥加密算法，现已被ISO推荐为公钥数据加密标准。 (2)2005年电子签名法的施行 (3)，是中国信息化进程发展的必然需求和有力保障，说明了密码学被公众相信、使用，并被立法支持。电子签名技术的实现需要用到非对称算法和报文摘要，所以，RSA作为公钥加密的标准算法，值得我去学习、研究和实现。RSA算法的数学基础是初等数论中的欧拉定理，其安全性建立在大整数因子分解的困难性上。为了有效地实现RSA密码体制，必须解决如下三个问题： (4)1. 大整数类的实现：计算机中，通常的编程语言的长整型是64

8、bits的，而计算安全的RSA要求密钥长度长达1024bits或以上，故要设计出一个无限大（大于10000bits）的整数类，并重载各种初等运算。2. 模幂运算的快速计算：RSA的加密解密算法都需要大量的模n指数运算，而模n和指数m都很大，所以模幂运算的快速算法十分重要。3. 快速产生大素数：RSA算法中每一个密钥的产生需要两个随机的大素数参与运算，然而现在还没有产生任意大素数的有用技术。通常的做法是随机选取一个需要数量级的奇数并验证是否素数，如此重复。因此验证素数的算法速度也十分重要。接下来，我会参考各个相关文献，找出办法解决问题，并实现RSA算法。（二）背景知识在古代战争中，因为需要的通信

9、，密码技术应运而生。但长久以来，军事、政治、外交等要害部门，为求，并不外传密码技术，而是一直把持着密码知识。然而随着计算机技术和网络通信技术的发展，越来越多的电子政务、电子商务普遍需求安全通信，密码技术才从军用走向商用民用，并得到更加迅速的发展。在如今的信息时代，信息安全的重要性日益彰显，密码学作为信息安全的核心也受到各个机构的重视。密码技术不但可以保证信息的性，还有防篡改和数字签名等功能。下面我将做一个密码学的简介。1. 密码技术的发展根据加密解密手段和器械的不同，密码技术的发展历史大致可以划分古典密码、近代密码和现代密码时期这三个时期。 (5)（1） 古典密码时期这一时期从古代到19世纪末

10、，长达数千年。由于这个时期社会生产力底下，产生的许多密码体制都是以“手工作业”的方式进行，用纸笔或简单的器械实现加密和解密。公元前440多年的斯巴达人发明了一种称为“天书”的加密器械来秘密传递军事情报。“天书”是通过把一个带状物如羊皮带，成螺旋状紧紧地缠绕在一根权杖或者木棍上，然后再沿着纵向书写信息，展开后就成为无意义的点线。解密时，找一个同样直径的木棍缠绕上，就可以看到明文。这是最早的移位密码（也称换位密码或置换密码）。在大约公元前1世纪，罗马帝国凯撒大帝设计出一种简单的替换式密码，并在高卢战争中使用。这种密码的实现方式是把信中每个文字的字母都按字母顺序表中相隔两位后的一个字母取代。这一时期

11、的密码技术仅是一门文字变换艺术，如上面所说的置换密码和替换密码。这样的密码研究和应用远没有形成一门科学，最多能称为密码术。（2） 近代密码时期近代密码时期是指20世纪初到20世纪50年代左右。这个时期的加密解密主要是用机电设备来实现的。1895年无线电诞生后，各国在通信，特别是军事通信中普遍采用无线电技术。由于无线电的广播性，为了实现，各国随即开始研究无线电密码的编制和破译。从1919年以后的几十年中，密码研究人员设计出了各种各样采用机电技术的密码与来取代手工编码加密方法，实现通信的自动编解码。近代密码时期可以看作是科学密码学的前夜，这阶段的密码技术是一种技巧和经验的结合体，还不是一门科学。密