MENU

RSA算法-原理

• November 14, 2017 • Algorithm阅读设置

一、数论基础

[1] 欧拉函数

欧拉函数 φ(n) 表示小于n的正整数中与n互质的数的数量,比如

 φ(5) = count{1,2,3,4} = 4
 φ(8) = count{1,3,5,7} = 4
 特殊的, φ(1) = 1

[2] 欧拉函数通式

求解欧拉函数有一道通式

  • φ(n) = n x (1 – 1/p1) x (1 – 1/p2) x … x (1 – 1/pi)

其中p1,p2…pi 代表n拆解出来的素因子,重复的素因子只取一次,比如

 若 n = 8 则 8 = 2 x 2 x 2 , p1 = 2 ; φ(8) = 8 x (1 - 1/2) = 4
 若 n = 24 则 24 = 2 x 2 x 2 x 3 , p1 = 2 , p2 = 3 ; φ(24) = 24 x (1 - 1/2) x (1 - 1/3) = 8

对于一些特殊情况,欧拉函数可能会有稍微方便的解法,但如果要求“任意一个正整数n的欧拉函数值φ(n)”,则不可避免地需要用到这道通式。此时需要做的便是拆分出这个“任意正整数n”的素因子,此时:

  • 如果n越大,对于现有算力的计算机而言,要拆分出它的素因子所需的时间就越长,当n大到一定程度时,我们可以认为n无法被当下的计算机拆解,也即无法求出φ(n)的值

这句话也是保证RSA算法安全性的核心


[2.1] 欧拉函数通式理解

假如无法理解通式,不妨从概率学的角度思考一下:

设 n = 24, n 的素因子 p1 = 2 , p2 = 3;
不超过n = 24的正整数中,
能被 p1 = 2 整除的有
count{2,4,6,8,10,12,14,16,18,20,22,24} = 12
能被 p2 = 3 整除的有
count{3 (1 x p2),6 (2 x p2),9 (3 x p2),12 (4 x p2),15 (5 x p2),18 (6 x p2),21 (7 x p2),24 (8 x p2)} = 8
任取一数 X ,令 1 <= X <= 24
则 X 能被 p1 = 2 整除的概率为 12/24 = 1/2 即是 1/p1
X 能被 p2 = 3 整除的概率为 8/24 = 1/3 即是 1/p2
所以 1-1/p1 便表示不能被 p1 = 2 整除的概率
1-1/p2 便表示不能被 p2 = 3 整除的概率
(1-1/2) x (1-1/3) 表示既不能被2整除,也不能被3整除的概率

回到通式中,φ(n)=n x (1-1/p1) x (1-1/p2) x ... x (1-1/pi) 中:
(1-1/p1) x (1-1/p2) x ... x (1-1/pi) 表示同时不能被p1,p2,...,pi整除的概率。
而我们知道p1,p2..pi是n的素因子,所以这个概率又表示“任取一不大于n的正整数X,X与n没有共同素因子的概率”,即“X与n互质的概率”。
此时集合元素总数n乘上概率,便可得出“X与n互质的数的数量”,即欧拉函数φ(n)


[2.2] 欧拉函数特殊情况

<1> φ(1) = 1

  • 和1互质的数(小于等于1)就是1本身
  • 这个有点像问 1+1为什么等于2,想扯的话可以扯出一大堆这个定义成立或不成立的理由,但总之就是这么约定了
  • 顺便一提,“1和-1与所有整数互素,而且它们是唯一与0互素的整数。”

<2> n为素数

由于素数的定义,显而易见地,不大于n的正整数中,n不与它本身互素,1与任何整数互素,而1~n中又都与n互素,所以此时 φ(n) = n-1
这一点也是RSA算法的核心之一

<3> etc.


[3] 积性函数

欧拉函数是积性函数,即它符合f(1)=1,当a,b为素数时f(ab)=f(a)f(b),因而有
任取两个素数p,q,令n = p x q,则有 φ(n) = φ(p) x φ(q)
又由于[2.2]<2>所述,当一个数X为素数时φ(X)=X-1,故而此时可以通过以下关系快速求出φ(n):
φ(n) = φ(p) x φ(q) = (p-1) x (q-1)
通过积性函数特性与素数欧拉函数的快速求解,是RSA能够成立的重要前提


[3.1] 欧拉函数是积性函数的理解

其实这个很好理解,只是单纯的化简

任取两个素数p,q,n=pq
此时n的素因子只有p,q
所以
φ(n) = φ(pq) = pq x (1-1/p) x (1-1/q) = pq x (p-1)/p x (q-1)/q = pq x (p-1)(q-1)/pq = (p-1)(q-1) = φ(p) x φ(q)

[4] 欧拉定理

欧拉定理是这么说的:若n,a为正整数,且n,a互素(gcd(n,a)=1),则有 a^φ(n) ≡ 1 (mod n),即当a与n互质时,a^φ(n)与1在模n的情况下同余。
或者说:a^φ(n) 除以 n 的余数与 1 除以 n 的余数相等,即 a^φ(n) 除以 n 的余数为 1

欧拉定理极大幅度地简化了幂的模运算,例如要求7^222除以10的余数,即7^222的个位数

由于7与10互质,所以
7^φ(10) ≡ 1 (mod 10)
即  
7^φ(10) / 10 = k ... 1
又因为 
φ(10) = 4,222 = 4 x 55 + 2
所以 
  7^222 
= 7^(4 x 55 + 2) 
= (7^(φ(10) x 55) x 7^2) 
≡ (1^55 x 49) 
≡ 9 (mod 10)
所以 
7^222 的个位数为9

其中,7^(4x55)到1^55的转换用到同余数的一个特性:
如果a ≡ b (mod m),那么a^k ≡ b^k (mod m)

[4.1] 扩展.同余 ≡

≡是同余号,假如 a ≡ b (mod m),这表示a除以m和b除以m的余数相同,当两数同余时有这些性质:

  • 反身性 a≡a (mod m)
  • 对称性 若a≡b(mod m),则b≡a (mod m)
  • 传递性 若a≡b (mod m),b≡c (mod m),则a≡c (mod m)
  • 同余式相加 若a≡b (mod m),c≡d(mod m),则a±c≡b±d (mod m)
  • 同余式相乘 若a≡b (mod m),c≡d(mod m),则ac≡bd (mod m)

由这些又可推出:

  • 如果ac≡bc(mod m),且c和m互质,则a≡b(mod m)
  • 如果a ≡ b (mod m),那么a^k ≡ b^k (mod m)

[5] 费马小定理

费马小定理是欧拉定理的延伸,我们知道欧拉函数中,当n为素数时 φ(n)=n-1,此时由欧拉定理有

a^φ(n) =  a^(n-1) ≡ 1 (mod n)
两边同时乘 a 得
a^n ≡ a (mod n) //费马小定理

[6] 模反元素


如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,即ab ≡ 1 (mod n),或者说ab被n除的余数是1。这时,b就叫做a的“模反元素”。

证明:

由[4] 欧拉定理,我们知道当a,n互质时
a^φ(n) ≡ 1 (mod n)
所以
  a^φ(n) 
= a^(φ(n)-1) x a 
≡ 1 (mod n)
此时 a^(φ(n)-1) 
即为 a对于n的模反元素“b”

此时也很容易想到,模反元素其实不止一个,b+kn都是a对于n的模反元素


二、RSA算法原理

[1] 准备

在RSA算法的初始阶段,我们需要准备一组六个关键数字:两个素数p,q,它们的乘积n,n的欧拉函数值φ(n),一个大于1小于φ(n)且与φ(n)互质的整数e,e对于φ(n)的模反元素d


[2.1] 准备第一步,p,q,n

任取两个不相等素数 p,q,把它们相乘得到n,n转成二进制的位数便是密钥的位数
此时已知:p,q,n

[2.2] 准备第二步,φ(n)

由 一、[3] 知,φ(n)=φ(p)φ(q)=(p-1)(q-1)
此时已知:p,q,n,φ(n)

[2.3] 准备第三步,e

选取一个大于1小于φ(n),且与φ(n)互质的整数e,实际应用中经常用e=65537
此时已知:p,q,n,φ(n),e

[2.4] 准备第四步,d

由一、[6] 知,模反元素式子 ab ≡ 1 (mod n)

 已知  φ(n),e 则 e 对于 φ(n) 的模反数 可立方程
 ed ≡ 1 (mod φ(n))
 设k为任意整数,方程可化为
 ed - 1 = kφ(n)
 ed - kφ(n) = 1
 写成函数就是 d(e,φ(n)) = (kφ(n) + 1) / e
 对方程用扩展欧几里得算法求得特解(k,d),从而得到d

此时已知所有关键数字:p,q,n,φ(n),e,d


[2.4.1] 扩展欧几里得算法求二元一次方程

我们知道辗转相除法可以被用来求两数的最大公约数,而通常谈到最大公约数时,我们都会提到一个非常基本的事实:给予二整数a、b,必存在有整数x、y使得ax + by = gcd(a,b)
对于[2.4],a,b对应的便是e,φ(n),x,y对应的便是d,k,我们知道e,φ(n)互质,所以gcd(e,φ(n))=1
那么[2.4]中 ed - kφ(n) = 1 其实就是 ed - kφ(n) = gcd(e,φ(n))

接下来以具体数字举例求解过程,其核心是辗转相除法的扩展:

设有方程 47x+30y=1 则
47 = 30 * 1 + 17
30 = 17 * 1 + 13
17 = 13 * 1 + 4
13 = 4 * 3 + 1
然后把它们改写成“余数等于”的形式
17 = 47 * 1 + 30 * (-1) //式1
13 = 30 * 1 + 17 * (-1) //式2
4 = 17 * 1 + 13 * (-1) //式3
1 = 13 * 1 + 4 * (-3)
然后把它们“倒回去”
1 = 13 * 1 + 4 * (-3)
1 = 13 * 1 + [17 * 1 + 13 * (-1)] * (-3) //应用式3
1 = 17 * (-3) + 13 * 4
1 = 17 * (-3) + [30 * 1 + 17 * (-1)] * 4 //应用式2
1 = 30 * 4 + 17 * (-7)
1 = 30 * 4 + [47 * 1 + 30 * (-1)] * (-7) //应用式1
1 = 47 * (-7) + 30 * 11
得解x=-7, y=11。

[2.5] 抛弃p,q,φ(n)

把p,q,φ(n)抛弃,因为通过p,q可以快速推出φ(n),从而推出其它4个关键数字,但当n足够大时却无法通过n逆过来推出素因子p,q及φ(n),所以这个世界上不再存在p,q,φ(n)后,我们可以淡定地说“除非私钥泄漏,否则这套RSA加密不再能被破解”

如图:
一开始我们生成了p,q,n然后通过p,q算出了φ(n)

当我们抛弃了p,q,φ(n)后,便相当于斩断了n,e,d之间的桥梁,而当n足够大时,想要通过n来恢复我们斩断的这些桥梁p,q,φ(n)又几乎是不可能的,所以只知道e,n或d,n中任意一对,将无法求出另一对,也即是公钥被公开的情况下,私钥不会被破解


[2.6] 封装公私钥

我们把e,n分到一组,作为公钥,把d,n分到一组,作为私钥。


[3] 加密与解密

我们假设有一个明文M,它加密后得结果为c
先将M按一定规则转换为与n互质的数m,由于n是两个质数的乘积,所以它的素因子只有 {p,q} 所以只要M不是p,q,都可以直接令m=M
那么它会符合以下的模等式:

  • 对于公钥e,n: m^e ≡ c (mod n)
  • 对于私钥d,b: c^d ≡ m (mod n)

那么我们就可以很轻松地求出:

  • c(m) = m^e mod n
  • m(c) = c^d mod n

然后再通过m,n转换规则求出明文M

例:

设我们生成了 
n = 3 x 7 = 21, e = 5, d = 5
而我们要加密的是 m = 4
那么
   c(4)
= 4^5 / 21 
= 1024 / 21 
= 48 ......  16
即密文 c = 16

那我们要解密的话就是
   m(16) 
= 16^5 / 21 
= 1048576 / 21 
= 49932 ......  4
即明文 m = 4


再假设我们要加密的是 m = 25
那么
  c(25) 
= 25^5 / 21 
= 9765625 / 21 
= 465029 ...... 16
即密文 c = 16

那我们要解密的话就是
  m(16) 
= 16^5 / 21 
= 1048576 / 21 
= 49932 ......  4
即明文 m = 4

是不是觉得上面的例子怪怪的?因为mod n这一步的存在,被加密的数必须小于n,否则加密出来的结果会与其它数字重复,导致解密出错


[4] 加密解密函数的快速计算

上面例子我用e,d均等于5还有一个原因就是我想让多次方后的数是我能够写出来作为例子的,如7^5 = 16807,所以我用了尽量小的数字,3,5/3,7,这两组算出来的e,d都是相等的。那我们如果要实现加密的话肯定得让e,d不相等,也就是幂运算的幂会比较大甚至很大,这个时候别说要用手把它算出来了,就算写程序跑,都会溢出。那么在RSA里这一步是怎么进行的呢?

这个我会在下一篇《RSA算法-实现》中解释


[5] 加密解密函数的成立

现在来捋一下思路,看看 m^e ≡ c (mod n) 和 c^d ≡ m (mod n) 为什么会成立:

任取两素数p,q,令n=pq
有φ(n)=(p-1)(q-1)
任取一整数e,令1 < e < φ(n),且 gcd(e,φ(n)) = 1
设d为e对于φ(n)的模反元素
则方程 ed - kφ(n) = 1 成立
此时有
ed = 1 + kφ(n)
ed ≡ 1 (mod n)
m^(ed) = m^(1 + kφ(n)) = m x m^(kφ(n)) = m x (m^(φ(n)))^k
由欧拉定理知
m^φ(n) ≡ 1 (mod n)
所以
m^(ed) = m x (m^(φ(n)))^k ≡ m x (1)^k ≡ m (mod n)
即 m^(ed) ≡ m (mod n)
又 m^(ed) = (m^e)^d
所以此时设 m^e ≡ c (mod n)
则 c^d = m^(ed) ≡ m (mod n)

[6] 私钥与公钥

私钥与公钥的目的最简单的是:将公钥发给一个人或一个群体,使得它们可以利用公钥进行加密并给私钥持有者发送消息,是多对一的单向通信。
但是从上述过程我们不难发现,e,n与d,n在功能上(强调功能上是因为我没验算它们在安全性上是否对等)其实是对等的,一个符合规则的明文m被e,n加密后能被d,n解密出来,那如果直接将m丢入d,n,那么‘解密’出来的数字也可以被e,n‘加密’成原文。也就是说如果你心情好的话可以把它们的公私钥地位给反过来,如此便能实现公私钥间多对一与一对多的双向通信。


三、安全性

上文中我多次提到当n无法被分解为素数因子时,我们视这组密钥为安全,这是因为目前认为最简单地获取到 d 的方法是将 n 分解为 p,q 从而快速推出 φ(n),解出 d。

  • “但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子,同时也还没有人能够证明这种算法不存在”
  • “至今为止也没有人能够证明对 n 进行因数分解是唯一的从 c 导出 m 的方法,但今天还没有找到比它更简单的方法。(至少没有公开的方法。)”
  • “因此今天一般认为只要 n 足够大,那么黑客就没有办法了。”
  • “假如有人能够找到一种有效的分解大整数的算法的话,或者假如量子计算机可行的话,那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。”
    ——来自维基百科

四、效率

与DES、AES相比,RSA的效率明显不如前两者,且当需要处理的数据越大时,差距越明显,所以一般应用中是用AES进行主体数据的加密,然后用RSA来传递AES的密钥。


五、参考

数论思路从这篇博文了解了个大概,然后推敲的过程中又从百度维基查了不少资料,再加上自己整理的理解及一些证明过程,最终写成这篇文章。

Last Modified: July 20, 2019