RSA加解密过程及实现

********************本科生作业********************兰州理工大学计算机与通信学院2017年春季学期信息安全课程专业：物联网工程姓名：学号：授课教师：郭显成绩：RSA加解密过程及其实现1.RSA概述1.1RSA算法RSA加密算法是一种最常用的非对称加密算法，CFCA在证书服务中离不了它。在公钥加密标准和电子商业中，RSA被广泛使用。RSA算法使用乘方运算，明文以分组为单位进行加密，每个分组的二进制值均小于n，也就是说，分组的大小必须小于或等于1)(log2n位，在实际应用中，分组的大小i位，其中122iin。对明文分组M和密文分组C，加密和解密过程如下：nMCemodnMnMnCMeddedmodmod)(mod其中收发双方均已知n，发送方已知e，只有接收方已知d，因此公钥加密算法的公钥为PU={e,n}，私钥为PR={d,n}。该算法要能做公钥加密，必须满足以下条件：（1）可以找到e,d,n,使得对所有的Mn,有MnMedmod。（2）对所有的Mn,计算eM和dC是比较容易的。（3）由e和n确定d是不可行的。1.2公钥与私钥（1）随意选择两个大素数p和q，p不等于q，计算pqn。（2）根据欧拉函数，不大于n且与n互素的整数个数为)1)(1(qp（3）选择一个整数e与)1)(1(qp互素，并且e小于)1)(1(qp（4）用以下这个公式计算d：))1)(1mod((1qpde（5）将p和q的记录销毁。),(en是公钥，),(dn是私钥。),(dn是秘密的。Alice将她的公钥),(en传给Bob，而将她的私钥),(dn藏起来。图1RSA加密过程2.实例描述（1）选择两个素数，11,17qp。（2）计算1871117pqn。（3）计算1601016)1)(1()(qpn。（4）选择e使其与160)(n互素且小于)(n，这里选择7e。（5）确定d使得160mod1de且160d。因为11601161723，所以23d。d可利用扩展的欧几里得算法来计算。所得的公钥}187,7{PU、私钥}187,23{PR。该例说明了输入明文177M时这些密钥的使用情况。加密时需计算187mod1777C。利用模算术的性质，我们如下计算：187mod)]187mod177()187mod177()187mod177[(187mod177247177187mod177100187mod31329187mod177289187mod981506241187mod177412187mod1575300187mod)89100177(187mod1777解密时，我们计算187mod1223M187mod)]187mod12()187mod12()187mod12()187mod12()187mod12[(187mod1288422312187mod12144187mod122166187mod20736187mod12467187mod429981696187mod128177187mod1287660672187mod)676716614412(187mod11233.RSA算法的安全性在RSA密码应用中，公钥PU是被公开的，即e和n的数值可以被第三方窃听者得到。破解RSA密码的问题就是从已知的e和n的数值（n等于pq），想法求出d的数值，这样就可以得到私钥来破解密文。从上文中的公式：)))1)(1(mod((1qped或))1)(1mod((1qpde我们可以看出。密码破解的实质问题是：从pq的数值，去求出)1(p和)1(q。换句话说，只要求出p和q的值，我们就能求出d的值而得到私钥。当p和q是一个大素数的时候，从它们的积pq去分解因子p和q，这是一个公认的数学难题。比如当pq大到1024位时，迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。然而，虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。此外，RSA的缺点还有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。因此，使用RSA只能加密少量数据，大量的数据加密还要靠对称加密算法。4.程序代码#includestdio.hintrsa(inta,intb,intc){intr=1;b=b+1;while(b!=1){r=r*a;r=r%c;b--;}printf(%d\n,r);returnr;}voidmain(){intp,q,e,d,m,n,t,c,r;chars;printf(请输入p,q:);scanf(%d%d,&p,&q);n=p*q;printf(n的值是%4d\n,n);t=(p-1)*(q-1);//欧拉函数printf(t的值是%4d\n,t);printf(请输入e:);scanf(%d,&e);if(e1||et){printf(e出错,请重新输入);scanf(%d,&e);}d=1;while(((e*d)%t)!=1)d++;printf(thencaculateoutthatthedis%d\n,d);printf(加密请输入1\n);printf(解密请输入2\n);scanf(%d,&r);switch(r){case1:printf(输入要加密的明文数字m:);/*输入要加密的明文数字*/scanf(%d,&m);c=rsa(m,e,n);printf(其密码是%d\n,c);break;case2:printf(输入要解密的密文数字c:);/*输入要解密的密文数字*/scanf(%d,&c);m=rsa(c,d,n);printf(其密码是%d\n,m);break;}}5.程序测试结果图2RSA加密图3RSA解密总结：通过c语言的程序实现对RSA算法的理解加深了。