揭开密码的神秘面纱——同余运算 Part V
[遇见数学创作小组] 核心成员: 蘑菇长颈鹿
一枚数学系的大学生，喜欢数学文化的小视频，写作/翻译中如有问题，请多指正~
在上一篇的文章中，我们提到我们想要建立一个像混合颜色一样，可以轻松合成，但不可逆转的公共密钥。但是怎样才能将这个思想应用到我们信息的传输当中呢？
离散对数问题
这时我们希望得到一个在一个方向上容易，在另一个方向上困难的数值过程。而我们之前所说的模运算恰好满足这一性质。
为了解决这个问题，我们使用质数模，比如 ，然后我们需要找到一个 的原根（即取不同的指数时，解在 到 之间均匀分布的根）本例中我们可以取 ，并将其称为生成器。事实上，在应用此方法加密时， 也经常会作为我们的生成器。
下面我们将选取的质数模和生成器带入到模运算中，当我们正向计算模运算时，比如我们在计算 时，我们可以很容易得到结果，但如果只给定 ，要想求出 的指数，我们将不得不经过很多次试错来找到匹配的指数。
因此，模函数即为我们想要的容易执行但很难逆转的单向函数。我们称这种方法为离散对数问题。
单向函数的强度取决于反转所需的时间。那么，怎样才能加强单项函数呢?对于 这样的小的数可能找到密文还相对容易找出，但是如果我们使用一个质数，它有几百位那么长，这就不太现实了。即使是世界上最强的计算能力，可能也要花上几千年才能完成所有的可能性。
迪菲‑赫尔曼密钥交换
迪菲‑赫尔曼密钥交换是一种可以在通信双方互相公开交换密钥的前提下，防止窃取者获得真正密文的方法。下面我们就通过一个具体实例来感受一下密钥交换的过程。Alice 和 Bob 想要互相交换信息，而 Eve 想要窃取这份信息。
首先，Alice 和 Bob 公开同意了质数模数和生成器，在这里是 。然后 Alice 选择一个私有随机数，比如 ，计算出 ，然后将这个结果公开发送给 Bob。
然后 Bob 选择他的私有随机数，比如 13，并计算出 ，然后将这个结果公开发送给 Alice。
现在是密钥交换的核心：Alice 获取 Bob 的公共结果 12，并将其作为底数，取她自己的私有数字 15 为幂，即为 以获得共享密钥。
同样的，Bob 将 Alice 的公共结果作为底数，取他的私有数字 13 为幂，即 ，从而得到相同的共享密钥。
在这里，他们做了相同的计算，尽管一开始看起来不像。以 Alice 为例，她从 Bob 那里得到的 12 是 。所以她的计算和 是一样的。
而 Bob，他从 Alice 那里得到的 6 是 。所以他的计算和 是一样的。
注意，他们用不同的顺序做了相同的计算。当指数翻转时，结果不变。所以他们都计算了 。如果没有这些私有数字中的一个， 或 ，Eve 将无法找到解决方案。
因此，当 Eve 被困在离散对数问题上时，如果有足够大的数字，我们可以说她实际上不可能在合理的时间内破解加密。这解决了密钥交换问题。它可以与伪随机生成器结合使用，来加密从未谋面的人之间的消息。
RSA 密钥
直到 20 世纪 70 年代，密码学都是基于对称密钥的。也就是说，发送方使用特定的密钥加密其消息，接收方使用相同的密钥解密。正如我们前面所说的，加密是从使用特定密钥的消息到密文消息的映射。要解密密文，可以使用相同的密钥来反转映射。因此，为了让 Alice 和 Bob 安全通信，它们必须首先共享相同的密钥。
如果 Alice 和 Bob 在使用迪菲‑赫尔曼密钥交换时需要实际见面或通信才能建立共享密钥，并且 Alice 需要与多人通信，比如她是一家银行，需要与很多人交换不同的密钥。她必须管理所有密钥并发送数千条消息来交换它们。那么是否存在一个更简单的方法来方便 Alice 的操作呢?
1970 年，英国政府通讯总部的工程师和数学家詹姆斯·埃利斯(James Ellis)致力于一种非秘密加密的想法。它基于一个非常简单概念：加密和解密是反向操作。
比如，Alice 可以买把锁，自己保管钥匙，然后把打开的锁送给 Bob。然后 Bob 锁上消息并将其发送回 Alice。这样就可以不交换钥匙而获取信息了。
这意味着她可以广泛发布这把锁，让世界上的任何人都可以用它来给她发信息。现在她只需要记住一把钥匙。
这个想法是把将密钥分为两部分，加密密钥和解密密钥。加密密钥公开发布(公钥)，每个人都可以使用它来加密明文，但是公钥不能被用来解密。只有拥有解密密钥(私钥)的人才能够成功解密。
然而，这需要一个数学解决方案来实现。
另一位英国数学家、密码学家克利福德·科克斯（Clifford Cocks）找到了答案。科克斯构造了一种特殊的单向函数，称为陷门函数(Trapdoor function)。这个函数很容易在一个方向上计算，但是很难逆转，除非你有特殊的信息。
想象 Bob 有一个消息，这是可以转换成一个数字 的。随后他增加一个公开的指数 ， 然后他把结果对随机数 进行模运算，经过计算 。得到数字 。
这个计算很容易，但是如果只给出 、 和 ，就很难确定用的是哪个 。这是我们构造了应用到 上的单向函数，很容易执行，但是很难逆转。这是我们所需要的数学锁。
那么，"钥匙"怎样用数学打造出来呢?
2000 多年前，欧几里得证明了每个数都有一个质因数分解，我们可以把它看作一个密钥。质因数分解是一个非常困难的问题。
当计算机进行加法运算时，即使使用相当大的数字，计算时间也会保持在 1 秒以内。然而在进行质因数分解时，例如有人告诉你要找出 589 的质因数分解，无论怎样，都需要反复试验，直到找到一个能被 589 整除的数字。随着数字的增长，执行计算所需的时间迅速增加，因为涉及的步骤更多，计算机需要几分钟，几小时，最终需要几百年，甚至几千年才能分解出巨大的数字。
因此，因数分解是科克斯用来构建陷门函数的解决方案的方法。
第一步，假设 Alice 随机生成一个质数，长度超过 位，称为 。然后，第二个随机质数大小大致相同，称为 。然后她将这两个质数相乘得到一个合数 N，它的长度超过 位。
然后，她用因式分解 ，然后把 、 隐藏起来。现在，如果她把 给其他人，那么他们必须让电脑运行数年才能找到答案。
第二步，我们需要找到一个依赖于 因式分解的函数 φ。这样，如果你知道 的因式分解，那么找到 φ 很简单。
第三步，如何把函数和模幂联系起来。科克斯想到了欧拉定理，即 φ。这意味着你可以挑选任意两个互质数字 和 ，假设 ， 。现在，当你计算 ，即为 ， 或 等等，你总会得到 1。
现在，我们需要用两个简单的规则来修改这个方程。
对于任意的 ，。同样的，根据模的幂运算，φ. 对于任意的 ，。同样的，我们有 φ。这个可以简化成 φ。
现在我们有了一个方程 来求出 。因此，当 的因式分解是已知的，就可以简单的计算除 ，即为 φ。而这就意味着 应该是 Alice 的私钥。
我们做一个简单的例子。假设 Bob 有一个消息，他转换成一个数字 。然后，Alice 生成她的公钥和私钥如下:首先，她生成两个大小相似的随机素数 、，并将它们相乘得到 。然后因为她知道 的因式分解，所以很容易计算出 φ，结果是 。
接下来，她选择一个小的公开指数 ，且必须是一个奇数并与 没有公因数，在这种情况下，她选择 等于 。最后，她找到了她的私有指数 的值，
现在，她隐藏了除 和 之外的所有值，因为 和 构成了她的公钥。她把这个寄给 Bob。
Bob 通过计算 ，得到他的加密消息 ，并将 发送回 Alice。
最后，Alice 用她的私钥 解密了他的信息。，等于鲍勃的原始消息 m。
注意此时 Eve 只得到了 ， ， 和 。除非她知道 的质因数分解，计算出 φ，找到指数 ，才能够得到加密信息。但是，如果 是足够大的，即便最强大的计算机网络这将需要数百年。
柯克斯最早发现了这个算法，但该算法被列入机密，直到1997年才得到公开。而在 1977 年，Ron Rivest， Adi Shamir 和 Len Adleman 也发现了这个方法，并公开发表，这就是为什么它现在被称为 RSA 加密。
RSA 是世界上使用最广泛的公钥算法，也是历史上拷贝最多的软件。地球上的每个互联网用户都在使用 RSA，或者它的某种变体。它的强度取决于质因数分解，这是关于质数分布的深层问题的结果。而这个问题几千年来一直没有得到解决。
参考资料：
1.khanacademy.org/computing/computer-science/cryptography/
2.密码学基础讲义http://59.108.48.5/course/Cryptography