RSA加密算法教程

一、rsa加密码过程

rsa加密是一种非对称加密算法，其主要过程如下：

1、乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

2、甲方获取乙方的公钥，然后用它对信息加密，把密文传给乙方。

3、乙方得到加密后的信息，用私钥解密。

二、算法过程

随意选择两个大的质数p和q，p不等于q，计算 n = p * q 。n的二进制长度就是密钥的长度。
根据欧拉函数，不大于n且与n互质的整数的个数为：

φ(n) = (p-1) × (q-1) 。

( 欧拉函数φ(n)，解决的问题是：小于n的正整数中与n互质整数的数目。

例如φ(8)=4，因为1,3,5,7均和8互质。)

选择一个整数e与φ(n) 互质，并且e小于 φ(n)。
用以下这个公式计算d：d × e ≡ 1 (mod φ(n) )。

上面公式表示的意思为 d×e对φ(n) 的余数与 1对φ(n)的余数相同。由于 1 对φ(n)的余数为1。所以上面的公式可以理解为d×e对φ(n) 的余数为1。公式可化为： (d×e) mod φ(n) = 1 。即d×e 对φ(n) 的余数为1。假设φ(n) 的值为20，那么d×e 的值为 21 ， 41 ， 61 ， 81 ，…。即d×e的值为k * φ(n) + 1。k为1， 2，3 ，4 ， 5 ， 6 ， 7…。

以上内容中，(n ，e) 就是公钥，(n ， d) 就是私钥。

总结：生成公钥和私钥就是求n，e，d的过程。

三、加密与解密过程

加密公式为：C ≡ M^emod n （C和M^e 对 n的求余结果相同）

M为待加密的整数。实际情况是加密文本的，所以先要先把文本转换成整数。如，可以把它先转换成它的ASCII码。C就是加密后的数据。

解密公式为：M ≡ C^dmod n

C是密文，M是解密后的明文。

四、实例描述：

　在这里通过一个简单的例子来理解RSA的工作原理。为了便于计算。在以下实例中只选取小数值的质数p,q,以及e，假设用户A需要将明文“fed”通过RSA加密后传递给用户B，过程如下：
（1）设计公私密钥(e,n)和(d,n)。
令p=3，q=11，得出n=p×q=3×11=33；

φ(n)=(p-1)(q-1)=2×10=20；

取e=3，（3与20互质）;

e×d≡1 mod φ(n)，即3×d≡1 mod 20。

由于3xd的值对20的余数为1，所以它最小的值为21，可以算出d为7。从而我们可以设计出一对公私密钥，加密密钥（公钥）为：KU =(n,e)=(33,3)，解密密钥（私钥）为：KR =(n,d)=(33,7)。

（2）英文数字化。
将明文信息数字化，可以自己设一个字母与数字的对应表。在这里为了简化，让它们和数字一一对应，即a对应1,b对应2，c对应3，d应4,e对应5,f对应6。下面对字符串fed加密，那么对应的明文为：6,5,4。
（3）明文加密
用户A有公钥 (33,3) 将数字化明文分组信息加密成密文。由C ≡ M^e mod n公式得：

C1 ≡ (M1) ^emod n => 6 ³ mod 33 = 18

C2 ≡ (M2) ^emod n => 5 ³ mod 33 = 26

C3 ≡ (M3) ^emod n => 4 ³ mod 33 = 31

因此，得到相应的密文信息为：18,26,31。
（4）密文解密。
用户B有私钥(33,7)，他收到密文，若将其解密，只需要根据解密公式算出来即可，

即：M ≡ C^d mod n。计算过程如下：

M1 = (C1) ^dmod n => 18 ⁷ mod 33 = 6

M2 = (C1) ^dmod n => 26 ⁷ mod 33 = 5

M3 = (C1) ^dmod n => 31 ⁷ mod 33 = 4

6,5,4分别对应的就是fed，这样就解密了。　你看，它的原理就可以这么简单地解释！
当然，实际运用要比这复杂得多，由于RSA算法的公钥私钥的长度（模长度）要到1024位甚至2048位才能保证安全，因此，p、q、e的选取、公钥私钥的生成，加密解密模指数运算都有一定的计算程序，需要仰仗计算机高速完成。