公钥加密的真实运作方式：只用到简单数学
支撑着互联网的安全系统使用着一种好奇的性质：把加密术的一部分公之于众，加密的信息反而更加安全。
John Pavlus 著
左 芬 译
【译注：原文2024年11月15日发表于QuantaMagazine。】
数千年来，要想发送一条秘密消息，基本上只有一种方法。用一种只有你和你的目标听众知道的特定规则打乱消息。这一规则就好像一把开锁的钥匙。只要你有了钥匙，就可以恢复消息；否则，你就只能撬锁了。有些锁非常之牢固，哪怕用无穷时间和精力也难以撬开。但即便是这些方案，也会遭受困扰所有这类加密系统的同一阿喀琉斯之踵：如何把钥匙交到适当的人手中，同时避免其他人拿到？
公钥加密就是针对这一弱点的一种解决方法，但有点反直觉。它并不依赖于对钥匙的保密，反而将其广泛地公开。其窍门在于，你还会使用第二把不跟任何人共享的钥匙，哪怕是与你通信的那个人。只有同时使用这两把钥匙——一把公钥，一把私钥——你才能在打乱消息后将它恢复。
要理解它的运作方式，最好不把这些“钥匙”当成跟一把锁配套的物体，而当成某种隐形墨水的两种互补成分。第一种成分让消息隐形，而第二种让它们显形。如果密探Boris想给他的副手Natasha发送一条秘密消息，他把消息写出来，然后使用第一种成分让它在纸上隐形。（对他来说这很容易：Natasha已经公布了隐形墨水的简易知名配方。）当Natasha收到邮件中的纸张后，她使用第二种成分让Boris的消息显形。
在这一方案中，任何人都可以让消息隐形，但只有Natasha能让它们再次显形。而由于她从不与任何人——甚至包括Boris——共享第二种成分的配方，她可以确信消息没有在途中被破译。当Boris想要接收秘密消息时，他只需要采取相同的步骤：他先公开让消息隐形的简易配方（使得Natasha或者任何其他人都可以使用），并保留另一种显形成分仅供自己使用。
在公钥加密中，“公钥”和“私钥”正如这种特殊隐形墨水的第一种和第二种成分那样运作：一种用来加密消息，另一种用来解密。不过公钥加密用的不再是化学制品，而是被称为陷门函数的数学难题。这些函数很容易正向计算，但求逆则极其困难。不过它们包含“陷门”，也就是一些信息片段，一旦被知晓，就会使这些函数的正逆向计算都变得容易之极。
一个常见的陷门函数就是两个大的素数相乘，很容易的一个运算。但逆运算——也就是说，从乘积出发找出每个素数因子——在计算上是不现实的。要生成公钥，先选定两个大素数。它们就是你的陷门。将两个数相乘，再执行一些附加数学运算，就得到了公钥。这一公钥现在可以用来加密消息。要解密它们，你需要相应的私钥，其中就包括两个素数因子——必需的陷门。有了这些数，很容易对消息进行解密。只要保密好这两个素数因子，消息就始终是秘密的。
公钥的运作方式 现代互联网安全往往设计两把密钥：帮助任何人加密一条消息的公钥，以及用于解密它的私钥。第一把钥匙像是保险箱，而第二把钥匙用来打开它。 |
步骤一：公布你的指令 Natasha介绍了构建一个独一无二的保险箱的方法。她的指令基于一个很大的数——两个大的素数的乘积。
步骤二：构建保险箱 Boris读了Natasha的指令，构建出保险箱。
步骤三：发送消息 Boris把他的消息放进保险箱，发给Natasha。
步骤四：打开保险箱 要打开保险箱，你需要一把密钥——它只能用原始的两个素数造出来。这些数单凭Natasha的指令是确定不了的。只有Natasha知晓它们，并用它们来制造密钥。
|
公钥加密的基础最先由任职于英国政府通讯总部的英国数学家们于1970至1974年间发现。正是这一通讯总部在第二次世界大战期间破译了纳粹的Enigma密码。他们的工作（一直保密至1997年）被共享给了美国国家安全局，但由于受限且昂贵的计算能力，两国政府都没有实行这一体系。1976年，受密码员Ralph Merkle启发，美国研究者Whitfield Diffie与Martin Hellman开发了第一种广为人知的公钥加密方案。就在一年后，以发明者Ron Rivest, Adi Shamir及Leonard Adleman命名的RSA算法建立了一套公钥加密的实用方法。它在今天仍被广泛使用，是现代互联网的基础模块，使得从购物到网络邮件等诸多事物成为可能。
这一双钥系统还可以用于“数字签名”——确保消息由私钥持有者生成的一种数学证明。其可行的原因在于，私钥也能用于加密消息，而不仅是解密。当然，这对于保密消息来说是无用的：如果你用私钥去打乱消息，任何人只要用相应的公钥就可以恢复它。但它确实证明是你，并且只能是你，生成了这一消息，因为作为私钥的持有者，只有你能加密该消息。比特币之类的数字货币完全依赖这一思想而存在。
既然两把加密钥匙相比于一把要有效得多，为何人们花了几千年才发现呢？据加州大学圣地亚哥分校的计算机科学家与密码理论家Russell Impagliazzo称，这是因为在计算机发明之前，陷门函数的概念并不是很有用。
“这是个技术问题，”他说，“19世纪的人把加密看作是发生在持有军事情报的各个特工之间的——并且他们身处枪火不断的战场。因此如果你的第一步是‘选出两个100位的素数相乘’，在你这么做之前战争就要结束了。”而如果你把问题约化到人脑能快速处理的程度，那它就不会那么安全了。
不过尽管计算机让公钥加密成为可能，它们也在其盔甲上产生了裂隙。1994年，数学家Peter Shor利用量子计算机开发出了一种算法，可以对支撑大多数当前公钥加密系统的陷门函数，包括素数分解在内，进行求逆。这一算法，一旦执行，会成为一种全能“显形墨水”，可以让任何隐形消息重现出来。互联网安全将宣告终结。
幸运的是，量子计算机本身“仍处在ENIAC阶段”，Impagliazzo说，意指美国陆军在1945年建造的房间大小的机器。等到量子计算机成熟到能对公钥加密产生真实威胁，可以把最初的陷门函数替换成“量子安全版”的所谓格问题。当然，这一新型计算“墨水”在将来也可能变得易于攻击。但这正是公钥加密的伟大之处：只要我们能发现新的可用函数，我们就可以不断地重造轮子。而在这里，就是重铸钥匙。
原文链接：
https://www.quantamagazine.org/how-public-key-cryptography-really-works-20241115/
转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。
链接地址：https://wap.sciencenet.cn/blog-863936-1461294.html?mobile=1
收藏
