原文：https://www.quantamagazine.org/how-public-key-cryptography-really-works-20241115/
作者：John Pavlus
译者：Kurt Pan
互联网底层的安全系统利用了一个奇怪的事实：你可以通过对加密的一部分进行广播，以使你的信息更加安全。
几千年来，如果你想发送一条秘密信息，基本上只有一种方法可以做到。使用只有你和你的目标受众知道的特殊规则来打乱消息。这条规则就像一把锁的钥匙。如果你有钥匙，你就可以解读信息；否则，你就需要撬开锁。有些锁效果非常好，即使有无限的时间和资源，也永远无法撬开。但即使是这些方案也面临着困扰所有此类加密系统的同样的致命弱点：如何将密钥交到正确的人手中，同时防止它落入错误的人手中？
https://link.springer.com/chapter/10.1007/978-3-031-33386-6_1
一种反直觉的解决方法，被称为公钥加密，不依赖于保持密钥秘密，而是反而依赖于使其广泛可获得。技巧在于还要使用第二把你永远不会与任何人（甚至包括你要与之通信的人）分享的密钥。只有通过使用两个密钥的组合（一个公钥，一个私钥），才能对同时对消息进行加扰和解密。
https://csrc.nist.gov/glossary/term/public_key_cryptography
为理解这是如何工作的，将“密钥”想象成隐形墨水中的两种互补的成分而不是插进锁的对象会更有帮助。第一个成分使消息消失，第二个使消息重现。如果一个名叫鲍里斯的间谍想要向他的搭档娜塔莎发送一条秘密消息，他会写一条消息，然后使用第一个成分使其在纸上不可见。 （这对他来说很容易做到：娜塔莎发布了一个简单且众所周知的墨迹消失公式。）当娜塔莎收到邮件中的纸张时，她使用第二种成分，使鲍里斯的信息重新出现。
在这个方案中，任何人都可以使消息不可见，但只有娜塔莎可以使其再次可见。而且因为她从未与任何人（甚至鲍里斯）分享第二种成分的配方，所以她可以确定该信息在此过程中没有被解密。当鲍里斯想要接收秘密消息时，他只需采用相同的过程：他发布一个使消息消失的简单方法（娜塔莎或其他任何人都可以使用），同时为自己保留另一个使消息重新出现的方法。
在公钥密码学中，“公钥”和“私钥”的工作原理就像这种特殊的隐形墨水中的第一个和第二个成分：一个加密消息，另一个解密消息。但公钥密码学不使用化学物质，而是使用称为陷门函数的数学难题。这些函数很容易在一个方向上计算，但很难逆向计算。但它们也包含“陷门”信息，如果知道这些信息，则可以使函数在两个方向上都很容易计算。
https://www.quantamagazine.org/graduate-student-solves-quantum-verification-problem-20181008/
一个常见的陷门函数涉及将两个大素数相乘，这是一种易于执行的操作。但反转它——即从乘积开始找到每个素因数——在计算上是不切实际的。要创建公钥，从两个大素数开始。这些是你的陷门。将两个数字相乘，然后执行一些额外的数学运算。这个公钥现在可以加密消息了。要解密消息，你需要相应的私钥，其中包含素因子 - 必要的陷门。有了这些数字，就可以轻松解密消息。将这两个素因子保密，消息就会得到保密。
https://dl.acm.org/doi/10.1145/359340.359342
公钥密码学的基础是由在英国政府通信总部工作的英国数学家在 1970 年至 1974 年间首次发现的，该政府机构在二战期间破解了纳粹恩尼格玛密码。他们的工作（直到 1997 年一直属于机密）与美国国家安全局共享，但由于有限且昂贵的计算能力，两国政府都没有实现该系统。 1976 年，美国研究者 Whitfield Diffie 和 Martin Hellman 受到密码学家 Ralph Merkle 的影响，发现了第一个公开的公钥密码方案。仅仅一年后，以其发明者 Ron Rivest、Adi Shamir 和 Leonard Adleman 命名的 RSA 算法建立了一种使用公钥加密的实用方法。它至今仍在广泛使用，是现代互联网的基本组成部分，支撑着从购物到基于网络的电子邮件的一切。
https://ieeexplore.ieee.org/document/1055638
这种双密钥系统还使“数字签名”成为了可能——对消息是由私钥持有者生成的数学证明。这是可行的，因为私钥也可以用于加密消息，而不仅仅是解密。当然这对于对消息保密是没有用的：如果你使用私钥来扰乱消息，那么任何人都可以使用相应的公钥来解读之。但它确实证明了你，而且只有你创建了该消息，因为作为私钥的持有者，只有你可以加密该消息。如果没有这个想法，像比特币这样的密码货币就不可能存在。
如果两个而不是一个密码学密钥如此有效，为什么要花上上千年的时间才得以发现呢？加州大学圣地亚哥分校的计算机科学家和密码学理论家Russell Impagliazzo表示，因为在计算机发明之前，陷门函数的概念还不够有用。
https://www.quantamagazine.org/the-researcher-who-explores-computation-by-conjuring-new-worlds-20240327/
“这是一个技术问题，”他说。 “19 世纪的人认为加密是在战场上拥有军事情报的特工个体之间进行的——字面意思上的有枪声的战场。因此，如果你的第一步是‘选择两个 100 位的素数相乘’，那么在你这样做之前，战斗就已经结束了。”如果你将问题简化为人类可以快速完成的事情，那么它就不会非常安全。
但是，尽管计算机使公钥密码学成为了可能，但也给它的盔甲带来了裂痕。 1994 年，数学家 Peter Shor 发现了一种让量子计算机高效逆转大多数当前公钥密码系统（包括素因子分解）背后的陷门函数的方法。该算法如果实现，就会像一种通用的“再现墨水”一样，能够使任何不可见的消息重新出现。互联网安全，拜拜。
https://www.quantamagazine.org/tag/quantum-computing/
幸运的是，量子计算机本身“仍处于 ENIAC 阶段”，Impagliazzo 说，他指的是 1945 年为美国陆军制造的整个房间大小的机器。等到量子计算机变得足够复杂，足以对公钥密码术构成真正的威胁的时候，其原始的陷门函数就可以被称为格问题的“量子安全”版本所取代。当然，这种新的计算“墨水”将来也可能受到攻击。但这就是公钥密码学的伟大之处：只要我们能找到新的函数来使用，我们就可以去继续重新发明轮子。或者在这种情况下，密钥。
https://www.quantamagazine.org/cryptographys-future-will-be-quantum-safe-heres-how-it-will-work-20221109/
