首页 > 代码库 > RSA算法
RSA算法
RSA是(Rivest Shamir and Adleman)的缩写,Ron Rivest, AdiShamir 和Leonard Adleman这仨哥们挺NB的,20多年前创造了这个算法,现在也已经广泛使用了。
这是一种公钥的加密算法,加密和解密是互逆的。如果用公钥加密,私钥解密,可实现保密通信;如果用私钥加密,公钥解密,可实现数字签名。下面说一下算法:
1、首先选择两个大素数p和q
都要大于10^100,因为小素数很容分解
2、令n=p*q和z=(p-1)*(q-1)
这部没什么可解释的
3、选择d,要求d与z互质。
只要是互质数都行
4、选择e,要求e*d=1 (mod z)
一说这个mod就烦人了,这里的mod的意思是数学符号,并非编程的mod,好比a=b (mod c),意思是a和b除以c后,余数相同。
5、明文P被分为k位的块,k要满足2^k<n的最大整数,于是0<=p<n。
这不没什么可说的。
下面是加密和解密过程,先说公钥加密,私钥解密的过程:
1、公钥加密用到e,n这两个数。C=P^e (mod n)
C是加密后的密文,P是明文,e和n就是算出来的数字了,但是这里的mod是电脑编程里的运算符,意思是取余数。
解密用到d,n,P=C^d (mod n)
这样明文P就出来了。
2、私钥用到d,n这两个数。C=P^d (mod n)
解密用到e,n这两个数。P=C^e (mod n)
可以代两个简单的2位素数来试试,不过你会发现,p和q很容易就被推算出来了,所以为什么说要大素数的原因就在这里。因为安全性是基于大素数分解的困难性,如果攻击者要分解200位的数,需要40亿年;500位的数,需要10^25年。这就是为什么RSA的重大缺陷是无法从理论上把握它的保密性能如何。
本文出自 “www.sina.com” 博客,请务必保留此出处http://139529.blog.51cto.com/129529/1870351
RSA算法