工程哲學：Adi Shamir

重點摘要

• 他是 RSA 中的「S」，史上第一個實用的公開金鑰密碼系統。 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 人卻一無所獲——連一點暗示、一絲線索都沒有。整套機制僅僅建立在一條多項式上的若干點之上。³
• 他是頂尖的密碼分析家——他以攻為守。 1980 年代末，Shamir 與 Eli Biham 公開發現了差分密碼分析，一種破解區塊密碼的通用方法；在此之前，他也已破解了 Merkle-Hellman 背包密碼系統。同一顆打造出 RSA 的腦袋，花了數十年學習破壞，因為在密碼學裡，這是唯一誠實地確認一套系統夠不夠強的方式。⁴⁵
• 他不斷把純粹的數學轉化為實用的機制。 除了 RSA 與祕密分享之外，Shamir 還共同發明了 Fiat-Shamir 啟發式——一種利用雜湊函數，把互動式證明轉為非互動式簽章的方法——以及以身分為基礎的密碼學與視覺密碼學方案。自 1980 年起，他便是 Weizmann 研究所的教授；他的整個生涯，是一場漫長的論證：深奧的數論是一套工具箱，而非博物館裡的展品。¹⁶

核心原則

「後來人們才發現，差分密碼分析早已為 IBM 與美國國家安全局所知——且被當作機密保守。」——談及 Biham 與 Shamir 在公開場域重新發現的那項技術，引述自史料的轉述⁴⁵

工程多半是朝著一場展示前進。你寫出那個東西，執行它，它能動，而「能動」本身就是證明。密碼學拒絕這種安慰。一套能正確加解密的密碼，對於它是否安全什麼都沒有證明——一套被破解的密碼和一套牢不可破的密碼，在有人攻擊它們之前，行為完全一樣。於是這個領域不得不另立一套關於真理的標準：一套系統值得信任，不是因為它能運作，而是因為認真的人們已竭力嘗試破解它卻失敗了。Shamir 的整個生涯，正是這套標準的具體化身。你要保護一套系統，靠的是學會破解系統——以攻為守。⁴

最清楚的表現，是他親手兼任了兩個角色。他打造了 RSA，公開金鑰密碼學的基石；他也打造了 Shamir 祕密分享，一套具有可證明之資訊理論安全性的方案。¹³ 但他同時也破解了 Merkle-Hellman 背包密碼系統——那是一個看似安全、實則不然的對手級公開金鑰方案——並且共同發現了差分密碼分析，一種足以威脅資料加密標準（DES）本身的通用方法。⁴⁵ 這並非兩段生涯，而是同一門學問。建構的工作告訴你什麼是可能的；破壞的工作告訴你什麼是真實的。一個只懂建構的密碼學家是在猜測；而最令人脊背發涼的證明，是後來才浮現的真相：IBM 與 NSA 早自 1970 年代中期便知曉差分密碼分析，卻將它列為機密——這意味著公開的學界一直在盲目地打造密碼，對一項對手早已握有的攻擊渾然不覺。⁴⁵

這條原則還有第二半，較為安靜，卻同樣支撐全局：把一個純粹的數學構想化為實用機制的力量。祕密分享不過就是多項式內插——一個每個學生在代數課上都會遇到的事實：兩點決定一條直線，三點決定一條拋物線。Shamir 看出，同一個事實反過來讀，就是一個安全原語：把點發出去，而曲線在足夠多的點聚集之前都保持隱藏。³ RSA 不過就是模冪運算加上分解質因數的困難。² Fiat-Shamir 啟發式不過就是用一個雜湊取代驗證者的擲幣。⁶ 找出乾淨的數學結構，然後把它讀成一個機制。 天才之處鮮少是嶄新的數學——而是看出舊的數學，從對的角度看過去，本身就已經是你需要打造的那個東西。

背景脈絡

Adi Shamir 於 1952 年 7 月 6 日生於以色列特拉維夫。¹ 他於 1973 年取得特拉維夫大學數學學士學位，隨後前往 Weizmann 科學研究所攻讀研究所，於 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 早在 GCHQ 的一份 1973 年機密文件中描述了一套等價的系統，直到 1997 年才解密——這又是一例：學界在黑暗中摸索建構，而情報機構在一旁看著。）²

1980 年，Shamir 回到 Weizmann 研究所，此後一直在該所的電腦科學與應用數學系擔任教授，後來也獲聘為巴黎高等師範學院（École Normale Supérieure）的客座教授。¹ 幾乎所有定義了他的成就——祕密分享、對背包密碼的攻擊、與他的學生 Eli Biham 共同提出的差分密碼分析、Fiat-Shamir 啟發式、與 Moni Naor 共同提出的視覺密碼學、立方攻擊、以及 TWIRL 與 TWINKLE 質因數分解裝置——都出自 Weizmann。2002 年，美國計算機協會（ACM）將 圖靈獎這項計算領域的最高榮譽頒給 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 的建構，接下來的這批工作則展現了他做著這個領域更迫切需要的事：破解。1970 年代末，Merkle-Hellman 背包密碼系統是 RSA 的主要對手，其安全性建立在「子集和」問題上；該問題是 NP 完全的，因此看似艱難無比。Shamir 破解了它。他證明 Merkle-Hellman 所用的那些特定的背包，並非難解的一般情況，而是一種特殊、有結構的情況，可以被高效求解——擊垮了許多人曾信賴的一套方案。¹ 這個教訓是密碼學一再重新學到的：一個問題在一般情況下很難，並不代表你的密碼實際使用的那些實例也很難。唯有攻擊，才能揭示其中的差別。

他最具影響力的密碼分析工作，出自 1980 年代末與他的學生 Eli Biham 的合作：差分密碼分析，約於 1990 年發表。⁴⁵ 這是一種通用技術，研究一套密碼中，成對輸入之間的差異如何傳播為輸出的差異。如果某些輸入差異會以非隨機的機率導致某些輸出差異，那道統計偏差就是一道裂縫——一處關於金鑰資訊的洩漏——而 Biham 與 Shamir 將它化為對一系列區塊密碼的攻擊，包括對當時全世界最重要的密碼 資料加密標準（DES） 的一項理論弱點。⁴⁵

接著，這個領域學到了一件令人謙卑的事。1994 年，Don Coppersmith 揭露，設計了 DES 的 IBM——早在 1970 年代——便「早至 1974 年」就知曉差分密碼分析，防禦它一直是 DES 一項明確的設計目標，而 NSA 曾施壓要將這項技術列為機密，因為「揭露這些設計考量會洩漏差分密碼分析這項技術，一種足以對付許多密碼的強大技術」。⁴⁵ DES 那些神祕的內部常數，長久以來被懷疑藏著一道後門，結果卻是藏著一道針對某項攻擊的防禦，而當時公眾並不知道那項攻擊存在。這段插曲，是支持 Shamir 那條原則的最強論證。整整二十年，開放社群一面打造並信賴密碼，一面對一項對手早已握有的根本性攻擊渾然不覺。Biham 與 Shamir 在公開場域的重新發現並未削弱密碼學——它反而強化了密碼學，因為它把那項攻擊拖進了光亮之中，讓每個人都能據此設計防禦。以攻為守，放大到整個領域的尺度。⁴⁵

Fiat-Shamir 與工具箱的廣度

同一種直覺——找出乾淨的結構，把它讀成機制——貫穿了 Shamir 的其他發明。Fiat-Shamir 啟發式，於 1980 年代中期與 Amos Fiat 共同提出，解決了互動式知識證明的一個實務問題：這類證明需要即時的一來一往，由驗證者送出隨機挑戰，由證明者回應。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 是以色列密碼學家，Weizmann 科學研究所的教授，最為人所知的身分是 RSA 中的「S」——史上第一個實用的公開金鑰密碼系統，由他與 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 在 1980 年代末公開發現，透過研究成對輸入之間的差異如何傳播為輸出的差異，來攻擊區塊密碼。那種傳播中的統計偏差可能洩漏關於祕密金鑰的資訊；Biham 與 Shamir 用它找出了 DES 的一項理論弱點。後來人們才發現，IBM 與 NSA 早自 1970 年代中期便知曉這項技術並將它列為機密，還暗中把 DES 設計成能抵抗它。⁴⁵

資料來源