在我上一篇文章中，我描述了数学家们对素数关键性质的不懈探索。这项努力似乎完全属于纯数学的范畴；但令人惊讶的是，素数的重要性远远超出了象牙塔数学家们的深奥执着。事实上，素数的应用正是过去几周新闻中最引人注目的事件的根源：爱德华·斯诺登的爆料，揭露了国家安全局（NSA）正在窃听美国公民和欧洲外交官的通信。
虽然欧洲人对他们的内部通信被NSA拦截一事表示抗议——讽刺的是——但防止任何人进行窃听的保护工具，在线上、专业文献以及公开的手册和教科书中都可以轻松获取。这些方法都依赖于对素数的巧妙运用。
这些技术的基础远非新近才出现。创造出即使窃听者动用全球所有可用计算能力也无法破解的代码的程序的基础，早在35多年前就已奠定。1976年，Diffie-Hellman密钥交换方法（以Whitfield Diffie和Martin Hellman命名；Ralph Merkle、James Ellis、Clifford Cocks和Malcolm Williamson的名字也常与此相关）得以发展；而紧随其后的1977年，RSA算法问世。这两种方法在过去三十五年中都得到了发展，但关于其扩展的信息对任何人来说也都 readily available。
这些技术是如何工作的？我将在此以一种简化的方式解释这两种方法。（有兴趣了解更多的人可以阅读本文中出现的链接中的一些文章。）
Alice给Bob发送一条秘密消息
Terence Tao，我在上一篇文章中提到过的素数研究领域的专家，用一个清晰简洁的类比描述了Diffie-Hellman密钥交换的想法。这个想法如下。Alice想给Bob发送一条秘密消息（密码学家更喜欢用“Alice发给Bob”而不是平淡的“A发给B”），并且她想阻止Eve（“窃听者”）阅读它。于是Alice把消息放进一个盒子里，锁上它，自己保留钥匙，然后把包裹寄给Bob。（如果Alice单独把钥匙寄给Bob，Eve就有可能同时截获包裹和钥匙。）
Bob没有Alice锁的钥匙。所以他所做的就是给自己锁上盒子。然后他把包裹寄回给Alice，锁了两次：既有她自己的锁，也有他的锁。Alice收到包裹，用她的钥匙解开她自己的锁，然后把盒子寄回给Bob，盒子仍然是安全的，因为它带着Bob的锁。现在Bob用他的钥匙，打开盒子，拿到消息！这里的每个人都使用了他/她自己的锁和钥匙——但消息却安全地从Alice传给了Bob。
数字版本
Diffie-Hellman密钥交换在数字上实现了这个想法。要发送给Bob的秘密消息是一个秘密数字，称之为n。Alice的“钥匙”是一个指数a，她自己选择，然后用来将n提高到该次幂。因此，Alice发给Bob的“带消息的锁盒”是na。Bob有他自己的“钥匙”，这是一个他自己选择的数字b，他将其用作指数。他不知道n或a，但他有从Alice那里得到的na，于是他将这个数字提高到b次幂。他因此寄给Alice“带两把锁的盒子”：nab。Alice使用她自己的钥匙解开她自己的锁，意味着她取nab的a次方根，根据指数的简单数学原理，我们知道这给了她nb，然后她将其发回给Bob。Bob使用他的“钥匙”，即他的指数b，取nb的b次方根，从而得到Alice想传达给他的秘密数字n。
用素数创建更强的代码
如我刚才所述，有可能从Alice发送一个秘密数字给Bob，并且如果数字足够大，那么Eve有可能无法推断出来。然而，在实际应用中，Diffie-Hellman密钥交换的现代实现使用更复杂的技术来增加破解代码的难度。而且，秘密数字并不是从Alice发送给Bob，而是由他们两人通过公式nab（当然，这也等于nba）共同推导出来的。
Alice和Bob选择一个*素数*，他们假设Eve或世界上任何人都可能知道这个数字。假设这个数字是11。然后他们将所有计算都基于模11的数学*乘法群*（就像一个时钟走到12然后从1开始，这个群在达到11后就开始重新计数）。他们还选择一个底数，假设它是数字5。Alice然后选择她的秘密数字，例如3。Bob独立选择他的秘密数字，4。
Alice将共同商定的底数5提高到她的秘密数字3的幂，并进行*模11*计算。她得到：5³ = 125，但125模11是4（这是125除以11的余数，得到11余4——它就像时钟上的16点，但这个时钟是基于11而不是12）。她把答案，数字4，发送给Bob。记住Bob选择的秘密数字是4，所以他将从Alice那里得到的4提高到4次幂，模11，得到4⁴ = 256，但256模11是3（因为11×23 = 253，余数为3），这是他的最终答案。
Alice从Bob那里得到他们两人都同意的原始数字5，但现在是*以他的秘密数字4的幂*，模11，即625模11，是9（因为11×56 = 616，余数为9）。然后她将这个数字提高到她的秘密数字3的幂，再次进行模11计算。她得到与Bob相同的数字，3（因为9³ = 729，但模11是3，因为11×66 = 726，余数为3）。
通过这种基于素数的复杂模运算，但本质上是将一个数字提高到隐藏的幂，就像在上一节中所描述的那样，Alice和Bob建立了一个共同的秘密数字，在这个例子中是3。使用素数的模运算有助于使算法更难被窃听者破解*。实际上，素数很大，其他数字也很大。*当Alice和Bob使用100位长的秘密数字时，即使Alice和Bob共同推导出的公共数字被Eve获取，她也无法得知，即使她拥有世界上所有的可用计算能力*。
一旦Alice和Bob建立了共同的秘密数字，他们就可以将其用作*密钥*，以便相互加密消息，并应有很高的概率保证他们的通信不会被外部人士破译。
两把钥匙胜过一把
Diffie-Hellman算法发布一年后，当时在MIT工作的三位学者——Ron Rivest、Adi Shamir和Leonard Adelman——提出了一个*加密消息的绝妙想法*。他们试图避免Alice和Bob必须创建一个共同秘密数字的阶段，因为这个阶段会减慢他们之间的通信速度。
这三位MIT科学家发展了*密钥对*的概念：*公钥*和*私钥*，它们 jointly 用于通信秘密消息。公钥可以公开并为所有人所知。它的使用可以节省时间。私钥是Bob保密的，让他能够解密Alice（或任何知道他公钥的人）发来的加密消息。Bob公开他的公钥，这是一个大数字。这个数字是他将两个非常大的素数相乘得到的，这两个素数只有他知道（它们构成了他的私钥）。当Alice想给Bob发送一条秘密消息时，她使用他已知的公钥对其进行加密。但要解密消息，就需要知道Bob的私钥，即他用来创建公开密钥的两个素数。据推测，只有Bob能做到这一点。
使用RSA算法加密和解密消息是一个*复杂的数学过程*，它依赖于模运算和素数，与上面Diffie-Hellman系统描述中的使用方式类似。但它更复杂，因此可以使用私钥来解密。公钥本身对于解密RSA代码是无用的。
RSA的关键在于，公钥是由两个非常大的未知素数相乘组成的。事实证明，当素数很大时，*将一个数字分解成其素数因子*是非常困难的。（35 = 7×5，两个素数的乘积，很容易；但46,324,637 = 5,881 × 7,877 就更难了，而RSA加密中使用的素数要大得多。）正是这一点让Eve一无所知。她知道两个素数的*乘积*——但她无法轻易（而且希望永远无法）推断出这两个素数是什么！
RSA挑战
RSA系统发明后不久，Martin Gardner在《科学美国人》上发表了一则加密消息和一个大型RSA数字，*有129位数字*，它是两个素数的乘积。他向读者挑战破解代码，并提供100美元的奖金。花了17年才将该数字分解并解密消息。这是一个相对*短暂*的时间——许多人曾预计这将需要极其长的时间，而Rivest、Shamir和Adelman曾开玩笑说可能需要几“百万万亿年”。这项复杂的运算是通过分布式计算实现的，全球数千台计算机执行了通用计算的一部分——从而证明了这种方法的强大。
由学者创立的RSA Security随后发布了几个类似的数字，曾经有一段时间提供现金奖励给将它们分解成素数对，后来该公司撤销了该奖励。现在，一些挑战已经被数学家使用分布式计算解决了。这里有一个问题仍然悬而未决，一个210位数的RSA数字，从未被分解成两个素数。
RSA-210 = 245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549103626827191679864079776723243005600592035631246561218465817904100131859299619933817012149335034875870551067
显然，要分解的数字越大，破解成一对素数所需的时间就越长。超过一定长度（以十进制数字计），RSA代码就变得坚不可摧，因此任何基于它的消息在合理有限的时间内都无法被窃听者破译。RSA算法如今在互联网安全领域得到广泛应用。
NSA对加密的使用与滥用
在美国采纳*加密标准以及出口加密产品*时，NSA推动并成功实施了对RSA编码中使用的数字大小的法律限制，以便——凭借其超级计算机——它能够破译任何基于它的消息。据推测，欧洲不受这些限制的约束，它们的密码分析师应该能够轻松设计出无法破解的RSA代码（通过选择足够大的素数）用于常规的欧洲外交通信以及保护它们的计算机免受黑客攻击。
正如历史所表明的那样，超级计算机在破解高级代码方面不如广泛的全球分布式计算有效——但NSA本质上永远无法采用后者。另一方面，最新的披露似乎表明，*NSA搜索的目的之一实际上是识别使用加密通信的个人或实体*。如果是这样，那么欧洲各国政府就更有理由使用成熟的西方先进代码，以便将自己与恐怖实体区分开来，因为恐怖实体的代码必然看起来不同。这实际上将有助于NSA专注于识别真正的威胁，而不是浪费资源拦截布鲁塞尔的电子邮件，例如：“皮埃尔，今天午餐吃意大利菜还是中国菜？汉斯敬上。”
因此，我们发现自己处于现在这样一个境地，在加密和解密之间进行一场军备竞赛，一个纯数学在发明越来越好的代码方面发挥关键作用的世界。随着代码变得越来越复杂，破译者也变得越来越复杂，这个循环会不断延续。最令人惊奇的是，几十年前被认为绝对无法破解的代码，随着技术的进步确实会被攻破——但同样，设计新加密方法的各方，都在使用越来越复杂的数学来保持在追击者之前。
*使用模运算有两个主要原因。第一个是它充当一个多对一函数，意味着许多数字被一个素数相除会得到相同的余数——这使得Eve的生活复杂得多（她无法唯一地重构Alice和Bob的秘密数字）。以时钟为例，如果她听到一个会议定在1点钟，她无法确定是上午还是下午，也无法确定是哪一天。第二个原因是，在使用指数时，它限定了涉及的数字的大小，因为（按定义！）没有模运算，这些数字会“指数级”增长，并可能使计算变得难以处理。
图片来源：Maksim Kabakou / Shutterstock
