c语言实现rsa加密算法过程详解

　　一、RSA算法 

　　首先， 找出三个数， p， q， r，

　　其中 p， q 是两个相异的质数， r 是与 （p-1）（q-1） 互质的数

　　p， q， r 这三个数便是 private key

　　接著， 找出 m， 使得 rm == 1 mod （p-1）（q-1）

　　这个 m 一定存在， 因为 r 与 （p-1）（q-1） 互质， 用辗转相除法就可以得到了

　　再来， 计算 n = pq

　　m， n 这两个数便是 public key

　　编码过程是， 若资料为 a， 将其看成是一个大整数， 假设 a 《 n

　　如果 a 》= n 的话， 就将 a 表成 s 进位 （s 《= n， 通常取 s = 2^t），

　　则每一位数均小於 n， 然後分段编码

　　接下来， 计算 b == a^m mod n， （0 《= b 《 n），

　　b 就是编码後的资料

　　解码的过程是， 计算 c == b^r mod pq （0 《= c 《 pq），

　　於是乎， 解码完毕 等会会证明 c 和 a 其实是相等的 ：）

　　如果第三者进行窃听时， 他会得到几个数： m， n（=pq）， b

　　他如果要解码的话， 必须想办法得到 r

　　所以， 他必须先对 n 作质因数分解

　　要防止他分解， 最有效的方法是找两个非常的大质数 p， q，

　　使第三者作因数分解时发生困难

　　《定理》

　　若 p， q 是相异质数， rm == 1 mod （p-1）（q-1），

　　a 是任意一个正整数， b == a^m mod pq， c == b^r mod pq，

　　则 c == a mod pq

　　证明的过程， 会用到费马小定理， 叙述如下：

　　m 是任一质数， n 是任一整数， 则 n^m == n mod m

　　（换另一句话说， 如果 n 和 m 互质， 则 n^（m-1） == 1 mod m）

　　运用一些基本的群论的知识， 就可以很容易地证出费马小定理的

　　《证明》

　　因为 rm == 1 mod （p-1）（q-1）， 所以 rm = k（p-1）（q-1） + 1， 其中 k 是整数

　　因为在 modulo 中是 preserve 乘法的

　　（x == y mod z and u == v mod z =》 xu == yv mod z），

　　所以， c == b^r == （a^m）^r == a^（rm） == a^（k（p-1）（q-1）+1） mod pq

　　1. 如果 a 不是 p 的倍数， 也不是 q 的倍数时，

　　则 a^（p-1） == 1 mod p （费马小定理） =》 a^（k（p-1）（q-1）） == 1 mod p

　　a^（q-1） == 1 mod q （费马小定理） =》 a^（k（p-1）（q-1）） == 1 mod q

　　所以 p， q 均能整除 a^（k（p-1）（q-1）） - 1 =》 pq | a^（k（p-1）（q-1）） - 1

　　即 a^（k（p-1）（q-1）） == 1 mod pq

　　=》 c == a^（k（p-1）（q-1）+1） == a mod pq

　　2. 如果 a 是 p 的倍数， 但不是 q 的倍数时，

　　则 a^（q-1） == 1 mod q （费马小定理）

　　=》 a^（k（p-1）（q-1）） == 1 mod q

　　=》 c == a^（k（p-1）（q-1）+1） == a mod q

　　=》 q | c - a

　　因 p | a

　　=》 c == a^（k（p-1）（q-1）+1） == 0 mod p

　　=》 p | c - a

　　所以， pq | c - a =》 c == a mod pq

　　3. 如果 a 是 q 的倍数， 但不是 p 的倍数时， 证明同上

　　4. 如果 a 同时是 p 和 q 的倍数时，

　　则 pq | a

　　=》 c == a^（k（p-1）（q-1）+1） == 0 mod pq

　　=》 pq | c - a

　　=》 c == a mod pq

　　首先是密钥对的生成：

　　（1）选取两个大素数p和q（目前两个数的长度都接近512bit是安全的）

　　（2）计算乘积n=p*q，Φ（n）=（p-1）（q-1），其中Φ（n）为n的欧拉函数（因为两素数乘积的欧拉函数等于两数分别减一后的乘积）

　　（3）随机选取整数e（1《e《Φ（n））作为公钥d，要求满足e与Φ（n）的最大公约数为1，即两者互素

　　（4）用Euclid扩展算法计算私钥d，已满足d * e ≡ 1 （mod Φ（n）），即d ≡ e^（-1） （mod Φ（n））。则e与n是公钥，d是私钥

　　注意：e与n应公开，两个素数p和q不再需要，可销毁，但绝不可泄露。

　　加密过程：

　　将接收到的明文转换成特定的编码方式。如p=43，q=59，e=13，明文为cybergreatwall，按照英文字母表的顺序a=00，b=01，。。。 ，z=25进行编码后为022401041706001922001111。

　　然后将转码后的字符串分块，分组要求：每个分组对应的十进制数小于0。这个要求是什么意思呢？我个人的理解通过举例向大家说明：上文字符串分组如下0224 0104 1706 0019 2200 1111。每一分组的数都小于n（2537），而2537能接受的最大的数为2525（也就是‘zz’的情况），所以是4位1组，即两字符一组。这样一来，m1=0224，m2=0104，。。。 ，m6=1111

　　现在可以加密了~~加密算法就是这个式子----ci ≡ mi^e （mod n），如第一分组 0224^13 ≡ mod 2537 ≡ 1692=c1 。这里有个隐藏的算法是需要了解的：

　　在RSA算法过程中容易出现天文数字（像上文的0224^13），而这些天文数字会为我们编程的过程造成一定的麻烦，更可恶的是会影响速度！！为了避免这种情况，快速取模指数算法可以很有效地算出c≡m^e mod n的准确结果且避免过程中出现天文数字~~

　　这个定理说明 a 经过编码为 b 再经过解码为 c 时， a == c mod n （n = pq）

　　但我们在做编码解码时， 限制 0 《= a 《 n， 0 《= c 《 n，

　　所以这就是说 a 等於 c， 所以这个过程确实能做到编码解码的功能

　　二、RSA 的安全性

　　RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解 RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前， RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。

　　三、RSA的速度

　　由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。

　　四、RSA的选择密文攻击

　　RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装（ Blind），让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：

　　（ XM ）^d = X^d *M^d mod n

　　前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公 钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用 One-Way HashFunction 对文档作HASH处理，或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。

　　五、RSA的公共模数攻击

　　若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：

　　C1 = P^e1 mod n

　　C2 = P^e2 mod n

　　密码分析者知道n、e1、e2、C1和C2，就能得到P。

　　因为e1和e2互质，故用Euclidean算法能找到r和s，满足：

　　r * e1 + s * e2 = 1

　　假设r为负数，需再用Euclidean算法计算C1^（-1），则

　　（ C1^（-1） ）^（-r） * C2^s = P mod n

　　另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无需分解模数。解决办法只有一个，那就是不要共享模数n。

　　RSA的小指数攻击。 有一种提高 RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有

　　所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。

　　RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能 如何，而且密码学界多数人士倾向于因子分解不是NPC问题。 RSA的缺点主要有：A）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B）分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET（ Secure Electronic Transaction ）协议中要求CA采用比特长的密钥，其他实体使用比特的密钥。

　　下面用伪代码为大家介绍下这种神奇的算法（个人感觉伪代码里的 ‘《-’ 就是平时用的 ‘=’ ）：

　　t《-0;c《-1

　　for i《-k downto 0

　　do t《-2*t

　　c《-（c*c）mod n

　　if bi=1 then t《-t+1

　　c《-（c*m）mod n

　　return c

　　（p.s：e的二进制表示为bk bk-1 。。。 b0，如e=13=（1101），所以k为3）

　　所以，用快速取模指数算法计算上文例子里的c1过程就该是这样子哒：

　　i 3 2 1 0

　　bi 1 1 0 1

　　t 1 3 6 13

　　ci （1*224）mod2537 （224*224*224）mod2537 （514*514）mod2537 （348*348*224）mod2537

　　=224 =514 =348 =1692

　　到这里RSA加密的算法就讲完了，下面附上代码

　　［cpp］ view plain copy#include《stdio.h》

　　#include《stdlib.h》

　　/* 函数申明 */

　　int long_n（int n）;

　　int shuru（char *arr， int k， char *wei， int is_first）;

　　void jiami（char *arr， int k， int e， int n）;

　　/* 输入函数，记录从键盘输入的明文*/

　　int shuru（char *arr， int k， char *wei， int is_first）

　　{

　　int i;

　　char ch;

　　/*判断是否为第一分组的输入，如果是则获取输入的字符，否则就将上一分组最后获取的字符作为这一分组的第一个字符*/

　　if （is_first == 1）

　　ch = getchar（）;

　　else

　　ch = *wei;

　　for （i = 0; （i 《 k） && （ch ！= ‘ ’）;i++） //获取字符直到获取到回车符为止

　　{

　　arr［i］ = ch;

　　ch = getchar（）;

　　}

　　*wei = ch; //最后获取到的字符准备作为下一分组的第一个字符

　　for （i = i; i 《 k; i++）

　　arr［i］ = ‘a’; //输入不够一组个数的整数倍则补‘a’（即为补零）

　　if （ch == ‘ ’） //接收到回车符返回0，否则为1

　　return 0;

　　else

　　return 1;

　　}

　　/*加密函数*/

　　void jiami（char *arr， int k， int e， int n）

　　{

　　int m = 0，c=1， i， j，t=0， shu，temp，num=0;

　　int *array;

　　/*Mi赋值过程*/

　　for （i = 0; i 《 k; i++）

　　{

　　temp = 1;

　　for （j = 0; j 《 （k-i-1）*2; j++）

　　temp = temp * 10;

　　shu = （int）arr［i］ - 97;

　　m = m + temp * shu;

　　}

　　temp = e;

　　/*获取e的二进制表达形式的位数*/

　　do{

　　temp = temp / 2;

　　num++;

　　} while （temp ！= 0）;

　　array = （int *）malloc（sizeof（int）*k）; //申请动态数组

　　temp = e;

　　/*动态数组存储e的二进制表达形式*/

　　for （i = 0; i 《 num; i++）

　　{

　　array［i］ = temp % 2;

　　temp = temp / 2;

　　}

　　/*避免出现天文数字的算法，详情见上文文字说明*/

　　for （i = num - 1; i 》= 0; i--）

　　{

　　t = t * 2;

　　temp = c*c;

　　if （temp 》 n）

　　{

　　for （j = 0; temp - n*j 》= 0; j++）;

　　j--;

　　c = temp - n*j;

　　}

　　else

　　c = temp;

　　if （array［i］ == 1）

　　{

　　t = t + 1;

　　temp = c*m;

　　if （temp 》 n）

　　{

　　for （j = 0; temp - n*j 》= 0; j++）;

　　j--;

　　c = temp - n*j;

　　}

　　else

　　c = temp;

　　}

　　e = e / 2;

　　}

　　temp = c;

　　i = 0;

　　/*c的位数小于分组长度则在前补零*/

　　do{

　　temp = temp / 10;

　　i++;

　　} while （temp ！= 0）;

　　for （i; i 《 num; i++）

　　printf（“0”）;

　　printf（“%d”， c）;

　　}

　　/*获取分组的长度*/

　　int long_n（int n）

　　{

　　int temp，i，j，k，shi，comp=0;

　　temp = n;

　　/*获取n的位数*/

　　for （i = 1; temp / 10 ！= 0; i++）

　　{

　　temp = temp / 10;

　　}

　　temp = i;

　　/*若n的位数为基数*/

　　if （i % 2 ！= 0）

　　{

　　i = i - 1;

　　return i;

　　}

　　/*若位数为偶数*/

　　else

　　{

　　for （j = 0; j 《 i/2; j++）

　　{

　　shi = 1;

　　for （k = 0; k 《 temp - 2; k++）

　　shi = shi * 10;

　　comp = comp + shi * 25;

　　temp = temp - 2;

　　}

　　if （comp 《= n）

　　return i;

　　else

　　{

　　i = i - 2;

　　return i;

　　}

　　}

　　}

　　/*主函数*/

　　int main（）

　　{

　　int p， q， e， d， n， fai_n， k， i，is_first=1;

　　char ch，*arr，wei=‘a’;

　　printf（“请输入p、q、e值，用空格间隔开 ”）;

　　scanf_s（“%d%d%d”， &p， &q， &e）; //从键盘获取p、q、e值

　　n = p*q;

　　fai_n = （p-1）*（q-1）; //Φ（n）

　　for （k = 0; （k*n + 1） % e ！= 0; k++）;

　　if （（k*n + 1） % e == 0）

　　d = （k*n + 1） / e; //d * e ≡ 1 （mod Φ（n））

　　k = long_n（n）;

　　k = k / 2; //分组的长度

　　ch = getchar（）; //缓冲回车符

　　arr = （char *）malloc（sizeof（char）*k）; //申请动态数组

　　printf（“请输入明文 ”）;

　　while （1）

　　{

　　i=shuru（arr，k，&wei，is_first）; //调用输入字符的函数，接收到回车符返回0，否则为1

　　is_first = 0; //第一分组录入结束设为0

　　jiami（arr，k，e，n）; //调用加密函数

　　if （i == 0） //接收到返回值为0跳出循环

　　break;

　　}

　　printf（“ ”）;

　　return 0;

　　}

　　运行结果：

　　

　　C语言实现

　　/*

　　算法描述

　　1．选择两质数p、q 2. 计算n = p*q，【注意实际要加密的数据要小于n】。

　　3. 计算n的欧拉函数 （n）=（p-1）（q-1）。

　　4. 选择整数e，使e与 （n）互质，且1《e《 （n）。

　　5. 计算d，使d*e=1 mod （n）。

　　6. 其中，公钥 KU＝{e，n}，私钥 KR＝{d，n}。

　　7. 加密：C=Me mod n

　　8. 解密：M＝Cd mod n=（Me）d mod n= Med mod n 。

　　*/

　　#include 《Windows.h》

　　#include 《stdio.h》

　　int candp（int a，int b，int c）

　　{

　　int r=1;

　　b=b+1;

　　while（b！=1）

　　{

　　r=r*a;

　　r=r%c;

　　b--;

　　}

　　printf（“%d ”，r）;

　　return r;

　　}

　　void main（）

　　{

　　int p，q，e，d，m，n，t，c，r;

　　char s;

　　printf（“please input the p，q： ”）;

　　scanf（“%d%d”，&p，&q）;

　　n=p*q;

　　printf（“the n is %3d ”，n）;

　　t=（p-1）*（q-1）;

　　printf（“the t is %3d ”，t）;

　　printf（“please input the e： ”）;

　　scanf（“%d”，&e）;

　　if（e《1||e》t）

　　{

　　printf（“e is error，please input again： ”）;

　　scanf（“%d”，&e）;

　　}

　　d=1;

　　while（（（e*d）%t）！=1）

　　d++;

　　printf（“then caculate out that the d is %d ”，d）;

　　bool flag = false;

　　while（1）

　　{

　　printf（“exit please input 0 ”）;

　　printf（“the cipher please input 1 ”）;

　　printf（“the plain please input 2 ”）;

　　scanf（“%d”，&r）;

　　switch（r）

　　{

　　case 0：

　　flag = true;

　　break;

　　case 1： printf（“input the m： ”）; /*输入要加密的明文数字*/

　　scanf（“%d”，&m）;

　　c=candp（m，e，n）;

　　printf（“the cipher is %d ”，c）;

　　flag = false;

　　break;

　　case 2： printf（“input the c： ”）; /*输入要解密的密文数字*/

　　scanf（“%d”，&c）;

　　m=candp（c，d，n）;

　　printf（“the cipher is %d ”，m）;

　　flag = false;

　　break;

　　}

　　if（flag）

　　break;

　　}

　　system（“pause”）;

　　}