简介

RSA加密算法是一种广泛使用的非对称加密算法。HTTPS,SSH等均有应用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。RSA就是他们三个大神的姓氏开头字母拼在一起组成的。还挺顺口的。

RSA算法不复杂,但是却非常强悍。其加密的数学依据来源于数论相关知识。这里,先从RSA算法过程入手,抽出其中用到的知识点,然后,逐个解答。

RSA算法

生成公私钥过程如下

1. 随机两个比较大的素数p和q,计算N=pq。
2. 根据欧拉函数,就得r=φ(N)=(p-1)(q-1)。
3. 选择一个小于r的整数e,使得e与r互质。并求e关于r的模逆元,命名为d。即ed ≡ 1 (mod r)。
4. 将p和q销毁。

(N, e)即为公钥,(N, d)即私钥。

加密解密方式如下

明文^e % N = 密文

密文^d % N = 明文

上述短短的4个步骤包含的知识点有

  1. 随机两个比较大的素数p和q

    如何随机两个比较大的素数?或者说,如何判断一个比较大的数是素数。

  2. 欧拉函数

    φ(N)=(p-1)(q-1)。

  3. 模逆元

    模逆元是什么。ed ≡ 1 (mod r),已知e怎么求d。

  4. 加密解密

    怎么证明加密解密是可行的。

数论

数论研究正整数集合,通常也称为自然数集合。常见的数有,奇数,偶数,素数,合数,斐波拉契数等。一个典型的数论问题是,哪些数可以表示成两个数的平方。小学学过的勾股定理中,(3, 4, 5),就是其中一个解。那有没有其他的正整数解呢?或者有这样关系的数有什么特点呢。这就是数论研究的一些问题。

高斯说,数学是自然科学的女皇,而数论则是女皇的皇冠。足以见数论在数学中的地位。大家耳熟的一些定理,费马大定理,哥德巴赫猜想等也是数论的一些经典话题。

我学习的书是《数论概论(第三版)》,写的非常好。如果对数论感兴趣的话,推荐这本书。

素数

素数也叫质数。指,不能被1和自身以外的其他任何数整除。例如,1,2,3,5,7等。

小学里面学习过,任何数都可以分解成素数的乘积形式。因此,素数也被称为整数的基础构件。通常很多定理都是在研究素数时产生的。

最大公因数

公因数指能同时整除几个数的数。最大公因数指,能整除这些数的因数中,最大的一个。记做gcd

两个数没有公因数,也叫两个数互质,其gcd(a, b) = 1。

同余式

了解编程的都知道模运算。模运算的结果就是除法的余数。同余式顾名思义就是两个数模一个数的余数相等。

a ≡ b (mod n)

上述式子即表示,a和b模n的余数相等。但是这种定义太抽象了,不利于进行数学研究。从数学的角度来定义,如果a-b能被n整除,则表明a和b模n同余。虽然显而易见,但是还是费两行来证明一下

令,a = xn + r,b = yn + t
(a - b) = (x - y)*n + (r - t)
如果r = t,则 n|(a-b),得证。

类似于加减乘除等基础运算,同余式也有一些运算规律。例如

如果,a1 ≡ b1 (mod m), a2 ≡ b2 (mod m)。则有

a1 ± a2 ≡ b1 ± b2 (mod m), a1 * a2 ≡ b1 * b2 (mod m)

证明

a1 = im + s, b1 = xm + s
a1 = jm + t, b2 = ym + t

a1 + a2 = (i+j)m + (s + t)
b1 + b2 = (x+y)m + (s + t)

a1 * a2 = (im + s) * (jm + t) = ijm^2 + (it + sj) * m + st
b1 * b2 = (xm + s) * (ym + t) = xym^2 + (xt + sy) * m + st

注意

a * c ≡ b * c (mod m),不能消去c,除非gcd(c, m) = 1。

最后一个运算的证明可以看这里

同余式的基本运算就这些了,但是并不表示其后面衍生的内容也这么简单。就像掌握了基本的加减乘除,后面就有幂运算,方程等等。

线性同余方程和模逆元

上面已经介绍了模运算的基本定理吧。是不是还提到了方程。我们学完了加减乘除,就开始学解方程了。同样的,同余式也有方程。

ax ≡ c (mod m)

根据同余式定义,上面的同余式即是方程ax + ym = c的解。当c=1时,我们称a与x是模m的一对逆元,也就是问题3。

继续分析,ax + my = c这个方程。有一个结论是,ax + my的最小正整数值是gcd(a, m),且c是gcd(a, m)的倍数。数学里面每个结论都有严格的证明,这里就不叙述了。接下来的重点放在求解ax + my = gcd(a, m)上。

要求解这个线性方程,我们先来了解怎么求gcd(a, m)。小学4年级的时候,老师教过一个怎么求最大公因数的方法。就是用相同的因数去同时整除两个数,然后直到没有公因数为止。这种方法对于比较小的数可行,能一眼看出因数。但是对于很大的两个数,一眼看不出因数的,就不太好用了。

欧几里得提出了一个求解公因数的定理,叫欧几里得定理,也叫辗转相除法。扩展欧几里得公式

设 A = Q*B + R

gcd(A, B) = gcd(B, R)

它的意思是,A和B的最大公因数等于B和余数R的最大公因数。

可以查看这里的一个证明过程。

辗转相除法,就是不断的和余数相除,最后剩下的就是最大公约数。例如求gcd(22, 60)的过程,虽然一眼就能看出来等于2。

60 = 2*22 + 16
22 = 1*16 + 6
16 = 2*6 + 4
6 = 1*4 + 2
4 = 2*2 + 0

好了。我们岔开了很多内容来谈怎么求最大公因数。这个和求解线性方程有什么关系呢?因为,我们根据gcd(a, b)有 a = q1 * b + r1。在辗转相除计算的过程中,会陆续算出r = a * a的倍数 + b * b的倍数,直到最终得到r=gcd(a, b)。此时的倍数就是线性方程ax + by = gcd(a, b)的解。具体的解法步骤就不介绍了,感兴趣的可以去了解哈。

学习线性同余方程,是为了让大家明白,模逆元以及ax ≡ 1 (mod m)是怎么求解的。

费马小定理和欧拉函数φ

好了,上面已经介绍了足够多的数论基础知识了,下面开始学习两个著名的定理。首先是,费马小定理。

费马小定理

设p是素数,a是任意整数,且a模p不等于0。则
a^(p - 1) ≡ 1 (mod p)

这个定理短小精悍,里面提到了幂。如果有这个定理的话,我们就可以求一些相当大的数的模了。例如2^22 % 23,直接计算的话,恐怕是不现实了。但是应用费马小定理,即可以快速求解得1。下面是一个证明

首先断言,
设p是素数,a是任意整数,且a模p不等于0。则
a, 2a, 4a, ..., (p - 1) * a (mod p)
与数
1, 2, 3, ..., (p - 1) (mod p)
相同,尽管顺序不同。

证明

第一个数列包含p-1个数,因为p是素数,所以没有一个被p整除。假设,从中取两个数,ja和ka,并假设它们模p同余。
则,p|(j - k)a。因为p不整除a,所以p|(j - k)。另外,1 <= j, k <= (p-1),则 |j - k| < p-1。只有一个数绝对值小于p-1且被p整除,就是0。但是j != k。所以,ja和ka模p不同余。即第一个数列,模p不同。

然后,我们利用前面同余式的基本运算,将下面两个数列相乘

a * (2a) * (4a) * ... * (p-1)a ≡ 1 * 2 * 3 * ... * (p-1) (mod p)

最后

a^(p-1) ≡ 1 (mod p)

欧拉函数φ

首先,考虑这么一个问题。对于任何一个数,在比他小的数中,有多少个与它互质的数?

例如,对于9,有{1, 2, 4, 5, 7, 8},共6个;对于10,有{1, 3, 7, 9},共4个。在0与m中,与m互质的数的个数是一个很重要的量。这个量记做φ。有前面可知,φ(9) = 6,φ(10) = 4。我们可以很快知道,如果m值素数,则φ(m) = m -1。这个函数也叫欧拉函数。

好了。欧拉函数出来了,接下来就是著名的欧拉公式

如果gcd(a, m) = 1,则
a^(φ(m)) ≡ 1 (mod m)

和费马小定理相对比。可以发现费马小定理其实是欧拉公式的一种特殊情况,即m是素数的情况。欧拉公式的证明可以参考网上的资料。

数论里面有很多欧拉的一些定理。越看越佩服,这个人是真厉害。同时,也有一个感受,数学不受时代的限制。欧拉等数学家距离现在几百年,但是他们研究的东西,和思维,没有因为时间太久而显老。

拉宾-米勒素性测试

最后一个问题了。解决了这个问题,大家就了解了RSA的全部知识。

RSA算法开头就蹦出个,生成两个非常大的随机素数p和q。问题是,怎么生成呢?如果是随机两个非常大的偶数的话,我可以先随机两个很大的数,然后,再乘以2即得到两个随机偶数。很可惜,目前并没有什么方法能直接得到一个超级大的随机素数。我们可以生成一个随机大数,然后判断它是不是一个素数。所以,问题就是,怎么判断一个超级大的数是一个素数。

前面学习了费马定理,可以得出

设n是素数,a是任意整数,且a模n不等于0。则
a^n ≡ a (mod n)

因此,2^m模m不同余于2模m,所以我们断定m不是素数。因为如果m是素数,它必然满足上面的定理。

这是一个充分必要条件的关系。根据上面的式子,如果不满足上面的公式,我们能肯定它不是素数。如果满足,则不能确定它是不是素数。

如果能找到a的值,使得上面的式子不相等。则称a是n的证据。于是,数学家就开始试验。对于一个合数n,找n-1个尽可能多的a,来验证a是不是n的证据。结果发现,a是证据的概率非常高。翻译成白话就是,如果n不是素数,找一个小于n-1的数a,计算a^n模n,其结果有很大概率不等于a模n。

那么,还是逻辑问题。是不是找不到a使得费马同余式不相等,就表明n是一个素数了呢?不是的。并且恰好就有这样的合数。它叫卡米歇尔数,也叫伪素数。

对于n是合数,对于每个证书1 <= a <= n,都有
a^n ≡ a (mod n)

卡米歇尔数存在意味着我们需要一个更好的判别素数的方法。合数的拉宾-米勒测试就是基于以下事实

设p是奇素数,记n - 1 = 2^k * q, q是奇数。对不被n整除的某个数a,如果下面两个条件都成立,则n是合数
(a) a^q模n不等于1
(b)对所有i = 0, 1, ..., a^(2^i)*q,都模n不等于-1。

最后,举一个例子来完成这节的内容。例如,判断n=561是否是合数。

n = 561

n - 1 = 560 = 2^4 * 35, k = 4, 选择a = 2
2^(2^0 * 35) ≡ 263 (mod 561)
2^(2^1 * 35) ≡ 263^2 ≡ 166 (mod 561)
2^(2^2 * 35) ≡ 166^2 ≡ 67 (mod 561)
2^(2^3 * 35) ≡ 67^2 ≡ 1 (mod 561)

根据测试,561是合数。

这个测试方法应该是应用比较广泛的了。Golang官方RSA生成素数也是如此测试。

RSA证明

接下来,对RSA算法进行数学证明,证明其解密方法确实能得到原文。

(N, e)是私钥,(N, d)是公钥。

假设,A = 明文,B = 密文

1. A^e ≡ B (mod N) // 加密
2. B^d ≡ A (mod N) // 解密

证明

已知,A ≡ B^d (mod N),则
A^e 
≡ (B^d)^e
≡ B^(de) // 因为ed ≡ 1 (mod φ(N)),则有,φ(N)|(ed - 1),ed - 1 = k * φ(N)。
≡ B^(1 + φ(N)*k) 
≡ B*(B^φ(N))^k // 利用欧拉公式,a^(φ(m)) ≡ 1 (mod m)
≡ B * 1^k 
≡ B (mod N)

为什么RSA破解很难?观察其生成的步骤,我们已知N和d,如果能知道r,就可以算出e。

r有两种方式计算,一种是根据定义列举N以内和它互质的数个数,另一种是根据p和q。前者得统计质数数量,比分解因数更困难,还不如直接求p和q。所以也就是归结为,对N进行质因数分解。目前没有有效的方法对大数进行因数分解,因此,这个才是RSA目前较安全的原因。

关于数论的体会

数论后面还有很多内容,但是先告一段落,花了一些精力在上面。主要是熟悉了初等数论相关的知识,对素数等的一些规律有了一些认识。在看数论的时候,有时候一个转弯就有点懵了。书里平淡的一句结论,还得想半天。有时候需要证明的东西,还是看别人的说明才明白。不过保持为什么是好事。

数论中的一个思想很有意思。所有的猜想,都是从一些简单的例子出发,列出一系列的数,然后观察数之间的规律。最后提出一个猜想,然后,证明得出通用的定理。

还有一个体会是,关于同余式。没想到这个同余在数论中这么广泛,平常开发中也就偶尔会用到模运算。

最后,学习数论挺有收获的。

参考资料

  • 《数论概论(第三版)》
  • 维基百科等