# 第 17 章 谈谈密码学的数学原理

加密的过程可以看做是一个函数的运算，解密的过程是反函数运算。明码是自变量，密码是函数值。好的加密函数不应该通过几个自变量和函数值就能推导出函数。

一般来讲，当密码之间分布均匀并且统计独立时，提供的信息最少。均匀使得敌人无从统计，而统计独立能够保证敌人即使看到一段密码和明码后，不能破译另一段密码。

## 设计一个密码系统

1. 找两个很大的素数（质数）P和Q，越大越好，然后计算他们的乘积：![N=PQ
   ](https://www.zhihu.com/equation?tex=N%3DPQ%0A)，![M=(P-1)(Q-1)
   ](https://www.zhihu.com/equation?tex=M%3D\(P-1\)\(Q-1\)%0A)。
2. 找一个和![M
   ](https://www.zhihu.com/equation?tex=M%0A)互素的整数![E
   ](https://www.zhihu.com/equation?tex=E%0A)，找一个整数![D
   ](https://www.zhihu.com/equation?tex=D%0A)，使得![E\times D\ \text{mod }M=1
   ](https://www.zhihu.com/equation?tex=E%5Ctimes%20D%5C%20%5Ctext%7Bmod%20%7DM%3D1%0A)（![ \text{mod }
   ](https://www.zhihu.com/equation?tex=%20%5Ctext%7Bmod%20%7D%0A)为两个表达式作除法运算后的余数）。![E
   ](https://www.zhihu.com/equation?tex=E%0A)是公钥，谁都可以用来加密，![D
   ](https://www.zhihu.com/equation?tex=D%0A)是私钥用于解密，一定要自己保存好。乘积![N
   ](https://www.zhihu.com/equation?tex=N%0A)是公开的。
3. 用公式对![X
   ](https://www.zhihu.com/equation?tex=X%0A)加密，得到密码![X^E\ \text{mod }N=Y
   ](https://www.zhihu.com/equation?tex=X%5EE%5C%20%5Ctext%7Bmod%20%7DN%3DY%0A)。根据费尔马小定理，得到：![Y^D\ \text{mod }N=X
   ](https://www.zhihu.com/equation?tex=Y%5ED%5C%20%5Ctext%7Bmod%20%7DN%3DX%0A)，所以要解密，必须知道![D
   ](https://www.zhihu.com/equation?tex=D%0A)。

公开密钥的好处有：

* 简单，只涉及一些乘法。
* 可靠，公开密钥方法保证产生的密文是统计独立而分布均匀的。更重要的是![N
  ](https://www.zhihu.com/equation?tex=N%0A)、![E
  ](https://www.zhihu.com/equation?tex=E%0A)可以公开给任何人加密使用，但只有掌握密钥!\[D

  ]\(<https://www.zhihu.com/equation?tex=D%0A%0A%0A)的人才能解密。>
* 灵活，可以产生很多![E
  ](https://www.zhihu.com/equation?tex=E%0A)和![D
  ](https://www.zhihu.com/equation?tex=D%0A)的组合给不同的加密者。

该种方法破解难度较大，破解的最好办法是对大数!\[N

]\(<https://www.zhihu.com/equation?tex=N%0A%0A%0A)进行因式分解，即通过![N>

]\(<https://www.zhihu.com/equation?tex=N%0A%0A%0A)反过来找![P>
]\(<https://www.zhihu.com/equation?tex=P%0A)、![Q>
]\(<https://www.zhihu.com/equation?tex=Q%0A)，得到![M>

]\(<https://www.zhihu.com/equation?tex=M%0A%0A%0A)、![N>
]\(<https://www.zhihu.com/equation?tex=N%0A)。而找到![P>

]\(<https://www.zhihu.com/equation?tex=P%0A%0A)、![Q>
]\(<https://www.zhihu.com/equation?tex=Q%0A)目前只有用计算机把所有的数字试一遍的笨办法，耗时很长。这也是为什么![P>

]\(<https://www.zhihu.com/equation?tex=P%0A%0A)、![Q>
]\(<https://www.zhihu.com/equation?tex=Q%0A)都需要非常大的原因。>

## 小结

密文之间需要相互无关，同时密文还是看似完全随机的序列。信息论诞生后，公开密钥是目前最常用的加密方法。