密码学之RSA加密算法

前言

以下是iOS签名原理系列的文章链接

密码学之RSA加密算法

Hash与对称加密算法

理解iOS签名原理

本篇是这个系列的第1篇，下面进入正题

1. 密码学

1.1 什么是密码学？

密码学是研究编制密码和破译密码的技术科学。在现代特别指对信息以及其传输的数学性研究，常被认为是数学和计算机科学的分支，和信息论也密切相关。

在这里简述一下密码学的发展历史。

1.2 密码学的发展历史

在1976年以前，所有的加密方法都是同一种模式：加密、解密使用同一种规则（密钥）。在交互数据的时候，彼此通信的双方就必须将规则告诉对方，否则没法解密。这种加密方式被称为 对称加密算法（symmetric encryption algorithm）。
1976年，两位美国计算机学家 迪菲（Whitfield Diffie）、赫尔曼（Martin Hellman） 提出了一种建立密钥的方法，其产生的密钥可用于加密、密钥管理或任何其它的加密方式。这被称为“迪菲赫尔曼密钥交换”算法，简称 D-H算法。D-H算法启发了其他科学家。人们意识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。
1977年三位麻省理工学院的数学家 罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir） 和 伦纳德·阿德曼（Leonard Adleman） 一起设计了一种算法，可以实现非对称加密。（所谓非对称，就是指该算法需要一对密钥，即公钥(public key) 和 私钥(private key)，且两密钥不同，使用其中一个加密，则需要用另一个才能解密）。这个算法用他们三个人的名字命名，叫做 RSA算法。

RSA算法的影响是巨大的，毫不夸张地说，只要有计算机网络的地方，就有RSA算法。这种算法非常可靠，密钥越长，它就越难破解。

接下来，我们需要学习几个数学概念，这有助于我们理解RSA加密算法。

2. 几个数学概念

2.1 取模运算(mod)

即求余运算，是在整数运算中求一个整数A除以另一个整数B的余数的运算，且不考虑运算的商。在计算机程序设计中也有mod运算，其格式为： mod(A, B)，即是两个数值作除法运算后的余数。

注意：

当A、B为同号时，即同为正整数或负整数时，mod运算与我们熟悉的%运算相同，可当作是%运算；
如，3 mode 17 = 3 % 17 = 3；-5 mod -3 = -5 % -3 = -2

A、B异号时，mod运算与%运算不同，在这里不作详细赘述，感兴趣的同学可自行查阅相关资料。

2.2 互质关系

如果两个正整数，除了1之外，没有其它公因数，我们就称这两个数存在互质关系，即这两个数互质。
关于互质关系，不难得到以下几个结论：

任意两个 不同的质数 互质。比如11和23互质，11和11不互质。

一个是质数，另一个只要不是前者的倍数，两者就构成互质关系。比如5和12互质。

一个质数与任意一个比它小的数互质。比如11和8。

1和任意一个大于1的自然数互质。比如1和99。

p是大于1的整数，则p和p-1互质。比如10和9。

注意： 两个正整数互质，意思是这两个整数存在互质关系，即没有1之外的其它公因数，并不意味着这两个数是质数。比如9和10互质，但是9和10均为合数。

2.3 欧拉函数

对于一个正整数n，小于n且和n互质的正整数的个数，计算这个值的方法叫做欧拉函数，记做：φ(n)。欧拉函数通式为

\phi(n)=n({1}-{1\over{p_1}})({1}-{1\over{p_2}})...({1}-{1\over{p_k}})

其中，p₁、p₂、...、p_k为n的质因数。
如12=2*2*3，2和3为12的质因数，则φ(12)=12*(1-1/2)(1-1/3)=4。关于欧拉函数，同样有几个推论：

特别声明，如果n=1，则φ(1)=1，因为1与任何数（包括它本身）形成互质关系。

当n是质数的时候，φ(n)=n-1。如φ(7)=6，即1、2、3、4、5、6均与7互质。

如果n可以分解成两个互质的整数之积，如n=a*b，则φ(n)=φ(a)*φ(b)。如φ(56)=φ(7)*φ(8)=24；注意，φ(49)≠φ(7)*φ(7) => φ(49)≠36，因为7与7不互质。事实上，φ(49)=42。

由2和3可以得到，如果n=a*b，且a、b均为质数，则φ(n)=(a-1)*(b-1)。如φ(35)=φ(5)*φ(7)=24；

如果n=p^k（其中p为质数，k为大于1的整数），则φ(n)=φ(p^k)=p^k-p^k-1=(p-1)p^k-1。如φ(49)=φ(7²)=(7-1)*7¹=42。

2.4 欧拉定理

欧拉定理指的是，如果两个互质的正整数m和n，那么m的φ(n)次方减去1，可以被n整除。即，

\mathbf{m}^{\phi(n)}\mod\mathbf{n}\equiv1

如7和3互质，7^φ(3) mod 3 = 7² mod 3 = 1

费马小定理：当n为质数的时候，则有 m^n-1 mod n ≡ 1

欧拉定理是RSA算法的核心，理解了这个定理，就理解了RSA算法。

n^1.3-2

2.5 模反元素

如果两个正整数m和n互质，那么一定可以找到整数d，使得md-1能被n整除，那么d就是m相对于n的模反元素。即

\mathbf{m}\mathbf{d}\mod\mathbf{n}\equiv1

由上式，可得 d=(kn+1)/m。

欧拉定理可以证明上式。由于m和n互质，那么m和n必满足欧拉定理，即 m^φ(n) mod n ≡ 1，令d=m^φ(n)-1，即得证！

如，3和5互质，当，k为大于等于1的整数，不难求出当k=4时，得到d=3，即3(d)就是11(e)相对于8(x)的一个模反元素。

3. RSA加密算法

介绍完以上几个数学概念，我们详细介绍一下RSA加密算法。

3.1 RSA加密算法原理

RSA使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。其原理是基于大数难以分解，即两个大素数相乘容易，但逆向得到一个由两个大质数相乘得到的更大数的因子则很困难。除了暴力破解，目前还没有其它有效的方法。换而言之，RSA加密算法的可靠性，取决于对极大整数做因式分解的难度。假如有人找到一种快速因数分解的算法（或者量子计算机技术快速发展？），那么RSA的可靠性就会极度下降。但就目前而言，1024位RSA基本安全，2048位是极其安全的。

举例来说，你可以对33进行因式分解（3*11），但是你没法对下面这个整数进行因式分解

12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

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

33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917

3.2 密钥生成的步骤

我们通过一个例子，来理解RSA加密算法。假如甲和乙两人进行通信。其流程如下：

甲选择两个不相等的质数p和q，甲选择了3和11，即p=3，q=11。
注意：实际应用中，这两个质数越大，就越难破解。

甲计算得到p和q的乘积n，即n=33
n的长度就是密钥长度，33写成二进制是100001，一共有6位，所以这个密钥是6位。

甲计算n的欧拉函数φ(n)，得到φ(n) = (p-1)(q-1) = 20

随机选一个整数e，满足1 < e < φ(n)，且e与φ(n)互质。甲选择了13。

再计算e相对于φ(n)的模反元素d。将e、φ(n)代入公式ed=kφ(n)+1，得到13d=20k+1，此二元一次方程可以用 “扩展欧几里得算法” 求解，此处省略过程。总之，甲算出一组整数解为(d,k)=(17,11)，即d=17

将n和e封装成公钥，n和d封装成私钥。即公钥是(33,13)，私钥是(33,17) 注意：实际应用中，公钥和私钥的数据都采用 ASN.1 格式表达。

3.3 RSA加密算法的可靠性分析

上述步骤共出现6个数字：p:3、q:11、n:33、φ(n):20、e:13、d:17。其中，公钥用了两个，即(n和e)，其余四个数字不公开。这些数字中最关键的是d，因为n和d组成了私钥，一旦d泄露，就等于私钥泄露。

讨论：在已知公钥(n,e)的情况下，推导d

由于d是e相对于φ(n)的模反元素，满足ed mod φ(n) ≡ 1，要想求出d，必须知道e和φ(n)。
又由φ(n) = (p-1)(q-1)，只有知道p和q，才能求出φ(n)。
而n = pq，只有将n因式分解，才能算出p和q。

结论：如果n可以被因式分解，d就可以算出，也就意味着私钥被破解。因此，RSA加密算法的可靠性，取决于对极大整数做因式分解的难度。

3.4 加密和解密

有了公钥和私钥，就可以进行通信了。

假设乙要向甲发送信息m，他需要用甲的公钥(n,e)即(33,13)对m进行加密，得到密文c。加密规则为：m^e mod n ≡ c，假设m为6，则c=18。于是，乙将18发给了甲。

甲收到了乙发送过来的信息，即18，也就是c的值，并用自己的私钥(n,d)即(33,17)进行解密。解密规则为：c^d mod n ≡ m，即m=6。因此，甲知道了乙发送过来的原文是6。

至此，“加密-解密”的过程就完成了。

思考：为什么解密规则是 c^d mod n ≡ m ？

3.5 解密规则的证明

根据加密规则 m^e mod n ≡ c，得到 c ≡ m^e - kn
将其代入我们要证明的解密规则，可得到：
(m^e - kn)^d mod n ≡ m
它等同于证明： m^ed mod n ≡ m
又由于d为e相对于φ(n)的模反元素，故ed mod φ(n) ≡ 1，即ed = k*φ(n)+1，将ed代入上式得：
m^kφ(n)+1 mod n ≡ m，(k为大于等于1的整数)
因此，上式得证则解密规则成立！

在此，我们再梳理一下加-解密过程中的这几个数字：p:3、q:11、n:33、φ(n):20、e:13、d:17、明文m:6、密文c:18。

n为两个质数p和q的乘积，则n与以上除了p、q、n之外的任意数互质。(实际运用中，p和q为大质数，从而保证了n被破解的难度很大)；

e满足1 < e < φ(n)，并且与φ(n)互质，d为e相对于φ(n)的模反元素，即ed=kφ(n)+1

接下来，分成两种情况证明解密。

m与n互质时

根据欧拉定理，m^φ(n) mod n ≡ 1

由于1^k≡1和1*m≡m，对两边表达式进行k次幂运算后，再各乘以m，得到 m^kφ(n)+1 mod n ≡ m，得证！

即m和n互质时，解密规则成立。

m与n不互质时

由于n为两个质数（p和q）的乘积，故m必为其中一个质数的倍数，在此取m=kp。

根据欧拉定理，有 (kp)^φ(q) mod q ≡ 1

由于1^[hφ(p)]≡1和1*(kp)≡kp，得到 (kp)^hφ(n)+1 mod q ≡ kp

又ed=kφ(n)+1，代入上式可得 (kp)^ed mod q ≡ kp，故 (kp)^ed ≡ tq + kp（思考t和p的关系）
t和p的关系：由上式得到 (kp)^ed mod t ≡ kp ，显然，t必然能被p整除，即 t=t'p。

因此，(kp)^ed ≡ t'pq + kp，由于m=kp和n=pq，所以 m^ed mod n ≡ m，得证！即，m和n不互质时，解密规则也成立！

综上，无论明文m是什么内容，都能通过加密规则：m^e mod n ≡ c 生成密文c，再由解密规则：c^d mod n ≡ m 得到明文m。

3.6 RSA算法的特点

通过对RSA算法原理、流程的验算分析，不难得出以下几个结论：

RSA算法不需要进行密钥传递，安全性高。

RSA算法的加密解密效率不高，一般应用于处理小数据。
如加密KEY、数字签名等。

4. 示例

讲了半天RSA算法的理论知识，是时候展示真正的技术了。接下来，我们用终端来玩一下RSA吧。

由于Mac系统内置OpenSSL(开源加密库)，所以我们可以直接在终端上使用命令来玩RSA。
OpenSSL中RSA算法的常用指令主要有三个：

genrsa，生成并输入一个RSA私钥
rsautl，使用RSA密钥进行加密、解密、签名和验证等运算
rsa，处理RSA密钥的格式转换问题。

操作流程如下：

生成一个长度为1024位的RSA私钥

openssl genrsa -out private.pem 1024

结果如下：

对私钥内容感兴趣的同学可以用下面的命令将私钥转换成明文。

openssl rsa -in private.pem -text -out private.txt

自行打开private.txt文件即可，这里不作文件内容说明。

从私钥中提取公钥

openssl rsa -in private.pem -pubout -out public.pem

结果如下：

假设明文文件内容是
对明文文件进行 公钥加密 和 私钥解密

通过公钥进行加密

openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt

通过私钥进行解密

openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt

结果如下：

解密后的文件dec.txt内容正好是【密码：helloRSA123456】，与明文内容一致。至此，RSA算法流程结束。

注意：也可用 私钥加密 和 公钥解密，如：
1). 通过私钥进行加密
openssl rsautl -sign -in message.txt -inkey private.pem -out enc.txt
2). 通过公钥进行解密
openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt

5. 参考资料

文末

本文github