毕业设计（论文）简述RSA密码体制的组成

1、简述rsa密码体制的组成摘 要自20世纪90年代以来，计算机网络技术使得计算机应用得到进一步普及和发展，但是如何保证信息的安全却是一个十分重要的问题。rsa算法在公钥密码体制中占有重要的地位。在论文中首先介绍了加密算法的数学基础，理论上说明了rsa算法的原理，以及rsa算法中参数的选择。用vc+编程实现了rsa算法加密和解密运算，在算法的实现过程中，调用了已有的大整数类函数所提供的接口函数。关键词：密码学；rsa；加密；解密implementation of rsa cryptosystem abstractcomputer network technology, whose applicat

2、ion has gone deep into almost every field of human life and social activity, has been further popularized and developed since 1900s, but it is a very important question to guarantee information security. rsa is a crucial and significant public key cryptosystem. in the paper first the encryption algo

3、rithm is introduced based on the mathematical and theoretical introduction of the rsa algorithm theory, rsa algorithm and the parameter choices. vc + + programming the rsa algorithm, the algorithm implementation process, has been called many interface functions of a given integer class. key words: c

4、ryptology; rsa; encryption; decryption目 录论文总页数: 19页1引言11.1密码学应用的相关背景11.2使用rsa加密的意义22 rsa相关理论知识32.1 rsa的数学基础知识32.1.1 关于数的基本理论32.1.2 欧拉定理 费马小定理42.1.3 中国剩余定理42.1.4单向陷门函数52.2 rsa加密解密算法52.3 rsa参数的选择62.3.1 模数n的确定62.3.2 模数e的选取原则72.3.3 素数的产生73需求分析与平台选择83.1需求分析83.2平台选择84 rsa密码体制的实现94.1设计流程94.2 截图及运行说明94.3代码实

5、现104.4 各个功能模块介绍104.4.1加密和解密函数的实现104.4.2 导入加密密钥模块114.4.3选择文件模块124.4.4加密模块124.4.5导入解密密钥模块134.4.6生成明文145测试16结 论17参考文献171引言1.1密码学应用的相关背景在当今的信息社会中，每天都有大量的信息在传输、交换、存储和处理，而这些处理过程几乎都要以来强大的计算机系统来完成，一旦计算机系统发生安全问题，就可能造成信息的丢失、篡改、伪造、假冒，以及系统遭受坏等严重后果，因此，如何保证计算机系统的安全，是当前一个需要立即解决的十分严峻的问题。通常保障网络信息安全的方法有两大类：一是以防火墙技术为代

6、表的被动防卫型，二是建立在数据加密，用户授权确认机制上的开放型网络安全保障技术。密码学是研究信息系统安全保密的科学，它包括两个分支，即密码编码学和密码分析学。密码编码学是对信息进行编码实现信息隐藏的技术和科学。密码分析学是研究分析破译密码的技术与科学。明文是指发送方想要发送给接受方的消息。密文是指明文被加密后的消息。加密是将明文变换为密文的过程。解密是将密文恢复为明文的过程。密码学是一门既古老又年轻的科学，它最早的应用可以追溯到几千年前的古罗马，但成为一门独立的学科则是从近几十年才开始的。1949年shannon发表的“保密系统的信息理论”和1976年diffie和hellman的“密码学的新

7、方向”首次提出的公钥密码思想奠定了现在密码学的理论基础。1977年美国加密数据加密标准des的正式发布和1977年r.l.rivest, shamir,l.adleman三人共同提出的第一个公钥密码思想的密码体制rsa公钥密码成为现在密码学研究迅速发展的两个里程碑。根据加密密钥和解密密钥是否相同或者本质上等同，即从其中一个容易推出另一个，可将现有的加密体制分为两种。一种是单钥加密体制（也叫对称加密密码体制），其典型代表是美国的数据加密标准des（data encryption standard）；另一种是公钥密码体制（也叫非对称加密密码体制），其典型代表是rsa密码体制。des（data en

8、cryption standard）是迄今为止最为广泛采用的一种加密算法，也是最具代表性的一种分组密码体制。des是美国1977年公布实施的第一个公开被官方采用的加密算法。美国政府目前正在征集、评估和制定新的数据加密标准，新的标准被称作aes。尽管如此，des对于推动密码理论的发展和应用起了重大的作用。掌握和了解这一算法的基本原理、设计思想、安全性分析等问题，对于研究分组密码理论和其实际应用具有重要的意义。单钥密码体制的特点是解密密码与加密密钥相同或者是很容易从加密密钥推导出解密密钥。在单钥密码体制中，加密密钥的暴露会使系统变得不安全。单钥密码系统的一个严重缺陷是在任何密文传输之前，发送者和接

9、受者必须使用一个安全信道预先商定和传送密钥。在实际的通讯网中，通信双方则很难确定一条合理的安全通道。为了解决这些问题，w.diffie和m.hellman在1976年发表的划时代的“密码学的新方向”一文中，提出了公钥密码体制思想，为近代密码学指明了方向，克服了单钥密码体制的缺点。它的出现是密码学研究中的一项重大突破，也是现代密码学诞生的标志之一。在公钥密码体制中，解密密钥和加密密钥不同，难以从一个计算出另一个，解密运算和加密运算可以分离。通信双方无须先交换密钥就可以建立起保密通信。公钥密码体制克服了单钥密码体制的缺点，特别使用于计算机网络中的多用户通信，它大大减少了多用户通信所需的密钥量，接生

10、了系统资源，也便于密钥管理。1977年rivest，shamir和adleman提出了第一个比较完善的公钥密码算法，这就是著名的rsa算法。自从那时起，人们基于不同的计算问题，提出了大量的公钥密码算法。这些算法中，比较重要的有rsa算法、merkle-hellman背包算法、elgamal算法和椭圆曲线密码算法等。1.2使用rsa加密的意义对于比较短的消息的加密，可以使用rsa。比如，因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。可行的方法未必是必要的，本小节讨论何种文件适合用非对称密钥加密，即rsa加密文件的意义所在。对于带有重要信息的

11、小型文本的维护，如果不加密，将无法放心的保存在计算机上，尤其是连网的或机房里的公共计算机。如果借助功能强大的大型多用户数据保护程序维护几个小型文件，显得十分烦琐，好比杀鸡用牛刀。如果采用对称密钥加密，即加密解密的密钥相同，只适合部分情况。在某些情况下，使用对称密钥加密文件，交流使用不够方便。比如，张三由于某种原因，需要将自己的某个文件在公共计算机上留给李四，而不希望别人看到内容。如果采用对称密钥加密，张三和李四提前约好一个密码就可以。但是如果张三想要在同一台公共计算机上再留一个秘密文件给王五，而不希望别人看到，就要和王五另外约定一个密码。如果需要在这台公共计算机上留十个文件给不同的人，自己就要

12、记和十个人约定好的密码，这样以来交流起来不够方便，因为对于张三，要自己维护太多的密钥。非对称密钥(公开密钥方式)恰好解决这样的问题。只要大家都在这台计算机或这台计算机可以访问到的地方，留下自己的公开密钥，一切就变的容易解决了。张三要留给李四的文件，就用李四的公开密钥加密，要留给王五的文件，就用王五的公开密钥加密。李四和王五只要把留给自己的文件用自己的私有密钥解密，就可以得到留给自己的文件了。显然，非对称密钥体制更适合多用户交流，而将这种加密方式直接应用于文件加密，使我们在公开场合的交流更加灵活方便。一种更实际的情况是，我们想通过internet上的公众论坛或邮件发送重要保密信息给某人。例如发送

13、一个银行帐号和密码给某人。这种情况要保证安全，在当今互联网络上是比较棘手的。如果用公众论坛直接留言给指定用户，论坛管理员和服务器管理员通常有方法看到数据。如果发送邮件，虽然传送过程是加密的，但是密码毕竟是由邮件服务器维护，所以系统管理员通常也有办法看到内容。问题的关键在于我们所有的数据包括密钥保存在服务器之上。在这种情况下，我们需要使用公开密钥方式，并自己维护私有密钥。rsa文件加密可以灵活的解决这些问题。例如，我们可以将任意一个文件用某人的公开密钥加密变换成一段可以复制粘贴的文本，然后粘贴在公众互联网上，对方只需把需要解密的文本复制保存成一个文本文件，在本地机用自己的私有密钥解密即可。我们可

14、以将自己的私有密钥通过des加密后保存在自己的移动磁盘上，使用的时候只要将其解密读取即可，用完后立即从当前操作环境清除。这样，我们自己维护自己的私有密钥，利用简单并且公开的方式，可以安全传送任意小型数据。综上所述，使用rsa的方式加密文件有两点重要意义：应用rsa加密文件更能够确保文件的安全性，应用rsa加密文件可以解决很多对称加密文件中不能解决的问题。2 rsa相关理论知识2.1 rsa的数学基础知识2.1.1 关于数的基本理论整除：设a，b是任意两个整数，其中b0.如果存在一个整数q使得等式 a=bq成立，就称为b整除a或者a被b整除，记作b|a，并把b叫做a的因数，把a叫做b的倍数。这时

15、，q也是a的因数，我们常常将q写成a/b。否则，就称b不能整除a或者a不能被b整除。模运算：如果a模n运算，它给出了a的余数，余数是从0到n-1的某个整数，这种运算称为模运算。素数与合数：一个大于1的正整数p，只能被1和它本身整除，不能被其它正整数整除，则这样的正整数p叫做素数或者质数；一个大于1的正整数a，除了能被1和它本身整除外，还能被其它的正整数整除，这样的正整数a叫做复合数或者合数。这样，全体正整数可分为三类：1，全体素数，全体合数。公因数和最大公因数：设a1an 是n（n=2）个整数。若整数d是它们中每一个数的因数，那么d就叫做a1,an 的一个公因数.由于任何非零整数只存在有限个因

16、数。因此，如果b和c不全为0，b和c只存在有限个公因数。在所有公因数中最大的一个，就称为最大公因数，并用符号gcd（b,c）表示。同余：若n|a-b，若a -b = kn，k是整数，则称整数a和b 模n同余，记为a b (mod n )，n称为同余式的模。模n同余具有以下性质：1、若 n|a-b，则a b (mod n )；2、(a mod n) =(bmod n )等价于a b(mod n )；3、自反性：aa(mod n )；4、对称性：ab (modn ) 等价于b a (modn )；5、传递性：若ab (modn ) 且bc (mod n) ，则ac (modn )。欧拉函数：用符号

17、(m )表示不大于m 并和m 互素的正整数的个数，它是正整数m 的函数，称( m)为m 的欧拉函数。 (m )具有以下的性质：1、 (1) = 1；2、如果 p 是素数，则( p) = p-1；3、欧拉 函数是积极函数。即如果gcd( m ,n ) = 1,则(mn ) = (m )(n )2.1.2 欧拉定理 费马小定理欧拉定理和费马定理在公钥密码学中有重要的理论基础作用。欧拉定理：如果(a ,m) = 1，则恒有a( m ) 1(modm)其中,( m)为m的欧拉函数。欧拉定理的另一种等价形式为：a(m ) +1a(mod m)费马小定理：令p为素数，如果( p, a )= 1则有：a p

18、-11(mod p)费马小定理的另一种等价形式为：如果 p 为素数，a为任意正整数，则：a pa(mod p )因此费马小定理实际上是欧拉定理的一个推论。2.1.3 中国剩余定理设m1，m2，mk，是k个两两互素的正整数，则对任意的整数b1，bk, 同余式组 xb1 ( mod m1) xb2 ( mod m2) . xbk ( mod mk)一定有解，且解是唯一的，事实上 若令 m=m1mk,m=mimi, i=1,k 则同于式组的解可表示为 x b1m1m 1 +b2m2m2 +. .+bkmkmk(modm) 其中 mmi1(modmi), i=1.2,k-12.1.4单向陷门函数公钥密

19、码体制中公开密钥密码是基于单向陷门函数。所谓单向函数，认为有许多函数正向计算上是很容易的，但是求其逆计算在计算上是不可行的，也就是很难从输出推算出它的输入。即已知x，我们很容易求出f（x）。但是已知f（x），却难于计算出x。单向函数不能用作加密。因为用单向函数加密的信息是无人能解开它的。 单向陷门函数是有一个陷门的一类特殊单向函数。它首先是一个单向函数，在一个方向上易于计算而反方向却难以计算。但是，如果知道那个秘密陷门，则也能很容易在另一个方向计算这个函数。即已知x，易于计算f（x），而已知f（x），却难以计算x。然而，一旦给出f（x）和一些秘密信息y，就很容易计算出x。在公开密钥密码中，计算

20、f（x）相当于加密，陷门y相当于私有密钥，而利用陷门y求f（x）中的x则相当于解密。2.2 rsa加密解密算法rsa加密解密算法如下： 取两个随机大素数p和q（保密）； 计算公开的模数n=pq（公开）； 计算秘密的欧拉函数(n)=（p-1）（q-1）（保密），两个素数p和q不再需要，应该丢弃，不要让任何人知道； 随机选取整数e，满足gcd（e,(n)）=1（公开e，加密密钥）； 计算d，满足de1（mod(n)）（保密d，解密密钥，陷门信息）； 将明文m首先分成小于n的数据块，加密，从而产生密文，公式为ci=mie（modn）要解密信息，取每个加密块ci并计算 mi=cid（modn）因为ed

21、=1-r(n)，因此cid(mie)dm i(mi( n)-r mi(mod n) = mi其中，r 为整数。这里利用了欧拉定理： mi( n)1(mod n)。以上公式从密文恢复出了明文。公钥 n：两个素数p和q的乘积（p和q必须保密）。e：与( p- 1)(q-1 )互素私钥 d :e-1 (mod( p - 1)(q -1)加密 c = me(mod n)解密 m = cd(mod n)2.3 rsa参数的选择技术上，rsa 算法的安全性等价于求解 rsa 单向函数的逆的困难性。但是，在实际应用中，很多时候是因为算法实现的细节的漏洞导致攻击，所以在使用rsa 算法构造密码系统时，为了保证

22、系统的安全性，必须仔细选择各个参数。rsa的主要参数有三个：模数n，加密密钥e，解密密钥d。下面我们讨论参数的选择以及相关的问题。2.3.1 模数n的确定rsa模数n=pq 是rsa算法的安全性的核心。如果模数 n 被分解，则 rsa体制立刻被攻破。相当一部分的对rsa的攻击就是试图分解模数n。选择合适的n 是实现rsa算法的重要环节。一般地，模数n的确定可以遵循以下四个原则：1.为了使n = pq不易被分解，即躲开若干因子分解的有效算法，要求p和q不仅是素数，而且最好是强素数(strong prime)。素数 p 是强素数的条件为：(1)存在两个大素数 p1和 p2，使得 p1|p-1且p2

23、|p+1。(2)存在四个大素数：r1,s1, r2,s2使得 r1|p1-1, s1|p1-1，r2| p2-1,s2 |p2-1。这里称 r1，s1，r2及 s2为三级素数； p1和 p2为二级素数。2. p 与 q 之差要大(差几个位以上)。若 p 与 q 之差很小，则可由 n=pq 估计p+q 。又可知 ( p + q)/2)2 -n=(p-q)/2)2。两式联立方程组，可以用试探法解方程组可得 p，q 的值。3. p-1 与 q-1 的最大公因子要小。4. p 和 q 要足够大。这是应用 rsa 算法要遵守的最基本的原则。如果 rsa 算法是安全的，那么n=pq 必须足够大，使得因式分

24、解模数 n 在计算上不可行的。基于安全性考虑，实际应用中所选择的素数p和q至少应该为100位以上的十进制数，相应的模数n=pq将是200位的十进制数。建议使用至少100位长度的大素数，从而得到长度为200位以上的大整数模数n。这里给出一个一般性原则：1.临时性(casual )：384bit，经过努力可以破译。2.商用(commercial )：512bit，可由专业组织破译。3.军用(military )：1024bit，专家预测十年内不可破译。512bit (154位)、664bit (200位)rsa已有产品。电子邮件安全协议pgp使用了最大长度的rsa密钥，2047bit。根据许多安全

25、专家预测1024bit模数在今后十年内足够安全。但是随着计算能力的提高和分布式运算的发展，没有人敢断言具体的安全密钥的长度。2.3.2 模数e的选取原则在rsa算法中 gcd( e ,(n)=1 的条件很容易满足，这是因为任意两个随机整数互素的概率为3/5。如果e小(例如选3)，加、解密速度快，也便于存储，但是太小的 e 会导致安全性问题。一般地，e 有如下的选取原则：1.e 不可过小：一般地，e选16位素数，可以有效防止攻击，又有较快的速度。否则，若e小，而 x 也小；则对yxe(mod n)，当xe n，不用取模运算，直接将 y 开 e 次方就可以求得 x。另外，极容易导致小指数攻击。2.

26、最好选e为mod( n)的阶数，即存在i，使得ei1(mod ( n)，i达到( p-1)(q-1)/2，可以有效抗击攻击。2.3.2 d 的选取原则一般地，d 要大于n1/4。选定e后可用欧几里德算法在多项式时间内计算出 d。d的值小，签名和解密运算快，这对于智能卡加密、签名尤为重要。但是d不能太小，否则由已知明文攻击可以迭代计算出yxe(mod n)，再估算 d，计算 x d(mod n) ,直到满足xd 1(mod n)，而得到d值。另外有一种对小 d 的系统攻击法，证明当d=q)if(!(*p=0&*p=0&*p=9) temp2=*p-a+10; else temp2=*p-0p-;

27、if(temp1=12&temp2=12&temp=-52) break;temp=temp1+temp2*16;resulti=temp;i+;resulti=0;strcpy(str,result);5测试测试所用的rsa系统参数如下：模数n的值为：31231c53a1bf43bc6ef2d6d97f9267496789d04c4bdba213b0c04ce5c5267e8d88324cf512057206d50a82c9d27f6a8aef8b28c331f176743d975c7c8cd11954f9c58e7936225e6481755c21569b2e914e90bdab23c53

28、89f00296372b8d6cd40d229c0dcdfc0ca04aff36e92dc5c8a5be90c7145a4ede51f1c4f69fc2cf62b81加密时的加密密钥e的值为：3e54a6b290309a12ea282ec4d07c37e670142ec0e9c617e68f601b2cc0e282ef解密时的解密密钥d的值为：17ffd79d93ce7a37a788d4fa1666edfe62f5d7d2662b377814abf25c8e25cf3bd3da6768476981ef9ea8b8d2cd540a7a08b1b1350d7ecd6953285182b04ab21

29、2ca8df01014cb62ffbb8187de5237fac622d6db6ef857eae1a17d6e2badcce533ac87a5715639859b9d0b2dd33a935547bebf64f5b3959235d7a1281bddd7d75b测试用例1：明文分组为：密码学是研究信息系统安全保密的科学，它包括两个分支，即密码编码学和密码分析学。加密后得到的密文为：2f483bb3385794155aaea2b68f7bba987debb6b4ea6f8cf4064df4f37501a5dc7c69213eba564bbb2ddb8e621aa0e877065f0a6affa514f6bb9e6441086da6c29f6d0e9b840ba10628187ea81eb5d84dfa27b3198fd36cdba6dc51993b6588e0580a4c981e1b26bede124b9d316730d3999399e1e9702de46aaf91c19acca470解密得到的明文为：密码学是研究信息系统安全保密的科学，它包括两个分支，即密码编码学和密码分析学。测试用例2：明文分组为：网络工程系现有在校本科学生1360余名。专业教师40名，其中7名