本科毕业论文RSA公钥加密算法的设计与实现.docx

RSA公钥加密算法的设计与实现院系：数学与计算科学学院专业：08级科学计算与计算机应用学生姓名：吴思稣学号：指导教师：谭军高级讲师二〇一二年五月RSA公钥加密算法的设计与实现【论文摘要】RSA公钥加密算法是目前最有影响力的非对称加密算法，为ISO的推荐的加密标准。而非对称加密因其安全性、开放性以及在数字签名技术中的重要性，在我们的生活中被使用得越加频繁。RSA的安全性建立在大整数的分解困难上，其基本原理是初等数论中的欧拉定理。在工业实现上，为了保证加密的安全性，通常要求密钥对大于1Kbits，然而计算机的整型变量为32bits，这构成一个矛盾。此外，RSA密钥的生成需要产生随机的大素数，这也是本文需要解决的问题。【关键词】RSA；非对称加密；素数The design and implementationof RSA public key encryption algorithm【ABSTRACT】RSA 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, openness and the importance in digital signature technology.RSAs security is built on the difficulties of big integer factorization, whose basic principle is the Eulers theorem in elementary number theory. In order to ensure the security of encryption, when it comes to industry, we often require the key pair is greater than 1Kbits.However, the integer class of computers occupies 32bits, which constitutes a contradiction. In addition, RSAs key-generation needs a random large prime number, which is also a problem to be solved.【Keywords】RSA; dissymmetrical encryption; prime number一．前言（一）引论从公元前5世纪，古希腊斯巴达人用木棍和带子进行换位密码，到现在的网上购物、网上银行，密码学在我们生活中占着越来越重要的地位。如同我们寄信会把信纸放入信封并在封口签名，以免他人获知信件内容以及在投递过程中被更改丢失原意，使用密码是为了保证信息的秘密性、不可更改性等。密码学真正得到革新，是在计算机的广泛传播之后。1977年，DES（the Data Encryption Standard，数据加密标准）被美国政府正式采纳。同年，RSA公钥加密算法由Ron Rivest、AdiShamirh和LenAdleman在美国麻省理工学院开发，是目前最有影响力的公钥加密算法，现已被ISO推荐为公钥数据加密标准。2005年电子签名法的施行，是中国信息化进程发展的必然需求和有力保障，说明了密码学被公众相信、使用，并被立法支持。电子签名技术的实现需要用到非对称算法和报文摘要，所以，RSA作为公钥加密的标准算法，值得我去学习、研究和实现。RSA算法的数学基础是初等数论中的欧拉定理，其安全性建立在大整数因子分解的困难性上。为了有效地实现RSA密码体制，必须解决如下三个问题：1. 大整数类的实现：计算机中，通常的编程语言的长整型是64bits的，而计算安全的RSA要求密钥长度长达1024bits或以上，故要设计出一个无限大（大于10000bits）的整数类，并重载各种初等运算。2. 模幂运算的快速计算：RSA的加密解密算法都需要大量的模n指数运算，而模n和指数m都很大，所以模幂运算的快速算法十分重要。3. 快速产生大素数：RSA算法中每一个密钥的产生需要两个随机的大素数参与运算，然而现在还没有产生任意大素数的有用技术。通常的做法是随机选取一个需要数量级的奇数并验证是否素数，如此重复。因此验证素数的算法速度也十分重要。