实验二：RSA公钥密码体制.doc

实验二：RSA公钥密码加、解密技术一、实验目的通过编写RSA算法（小素数）程序，并运行此程序对实验数据进行加密和解密操作，使学生进一步掌握RSA公钥密码体制。二、实验要求（1）用V C+写出加密、解密程序代码。（要求完成加密和解密,明文仅限为英文字母、数字、空格和标点符号）；（2）运行自己编写的程序，输入素数p=7,q=13：明文为最多两位整数学号： 如2，23等，得出相应的密文，并对其解密，验证解密后得到的明文是否与输入的学号相同。三、相关知识1976年，W.DiffieM.E.Hellman提出了公钥密码学的思想。在公钥密码体制中，加密密钥和解密密钥是不一样的，加密密钥可以公开传播而不危及密码体制的安全性。公钥密码体制主要有三种：RSA公钥密码体制、EIGamal公钥密码体制、Menezes-Vanstone公钥密码体制。本次实验内容是关于RSA公钥密码体制。RSA公钥密码体制的安全性是基于大整数的素分解问题的难解性。其有自身的优缺点,优点是加密密钥可以公开传播，缺点是运算速度较慢。算法描述：（本次试验只要求对小素数实现RSA算法）1. 密钥的产生 1) 找出两个相异的素数P和Q，令NPQ，M（P1）（Q1）。 2) 找出与M互素的整数E，且 1EM利用欧氏算法计算出整数D，使DE1 MOD M。欧氏算法: n1M,n2E,b10,b21; k=n1/n2,rn1-k*n2; 如果r0，则n1n2,n2r,tb2,b2b1-k*b2,b1t;转第步； 如果n21,则E模M 不存在逆元； 如果n2=1，则E模M 的逆元为b2 mod M为什么有：E模M 的逆元为b2 mod M根据课本中定理5.6，只要E,M互素且1EM，则存在整数a, b使得：b*E + a*M=1 于是： b*E mod M=1令 b1(0)=0,b2(0)=1,则：n1(0)=a1(0)n1(0)+b1(0)n2(0)n2(0)=a2(0)n1(0)+b2(0)n2(0)假设 i=j时成立，则有n1(j)=a1(j)n1(0)+b1(j)n2(0)n2(j)=a2(j)n1(0)+b2(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） mod M ,则 b2*E mod M = 1 故：b2是E关于模M的逆元3) 丢弃P和Q，公开E，D和N。E和N即加密密钥，D和N即解密密钥。 2. 明文加密字符a属于明文集A ,进行caE MOD N运算。c就是密文数据的一个字符块，将所有密文块合并起来，就得到了密文数据C。3. 密文解密字符块c属于密文C，进行acD MOD N运算。a就是明文数据的一块，将所有明文块合并起来，就得到了明文数据A。 /*RSA algorithm */ #include #include #include #include #include using namespace std;int gcd(int x,int y) /* 求x y的最大公因子*/ int t; while (y) t=x, x=y, y=t%y; return x; long cmp(long a) /*求与a互素的数*/long x,y;for (long i=3;ia;i+)y=i;x=gcd(i,a);/*如果两个数的最大公因子为1 则这两个数互素*/if(x=1)break;return y;int niyuan(int sn,int e)int d, n1,n2, b2=1,b1=0,k,r,t;n1=sn;n2=e;while(1) k=n1/n2; r=n1-k*n2; if(r!=0)n1=n2;n2=r;t=b2;b2=b1-k*b2;b1=t;elsebreak;if(n2!=1)coute关于模sn的逆元不存在。endl;exit(0);d=(sn+b2)%sn;return d;void main()long int m,n,d,c,p,q,e,sn,k,r,n1,n2,t,b1=0,b2=1;cout*RSA加密解密过程的演示*endl;cout请输入小整数明文:m;cout输入两个小素数p,q:pq;n=p*q;sn=(p-1)*(q-1);cout计算后得到：endl;coutn=nendl;coutsn=snendl;cout请输入与sn互素的小整数e时e;d=niyuan(sn,e);coutd=dendl