【《数学之美》笔记（四）】加密算法

1. 对称性加密与非对称性加密

假设一个形象理解的场景：

考试时，超模君通过小天给学渣表妹传递答案

对称性加密
非对称性加密

加密和解密规则：

考试前超模君找到表妹，给了她一张纸片，纸片上有20行数，每行有4个数字，4个数字为乱序的1、2、3、4（如下图所示）

超模君考试时传递的小纸条中第一个数字X1表示纸片中X1行里的第x1个数字，第二个数字X2开始表示下一行中的第X2个数。例如，超模君的纸条上数字为2123，那么根据上面的纸片从第二行开始找数字，得到答案2、4、2、2（下图所示）

非对称性加密与对称性加密最大的区别就在于非对称性加密拥有两把钥匙，分别为私匙和公匙，其中只有公匙会传播出去，而私匙只会在自己手中，不会传播到外界

2. RSA加密算法

2.1. 加密解密原理

RSA算法是1977年由三位麻省理工学院教授——罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出。RSA就是他们三人姓氏开头字母拼在一起组成的

RSA算法过程：

如何得到公匙 $e$ 和匙 $d$

(1) 找出两个质数，一个是 $p$ ，另一个是 $q$

(2) 做一个乘法： $n=p\times q$

(3) 取一个函数： $\psi(n)=(p-1)\times(q-1)$

(4) 找出公匙 $e$ 和匙 $d$

$\begin{cases}1<e<\psi(n) \\ e \text{和}\, \psi(n) \text{需要互质} \\ e·d\,\text{除以}\,\psi(n)\text{余数为}\,1 \end{cases}$
如何加密和解密

假设传输的信息的数字为 $m$ ，接下来我们就可以得到加密公式：

$c=m^e \% n$

其中 $\%$ 为取余运算

c就是我们发送出去的加密后的数字

再来看看解密的公式：

$m=c^d\%n$

这个余数就是我们传输的信息——m

举个例子：

(1) 找出两个质数，一个是7，另一个是13

(2) $n=p\times q=7 \times 13=91$

(3) $\psi(n)=(p-1)\times(q-1)=6 \times 12=72$

(4) 找出公匙 $e$ 和匙 $d$ ： $\begin{cases}e=5 \\ d=29\end{cases}$

(5) 假设我们要加密的数字是 $m=4$

(6) 加密： $m^e \div n=4^5 \div 91...23$

(7) 解密： $c^d \div n=23^29 \div 91...4$

2.2. 安全性分析

为什么RSA算法是安全的（目前来说）？

在传输的过程中， $e$ （公匙）、 $n$ （质数乘积）、 $c$ （余数）是可以被黑客窃听到的，但参考上面加密公式可以知道 $d$ （私匙）和 $\psi(n)$ 没有参与加密过程，所以窃听者并不知道 $d$ 和 $\psi(n)$

那么窃听者能不能通过e、n、c算出私匙d呢？

$\begin{cases} (e · d)\,\%\,\psi(n)=1 & (1)\\ \psi(n) = (p-1)(q-1) & (2)\\ n=p·q & (3) \end{cases}$

看看用这3个公式黑客能不能算出私匙d：

假设黑客已经监听到了：

$e=5,\quad c=23,\quad n=p·q=91$

根据公式(1)知：

$5·d\,\%\,\psi(n)=1$

要想求出 $d$ 就得知道 $\psi(n)$ ，而 $\psi(n) = (p-1)(q-1)$

因此要想知道 $\psi(n)$ ，就得知道 $p$ 和 $q$ ，而黑客已经知道了

$n=p·q=91$

所以只需要对 $n$ 进行质因式分解，可以得到

$p=7,\quad q=13$

从上面的分析中可以看出，破解私匙的关键的一步是对 $n$ 进行质因式分解，虽然上面举的例子中的因式分解很简单，分分钟就能被破解，但是在实际使用中的 $n$ 是一个很大的数——1024位的二进制数字，换算成十进制约为308位

目前还没有公式可以对这么大的一个数进行质因数分解，想硬解就需要用穷举法一个个的试出p、q

那么，用普通计算机进行穷举需要花费多久的时间呢？答案是整整一年

参考资料：

(1) 超级数学建模《区区6位密码，凭什么守护我的百万家产？》

【《数学之美》笔记（四）】加密算法

1. 对称性加密与非对称性加密

2. RSA加密算法

2.1. 加密解密原理

2.2. 安全性分析

推荐阅读更多精彩内容