RSA加密算法

1网络工程131任国健1308060317一、RSA加密简介RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（RonRivest）、阿迪·萨莫尔（AdiShamir）和伦纳德·阿德曼（LeonardAdleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（CliffordCocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。二、RSA原理RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。尽管如此，只有一些RSA算法的变种被证明为其安全性依赖于因数分解。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。2三、密钥生成随意选择两个大的质数p和q，p不等于q，计算qpn*。根据欧拉函数，求得1)-(q1)-(p=φ(q)φ(p)=φ(n)选择一个整数e使得(n)φe1且1=φ(n))gcd(e,，(n,e)作为公钥发布选择一个整数d使得d是e关于模φ(n)的模反元素即φ(n))(moded-1，φ(n))(mod1≡ed，把(n,d)作为私钥保存。将p和q的记录销毁。设明文分组m，则加密算法为：)mod(nmce对密文分组c的解密运算为：)mod(ncmd四、代码实现//主函数voidmain(){intp,q,e,d,n,yn,m[1000],c[10000];//c[10000]存放加密后的数字密文，m[1000]存放解密后的数字明文，即英文明文在zimu_biao[69]中的下标。inti,j;//i,j用于循环遍历数组intmi_yue;//用户输入的密钥intcount=1;//统计输入密钥的次数，count3时将不允许用户再输入。charmin_wen[1000],re_min_wen[1000];//分别为用户输入的明文、密文，解密后的明文。//密钥生成3charzimu_biao[69]=abcdefghijklmnopqrstuvwxyz,ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'.?!;printf(请输入您要发送的明文文件（小写英文表示）:\n);printf(******************************************************\n);gets(min_wen);printf(******************************************************\n);printf(\n加密开始，请按要求操作。。。\n\n);printf(请输入第一个大素数p：\n);while(1){scanf(%d,&p);if(Witness(2,p)==1){printf(您输入的第一个大素数%d符合要求\n,p);break;}elseprintf(您输入的%d不是素数,请重新输入：\n,p);}printf(请输入第二个大素数q：\n);while(1){scanf(%d,&q);if(Witness(2,q)){printf(您输入的第二个大素数%d符合要求\n,q);break;}elseprintf(您输入的%d不是素数,请重新输入：\n,q);}n=p*q;yn=(p-1)*(q-1);printf(请输入加密指数（整数）e,且0e%d\n,yn);//下面由用户设定加密指数while(1){scanf(%d,&e);if(gcd(yn,e)==1){printf(您输入加密指数%d与%d互素,符合要求\n,e,yn);break;}elseprintf(您输入加密指数%d与%d不互素,请重新输入。。。\n,e,yn);}d=extend(yn,e);//求解密指数dprintf(\n\n请记住您的两个大素数分别为p=%d(保密),q=%d(保密),模数n=%d(公开),欧4拉函数yn=%d(保密),加密指数e=%d(公钥,公开),。。。解密指数d=%d(私钥,保密)\n\n,p,q,n,yn,e,d);//明文转换过程/*scanf(%s,min_wen);printf(%s,min_wen);*/for(i=0;istrlen(min_wen);i++)for(j=0;j68;j++)//for(j=0;j26;j++)if(min_wen[i]==zimu_biao[j])m[i]=j;//将字符串明文换成数字，并存到整型数组m里面，即明文的另一种表示方法//加密过程for(i=0;istrlen(min_wen);i++)c[i]=js_mod(m[i],e,n);printf(输出密文：\n);printf(******************************************************\n);for(i=0;istrlen(min_wen);i++)printf(%d,c[i]);printf(\n******************************************************\n);//解密过程for(i=0;istrlen(min_wen);i++)m[i]=js_mod(c[i],d,n);for(i=0;istrlen(min_wen);i++)re_min_wen[i]=zimu_biao[m[i]];//提示用户解密printf(\n\n您有3次输入密钥的机会，密钥正确后将进行解密显示明文，3次输入错误解密将终止，请注意。。。\n\n);while(1){scanf(%d,&mi_yue);if(mi_yue==d){printf(密钥输入正确，您得到的明文为：\n\n);for(i=0;istrlen(min_wen);i++)printf(%c,re_min_wen[i]);printf(\n\n);break;}else{printf(您第%d次输入的密钥错误，请重新输入。。。\n,count);count++;if(count3){printf(\n您已%d次输入的密钥错误，将不允许继续输入\n,count-1);5break;}}}}五、运行结果6六、用途RSA除了可以用来加密意外也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话，那么他可以为他的消息计算一个散列值(Messagedigest)，然后用她的密钥(privatekey)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。