首页 > 代码库 > RSA算法

RSA算法

RSA是(Rivest Shamir and Adleman)的缩写,Ron Rivest, AdiShamir Leonard Adleman这仨哥们挺NB的,20多年前创造了这个算法,现在也已经广泛使用了。

这是一种公钥的加密算法,加密和解密是互逆的。如果用公钥加密,私钥解密,可实现保密通信;如果用私钥加密,公钥解密,可实现数字签名。下面说一下算法:

1、首先选择两个大素数pq

都要大于10^100,因为小素数很容分解

2、令n=p*qz=(p-1)*(q-1)   

这部没什么可解释的

3、选择d,要求dz互质。         

只要是互质数都行

4、选择e,要求e*d=1 (mod z)    

一说这个mod就烦人了,这里的mod的意思是数学符号,并非编程的mod,好比a=b (mod c),意思是ab除以c后,余数相同。

5、明文P被分为k位的块,k要满足2^k<n的最大整数,于是0<=p<n

这不没什么可说的。

 

下面是加密和解密过程,先说公钥加密,私钥解密的过程:

1、公钥加密用到en这两个数。C=P^e (mod n)

C是加密后的密文,P是明文,en就是算出来的数字了,但是这里的mod是电脑编程里的运算符,意思是取余数。

    解密用到dnP=C^d (mod n)

    这样明文P就出来了。

2、私钥用到dn这两个数。C=P^d (mod n)

    解密用到en这两个数。P=C^e (mod n)

 

可以代两个简单的2位素数来试试,不过你会发现,pq很容易就被推算出来了,所以为什么说要大素数的原因就在这里。因为安全性是基于大素数分解的困难性,如果攻击者要分解200位的数,需要40亿年;500位的数,需要10^25年。这就是为什么RSA的重大缺陷是无法从理论上把握它的保密性能如何。


本文出自 “www.sina.com” 博客,请务必保留此出处http://139529.blog.51cto.com/129529/1870351

RSA算法