实验二：RSA公钥密码体制

《实验二：RSA公钥密码体制》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二：RSA公钥密码加、解密技术一、实验目的通过编写RSA算法（小素数）程序，并运行此程序对实验数据进行加密和解密操作，使学生进一步掌握RSA公钥密码体制。二、实验要求（1）用VC++写出加密、解密程序代码。（要求完成加密和解密,明文仅限为英文字母、数字、空格和标点符号）；（2）运行自己编写的程序，输入素数p=7,q=13：明文为最多两位整数学号：如2，23等，得出相应的密文，并对其解密，验证解密后得到的明文是否与输入的学号相同。三、相关知识1976年，W.DiffieM.E.Hellman提出了公钥密码学的思想。在公钥密码体制中，加密密钥和解密密钥是不一样的，加密密钥可以公开传播而不危及

2、密码体制的安全性。公钥密码体制主要有三种：RSA公钥密码体制、EIGamal公钥密码体制、Menezes-Vanstone公钥密码体制。本次实验内容是关于RSA公钥密码体制。RSA公钥密码体制的安全性是基于大整数的素分解问题的难解性。其有自身的优缺点,优点是加密密钥可以公开传播，缺点是运算速度较慢。算法描述：（本次试验只要求对小素数实现RSA算法）1.密钥的产生1)找出两个相异的素数P和Q，令N＝P×Q，M＝（P－1）（Q－1）。2)找出与M互素的整数E，且1

3、n1-k*n2;③如果r≠0，则n1←n2,n2←r,t←b2,b2←b1-k*b2,b1←t;转第②步；④如果n2≠1,则E模M不存在逆元；⑤如果n2=1，则E模M的逆元为b2modM为什么有：E模M的逆元为b2modM根据课本中定理5.6，只要E,M互素且1

4、(j)n2(0)当i=j+1时有：n1(j+1)=n2(j)=a2(j)n1(0)+b2(j)n2(0)n2(j+1)=n1(j)-q(j)n2(j)=a1(j)n1(0)+b1(j)n2(0)-q(j){a2(j)n1(0)+b2(j)n2(0)}=(a1(j)-q(j)a2(j))n1(0)+(b1(j)-q(j)b2(j))n2(0)这样循环下去，直到q(i)=0,n2(i)=1则b2（i）满足：b2（i）*E+a*M=1令：b2=b2（i）modM,则b2*EmodM=1故：b2是E关于模M的逆元3)丢弃P和Q，公开E，D和N。E和N即加密密钥，D和N即解密密钥。2.明文加密字符a属

5、于明文集A,进行c＝a^EMODN运算。c就是密文数据的一个字符块，将所有密文块合并起来，就得到了密文数据C。3.密文解密字符块c属于密文C，进行a＝c^DMODN运算。a就是明文数据的一块，将所有明文块合并起来，就得到了明文数据A。5/*RSAalgorithm*/#include#include#include#include#includeusingnamespacestd;intgcd(intx,inty)/*求xy的最大公因子*/{intt;while(y)t=x,x=y,y=t%y;retu

6、rnx;}longcmp(longa)/*求与a互素的数*/{longx,y;for(longi=3;i

7、endl;exit(0);}d=(sn+b2)%sn;returnd;}voidmain(){longintm,n,d,c,p,q,e,sn,k,r,n1,n2,t,b1=0,b2=1;cout<<"*****RSA加密解密过程的演示*****"<>m;cout<<"输入两个小素数p,q:"<>p>>q;n=p*q;sn=