工程哲学：Adi Shamir

核心要点

• 他是 RSA 中的“S”，而 RSA 是第一个实用的公钥密码系统。 1977 年，Adi Shamir 与 Ron Rivest、Leonard Adleman 一起在 MIT 共同发明了 RSA——当年即公开描述，并于 1978 年 2 月发表在 Communications of the ACM 上。这套方案让人们无需事先共享任何秘密，就能向某人加密信息、并验证其签名，其安全性建立在大数分解的难度之上。这项工作为三人赢得了 2002 年 ACM 图灵奖。¹²
• 他把一条多项式变成了完美的秘密。 1979 年，Shamir 发表了《How to Share a Secret》，提出了一种门限方案：把一个秘密分发给 n 个人，其中任意 k 人合起来就能重建它，而任意 k-1 人却一无所获——既无半点提示，也无从缩小范围。整套机制完全建立在多项式上的点之上。³
• 他是密码分析大师——以攻为守。 20 世纪 80 年代末，Shamir 与 Eli Biham 一起公开发现了差分密码分析，一种攻破分组密码的通用方法；在此之前，他还攻破了 Merkle-Hellman 背包密码系统。同一个构建出 RSA 的头脑，花了数十年去学习如何攻破事物——因为在密码学里，这是确认一套系统是否真正坚固的唯一诚实途径。⁴⁵
• 他始终在把纯净的数学转化为实用的机制。 除了 RSA 和秘密共享，Shamir 还共同发明了 Fiat-Shamir 启发式——一种借助哈希函数把交互式证明转化为非交互式签名的方法——以及基于身份的密码学与视觉密码学方案。自 1980 年起，他便是 魏茨曼研究所（Weizmann Institute）的教授；他的整个生涯都在论证一件事：高深的数论是一套工具箱，而非博物馆里的陈列。¹⁶

原则

“后来人们才发现，差分密码分析早已为 IBM 和美国国家安全局所知——并被严守为秘密。” —— 论 Biham 与 Shamir 在公开领域重新发现的这一技术，对历史记录的转述⁴⁵

工程领域的大多数工作，都奔着一场演示而去。你写出东西，运行它，它能跑通，而“能跑通”就是证明。密码学却拒绝这份安逸。一个能正确加解密的密码，对于它是否安全这件事什么都没有证明——在有人发起攻击之前，一个已被攻破的密码和一个牢不可破的密码表现得一模一样。于是这个领域不得不发明出一套不同的真理标准：一套系统之所以可信，不在于它能运行，而在于有认真的人拼尽全力去攻破它却失败了。Shamir 的整个生涯，正是这一标准的化身。保护一套系统的方式，是学会攻破系统——以攻为守。⁴

最清晰的体现，是他亲手完成了两半工作。他构建了 RSA，公钥密码学的基石；也构建了 Shamir 秘密共享，一套具备可证明的信息论安全性的方案。¹³ 但他同样攻破了 Merkle-Hellman 背包密码系统——一个看似安全、实则不然的对手级公钥方案——并共同发现了差分密码分析，一种通用到足以威胁数据加密标准（DES）本身的方法。⁴⁵ 这不是两段生涯，而是同一门学问。构建的工作告诉你什么是可能的；破坏的工作告诉你什么是真实的。只会构建的密码学家是在猜测；而对此最令人脊背发凉的证明出现在后来：原来 IBM 和 NSA 早在 20 世纪 70 年代中期就已知晓差分密码分析，并将其列为机密——这意味着公开领域一直在对一种对手早已掌握的攻击毫不知情的情况下构建密码。⁴⁵

这条原则还有第二半，更安静，却同样举足轻重：把一个纯净的数学思想转化为实用机制的力量。秘密共享不过是多项式插值——每个学生在代数课上都会遇到的事实：两点确定一条直线，三点确定一条抛物线。Shamir 看出，把这同一个事实反过来读，就是一个安全原语：分发出一些点，而那条曲线在足够多的点聚拢之前始终隐藏。³ RSA 不过是模幂运算加上分解的困难性。² Fiat-Shamir 启发式不过是用一个哈希取代验证者的掷币。⁶ 找到那个纯净的数学结构，然后把它读作一种机制。 天才之处很少在于新的数学——而在于看出旧的数学，从恰当的角度看去，本身就已是你需要构建的那个东西。

背景

Adi Shamir 于 1952 年 7 月 6 日生于以色列特拉维夫。¹ 他于 1973 年在特拉维夫大学取得数学学士学位，随后转入魏茨曼科学研究所攻读研究生，1975 年取得计算机科学硕士学位，1977 年取得博士学位。¹ 他的时机，正如这个领域的时机一样，即将迎来转折：1977 年正是公钥密码学从一个诱人的想法变为可用系统的那一年。

取得博士学位后，他在英国的华威大学做了一年博士后研究，随后前往麻省理工学院，在 1977 至 1980 年间担任研究人员。¹ RSA 就诞生在 MIT。密码学家 Ron Rivest 一直在追寻一种受 Diffie-Hellman 思想启发的公钥方案——两方无需共享秘密即可建立保密通信；Shamir 和 Adleman 既是他的合作者，更关键的是，也是他的对手——Rivest 提出一个方案，Shamir 和 Adleman 就去攻破它，一次又一次，直到有一个挺了过来。挺过来的那个就是 RSA，以三人之名命名，1977 年公开，1978 年发表于 Communications of the ACM。²（他们并不知道，英国数学家 Clifford Cocks 早在 1973 年就已在 GCHQ 的一份机密文件中描述过一套等价系统，该文件直到 1997 年才解密——这又是一例：公开领域在黑暗中构建，而情报机构在一旁注视。）²

1980 年，Shamir 回到魏茨曼研究所，此后一直在计算机科学与应用数学系任教授，后来还在巴黎高等师范学校（École Normale Supérieure）担任客座教授。¹ 几乎所有定义了他的成果——秘密共享、对背包密码的攻击、与学生 Eli Biham 合作的差分密码分析、Fiat-Shamir 启发式、与 Moni Naor 合作的视觉密码学、立方攻击，以及 TWIRL 和 TWINKLE 分解装置——都出自魏茨曼。2002 年，美国计算机协会因 Rivest、Shamir 和 Adleman 对公钥密码学的贡献，将计算领域的最高荣誉图灵奖授予了他们。¹²

成就

Shamir 秘密共享：一条守住秘密的抛物线

从这里开始，因为它以最纯粹、最优美的形式呈现了那条原则。假设你有一个秘密——一把主密钥、一段发射代码、一个金库的口令——你想把它分发给五位受托人，使其中任意三人合起来就能恢复它，而任意两人却什么都学不到。你或许会试着把这把密钥物理地切成几块，但那会泄露信息：每一块都会缩小猜测的范围。Shamir 在 1979 年的《How to Share a Secret》中给出的洞见是：多项式恰好精确地解决了这个问题。³

诀窍在于把一个小学就学过的事实反过来读。两点确定唯一一条直线；三点确定唯一一条抛物线；一般而言，k 个点确定唯一一条 k-1 次多项式。于是，要在 n 个人之间以门限 k 来共享一个秘密，你就把这个秘密藏作一条随机的 k-1 次多项式的常数项——即曲线在 x = 0 处的取值——再交给每个人这条曲线上的一个点。³ 任意 k 人都能通过他们手中的点插值出那条唯一的曲线，并读出它在零点处的值。但真正令人惊叹的是其安全性：只有 k-1 个点时，这条曲线不仅仅是难以找到——而是真正无从确定。对于每一个可能的秘密值，恰好存在唯一一条正确次数的曲线穿过他们的点，并在零点处命中那个值。正如 Shamir 的方案所保证的，“知晓任意 k-1 个或更少的份额，会使 S 完全无从确定。”³ 少于门限便毫无所获；达到门限便尽收眼底。正是这条干净利落的全有或全无的边界，使它具备信息论安全性——它安全，不是因为攻破它在计算上很难，而是因为那份信息根本就不在那里。³

它作为工程的意义何在：这套方案是 Shamir 把数学读作机制的典范之作。他并没有发明多项式插值——它已有数百年历史。他看出，它的失效模式——你无法从太少的点恢复出一条曲线——恰恰是一种安全性质；而它的成功模式——足够多的点能把它精确钉死——恰恰是一种恢复性质。同一个事实，在两个方向上使用，便成了一个今天运行在硬件安全模块、加密货币托管和证书颁发机构内部的密码学原语。纯净的数学，被读作了工具。³

RSA：向陌生人加密

RSA 回答了一个近乎悖论的问题：两个素未谋面、只能通过一条被对手监听的线路通信的人，如何交换秘密？经典密码学要求事先建立一把共享密钥——可你无法在你正试图保护的那条信道上共享密钥。Rivest、Shamir 和 Adleman 于 1977 年构建进可用系统的突破口，是陷门单向函数：一种正向计算容易、逆向却不可行的运算——除非你掌握着一段秘密信息。²

RSA 的陷门是分解。你挑选两个大素数，把它们相乘得到模数 n；n 和一个公开指数构成你的公钥，你可以把它公布给全世界。任何人都能用它，通过模幂运算向你加密一条消息。但解密需要私钥，而私钥只能从那两个原始素数推导出来——要从它们的乘积中还原出这两个素数，就意味着分解一个极大的数，这个问题至今没有已知的高效解法。² 正如那个表述所说，虽然构造密钥是可行的，但“仅给定 e 和 n 时，计算模 n 的 e 次方根是不可行的。”² 你公布那把锁；只有你握着钥匙；而两者之间的鸿沟，就是分解的困难。

Shamir 的具体角色值得直白地说出来，因为这又一次印证了那条原则：他与 Adleman 一道，是三人组里的密码分析者。RSA 诞生的故事，是一个关于攻破的故事——Rivest 提出候选方案，Shamir 和 Adleman 不断攻击，直到只剩一个顶住了猛攻。幸存下来的那套方案之所以坚固，恰恰是因为它经受住了两个决意攻破它的人的攻击。RSA 不是一套被设计成安全、然后只能寄望于安全的系统；它是一套靠在自己作者手下幸存下来，从而赢得了这一论断的系统。²

以攻为守：攻破背包与差分密码分析

如果说 RSA 展现的是 Shamir 在构建，那么接下来这部分工作展现的，则是这个领域更为需要的：攻破。20 世纪 70 年代末，Merkle-Hellman 背包密码系统是 RSA 的一个主要对手，其安全性依托于“子集和”问题——这是个 NP 完全问题，因而看上去坚不可摧。Shamir 攻破了它。他证明，Merkle-Hellman 所用的那类特定背包，并非那个困难的一般情形，而是一个特殊的、有结构的情形，可以被高效求解——就此摧毁了一个许多人曾信任的方案。¹ 这个教训，密码学一再重新习得：一个问题在一般情形下困难，并不意味着你的密码实际使用的那些实例也困难。唯有攻击，才能揭示其中的差别。

他最具影响力的密码分析工作，出自 20 世纪 80 年代末与学生 Eli Biham 的合作：差分密码分析，约 1990 年发表。⁴⁵ 这是一种通用技术，研究一个密码的成对输入之间的差分如何传播为输出中的差分。如果某些输入差分以非随机的概率导致某些输出差分，这种统计偏差就是一道裂缝——一处关于密钥的信息泄露——Biham 和 Shamir 把它转化为对一系列分组密码的攻击，其中包括数据加密标准中的一个理论性弱点，而 DES 当时是世界上最重要的密码。⁴⁵

随后，这个领域学到了一件令人谦卑的事。1994 年，Don Coppersmith 披露，设计了 DES（于 70 年代）的 IBM“早在 1974 年”就已知晓差分密码分析，抵御它正是 DES 的一个明确设计目标，而 NSA 曾极力主张将该技术列为机密，因为“披露这些设计考量会暴露差分密码分析这一技术——一种可用来攻击许多密码的强大技术。”⁴⁵ DES 那些神秘的内部常数，长久以来被怀疑藏着后门，结果却原来藏着对一种公众尚不知存在的攻击的防御。这段插曲，是支持 Shamir 那条原则的最有力论据。整整二十年里，公开社区一直在构建并信任各种密码，却对一种对手早已掌握的根本性攻击毫无察觉。Biham 和 Shamir 的公开重新发现并没有削弱密码学——反而强化了它，因为它把这种攻击拖到了光亮之下，让每个人都能据此设计防御。以攻为守，放大到了整个领域的尺度。⁴⁵

Fiat-Shamir 与工具箱的广度

同样的直觉——找到纯净的结构，把它读作机制——贯穿于 Shamir 的其他发明。Fiat-Shamir 启发式，与 Amos Fiat 于 20 世纪 80 年代中期合作，解决了交互式知识证明中的一个实际问题：这类证明需要一场实时的来回——验证者发出一个随机挑战，证明者作出回应。Fiat 和 Shamir 看出，验证者唯一的任务，就是提供不可预测的随机性，而把一个密码学哈希函数作用于证明者自己的消息，就能同样好地提供这份随机性——从而把一场对话变成一个单一、自足、非交互的证明，也就是说，一个数字签名。⁶ 这一个变换，支撑起了现代签名方案和零知识系统中的很大一部分。他还提出了基于身份的密码学（用一个人的身份作为其公钥），与 Moni Naor 共同发明了视觉密码学（把一幅图像拆成若干透明片，唯有叠放时才显出秘密——一种你看得见的秘密共享），后来又发展出立方攻击以及 TWIRL 和 TWINKLE 分解装置。¹ 贯穿这一切，模式始终如一：一段已知的数学，以恰当的方式转过来，便成了一件工具。

方法

通览 RSA、秘密共享、被攻破的背包、差分密码分析与 Fiat-Shamir，同样的一些信条反复出现。Shamir 的方法，与其说是一句口号，不如说是一组长期奉行的习惯。

用同一双手去构建和攻破。 其标志性的做法，是拒绝在构建系统者与攻击系统者之间作分工。Shamir 共同发明了 RSA，也攻破了 Merkle-Hellman 背包；他证明了秘密共享的安全性，也共同发现了差分密码分析。这个教训远远超出密码学：在你拼尽全力试图击败你所构建的东西之前，你并不真正理解它。这是把证据门槛提升为一种生活方式——“它能跑通”不是安全的证据；“认真的人试过却攻不破”才是。²⁴

只信任经受住攻击的东西。 一个仅仅被精心设计过的密码，是一份指望；一个顶住过集中密码分析的密码，才是一个事实。这门功课在于把你自己的系统当作有罪推定，直到它被攻击为止——假定存在一道裂缝并主动去寻找它，而不是坐等对手替你找到。这是Thompson《Reflections on Trusting Trust》的密码学版本：那个奠基性的洞见是，你无法信任你未曾对抗性审视过的东西，因为那个你看不见的威胁，正是会拿下你的那个——差分密码分析的机密历史已经证明了这一点。⁴⁵

把数学读作机制。 最强大的原语很少是新的数学；它们是从一个新角度看去的旧数学。多项式插值变成了秘密共享；分解的困难性变成了一道陷门；一个哈希函数变成了交互式验证者的替身。这个习惯，是看着一个纯净的结构，问的不是“这是什么？”而是“这能做什么？”——正是这种手段上的节俭，使最强大的原语也成为最简单的，这与最小可贵产品的精神一脉相承。³⁶

能取得可证明的安全性就取得它，在其他一切地方则取得赢来的安全性。 秘密共享具备信息论安全性——无论多么强大的计算机，都无法从太少的份额中提取出秘密，因为那份信息根本不在场。³ RSA 具备计算安全性——只有在分解仍然困难时才安全。Shamir 在两个层面上工作，并且对自己手握的是哪一种安全性十分清楚。这门功课在于：确切地知道你的安全性主张依凭什么，并且永远不要把“还没有人攻破它”与“它无法被攻破”混为一谈。这是把质量是唯一的变量应用于信任：唯一算数的，是那份保证是否真实。²³

警惕藏在一般情形中的特殊情形。 攻破 Merkle-Hellman 让这个领域明白：一个问题在一般情形下是 NP 完全的，对密码实际使用的那些具体实例却什么也说明不了。¹ 这条长期习惯在于怀疑：一个困难问题中那个方便、有结构的版本——那个容易到足以拿来构建系统的版本——可能恰恰就是容易被攻破的版本。这与Leslie Lamport带给分布式系统的怀疑如出一辙：不要信任你假定成立的那个性质；去找出它实际成立所依凭的精确条件。

影响链

谁塑造了他

Diffie、Hellman 与公钥思想。 RSA 是对 Whitfield Diffie 与 Martin Hellman 1976 年那个提议的直接回应：无需预先共享密钥也能建立保密。Diffie-Hellman 提出了问题——一个公钥密码系统应当是存在的——而 Rivest、Shamir 和 Adleman 构建了第一个实用的答案。²（直接影响）

Ron Rivest 与 Leonard Adleman。 RSA 的合作是名副其实的三手联弹：Rivest 是不知疲倦的提出者，Shamir 和 Adleman 是不知疲倦的攻破者。这种合作中的对抗结构——提出、攻击、重复——塑造了 Shamir 终生的信念：构建与密码分析是同一门学问。²（奠基性影响）

数论传统。 Shamir 的标志性做法——把经典数学读作密码学机制——承自一个悠久的传统，它把数论、分解的困难性以及有限域的代数与计算联系在一起。他的天才在于对那门数学的应用，而非发明。（奠基性影响）

他塑造了谁

Eli Biham 与现代密码分析。 与学生 Biham 共同发展的差分密码分析，成了一件标准工具，如今每一位严肃的分组密码设计者都必须据此设防——它重塑了密码的构建方式，包括高级加密标准（AES）的设计准则。⁴⁵

整个公钥生态。 RSA 支撑了数十年的安全通信、数字签名与密钥交换。每当一个浏览器建立一次安全连接、或验证一张证书时，它都站在 Shamir 协助奠定的公钥基础之上。²

零知识与签名方案。 Fiat-Shamir 启发式是一头主力，支撑着名目繁多的现代数字签名与零知识证明系统，包括如今对隐私保护和区块链密码学至关重要的那些。⁶

贯穿的主线

Shamir 是本系列的安全拱顶石——那个让其余整个技术栈得以可信的人物。Tim Berners-Lee构建了一个人人可用的网络，但一个你能在上面购物、理财、自由发声的网络，其 TLS 连接和签名证书完全依赖公钥密码学——也就是说，它依赖 RSA 以及 Shamir 协助创立的那个领域。Thompson 和 Ritchie给了我们赖以运行的系统，并在《Reflections on Trusting Trust》中给出了那个奠基性的警告：你无法信任你未曾对抗性审视过的东西——这正是 Shamir 据以构建整个生涯的那种直觉。而Leslie Lamport给了分布式系统这样一种功夫：精确地定义正确性并证明它，以对抗行为任意的拜占庭式对手；Shamir 的秘密共享正是这同一种冲动的密码学形态，一个带有证明而非指望的原语。当 Berners-Lee 说这是为所有人准备的、Thompson 说不要信任任何不是你亲手构建的东西时，Shamir 说：我会为你构建出某种安全的东西，然后我会用我的一生去试图攻破它——因为这是我们俩确认它真实可靠的唯一途径。（系列之桥）

我从中汲取了什么

我从 Shamir 身上留存的教训是只信任经受住攻击的东西。我的本能，和大多数构建者一样，是把能跑通的代码当作证明——测试通过了，演示跑起来了，发布吧。密码学禁止这份安逸，因为一套被攻破的系统和一套稳固的系统在有人攻击之前看上去一模一样，而 Shamir 的回答是率先成为那个攻击者。他攻破了背包密码；他和 Adleman 不断攻破 Rivest 的候选方案，直到 RSA 幸存；他和 Biham 把 DES 攻得够狠，狠到暴露出情报机构隐藏了二十年的东西。所以如今我构建什么东西时——一套认证流程、一道权限边界、一条数据管线——我都试着在攻击者动手之前先戴上攻击者的帽子，假定存在一道裂缝并主动去猎寻它，而不是坐等被人告知。真正算数的信心，不是“我看不出这会怎么坏掉”；而是“我拼尽全力想攻破它却没能成功”。

第二个教训是：最强大的机制，是以恰当方式读出的纯净数学。我第一次真正理解秘密共享时，它把我小小地击溃了一下——它不过是那个课本上的事实：点确定一条多项式，然而它却产出了一个可证明、信息论上安全的秘密。Shamir 并没有发明更难的数学；他看出，他手头已有的数学，从某个角度看去，恰恰就是一个安全原语。这改变了我看待眼前那些既有结构的方式。我用来查找的哈希，可以是一个承诺；我为可靠性而加入的冗余，可以是一个门限方案；我当作累赘对待的约束，可以是那把锁。这门本事，并不总是发明某种新东西——而是认出你已经理解的那个纯净之物，以恰当方式转过来，正是你所需要的那个机制。

常见问题

Adi Shamir 以什么闻名？

Adi Shamir 是以色列密码学家、魏茨曼科学研究所教授，最为人所知的身份是 RSA 中的“S”——RSA 是第一个实用的公钥密码系统，由他与 Ron Rivest、Leonard Adleman 于 1977 年在 MIT 共同发明。三人因这项工作分享了 2002 年 ACM 图灵奖。他还发明了 Shamir 秘密共享（1979），与 Eli Biham 共同发现了差分密码分析，并共同创造了 Fiat-Shamir 启发式，此外对密码学还有诸多其他贡献。¹²

什么是 Shamir 秘密共享？

这是 Shamir 于 1979 年在《How to Share a Secret》中发表的一种方法，用于把一个秘密分发给 n 个人，使其中任意 k 人能重建它，而任意 k-1 人却一无所获。秘密被藏作一条随机 k-1 次多项式的常数项，每个人各收到这条曲线上的一个点。由于 k 个点能唯一确定一条 k-1 次多项式，任意 k 份份额便能恢复秘密——而少于 k 份则使它“完全无从确定”，这赋予该方案信息论安全性。³

RSA 中的“S”是谁，RSA 又是如何工作的？

“S”就是 Shamir；RSA 代表 Rivest、Shamir 和 Adleman。RSA 是一套公钥密码系统：每位用户都有一把公钥，任何人都能用它向其加密消息或验证其签名，以及一把只有本人持有的私钥。它的安全性依凭一道陷门——公钥由两个大素数的乘积构建而成，而要恢复私钥就必须把那个乘积重新分解回它的素因子，对足够大的数而言，这在计算上不可行。RSA 于 1978 年发表在 Communications of the ACM 上。²

什么是差分密码分析？

差分密码分析是一种通用技术，由 Eli Biham 和 Adi Shamir 在 20 世纪 80 年代末公开发现，通过研究成对输入之间的差分如何传播为输出中的差分来攻击分组密码。这种传播中的统计偏差能泄露关于秘密密钥的信息；Biham 和 Shamir 用它在 DES 中找到了一个理论性弱点。后来人们才发现，IBM 和 NSA 早在 70 年代中期就已知晓这一技术并将其列为机密，还秘密地把 DES 设计成能抵御它。⁴⁵

来源