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互质。)

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

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

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

 

三、加密与解密过程

加密公式为:C ≡ Mmod  n     (C和Me 对 n的求余结果相同)

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

解密公式为:M ≡ Cmod  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 ≡ Me  mod  n公式得:

 

C1 ≡ (M1) mod n  =>  6 3  mod 33   = 18

C2 ≡ (M2) mod n  =>  5 3  mod 33   = 26

C3 ≡ (M3) mod n  =>  4 3  mod 33   = 31

 

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

即:M ≡ Cd  mod  n。计算过程如下:

 

M1 = (C1) mod n  =>  18 7  mod 33   = 6

M2 = (C1) mod n  =>  26 7  mod 33   = 5

M3 = (C1) mod n  =>  31 7  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等等。
模指数运算就是先做指数运算,取其结果再做模运算。