从凯撒密码到公钥加密的兴起，数学中同余运算是如何发挥作用的？ _同余

同余运算(请见下面链接)在经典的密码问题中也发挥着至关重要的作用，在下面文章中我们将会把密码学与同余运算两者结合起来，探索同余运算是怎样运用到密码学中的。
你所想知道密码背后的数学——同余运算, 你所想知道密码背后的数学——同余运算 Part II
密码学的起源想象一下，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)的阿拉伯数学家出版了《凯撒密码的弱点》。他利用语言中一个重要属性的线索破解了凯撒密码。如果你从任何一本书中扫描文本并计算每个字母的频率，你会发现一个相当一致的模式。例如，下面条形图所表示就是用典型的英语书写的文字样本中各字母出现频率。

文章插图

▲ 图自维基
这条线索是密码破译者最有价值的工具之一。为了破解这个密码，他们计算出加密文本中每个字母的频率，并检查频率最高的字母移动了多远。例如，如果是加密消息中最受欢迎的字母，而不是，那么移位可能是。