RSA加密算法说明

 

—作者：李兴球

一、rsa加密码过程

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

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

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

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

 

二、算法过程

 

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

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

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

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

3. 选择一个整数e与φ(n) 互质，并且e小于 φ(n)。
4. 用以下这个公式计算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…。

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

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

 

三、加密与解密过程

 

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

 

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

 

解密公式为：M ≡ C^d  mod  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) ^e  mod n  =>  6 ³  mod 33   = 18

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

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

 

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

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

 

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

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

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

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

相关数学知识：

一、 什么是“素数”？
素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。素数也称为“质数”。

二、什么是“互质数”（或“互素数”）？
小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”这里所说的“两个数”是指自然数。
判别方法主要有以下几种（不限于此）：
（1）两个质数一定是互质数。例如，2与7、13与19。
（2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与 26。
（3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。
（4）相邻的两个自然数是互质数。如 15与 16。
（5）相邻的两个奇数是互质数。如 49与 51。
（6）大数是质数的两个数是互质数。如97与88。
（7）小数是质数，大数不是小数的倍数的两个数是互质数。如 7和 16。
（8）两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数，这两个数为互质数。等等。

三、什么是模指数运算？ 
指数运算谁都懂，不必说了，先说说模运算。模运算是整数运算，有一个整数m，以n为模做模运算，即m mod n。怎样做呢？让m去被n整除，只取所得的余数作为结果，就叫做模运算。例如，10 mod 3=1；26 mod 6=2；28 mod 2 =0等等。
模指数运算就是先做指数运算，取其结果再做模运算。如