从凯撒密码到公钥加密的兴起，数学中同余运算是如何发挥作用的？
本文作者 [遇见数学] 核心成员: 蘑菇长颈鹿
同余运算(请见下面链接)在经典的密码问题中也发挥着至关重要的作用，在下面文章中我们将会把密码学与同余运算两者结合起来，探索同余运算是怎样运用到密码学中的。
密码学的起源
想象一下，Alice 和 Bob 两个人要远距离的分享了一个重要的秘密。然而，一个叫 Eve 的窃听者也想要这些信息，并且有能力截获他们的消息。所以，Alice 决定用某种密码写的信来交流。首先，Alice 用一个只有她和 Bob 知道密码的锁将消息锁在一个盒子里。这就是所谓的“加密”（encryption）。
爱丽丝(Alice)和鲍伯(Bob)在密码学中是最基本的两位代用人物，其次是伊夫(Eve)。头一个英文字母越接近 z，该角色的使用率相对上也越低。
然后，将被锁的信息发送给鲍勃。当 Bob 收到盒子时，他使用他们预先共享的钥匙打开盒子。这叫做“解密”（decryption）。
当我们放弃物理锁而使用“密码”时，密码学就要登场了。我们可以将密码看作虚拟锁。密码使 Alice 和 Bob 能够对他们的信息进行整理和解码，这样，如果 Eve 截获它们，它们就会显得毫无意义。
一般来说，如果我们可以将整个加密系统看作一个模型
凯撒密码
第一个众所周知的密码是一个移位密码，大约在公元前 58 年被凯撒大帝使用。它现在被称为凯撒密码。凯撒把他的军事命令中的每一个字母都做了调整，以便在敌人拦截的时候让它们显得毫无意义。
想象 Alice 和 Bob 决定使用凯撒密码进行通信。首先，他们需要在转换使用之前达成一致，比如转换为 3。因此，为了加密她的消息，Alice 需要对原始消息中的每个字母进行移位 3 次。 A 变成了 D，B 变成了 E，C 变成了 F，等等。
▲ 当偏移量是 3 的时候，所有的字母 A 将被替换成 D，B 变成 E，以此类推。(图自维基)
这条加密的消息然后公开发送给 Bob。然后 Bob 简单地从每个字母中减去 3 的移位，以读取原始消息。这个基本密码在凯撒之后的几百年里被军事领导人使用。
这种移位密码的工作方式是使用模运算对消息进行加密和解密。移位密码的密钥 K 是从 0 到 25 的整数。
对于消息中的每一个字母:
例如：我们同意我们的朋友使用密钥 K=19 的移位密码作为我们的消息。我们加密信息“SECRET”，因此，在应用密钥 K=19 的移位密码后，我们的消息文本“SECRET”为我们提供了密码文本“KWUJWL”。 我们把信息“KWUJWL”发送给我们的朋友。
对于密文中的每一个字母:
我们的朋友现在使用我们商定的密钥 K=19 来解码消息。如下: 因此，在用密钥 K=19 解密了移位密码之后，我们的朋友将密码文本“KWUJWL”解密为消息文本“SECRET”。
然而，一把锁的坚固程度取决于它最薄弱的地方。开锁器可能会寻找机械缺陷。如果做不到这一点，则提取信息以缩小正确的组合范围。锁的破解和密码破解的过程非常相似。
800 年后，一位名叫阿尔·肯迪(Al-Kindi)的阿拉伯数学家出版了《凯撒密码的弱点》。他利用语言中一个重要属性的线索破解了凯撒密码。如果你从任何一本书中扫描文本并计算每个字母的频率，你会发现一个相当一致的模式。例如，下面条形图所表示就是用典型的英语书写的文字样本中各字母出现频率。
▲ 图自维基
这条线索是密码破译者最有价值的工具之一。为了破解这个密码，他们计算出加密文本中每个字母的频率，并检查频率最高的字母移动了多远。例如，如果 是加密消息中最受欢迎的字母，而不是 ，那么移位可能是 。
因此，只需要逆转其偏移量就可以进行解密。这样即便是在仅知已加密文字的情况下就可以通过频率分析，或者穷举法就可以攻破信息，这对凯撒密码的安全性是一个打击。
公共密钥
第二次世界大战后，随着欧洲大部分地区的废墟，苏联和美国之间的紧张关系加剧，互联网在全球范围内的蓬勃发展，一个新的问题出现了。当时，加密需要双方首先共享一个称为密钥的秘密随机数。那么，两个素未谋面的人怎么可能在共享密钥的问题上达成一致，而又不让一直在偷听的 Eve 获得一份副本呢?
1976 年，惠特菲尔德·迪菲（Whitfield Diffie）和马丁·赫尔曼（Martin Hellman）发明了一种神奇的方法。
首先，让我们来看看如何使用颜色来完成这个方法。Alice 和 Bob 怎么能在一个秘密的颜色上达成一致而不被 Eve 发现呢?
这个方法基于两个事实:
我们很容易把两种颜色混合在一起，并形成第三种颜色;
对于混合后的颜色，要想找到完全相同的原始颜色是很困难的。
即密码要满足朝一个方向容易，朝反方向难，也就是所谓的单向函数(One-way function)。
现在，我们的方案如下:
首先，他们公开同意一种起始颜色，比如黄色。作为偷听者 Eve 也能成功获取此消息，如下图所示。
接下来，Alice 和 Bob 都随机选择了私有颜色(红蓝两色)，将它们混合到公共黄色中，以掩盖它们的私有颜色并发送给对方，这个过程如下面图形所示。
而后，Alice 和 Bob 将他们的私有颜色添加到另一个人的混合色中，得到一个共享的秘密颜色，下右图为混合后颜色。
注意到偷听者伊芙无论如何都无法确定这个确切的颜色，因为她需要一个他们的私人颜色来做这件事。
这就是关键所在。现在，为了在数学上实现，我们就需要一个在单方向上容易计算，而在反方向上计算很困难的过程，这就是下面一节的内容。