RSA加密算法详解(二)

时间:2021-10-22 15:55:44

研究RSA

不知为何,这几天突然有些心烦。望苍茫大地,凭添几分忧伤,可能是下雨的缘故。本篇主要想详细介绍RSA加密算法的原理,经常听别人说,这里是自己想搞清楚,弄明白。首先介绍了基本的数学原理,然后给出一个具体的计算例子和相关的理论充分性证明。

RSA加密算法详解(二)皓眸大前端开发学习

转载请注明出处:http://www.haomou.net/2014/08/27/2014_rsa/

RSA由来

1976年以前,所有的加密方法都是同一种模式:
  (1)甲方选择某一种加密规则,对信息进行加密;
  (2)乙方使用同一种规则,对信息进行解密。
由于加密和解密使用同样规则(简称”密钥”),这被称为”对称加密算法”(Symmetric-key algorithm)。这种加密模式有一个最大弱点:甲方必须把加密规则告诉乙方,否则无法解密。保存和传递密钥,就成了最头疼的问题。
RSA加密算法详解(二)皓眸大前端开发学习
1976年,两位美国计算机学家Whitfield Diffie 和 Martin、Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为”Diffie-Hellman密钥交换算法”。这个算法启发了其他科学家。人们认识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应关系即可,这样就避免了直接传递密钥。这种新的加密模式被称为”非对称加密算法”。
  (1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
  (2)甲方获取乙方的公钥,然后用它对信息加密。
  (3)乙方得到加密后的信息,用私钥解密。
如果公钥加密的信息只有私钥解得开,那么只要私钥不泄漏,通信就是安全的。
RSA加密算法详解(二)皓眸大前端开发学习
1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。
这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。
下面,我就进入正题,解释RSA算法的原理。文章共分成两部分,今天是第一部分,介绍要用到的四个数学概念。你可以看到,RSA算法并不难,只需要一点数论知识就可以理解。

理论基础

这里介绍一点理论基础,都是比较简单的,小学的数学知识。看我细细道来~

####什么是“素数”?
素数是这样的整数,它除了能表示为它自己和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等等。
  模指数运算就是先做指数运算,取其结果再做模运算。如2^3 mod 5 = 3

什么是同余式

表示同余关系的数学表达式,与等式相似。将等式中的等号“=”换成同余符号“≡”,必要时在式尾缀以(mod m) 注明模m(即除数),就是同余式。含有未知数的同余式叫做同余方程,通常要求整数解。
如果两个正整数 a和 b之差能被 n整除,那么我们就说 a和 b对模n同余,记作:
a ≡b (mod n)

####什么是费马定理
若p是素数,a与p互素,则
a^(p-1)≡1 (mod p)

什么是欧拉定理

欧拉函数φ(n)表示不大于n且与n互素的正整数的个数。
当n是素数,φ(n)=n-1。n=pq,p,q均为素数时,则φ(n)= φ(p)φ(q)=(p-1)(q-1)。
对于互素的a和n,有a^φ(n)≡1(mod n)

什么是模反元素?

如果两个正整数a和n互质,那么一定可以找到整数b,使得ab-1被n整除或者说ab被n除的余数是1。这时,b就叫做a的”模反元素”。
比如,3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…},即如果b是a的模反元素,则 b+kn 都是a的模反元素。欧拉定理可以用来证明模反元素必然存在。

密钥生成步骤

这里通过实例来说明。假设爱丽丝要与鲍勃进行加密通信,她该怎么生成公钥和私钥呢?
RSA加密算法详解(二)皓眸大前端开发学习
第一步,随机选择两个不相等的质数p和q。
爱丽丝选择了61和53。(实际应用中,这两个质数越大,就越难破解。)
第二步,计算p和q的乘积n。
爱丽丝就把61和53相乘。
  n = 61×53 = 3233
n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。
第三步,计算n的欧拉函数φ(n)。
根据公式:
  φ(n) = (p-1)(q-1)
爱丽丝算出φ(3233)等于60×52,即3120。
第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。
爱丽丝就在1到3120之间,随机选择了17。(实际应用中,常常选择65537。)
第五步,计算e对于φ(n)的模反元素d。
所谓”模反元素”就是指有一个整数d,可以使得ed被φ(n)除的余数为1。
  ed ≡ 1 (mod φ(n))
这个式子等价于
  ed - 1 = kφ(n)
于是,找到模反元素d,实质上就是对下面这个二元一次方程求解。
  ex + φ(n)y = 1
已知 e=17, φ(n)=3120,
  17x + 3120y = 1
这个方程可以用”扩展欧几里得算法”求解,此处省略具体过程。总之,爱丽丝算出一组整数解为 (x,y)=(2753,-15),即 d=2753。
至此所有计算完成。
第六步,将n和e封装成公钥,n和d封装成私钥。
在爱丽丝的例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。
实际应用中,公钥和私钥的数据都采用ASN.1格式表达。如下:
RSA加密算法详解(二)皓眸大前端开发学习
比如上面显示的这个公钥,那么怎么看出加密指数和模数呢?

下面是我随便从IE里导出的一个证书的公钥

1
30 81 89 02 81 81 00 ee fa 1f c9 b0 43 df 7e 75 81 4e 31 71 91 0b fc 15 9d d9 4a 8a 51 f5 09 18 c6 7c c5 f1 27 c4 01 62 fc bf fc 84 29 a6 2f e6 1e 02 06 0b 96 89 d3 42 b1 73 9f 02 ae 75 62 09 3f 83 80 34 46 60 39 0a e3 21 4e e7 04 42 d5 7e 5e 98 45 27 5d 04 b9 27 32 c0 65 a4 94 85 13 25 db 16 f2 fb 51 c7 ff 28 62 d1 83 31 4f a9 a4 f4 c5 4f 9d 00 2e 14 3f 95 16 9c 4e 25 07 1b d5 7d 38 71 d8 40 f8 aa 71 02 03 01 00 01

在PKCS#1中的RSA的公钥的标准格式为

1
2
3
4
5
6
7
PKCS#1 :
An RSA public key should be represented with the ASN.1 type RSAPublickey: RSAPublickey ::= SEQUENCE {
modulus INTEGER, -- n
publicExponent INTEGER -- e
}

然后按照ASN的标准编码,所以说:

1
2
3
4
5
6
30 81 89 02 81 81 00 ee fa 1f c9 b0 43 df 7e 75 81 4e 31 71 91 0b fc 15 
9d d9 4a 8a 51 f5 09 18 c6 7c c5 f1 27 c4 01 62 fc bf fc 84 29 a6 2f e6 1e
02 06 0b 96 89 d3 42 b1 73 9f 02 ae 75 62 09 3f 83 80 34 46 60 39 0a e3
21 4e e7 04 42 d5 7e 5e 98 45 27 5d 04 b9 27 32 c0 65 a4 94 85 13 25 db
16 f2 fb 51 c7 ff 28 62 d1 83 31 4f a9 a4 f4 c5 4f 9d 00 2e 14 3f 95 16 9c 4e
25 07 1b d5 7d 38 71 d8 40 f8 aa 71 02 03 01 00 01

0x30 0x81 0x89 是一个标识头,整个编码应该是:

1
2
3
4
5
6
02 81 81 00 ee fa 1f c9 b0 43 df 7e 75 81 4e 31 71 91 0b fc 15 9d d9 4a 
8a 51 f5 09 18 c6 7c c5 f1 27 c4 01 62 fc bf fc 84 29 a6 2f e6 1e 02 06 0b
96 89 d3 42 b1 73 9f 02 ae 75 62 09 3f 83 80 34 46 60 39 0a e3 21 4e e7
04 42 d5 7e 5e 98 45 27 5d 04 b9 27 32 c0 65 a4 94 85 13 25 db 16 f2 fb
51 c7 ff 28 62 d1 83 31 4f a9 a4 f4 c5 4f 9d 00 2e 14 3f 95 16 9c 4e 25 07
1b d5 7d 38 71 d8 40 f8 aa 71 02 03 01 00 01

1
2
3
4
5
6
02 81 81 00 ee fa 1f c9 b0 43 df 7e 75 81 4e 31 71 91 0b fc 15 9d d9 4a 
8a 51 f5 09 18 c6 7c c5 f1 27 c4 01 62 fc bf fc 84 29 a6 2f e6 1e 02 06 0b
96 89 d3 42 b1 73 9f 02 ae 75 62 09 3f 83 80 34 46 60 39 0a e3 21 4e e7
04 42 d5 7e 5e 98 45 27 5d 04 b9 27 32 c0 65 a4 94 85 13 25 db 16 f2 fb
51 c7 ff 28 62 d1 83 31 4f a9 a4 f4 c5 4f 9d 00 2e 14 3f 95 16 9c 4e 25 07
1b d5 7d 38 71 d8 40 f8 aa 71

是n的编码。

0x02 0x03 0x01 0x00 0x01是e的编码,不过你还是看不出来这什么整数,
举个例子
对于上面的0x02,0x03,0x01,0x00,0x01 其中0x02,0x03是e的编码的标识头
e的表示是0x01,0x00,0x01,所以e就是0x01256^2+0x00256^1+1=65537

同理n就是

1
2
3
4
5
6
81 00 ee fa 1f c9 b0 43 df 7e 75 81 4e 31 71 91 0b fc 15 9d d9 4a 8a 51 f5 
09 18 c6 7c c5 f1 27 c4 01 62 fc bf fc 84 29 a6 2f e6 1e 02 06 0b 96 89 d3
42 b1 73 9f 02 ae 75 62 09 3f 83 80 34 46 60 39 0a e3 21 4e e7 04 42 d5
7e 5e 98 45 27 5d 04 b9 27 32 c0 65 a4 94 85 13 25 db 16 f2 fb 51 c7 ff 28
62 d1 83 31 4f a9 a4 f4 c5 4f 9d 00 2e 14 3f 95 16 9c 4e 25 07 1b d5 7d 38
71 d8 40 f8 aa 71 02 03 01 00 01

注意,这个是一个整数的编码,也要像e,那样解码。

RSA算法的可靠性

回顾上面的密钥生成步骤,一共出现六个数字:

1
2
3
4
5
6
  p
  q
  n
  φ(n)
  e
  d

这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。
那么,有无可能在已知n和e的情况下,推导出d?
  (1)ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。
  (2)φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。
  (3)n=pq。只有将n因数分解,才能算出p和q。
结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。
可是,大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。*这样写道:
  “对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。
  假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。
  只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。”
举例来说,你可以对3233进行因数分解(61×53),但是你没法对下面这个整数进行因数分解。

1
2
3
4
5
6
7
8
9
  12301866845301177551304949
  58384962720772853569595334
  79219732245215172640050726
  36575187452021997864693899
  56474942774063845925192557
  32630345373154826850791702
  61221429134616704292143116
  02221240479274737794080665
  351419597459856902143413

它等于这样两个质数的乘积:

1
2
3
4
5
6
7
8
9
10
11
  33478071698956898786044169
  84821269081770479498371376
  85689124313889828837938780
  02287614711652531743087737
  814467999489
    ×
  36746043666799590428244633
  79962795263227915816434308
  76426760322838157396665112
  79233373417143396810270092
  798736308917

事实上,这大概是人类已经分解的最大整数(232个十进制位,768个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。

加密和解密

有了公钥和密钥,就能进行加密和解密了。
(1)加密要用公钥 (n,e)
假设鲍勃要向爱丽丝发送加密信息m,他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。
所谓”加密”,就是算出下式的c:

1
  me ≡ c (mod n)

c = m^e%n

爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么可以算出下面的等式:

1
  6517 ≡ 2790 (mod 3233)

于是,c等于2790,鲍勃就把2790发给了爱丽丝。
(2)解密要用私钥(n,d)
爱丽丝拿到鲍勃发来的2790以后,就用自己的私钥(3233, 2753) 进行解密。可以证明,下面的等式一定成立:

1
  cd ≡ m (mod n)

m=c^d%n

也就是说,c的d次方除以n的余数为m。现在,c等于2790,私钥是(3233, 2753),那么,爱丽丝算出

1
  27902753 ≡ 65 (mod 3233)

因此,爱丽丝知道了鲍勃加密前的原文就是65。
至此,”加密–解密”的整个过程全部完成。
我们可以看到,如果不知道d,就没有办法从c求出m。而前面已经说过,要知道d就必须分解n,这是极难做到的,所以RSA算法保证了通信安全。
你可能会问,公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?有两种解决方法:一种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种”对称性加密算法”(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。

私钥解密的证明

最后,我们来证明,为什么用私钥解密,一定可以正确地得到m。也就是证明下面这个式子:

1
c^d ≡ m (mod n)

因为,根据加密规则

1
m^e ≡ c (mod n)

于是,c可以写成下面的形式:

1
c = m^e - kn

将c代入要我们要证明的那个解密规则:

1
(m^e - kn)^d ≡ m (mod n)

它等同于求证

1
m^ed ≡ m (mod n)

由于

1
ed ≡ 1 (mod φ(n))

所以

1
ed = hφ(n)+1

将ed代入:

1
m^(hφ(n)+1) ≡ m (mod n)

接下来,分成两种情况证明上面这个式子。
(1)m与n互质。
根据欧拉定理,此时

1
  m^φ(n) ≡ 1 (mod n)

得到

1
  (m^φ(n))^h × m ≡ m (mod n)

原式得到证明。
(2)m与n不是互质关系。
此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq。
以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:

1
  (kp)^q-1 ≡ 1 (mod q)

进一步得到

1
  [(kp)^q-1]^h(p-1) × kp ≡ kp (mod q)

1
  (kp)^ed ≡ kp (mod q)

将它改写成下面的等式

1
  (kp)^ed = tq + kp

这时t必然能被p整除,即 t=t’p

1
  (kp)^ed = t'pq + kp

因为 m=kp,n=pq,所以

1
  m^ed ≡ m (mod n)

原式得到证明。

RSA缺陷

当p和q是一个大素数的时候,从它们的积pq去分解因子p和q,这是一个公认的数学难题。比如当pq大到1024位时,迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。因此,RSA从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。
  然而,虽然RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。
  此外,RSA的缺点还有:
A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。
B)分组长度太大,为保证安全性,n 至少也要 600 bits 以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。因此,使用RSA只能加密少量数据,大量的数据加密还要靠对称密码算法。