多亏这套密码系统，你才能放心的逛淘宝
以下文章来源于科学大院 ，作者马库斯·索托伊
中国科学院官方科普平台。前沿、权威、有趣、有料。
你有没有想过，在设置密码时，你输入“2333！@#￥”之后，到底网站是怎么生成密码的呢？
目前广泛使用的加密算法是怎样的产生的？它何以能保护世界范围内的在线金融活动？黑客又是怎样破译密码的？其实，这些都源于一个数学问题。
（图片来源：veer图库）
网络加密的诞生
人类自从能够交流以来，就需要媒介来传递秘密的消息。为了防止重要的信息落入不该知道的人手中，我们的祖先发明了相当多的有趣的加密方式。其中一种最早的加密消息的手段是2500多年前由斯巴达军队发明的。消息的发送方和接收方分别持有一个尺寸相同的圆柱体，称为斯巴达密码棒（scytale）。为了编码信息，发送方首先将一条狭窄的羊皮纸沿水平方向包在密码棒上，这样它就一圈圈地缠绕起来。然后顺着密码棒的垂直方向竖着写下信息。展开羊皮纸之后，上面的文字看起来毫无意义。只有将它重新缠绕在尺寸相同的密码棒上时，信息才会重现。
密码棒（图片来源：维基百科）
从那以后，一代代人不断创造出更多的复杂加密方法。其中最复杂的一种机器编码装置是德国人发明的恩尼格玛，在二战中被德军所利用。
恩尼格玛密码机（图片来源：维基百科）
在1977年之前，所有想要发送加密消息的人都面临着一个固有的问题。发送方和接收方必须提前见面来决定使用哪种密码。例如，斯巴达的将军们需要对密码棒的尺寸达成一致。即使是批量生产的恩尼格玛，柏林方面依然需要派出特工，给潜水艇舰长和坦克指挥官传送密码本，详细说明每天加密所需的机器设置。当然，如果敌人得到了密码本，那他们就玩儿完了。
想象一下互联网电子商务使用这种密码系统的后勤状况。在安全发送银行账户信息之前，我们必须接收来自购物网站的安全信件，信中会告诉我们如何加密信息。考虑到庞大的网络信息流量，很可能会有大量的安全信件被拦截。一种适用于快速的全球通信时代的密码系统亟需开发。就像布莱切利园的数学家在二战时破解了恩尼格玛一样，现在也是数学家发明了一代又一代的密码，并将其从谍战小说带到了地球村。这些数学密码为我们所知的公钥密码系统的诞生奠定了基础。
（图片来源：veer图库）
其实加密和解密就像锁门和开门一样。对于传统的门，锁门和开门用的是同一把钥匙。对于恩尼格玛，用于加密的设置也可以用于解密。这个设置——称为密钥——一定要保密。接收者和发送者距离越远，后勤运送加密和解密的密钥就越困难。设想一个间谍头目想要安全地接收不同的特工发过来的加密消息，但是不希望这些特工看到彼此的消息。因此，不同的密钥需要分别发给不同的特工。现在把特工换成几百万名饥渴的购物网站用户。这种规模的操作虽说并非完全不可能，但对后勤来说简直是噩梦。首先，访问网站的用户无法立即下单，因为它们必须等待安全密钥传过来。万维网（WorldWideWeb）真的变成了“万未网”（WorldWideWait）。
公钥密码系统则像有两把不同钥匙的门：钥匙A用来锁门，钥匙B用来开门。你会忽然发现，对于钥匙A来说，没有必要再添加什么安全措施。其他人拥有这把钥匙并不会危及安全。现在把这个门想象成公司网站的安全部门的入口。公司可以自由地向任何访问者分发密钥A，使得访问者可以给网站发送加密消息，比如信用卡号码。尽管每个人都可以用这个密钥来加密数据，也就是把秘密锁在门后，但没人可以读取其他人加密后的消息。实际上，一旦数据被加密，用户就无法读取，即使是自己发送的消息也不行。只有幕后运营这个网站的公司拥有密钥B，而只有拥有密钥B才能解密并读取那些信用卡号码。
公开密钥加密（图片来源：维基百科）
公钥密码系统的首次公开提出是在1976年的一篇影响深远的论文中，作者是斯坦福大学的两位数学家，惠特菲尔德·迪菲和马丁·赫尔曼。两人在密码世界中掀起了一种反主流文化的潮流，欲挑战政府机构对密码系统的垄断。尤其是迪菲，一个典型的反建制派，属于20世纪60年代的那种叛逆长发青年。两人都热衷于让密码学面向公众，并认为它不该仅仅是由政府关起门来讨论的话题，而是应该用于造福个人。但后来人们才知道，一些政府安全机构早就联合推进了这一密码系统，只是没有公开发表在期刊上，而是被列为最高机密，并被束之高阁。
左：惠特菲尔德·迪菲 右：马丁·爱德华·赫尔曼（图片来源：维基百科）
斯坦福大学的一篇题为《密码学新方向》的论文，预示着加密技术和电子安全技术的新时代的到来。配有两个密钥的公钥密码系统，理论上听起来十分强大，但是能否将理论用于实践并创造有效的密码呢？经过几年的尝试，一些密码学家开始怀疑这种加密技术的可行性。他们担心这种学术化的密码系统无法应对真实世界的间谍活动。
RSA：MIT三剑客
迪菲和赫尔曼的论文激发了众多人的灵感，其中就有麻省理工学院的罗纳德·L.李维斯特。和叛逆的迪菲和赫尔曼不同，李维斯特是个传统的人。他沉默寡言，讲话温和，行为举止也很慎重。当他读到《密码学新方向》这篇论文的时候，他的职业目标还是成为学术机构的一员。他的梦想是教授职位和定理，而不是密码和间谍。那时他还不知道，他所读的这篇论文将带他走上另一条路：创造出史上最强大、商业上也最为成功的密码系统之一。
罗纳德·李维斯特（图片来源：维基百科）
在斯坦福大学和巴黎工作了一阵子之后，李维斯特于1974年加入MIT的计算机科学系。和图灵一样，他对抽象理论和具体机器的相互作用十分感兴趣。在斯坦福大学他花了一阵子时间来制作智能机器人，但是他的思想却转向了计算机科学更加理论化的层面。
在图灵的时代，受到希尔伯特的第二和第十问题的启发，计算机所面对的主要问题是，理论上是否存在这样的一种程序，它能够解决特定类型的问题。正如图灵所展示的那样，没有程序可以决定某个数学事实能否被证明。到了20世纪70年代，另一个理论问题在计算机科学界掀起了一阵风潮。假设的确存在解决特定数学问题的程序，那么是否有可能分析该程序解决问题的速度？如果要实现该程序的话，那么这个问题显然很重要。这个问题需要很强的理论分析能力，却又植根于现实世界。
这种理论与实际的结合对李维斯特而言简直是完美的挑战。他离开了斯坦福大学的机器人项目，加入了MIT，转而研究计算复杂度这一新兴学科。
李维斯特回忆道：“一天，有个研究生带着这篇论文来找我，对我说：‘您或许会对这个感兴趣。’”那正是迪菲和赫尔曼的论文，他立刻被吸引了。“他还说：‘这篇论文在宏观上讨论了密码学的定义和发展。要是您也可以给出出主意就好了。’”文中的挑战囊括了李维斯特所有的兴趣：计算、逻辑学和数学。其中有个问题显然是出于对现实世界的考虑，但也直接关联到和李维斯特所关心的一个理论问题。“在密码学中，你所关心的是如何区分容易的问题和困难的问题，”他解释道，“而这正是计算机科学所研究的东西。”如果一个密码很难破解，那么它一定是基于某个很难计算求解的数学问题。
李维斯特开始尝试构建公钥密码系统，他从数学宝库中挑选所需的难题，这些问题都是计算机需要花很长时间才能破解的。他也需要有人来给他的工作提供反馈意见。那时的MIT已经开始打破传统大学的桎梏，加强各院系之间的互动和沟通，为的是鼓励跨学科研究。李维斯特虽然在计算机科学系工作，但他和数学系的同事在同一楼层。在他附近的办公室就坐着两位数学家，伦纳德·阿德曼和阿迪·萨莫尔。
阿德曼比李维斯特更善于交际，但仍然符合学者的经典形象，对那些看似不切实际的事物有着疯狂而奇妙的想法。阿德曼回想起有一天早晨，当他来到李维斯特的办公室时的情景：“罗就坐在那儿，手里拿着一份稿子。他对我说：‘你看过这篇斯坦福的论文吗，是关于加密、密码、加扰之类的……’我回答：‘好吧，这挺好的，罗，但我还有重要的事情要谈，我真的不关心这些。’但是罗对此很兴趣。”阿德曼关心的是高斯和欧拉的抽象世界。证明费马大定理对他来说才是重要的事情，而不是投身于密码学这种流行学科的研究。
伦纳德·阿德曼（图片来源：维基百科）
李维斯特在附近的办公室里发现了更好的聆听者——阿迪·萨莫尔，来MIT访学的以色列数学家。萨莫尔就和李维斯特一起寻找可用来实现迪菲和赫尔曼的设想的方法。尽管阿德曼并不怎么感兴趣，他还是难以无视李维斯特和萨莫尔的研究热情：“每次我走进办公室里，他们都在讨论这个。他们尝试的多数系统都失败了。既然我也在那里，我就索性加入了讨论，看看他们的提议靠不靠谱。”
阿迪·萨莫尔（图片来源：维基百科）
随着他们对“困难”的数学问题的研究范围不断拓展，他们的密码系统已初具雏形，并开始用到了越来越多的数论知识。这正是阿德曼的本行：“因为那是我的专业领域，所以分析他们的系统时，我可以施展拳脚，而且大部分时间也用不着他们。”当李维斯特和萨莫尔提出一个看起来非常安全的系统时，他以为自己输定了。但是借助自己的数论知识，只需工作一宿就足以破解他们最新的密码：“这种情况周而复始。在去滑雪的路上，我们讨论的是这个……甚至我们坐着缆车，快要到达山顶的时候，我们还在讨论这个……”
转折点发生在一天晚上，三人受邀去往研究生院，参加逾越节第一夜的晚餐。阿德曼没喝酒，但他记得李维斯特喝了一瓶逾越节家宴的酒。阿德曼半夜才回家。他到家不久后，电话铃就响了。打来电话的是李维斯特：“我想到了另一个点子……”阿德曼仔细地听着，说：“罗，这次你成功了！我觉得你这个想法是对的。”关于因数分解的难题，他们已经思考了一段时间。对寻找构造出某个数的素因数而言，目前尚未出现任何巧妙的编程方法。这个问题太合适了。在逾越节晚宴酒的影响下，李维斯特已经看到了如何将这个问题通过编程融入到他的新密码中。李维斯特回忆道：“当时的第一感觉真是太棒了。但我们知道，起初感觉良好并不意味着后面的路就会好走。所以我们把问题搁到了第二天早晨。”
次日上午，阿德曼来MIT上班的时候，李维斯特拿着一份手稿跟他打招呼，稿子的顶部写着阿德曼、李维斯特和萨莫尔的名字。阿德曼翻阅着手稿，回想起李维斯特昨天晚上打电话告诉他的事情。“于是我对罗说，‘把我的名字去掉，这是你完成的’，之后我们为了要不要留下我的名字差点打起来。”最后，阿德曼同意再考虑考虑。当时阿德曼觉得署名与否并不重要，因为这篇文章有可能是他发表的文章中阅读量最低的。不过他又想到，为了这个早期的密码系统，他没日没夜地研究，终于让它有了较为成熟的方案，也让这篇论文避免了因生成不安全的密码而在发表后遭人唾弃的危险。“于是我回去找罗，对他说：‘让我来当第三作者吧。’这就是RSA加密算法的名称的由来。”
李维斯特觉得他们最好研究一下因数分解问题到底有多难：“研究因数分解在那时属于一种高深的艺术，相关文献也很少。我们所提出的算法究竟要花多少时间才能完成，我们也不好说。”不过恰好马丁·加德纳对这个问题有所了解，他是世界上最受欢迎的数学科普作家之一。加德纳被李维斯特的想法迷住了，正好他在《科学美国人》杂志上有一个专栏，他便问李维斯特是否愿意由他来写一篇专栏文章，介绍这一思想。
加德纳的文章发表后，读者的反响让阿德曼最终确信，他们真的搞了件大事情：
那年夏天，我在伯克利的某间书店里面。有一位顾客在和柜台后面的人谈论着什么，然后我听到他说：“你有没有看过《科学美国人》里的那篇关于密码的文章？”我就走了过去，对他说：“嗨，我就是文中提到的研究者之一。”他就回过头来，对我说：“我可以得到你的亲笔签名吗？”我们可曾被人要过亲笔签名？从未有过。喔，当时感觉……也许我们的出头之日就要来了！
加德纳在文中还提到，只要提供贴好邮票并写上收信地址的信封，这三位数学家就会寄出论文的预印本。“等我回到MIT的时候，我们已经收到了数以千计的——毫不夸张，真是数以千计的——来自世界各地的信封，其中还有来自保加利亚国家安全局的……”
人们开始告诉他们三个，他们要发财了。即使是在20世纪70年代，电子商务还很难想象的时候，人们也能看出他们的想法拥有巨大的潜能。阿德曼觉得用不了几个月就会财源滚滚，于是直接出门买了辆红色跑车庆祝一下。看来邦别里并不是唯一一位用跑车来奖励自己在数学上的成就的人。
阿德曼的跑车最后还是用他在MIT的工资分期付清的。安全机构和商业机构着实花了一段时间，才真正领会了RSA加密算法在密码安全方面的威力。当阿德曼一边开着跑车，一边还想着费马大定理时，李维斯特已经开始着手推动他们的想法落地：
我们认为我们的方案或许还有一些商业价值。我们去MIT的专利办公室碰了碰运气，看看有没有公司愿意将其投入市场。但那时是20世纪80年代早期，我们几乎没有市场。那个时代对此感兴趣的人太少了。互联网尚未兴起，个人计算机也尚未普及。
对此最感兴趣的当然是安全机构。“安全机构开始密切关注这一技术的进展，”李维斯特说，“但他们仔细研究后，认为我们的研究计划不会进展太快。”在情报机构紧闭的大门背后，似乎有人做着同样的事情。不过安全机构也不是很确定，能否将特工人员的生命安全托付给几位研究密码的数学家。根据来自德国联邦信息安全局的安斯加尔·霍伊泽尔的回忆，在20世纪80年代，他们曾考虑在该领域使用RSA加密算法。他们问了这几位数学家一个问题：西方国家的数学家在数论上是否强于俄罗斯数学家。当得到否定的回答时，这个想法就被搁置了。但是在接下来的十年中，RSA加密算法证明了自己的价值：它不仅能保护特工人员的生命安全，还能在商业领域大显身手。
一个密码学的纸牌戏法
如今网络上进行的大部分交易都是由RSA加密算法保护的。值得注意的是这种公钥密码系统背后的数学计算，令人想起高斯的时钟计算器，以及费马（阿德曼的偶像）所证明的定理，即费马小定理。
皮埃尔·德·费马（图片来源：维基百科）
高斯计算器上的加法运算和我们所熟悉的12小时表盘的工作原理一致。我们知道，如果现在是9点，那么再过4小时就是1点。这就是时钟计算器上的加法运算：对数字进行求和，然后除以12。以下就是高斯200多年前所写的式子：
4+9=1（以12为模）
在高斯的时钟计算器上，乘法和幂运算的原理也一样：先用传统计算器来计算，再将结果除以12，最后取余数。
高斯还意识到，这种计算器不必拘泥于传统的12小时表盘。甚至在高斯明确提出时钟计算器的概念之前，费马就已经发现了一个基本规律，即所谓的费马小定理。假设有一个表盘时间为素数的时钟计算器，该素数用p表示。如果在该计算器上计算某个数字的p次幂的话，那么结果总是会出现最初的数字。例如，使用5小时表盘的时钟计算器来计算2的5次幂。传统计算器的计算结果是32，而在5小时的表盘上，时针会指向2点。费马发现，每次将计算结果乘以2时，时针指向的钟点是有规律地变化的。5次操作之后，时针就指向最初的钟点，并开始重复前5次的规律，如下表所示。
如果使用13小时表盘的时钟计算器来进行3的13次幂运算，即31，32，…，313，就会得到：
3，9，1，3，9，1，3，9，1，3，9，1，3
这时候指针并没有遍及表盘上所有的数字，但其指向的钟点还是有规律地重复的。也就是说，如果对3进行13次幂运算，那么第一次和最后一次运算的结果都是3。无论费马选择了什么样的p值，这种神奇的现象都一样会发生。采用高斯的时钟运算或模运算的记法，可以将费马的这一发现描述为，在p小时表盘上，对任意素数p及表盘的任意钟点x，都有：
xp=x（以p为模）
费马的发现在某种程度上令数学家们热血沸腾。素数居然如此神奇，但背后的原因是什么呢？费马并不满足于实验观察，他希望从理论上证明，无论表盘时间选择什么素数，这一结论都能站得住脚。
费马在1640年写给他的朋友伯纳德·弗莱尼科·德贝西的一封信中描述了这一发现。他好歹没有像对待费马大定理那样，只在某本书的空白处写了几句话，声称“我确信已发现了一种美妙的证法，可惜这里空白的地方太小，写不下”。虽然他承诺将证明寄给弗莱尼科，但这一证明的文本至今下落不明。又过了一个世纪，相关的讨论才重新进入人们的视野。1736年，欧拉发现了费马的素数表盘指针在进行素数幂次运算之后还能指向起始钟点的原因。欧拉还设法将费马的发现推广到N小时表盘上，其中N=p×q，p和q都是素数。欧拉发现，在这种表盘上，时针指向的钟点在(p-1)×(q-1)+1步操作之后开始有规律地重复。
由费马发现并由欧拉推广的神奇的素数时钟运算，在逾越节晚宴结束后的深夜闯入李维斯特的脑海。李维斯特想到，可以将费马小定理作为设计新密码的关键机制，用于信用卡号码的加密和解密。
加密信用卡号码就像开始演示某种纸牌戏法，但这不是普通的纸牌：如果要记录这摞纸牌共有多少张，那么这个数字可以达上百位。用户的信用卡号码就是这些纸牌中的一张。用户将信用卡号码的纸牌放在这摞纸牌的顶部，然后由网站来洗牌，这样用户的纸牌似乎就“消失”了。想要从这摞打乱的纸牌中找回这张牌，无异于大海捞针，这对任何黑客而言都是不可能的任务。然而网站知道这个戏法背后的窍门。多亏有了费马小定理，网站只需要再洗一次牌，就能让信用卡号码那张牌在纸牌的顶端重现。第二次洗牌就是只有网站的所有者——也就是公司——才能掌握的密钥。
（图片来源：veer图库）
李维斯特设计这一加密技巧所用到的数学计算相当简单。洗牌也是通过数学计算来完成的。用户在网站上下单之后，计算机就会获取用户的信用卡号码并进行计算。计算很容易执行，但是如果不知道密钥的话，那就几乎不可能破解。这是因为计算使用的并不是传统的计算器，而是高斯的时钟计算器。
互联网公司会告诉客户，在他们下单之后，应该用多少个钟点的表盘进行时钟计算。这取决于素数p和q的大小，它们分别有约60位数。之后公司将两个数字相乘，得到第三个数字，即N=p×q。这样一来，表盘上的钟点数会特别大，可达120位。每个客户始终用相同的时钟计算器来加密信用卡号码。密码的安全性意味着公司可以一连几个月使用相同的表盘而无须更换。
为网站的时钟计算器选择表盘上的钟点数，这就是公钥选择的第一步。尽管数字N是公开的，两个素数p和q却依然保密。p和q就是破解已经加密的信用卡号码的两个要素。
下一步，每个客户都会收到数字E，它被称为加密数字。每个人的E都一样，而且它和N一样是公开的。如果要加密信用卡号码C的话，那么就在网站的时钟计算器上将其进行E次幂的运算。（把E看成魔术师洗牌的次数，洗牌之后就可以隐藏你选择的那张牌了。）借用高斯的表述，可以写作CE（以N为模）。
为什么这个加密算法如此安全呢？毕竟任何黑客都可以在网络空间里看到加密后的信用卡号码，而且他们还可以查询加密使用的公钥，公钥包含了N小时表盘的时钟计算器以及信用卡号码的E次幂运算。要破解这个密码的话，黑客要做的就是找到一个数字，该数字在N小时表盘的时钟计算器上经过E次幂运算，就能得到加密的信用卡号码。但是找到这个数字相当困难。因为幂运算是在时钟计算器而非传统计算器上进行的，所以破解起来格外困难。使用传统计算器的话，计算结果会和信用卡号码相乘的次数等比例增长，但使用时钟计算器就不会这样。这样一来，黑客就很难知道纸牌的初始位置，因为计算结果的数值大小和你从哪里开始没什么关系。于是，经过E次洗牌之后，黑客对于牌面几乎一无所知。
（图片来源：veer图库）
如果黑客对时钟计算器发起暴力枚举攻击呢？这也不可能成功。密码学家现在所利用的时钟计算器的N，也就是表盘上的钟点数，已经有100多位了。也就是说，表盘上的钟点数比宇宙中的原子数还多。（相比之下，加密数字E通常就小得多了。）但是，如果这个问题不可能解决的话，那么互联网公司究竟是如何找回客户的信用卡号码的呢？
李维斯特知道，费马小定理能保证一个神奇的解码数字D的存在。互联网公司对加密的信用卡号码进行D次幂运算之后，最初的信用卡号码就会出现。魔术师在纸牌戏法中也使用了相同的技巧。一定次数的洗牌之后，纸牌顺序看似完全被打乱，但是魔术师知道，再洗几次牌就可以恢复原来的顺序。例如完美洗牌，一摞牌对半均分，然后让两侧的每张牌交错重叠，这样洗8次牌后，就可恢复原来的纸牌顺序。当然，魔术师的艺术是可以完成连续8次的完美洗牌。费马也发现了类似的时钟算法，即让52张纸牌恢复原来顺序的完美洗牌次数。而费马的戏法正是李维斯特用来破解RSA加密算法的武器。
尽管经过网站多次洗牌之后，客户信用卡号码的那张牌已经难寻踪迹，但互联网公司知道，就像数学魔术师一样，再经过D次洗牌，它就会出现在纸牌的顶部。但是只有知道秘密素数p和q才能知道D。李维斯特利用了欧拉所推广的费马小定理，其时钟计算器使用两个素数而不是一个。欧拉已经证明，在这样的时钟计算器上，经过(p-1)×(q-1)+1次洗牌后，这摞纸牌就会恢复原先的顺序。因此，想要知道表盘钟点数为N=p×q的时钟计算器的重复周期到底有多长，唯一的办法就是知道p和q。因此，掌握这两个素数就成了破解RSA加密算法的关键。令“消失”的信用卡号码重现的洗牌次数只有互联网公司知道，因此p和q也都是保密的。
尽管p和q是保密的，但它们的乘积N是公开的。因此，李维斯特的RSA加密算法的安全性是建立在对N进行因数分解的超高难度上的。黑客所面临的挑战和科尔教授在20世纪初所面对的问题是一样的：找到N的两个素因数。
来源：科学大院
编辑：GUOmazing
近期热门文章Top10
