RSA算法分析与编程实现
实验二 RSA算法
实验目的：
1．深入了解RSA加密算法的加密原理
2．通过编程模拟RSA算法的加密过程
实验内容：
一. RSA概述
①RSA加密算法是一种最常用的非对称加密算法，CFCA在证书服务中离不了它。在公钥加密标准和电子商业中，RSA被广泛使用。
②公钥和私钥
1. 随意选择两个大的质数p和q，p不等于q，计算N=pq。
2. 根据欧拉函数，不大于N且与N互质的整数个数为(p-1)(q-1)
3. 选择一个整数e与(p-1)(q-1)互质，并且e小于(p-1)(q-1)
4. 用以下这个公式计算d：d× e≡ 1 (mod (p-1)(q-1))
5. 将p和q的记录销毁。
(N,e)是公钥，(N,d)是私钥。(N,d)是秘密的。Alice将她的公钥(N,e)传给Bob，而将她的私钥(N,d)藏起来。
二.RSA算法的编程实现
#include
#include
using namespace std;
void main()
{
int p,q;//定义存放两个质数的变量
cout<<"请输入两个较大的素数："< cin>>p>>q; cout<<"p="< int n,o; n=p*q; o=(p-1)*(q-1); cout<<"n="< cout<<"请从【0，"< int e,i; float d; cin>>e;//输入e值 for(i=1;;i++)//计算d值 { d=(float)(o*i+1)/e; if(d-(int)d==0) break; } cout<<"e="< cout<<"公开密钥Pk={e,n}={"< cout<<"秘密密钥Sk={d,n}={"< cout< cout<<"请输入要加密的正整数（以-1结束）："< int m1[500],m3[500],m4[500]; double m2[500]; int j; for(j=0;j<500;j++)//对明文进行加密 { cin>>m1[j]; if(m1[j]==-1) break; m2[j]=pow(m1[j],e); m4[j]=m2[j]/n; m3[j]=m2[j]-m4[j]*n; } cout<<"密文为："< int k; for(k=0;k cout< cout< } 三.实例描述 在以下实例中只选取小数值的素数p,q,以及e，假设用户A需要将明文“key”通过RSA加密后传递给用户B，过程如下： （1）设计公私密钥(e,n)和(d,n)。 令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3，（3与20互质）则e×d≡1 mod f(n)，即3×d≡1 mod 20。 d怎样取值呢？可以用试算的办法来寻找。试算结果见下表： 通过试算我们找到，当d=7时，e×d≡1 mod f(n)同余等式成立。因此，可令d=7。从而我们可以设计出一对公私密钥，加密密钥（公钥）为：KU =(e,n)=(3,33)，解密密钥（私钥）为：KR =(d,n)=(7,33)。 （2）英文数字化。 将明文信息数字化，并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值，即： 则得到分组后的key的明文信息为：11，05，25。 （3）明文加密 用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由C≡Me(mod n)得： 因此，得到相应的密文信息为：11，26，16。 （4）密文解密。 用户B收到密文，若将其解密，只需要计算M= Cd(mod n),即： 用户B得到明文信息为：11，05，25。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“key”。 当然，实际运用要比这复杂得多，由于RSA算法的公钥私钥的长度（模长度）要到1024位甚至2048位才能保证安全，因此，p、q、e的选取、公钥私钥的生成，加密解密模指数运算都有一定的计算程序，需要仰仗计算机高速完成。 四.运行结果 五.RSA的安全性 在RSA密码应用中，公钥KU是被公开的，即e和n的数值可以被第三方窃听者得到。破解RSA密码的问题就是从已知的e和n的数值（n等于pq），想法求出d 的数值，这样就可以得到私钥来破解密文。从上文中的公式：d ≡e-1 (mod((p-1)(q-1)))或de≡1 (mod((p-1)(q-1))) 我们可以看出。密码破解的实质问题是：从pq的数值，去求出(p-1)和(q-1)。换句话说，只要求出p和q的值，我们就能求出d的值而得到私钥。 当p和q是一个大素数的时候，从它们的积pq去分解因子p和q，这是一个公认的数学难题。比如当pq大到1024位时，迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。然而，虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。 此外，RSA的缺点还有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。因此，使用RSA只能加密少量数据，大量的数据加密还要靠对称加密算法。 六.心得体会 通过本次实验，我对非对称加密算法RSA的理解加深了，会运用一些现成的算法进行编程，对一些比较复杂的算法有了进一步的认识。