RSA算法是一种基于公钥和私钥的加密算法, 是由Ronald Rivest, Adi Shamir和Len Adleman三人在Diffie-Helman指数密钥交换算法的
基础上于1977年设计出来的,Rivest设计的加密系统利用了数学领域的一个事实，那就是虽然把两个大素数相乘生成一个合数是件很容易
的事， 但要把一个合数分解为两个素数却十分困难。
RSA的安全性依赖于大数分解，公钥和密钥都是两个大素数(大于100个十进制位)的函数。据猜测，从一个密钥和密文推断出明文的难度
等同于分解两个大素数之积。
密钥对的产生，选对两个大素数p和q,计算
n=p*q
然后随机选择加密密钥e, 要求e和(p-1)*(q-1)互质，最后，利用Euclid算法计算解密密钥d，满足
(e*d) mod ((p-1)*(q-1))=1
其中n和d也要互质, 数e和n是公钥,d是私钥.现在两个素数p和q可以丢弃不再需要，不要让任何人知道.
加密信息m(二进制表示)时，首先把m分成等长数据块m1,m2....mi,块长s,其中2^s<=n, s尽可能地大.对应的密文是:
ci=mi^e (mod n) (a)
解密时作如下计算:
mi=ci^d (mod n) (b)
RSA可用于数字签名,方案是用(a)式签名，(b)式验证.具体操作时考虑到安全性和m信息量较大等因素,一般先作hash运算.
RSA算法示例:
(1) 选择两个素数:p=7, q=17
(2) 计算n=p*q=7*17=119
(3) 计算φ(n)=(p-1)*(q-1)=96
(4) 选择e,e为φ(n)=96的相对素数,要比φ(n)小,本例中e=5
(5) 决定d,使(d*e) mod 96=1,且d<96,正确值为d=77,因为77*5=385=4*96+1.
结果密钥为公钥KU={5, 119}和私钥KR={77, 119}
如输入明文M=19,使用以上密钥加密:
ci=M^e (mod n)
=19^5 mod 119
=2476099 mod 119
=66
解密由66^77 mod 119=19决定.
《黑客防线---口令破解与加密技术》笔记
来源：http://blog.csdn.net/study_live/archive/2009/12/19/5038828.aspx
作者：jackxiang@向东博客 专注WEB应用 构架之美 --- 构架之美，在于尽态极妍 | 应用之美，在于药到病除
地址：http://jackxiang.com/post/2853/
版权所有。转载时必须以链接形式注明作者和原始出处及本声明！
利用SMTP发送Mail详解
端口扫描程序实现原理评论列表
