RSA算法之原理篇

序言

RSA算法是最早得到广泛应用的公钥加密算法。它在通信加密、签名认证等领域都起着重要作用。

RSA算法最早由英国数学家Clifford Cocks在1973年发明，但由于当时被英国政府列为最高机密，直到死后不久其工作成果才被公布。而1977年，Ron Rivest、Adi Shamir 和 Leonard Adleman三人在MIT合作发表了一篇完整描述RSA算法的论文，被正式承认为该算法的发明者。RSA这个名字也正是由三人姓氏的首字母组成。

很有意思的一件事情是，RSA算法并不是第一个公钥加密算法，比RSA算法更早的是一个基于背包问题的公钥加密算法。该算法作者悬赏100美元寻找能够破解他的加密的人，结果这100美元被RSA中的S(Adi Shamir)轻松拿到了。之后不信邪的作者改进了算法，悬赏1000美元继续寻找能破解改进算法的人，不久又被RSA中的R(Ron Rivest)破解了，并且该破解方法适用于背包加密及其变种。

而RSA算法作者也在首次公布RSA算法时悬赏100美元寻找能破解他们的加密信息的人。这个挑战直到17年后，也就是1994年才被破解。而且这个破解有超过600人参与，使用了1600台计算机运算七个多月后才最终得到结果。当然，没有人能拿到那100美元，因为17年已经远远超出了当年作者设置的破解时限。

数学背景知识

RSA算法是一个基于数论的算法，要弄懂RSA，一些数论中的基础知识是必要的，如果你此前已经学过数论相关内容，可以直接跳到下一章。

同余

两个整数a、b，如果他们除以正整数m的余数相等，那a和b同余。用公式来表示就是：

amodm=bmodm⇔a≡bmodm" role="presentation">amodm=bmodm⇔a≡bmodm$$a\mathrm{mod}m=b\mathrm{mod}m\iff a\equiv b\mathrm{mod}m$$ $$amod m=bmod m⇔aequiv bmod m$$

符号“≡”表示同余相等。比如37跟13关于模24同余，也就是37≡13mod24" role="presentation" style="position: relative;">37≡13mod24$37\equiv 13\mathrm{mod}24$$37≡13mod 24$
而形如 a+b≡cmodm" role="presentation" style="position: relative;">a+b≡cmodm$a+b\equiv c\mathrm{mod}m$$a + b equiv c mod m$ 这样带有同余相等符号的式子被称为同余式。我们也可以把它转化为常见的形式a+bmodm=cmodm" role="presentation" style="position: relative;">a+bmodm=cmodm$a+b\mathrm{mod}m=c\mathrm{mod}m$$a + b mod m = c mod m$，但这样写未免太繁琐了。
根据同余关系的性质，在求模运算中，任何大于或等于模数的数都可以用跟它同余的数来代替。比如：
因为

56≡8mod24" role="presentation" style="position: relative;">56≡8mod24$56\equiv 8\mathrm{mod}24$$56≡8mod24$
25≡1mod24" role="presentation" style="position: relative;">25≡1mod24$25\equiv 1\mathrm{mod}24$$25≡1mod24$

所以下列等式都是成立的：

(56+25)mod24=(8+1)mod24" role="presentation" style="position: relative;">(56+25)mod24=(8+1)mod24$(56+25)\mathrm{mod}24=(8+1)\mathrm{mod}24$$(56+25)mod24=(8+1)mod24$
(56−25)mod24=(8−1)mod24" role="presentation" style="position: relative;">(56−25)mod24=(8−1)mod24$(56-25)\mathrm{mod}24=(8-1)\mathrm{mod}24$$(56−25)mod24=(8−1)mod24$
(56×25)mod24=(8×1)mod24" role="presentation" style="position: relative;">(56×25)mod24=(8×1)mod24$(56\times 25)\mathrm{mod}24=(8\times 1)\mathrm{mod}24$$(56×25)mod24=(8×1)mod24$

利用同余性质，将较大的操作数替换为同余的较小的数，可以大大加快模运算的速度。

数论倒数

普通算术运算中，如果ab=1" role="presentation" style="position: relative;">ab=1$ab=1$$ab = 1$，那么我们说a和b互为倒数。类似地，在同余式中，如果ab≡1modm" role="presentation" style="position: relative;">ab≡1modm$ab\equiv 1\mathrm{mod}m$$ab equiv 1 mod m$ ，我们说在模m下，a和b互为数论倒数，或者说乘法逆元。有时候也记作a≡b−1modm" role="presentation" style="position: relative;">a≡b−1modm$a\equiv b^{-1}\mathrm{mod}m$$aequiv b^{−1}mod m$或者b≡a−1modm" role="presentation" style="position: relative;">b≡a−1modm$b\equiv a^{-1}\mathrm{mod}m$$b≡a^{−1}mod m$

欧拉函数

欧拉函数φ(n)" role="presentation" style="position: relative;">φ(n)$\phi (n)$$φ(n)$，也就是对于正整数n，小于或等于n且与n互质的正整数的个数。比如φ(6)" role="presentation" style="position: relative;">φ(6)$\phi (6)$$φ(6)$，不超过6并且跟6互质的有1和5两个数，则φ(6)=2" role="presentation" style="position: relative;">φ(6)=2$\phi (6)=2$$φ(6) = 2$。
特别地，对于任意素数p，所有小于p的正整数都跟它互质，所以φ(p)=p−1" role="presentation" style="position: relative;">φ(p)=p−1$\phi (p)=p-1$$φ(p) = p - 1$。
另外，如果p和q均为素数，那么对于整数n=pq" role="presentation" style="position: relative;">n=pq$n=pq$$n = p q$，有φ(n)=φ(p)φ(q)=(p−1)(q−1)" role="presentation" style="position: relative;">φ(n)=φ(p)φ(q)=(p−1)(q−1)$\phi (n)=\phi (p)\phi (q)=(p-1)(q-1)$$φ(n) = φ(p) φ(q) = (p - 1)(q - 1)$。

欧拉定理

如果a和m都是整数，并且互质，那么有：

aφ(m)≡1modm" role="presentation">aφ(m)≡1modm$$a^{\phi (m)}\equiv 1\mathrm{mod}m$$ $$a^{φ(m)}≡1mod m$$

以a=5，m=6为例，上面计算过φ(6)=2" role="presentation" style="position: relative;">φ(6)=2$\phi (6)=2$$φ(6)=2$，那么，52=25，25mod6=1" role="presentation" style="position: relative;">52=25，25mod6=1$5^2=25，25\mathrm{mod}6=1$$5^2=25，25 mod 6 = 1$，也就是5φ(6)≡1mod6" role="presentation" style="position: relative;">5φ(6)≡1mod6$5\phi (6)\equiv 1\mathrm{mod}6$$5φ(6)≡1mod 6$，验证了上述定理。

费马小定理

如果a为整数，p为素数，且a与p互质（也就是p不能整除a），那么：

ap−1≡1modp" role="presentation">ap−1≡1modp$$a^{p-1}\equiv 1\mathrm{mod}p$$ $$a^{p−1}≡1mod p$$

费马小定理其实就是欧拉定理的特殊情况。也就是当m为素数时的欧拉定理。由于它在RSA算法中的重要作用，我们有必要将它单独拿出来说明。

中国剩余定理

中国剩余定理常用于一元线性同余方程组的求解，在这里我们介绍它的一个推论。
如果 p, q 互质，n = p * q，则对任意整数 x 和 a

(1){x≡amodpx≡amodq⇔x≡amodn" role="presentation">{x≡amodpx≡amodq⇔x≡amodn(1)$$\begin{array}{}\text{(1)}& \{\begin{array}{r}x\equiv a\mathrm{mod}p\\ x\equiv a\mathrm{mod}q\end{array}\iff x\equiv a\mathrm{mod}n\end{array}$$ $$egin{equation} left{ egin{aligned} x equiv a mod p\ x equiv a mod q\ end{aligned} ight. quad Leftrightarrow quad x equiv a mod n end{equation}$$

也就是说，要证明x与a关于n同余，相当于证明x与a关于p和q都同余。

密码学基础知识

RSA算法是一种非对称加密算法，在正式介绍RSA算法前，我们先简单了解一下与非对称加密相对应的对称加密的概念。

对称加密

对称加密是最早出现的加密方式，目前发展已经十分成熟。对称加密的特征是，加密时，根据输入的密钥对明文进行打乱，得出密文；解密时，输入同一个密钥，根据密钥对密文做逆运算，即得出明文。平时我们对文件进行加密，使用的就是对称加密算法，设置的密码就是所谓的密钥；平时开门、锁门在某种程度上也是一种对称加密，只是它的作用对象是实物而非信息，在这里钥匙就是密钥。对称加密用数学的方式来表示即为：

加密：
fk(M)=C" role="presentation" style="position: relative;">fk(M)=C$f_k(M)=C$$f_k(M)=C$

解密：
fk(C)=M" role="presentation" style="position: relative;">fk(C)=M$f_k(C)=M$$f_k(C)=M$
f为加密函数，k为密钥，M为明文，C为密文

一种简单对称加密方法就是，在一封英文信件中将所有字母向后推移一定的位数，比如两位，A->C，B->D，C->E……以此类推，全部加密完成后，这封信的内容乍看上去就是一堆毫无意义的英文字母，起到了一定的加密作用。而解密，自然就是将字母向前推移两位了。在这个加密方法中，2就是一个密钥，加密函数为f(M)=M+2" role="presentation" style="position: relative;">f(M)=M+2$f(M)=M+2$$f(M)=M+2$，解密函数为f(C)=C−2" role="presentation" style="position: relative;">f(C)=C−2$f(C)=C-2$$f(C)=C-2$。

非对称加密

我们知道，文件加密通常使用对称加密，那在通信加密中能不能也用对称加密呢？可以的，如果事先约定好密钥，然后在通信中使用该密钥对信息进行加密然后发送出去，收信方再使用密钥进行解密就可以了。

但如何约定密钥是个大问题。文件加密的密码自己记住就行了，不怕别人截取到，但通信加密需要把密钥发送给对方，这个过程就大大增加了被截取的风险。所以首先需要保证密钥在传输过程中不被第三方窃听。在非对称加密发明之前，这是一个非常复杂的问题。实际上，历史上的很多著名的情报战就是围绕着密钥的保护与窃取展开的。

而非对称加密算法的出现大大改变了这种格局。

跟对称加密算法相比，非对称加密算法需要两个密钥，其中一个密钥用于加密，另外一个用于解密。这两个密钥中，用于解密的密钥必须跟对称加密的密钥一样，不能泄露，称为私钥。而用于加密的密钥可以随意公开，称为公钥。由于这公钥跟私钥总是成对出现并且一一对应的，所以我们经常将他们合称为密钥对。

非对称加密与解密的过程数学描述如下：

加密：
fp(M)=C" role="presentation" style="position: relative;">fp(M)=C$f_p(M)=C$$f_p(M)=C$

解密：
fs(C)=M" role="presentation" style="position: relative;">fs(C)=M$f_s(C)=M$$f_s(C)=M$
其中f为加密函数，p为公钥，s为私钥，M为明文，C为密文

由于非对称加密算法加密与解密使用的密钥不同，通信之前也就不用费尽心机去考虑如何把密钥发送给对方并且不被窃听。事实上，公钥加密体系中，公钥只能用于加密，不需要考虑其保密性，所以只要双方将各自的公钥直接发送给对方，约定密钥这一过程就很轻松地完成了。

在非对称加密体系中，一方向另一方发送信息的流程如下：

• 收信方生成密钥对
• 收信方将密钥对中的公钥发送给发信方
• 发信方使用收到的公钥加密明文，得到密文，然后将密文发送给收信方
• 收信方用私钥解密接收到的密文，即得到明文

在这个过程中，私钥始终是由收信方保存在本地的，第三方最多只能截获公钥以及被公钥加密过的信息，没有私钥，即使截获了这些信息，也无法进行解密。

原理

非对称加密是如何做到加密用一个密钥，解密又要用另一个密钥呢？这一点看起来有点不可思议。按照我们的日常认知来说，一段文字不管怎么打乱，只要知道它的打乱过程，我们总可以将它复原。

为了方便理解，还是跟对称加密进行对比。

我们说过，密码学中，加密函数与解密函数互为反函数。对称加密中我们可以很容易通过加密函数推导出它的反函数，也就是解密函数。比如上面提到的简单的加密方法，加密函数为fk(x)=x+k" role="presentation" style="position: relative;">fk(x)=x+k$f_k(x)=x+k$$f_k(x)=x+k$，那很显然它的反函数就是fk(x)=x−k" role="presentation" style="position: relative;">fk(x)=x−k$f_k(x)=x-k$$f_k(x)=x−k$

事实上，有这样一种函数， y=f(x)" role="presentation" style="position: relative;">y=f(x)$y=f(x)$$y=f(x)$ 很容易求得，它的反函数 x=f−1(y)" role="presentation" style="position: relative;">x=f−1(y)$x=f^{-1}(y)$$x=f^{-1}(y)$却不容易计算，我们通常把这种函数称为单向函数。可以这么理解的：生活中我们把一个盘子打碎很容易，要将它拼回去却很难；把一滴墨水滴进水里很容易，要把墨水从水里重新提取出来却很难。

目前找到的适合用于加密的单向函数并不多，得到广泛应用的仅有两种：质因数分解和离散对数，其中离散对数又包括模n乘法群上的离散对数和椭圆曲线群上的离散对数。这些单向函数是公钥加密体系的支柱。

RSA加密算法

简介

RSA算法的单向函数基于质因数分解问题。
质因数分解问题指数论中的一个简单事实：计算两个素数的乘积很简单，但要把这个乘积重新分解为两个素数却很难。

步骤

RSA算法由三部分构成：

• 密钥生成算法
• 加密算法
• 解密算法

1. 密钥生成算法

• 随机生成两个素数 p,q
• 计算 n=pq

• 计算欧拉函数 φ(n)=(p−1)(q−1)" role="presentation" style="position: relative;">φ(n)=(p−1)(q−1)$\phi (n)=(p-1)(q-1)$$φ(n)=(p−1)(q−1)$

• 选取一较小的与φ(n)" role="presentation" style="position: relative;">φ(n)$\phi (n)$$φ(n)$互质的正整数e。那么(n, e)为密钥对中的公钥

• 计算e在模φ(n)" role="presentation" style="position: relative;">φ(n)$\phi (n)$$φ(n)$下的数论倒数d，d≡e−1modφ(n)" role="presentation" style="position: relative;">d≡e−1modφ(n)$d\equiv e^{-1}\mathrm{mod}\phi (n)$$d≡e^{−1}modφ(n)$，那么(n, d)为密钥对中的私钥

2. 加密算法

• 计算
  C=fe(M)=Memodn" role="presentation">C=fe(M)=Memodn$$C=f_e(M)=M^e\mathrm{mod}n$$ $$C=f_e(M)=M^emod n$$
  其中M为明文，(n, e)为公钥，C为密文

3. 解密算法

• 计算
  M=fd(C)=Cdmodn" role="presentation">M=fd(C)=Cdmodn$$M=f_d(C)=C^d\mathrm{mod}n$$ $$M=f_d(C)=C^dmod n$$
  其中C为密文，(n, d)为私钥，M为明文

根据加密、解密过程中n、e、d三数扮演的角色，我们把n称为公共模数，把e称为公共指数，把d称为私有指数。

实例演示

在公钥加密通信中，小明要给小红发信息，那么小红首先需要生成两个素数p和q。为了计算简单，我们假设p = 17和q = 23，实际应用中p和q往往长达数百上千位。
计算n=17∗23=391" role="presentation" style="position: relative;">n=17∗23=391$n=17\ast 23=391$$n = 17 * 23 = 391$
而φ(n)=(17−1)(23−1)=352" role="presentation" style="position: relative;">φ(n)=(17−1)(23−1)=352$\phi (n)=(17-1)(23-1)=352$$φ(n) = (17 - 1)(23 - 1) = 352$
选取和352互质的7作为公钥中的e。那么公钥就是(391, 7)。
然后计算7在模352下的数论倒数d。使用扩展欧几里德算法求得d = 151。
验证一下，d∗e=151∗7=1057" role="presentation" style="position: relative;">d∗e=151∗7=1057$d\ast e=151\ast 7=1057$$d*e = 151 * 7 = 1057$，而1057mod352=1" role="presentation" style="position: relative;">1057mod352=1$1057\mathrm{mod}352=1$$1057 mod 352 = 1$，所以151是7在模352下的数论倒数。私钥为(391, 151)。
小红通过公共信道把公钥(391, 7)发给小明。
假设小明要发给小红的信息是79，对它进行加密，也就是计算797mod391=37" role="presentation" style="position: relative;">797mod391=37${79}^7\mathrm{mod}391=37$$79^7 mod 391=37$。得到密文C = 37。
小明将密文37发送给小红。
小红收到后，进行解密运算37151mod391=79" role="presentation" style="position: relative;">37151mod391=79${37}^{151}\mathrm{mod}391=79$$37^{151}mod 391=79$。得到原文79。

原理

关于RSA算法的原理，实际上我们主要关心两点：

• 为什么RSA加密是正确的？
• 为什么RSA加密不容易破解？

正确性

所谓正确性，也就是指加密后的密文可以被正确解密为明文，即证明等式

M=fd(fe(M))" role="presentation">M=fd(fe(M))$$M=f_d(f_e(M))$$ $$M=f_d(f_e(M))$$

成立。

证明过程：
对原式进行展开

fd(fe(M))=fd(Memodn)=(Memodn)dmodn=Medmodn" role="presentation">fd(fe(M))=fd(Memodn)=(Memodn)dmodn=Medmodn$$f_d(f_e(M))=f_d(M_e\mathrm{mod}n)=(M^e\mathrm{mod}n{)}^d\mathrm{mod}n=M^{ed}\mathrm{mod}n$$ $$f_d(f_e(M)) =f_d(M_emod n) =(M^emod n)^dmod n =M^{ed}mod n$$

由中国剩余定理推论，我们可以知道，要证明

Med≡Mmodn" role="presentation">Med≡Mmodn$$M^{ed}\equiv M\mathrm{mod}n$$ $$M^{ed}≡Mmod n$$

相当于证明

Med≡Mmodp以及Med≡Mmodq" role="presentation">Med≡Mmodp以及Med≡Mmodq$$M^{ed}\equiv M\mathrm{mod}p以及M^{ed}\equiv M\mathrm{mod}q$$ $$M^{ed}≡Mmod p 以及 M^{ed}≡Mmod q$$

下面我们使用费马小定理证明 Med≡Mmodp" role="presentation" style="position: relative;">Med≡Mmodp$M^{ed}\equiv M\mathrm{mod}p$$M^{ed}≡Mmod p$
首先需要对M进行分情况讨论。
当p整除M时，
不符合费马小定理的应用条件，但此时有 M≡0modp" role="presentation" style="position: relative;">M≡0modp$M\equiv 0\mathrm{mod}p$$M≡0mod p$ ，所以 Med≡Mmodp" role="presentation" style="position: relative;">Med≡Mmodp$M^{ed}\equiv M\mathrm{mod}p$$M^{ed}≡Mmod p$ 必然成立。
当p不能整除M时，
因为RSA算法中d为e在模φ(n)下的数论倒数，则

d≡e−1modφ(n)⇒ed≡1modφ(n)⇒ed=1+kφ(n)=1+k(p−1)(q−1)" role="presentation">d≡e−1modφ(n)⇒ed≡1modφ(n)⇒ed=1+kφ(n)=1+k(p−1)(q−1)$$d\equiv e^{-1}\mathrm{mod}\phi (n)\Rightarrow ed\equiv 1\mathrm{mod}\phi (n)\Rightarrow ed=1+k\phi (n)=1+k(p-1)(q-1)$$ $$d≡e^{−1}modφ(n) ⇒ed≡1modφ(n) ⇒ed=1+kφ(n)=1+k(p−1)(q−1)$$

所以有

Medmodp=M1+k(p−1)(q−1)modp=M(Mp−1)k(q−1)modp" role="presentation">Medmodp=M1+k(p−1)(q−1)modp=M(Mp−1)k(q−1)modp$$M^{ed}\mathrm{mod}p=M^{1+k(p-1)(q-1)}\mathrm{mod}p=M(M^{p-1}{)}^{k(q-1)}\mathrm{mod}p$$ $$M^{ed}mod p =M^{1+k(p−1)(q−1)}mod p =M(M^{p−1})^{k(q−1)}mod p$$

由费马小定理可知 Mp−1≡1modp" role="presentation" style="position: relative;">Mp−1≡1modp$M^{p-1}\equiv 1\mathrm{mod}p$$M^{p−1}≡1mod p$
所以有

Medmodp=M(Mp−1)k(q−1)modp=M(1)k(q−1)modp=Mmodp" role="presentation">Medmodp=M(Mp−1)k(q−1)modp=M(1)k(q−1)modp=Mmodp$$M^{ed}\mathrm{mod}p=M(M^{p-1}{)}^{k(q-1)}\mathrm{mod}p=M(1{)}^{k(q-1)}\mathrm{mod}p=M\mathrm{mod}p$$ $$M^{ed}mod p=M(M^{p−1})^{k(q−1)}mod p=M(1)^{k(q−1)}mod p=Mmod p$$

同理可以证明 Med≡Mmodq" role="presentation" style="position: relative;">Med≡Mmodq$M^{ed}\equiv M\mathrm{mod}q$$M^{ed}≡Mmod q$
所以等式M=fd(fe(M))" role="presentation" style="position: relative;">M=fd(fe(M))$M=f_d(f_e(M))$$M=f_d(f_e(M))$成立。

安全性

观察RSA加密的过程
C=fe(M)=Memodn" role="presentation">C=fe(M)=Memodn$$C=f_e(M)=M^e\mathrm{mod}n$$ $$C=f_e(M)=M^emod n$$
在只知道密文C和公钥（n，e）的情况下，要得到明文M，其实也就是计算模n群上C的e次方根。即：
M=Ce