一、RSA加密简介
RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
1973年，在英国通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。
二、RSA原理
RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。尽管如此，只有一些RSA算法的变种被证明为其安全性依赖于因数分解。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。
三、密钥生成
随意选择两个大的质数和，不等于，计算。
根据欧拉函数，求得选择一个整数使得且， (n, e) 作为公钥发布
选择一个整数使得是关于模的模反元素即，，把(n, d) 作为私钥保存。
将 p 和 q 的记录销毁。
设明文分组，则加密算法为：
对密文分组的解密运算为：
四、代码实现
加密解密部分实现有错误，还需继续分析。
#include long p = 149, q = 193, n, r, e, d; int is_primenumber(int num); long (long a, long b); int main() { char *w = "请输入质数p：", str[100] = {'\\0',}, decrypt[100] = {'\\0',}; long a, b, c, encrypt[100] = {0,}; int i = 0, len; input_p: printf("%s", w); scanf("%ld", &p); if (!is_primenumber(p)) { printf("%ld不是质数\\n", p); w = "请重新输入p："; goto input_p; } printf("您输入的是%ld\\n", p); w = "请输入质数q："; input_q: printf("%s", w); scanf("%ld", &q); if (!is_primenumber(q)) { printf("%l不是质数\\n", q); w = "请重新输入q："; goto input_q; } printf("您输入的是%ld\\n", q); n = p * q; r = (p-1) * (q-1); e = 2; while(1) { if ((e, r) == 1) break; e++; } d = 1; while(1) { if((r * d + 1) % e == 0) { d = (r * d + 1 ) / e; break; } d++; } printf("n=%ld;e=%ld;d=%ld", n, e, d); w = "请输入明文:"; gets(str); printf("%s", w); gets(str); printf("您输入的明文是%s\\n", str); /*加密*/ i = 0; while ((c = str[i]) != '\\0') { a = e; b = 1; for ( ;a > 0 ; a >>= 1) { if(a % 2 == 1) b = (b * c) % n; c = (c * c) % n; } encrypt[i++] = b; } len = i; i = 0; printf("加密后密文为 "); while(i < len) { long l = encrypt[i++]; printf("%ld\", l); } printf("\\n"); /*解密*/ for(i=0; i for( c = encrypt[i] ; a > 0 ; a >>= 1) { if( a%2 == 1) { b = (b * c) % n; } c = (c*c)%n; } decrypt[i]=(char)b; } printf("解密为%s\\n", decrypt); system("pause"); exit: return 0; } int is_primenumber(int num) { for(int i = 2; i < num-1; i++) { if(num % i == 0) return 0; } return 1; } long (long a, long b) { long c; while(b != 0) { c = a % b; a = b; b = c; } return a; 黑客获取了公钥n和e以及加密消息c，但他无法直接获得私钥d。要获得d，最简单的方法是将n分解为p和q，这样她可以得到同余方程并解出d，然后代入解密公式 导出m（破密）。但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在。 至今为止也没有人能够证明对n进行因数分解是唯一的从c导出m的方法，但今天还没有找到比它更简单的方法。（至少没有公开的方法。） 因此今天一般认为只要n足够大，那么黑客就没有办法了。 假如n的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的n。今天对n的要求是它至少要1024位长。 6、用途 RSA除了可以用来加密意外也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话，那么她可以为她的消息计算一个散列值(Message digest)，然后用她的密钥(private key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。 附录： 素数 素数又称质数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。 互质数 百度百科上的解释是：公因数只有1的两个数，叫做互质数。；维基百科上的解释是：互质，又称互素。若N个整数的最大公因子是1，则称这N个整数互质。 常见的互质数判断方法主要有以下几种： 1两个不同的质数一定是互质数。例如，2与7、13与19。 2一个质数，另一个不为它的倍数，这两个数为互质数。例如，3与10、5与 26。 3相邻的两个自然数是互质数。如 15与 16。 4相邻的两个奇数是互质数。如 49与 51。 5较大数是质数的两个数是互质数。如97与88。 6小数是质数，大数不是小数的倍数的两个数是互质数。例如 7和 16。 72和任何奇数是互质数。例如2和87。 81不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。 9辗转相除法。 指数运算 指数运算又称乘方计算，计算结果称为幂。nm指将n自乘m次。把nm看作乘方的结果，叫做¡±n的m次幂¡±或¡±n的m次方¡±。其中，n称为¡°底数¡±，m称为¡°指数¡±。 模运算 模运算即求余运算。¡°模¡±是¡°Mod¡±的音译。和模运算紧密相关的一个概念是¡°同余¡±。 同余 数学上，当两个整数除以同一个正整数，若得相同余数，则二整数同余。两个整数，，若它们除以正整数所得的余数相等，则称，对于模同余，记作 逆模元素 一整数对同余之模逆元素是指满足以下公式的整数 也可以写成以下的式子 费马小定理 是数论中的一个定理：假如是一个整数，是一个质数，那么是的倍数，可以表示为下载本文
五、破解}
