圖靈獎得主麥可·拉賓逝世

背景

本文報導了計算機科學與數學界的泰斗、1976 年圖靈獎得主麥可·拉賓（Michael O. Rabin）逝世的消息。拉賓教授在計算複雜度理論、非確定性自動機、隨機演算法以及現代密碼學等領域皆有開創性的貢獻，其研發的米勒-拉賓質數判定法與 Rabin-Karp 字串搜尋演算法至今仍是資訊工程教育與實務中的核心基石。

社群觀點

在 Hacker News 的討論中，社群成員對拉賓在密碼學領域的實質貢獻給予了極高的評價，甚至認為他在公鑰密碼學發展史上的地位被嚴重低估。有觀點指出，雖然 RSA 團隊（Rivest, Shamir, Adleman）因創立成功的商業公司而名聲大噪，但從技術演進的角度來看，拉賓的貢獻更具必要性。若沒有 RSA 演算法，公鑰密碼學仍能透過 Merkle、Diffie、Hellman 與拉賓所奠定的基礎發展成熟；反之，若缺少拉賓在 1970 年代後期的研究，公鑰密碼學的進程恐將延遲數年。

社群特別強調了拉賓在加密雜湊函數（Cryptographic Hash Functions）定義上的關鍵角色。他與 Ralph Merkle 共同發現了安全雜湊函數在數位簽章中的必要性。當時 RSA 最初提出的簽章演算法存在安全性漏洞，是拉賓指出了必須結合「單向雜湊函數」才能確保簽章在實務上不可破解。在學術定義的演進中，Merkle 定義了抗原像攻擊與抗第二原像攻擊，而拉賓則定義了抗碰撞攻擊，這兩者的理論結合最終形塑了現代安全雜湊函數的標準定義。

然而，討論中也帶出了一段技術發展的遺憾。儘管拉賓與 Merkle 奠定了雜湊函數的基礎，但他們當時皆忽略了「抗長度擴展攻擊」（Length Extension Attacks）這一關鍵屬性。這項定義上的缺失直接影響了後來美國安全雜湊演算法（SHA）標準的制定，導致許多應用程式必須額外採用 HMAC 等補強方案來彌補缺陷，直到 GCM 等更高效的驗證演算法普及後才得以改善。儘管如此，拉賓在隨機化演算法的先驅工作，特別是將「擲硬幣」的概念引入計算過程以大幅提升效率，仍被視為改變計算機科學範式的革命性舉措。

延伸閱讀

• 米勒-拉賓質數判定法（Miller–Rabin primality test）：現代加密金鑰生成的基礎演算法。
• Rabin-Karp 演算法：利用滾動雜湊（Rolling Hash）實現的高效字串搜尋技術。
• Rabin 簽章演算法：首個安全性被證明等同於整數分解難度的非對稱加密系統。