正文開始之前我得重申一下，本文所講的不是所謂量子計算啟示錄（末日預言），也不是要講 21 世紀密碼學的成功。我們要談論的是另一件未成定局的事情——密碼學有史以來最簡單的（也是最酷炫的）技術之一：基於雜湊函式的簽名。
在 20 世紀 70 年代末，Leslie Lamport 發明了基於雜湊函式（Hash Function，又稱雜湊函式）的簽名 ，並經過 Ralph Merkle 等人進一步改進。而後的很多年，這被視為密碼學領域一灘有趣的“死水”，因為除了相應地產生冗長的（對比其他複雜方案）簽名，基於雜湊函式的簽名好像沒有什麼作用。然而近幾年來，這項技術似乎有了復甦的跡象。這很大程度歸因於它的特性——不同於其他基於RSA或離散對數假設的簽名，雜湊函式簽名被視為可以抵抗量子計算攻擊（如 Shor's 演算法）。
首先，我們進行一些背景介紹。
背景：雜湊函式和簽名方法
在正式介紹雜湊函式簽名之前，首先你得知道密碼學中的雜湊函式是什麼。雜湊函式可以接受一串字元（任意長度）作為輸入，經過“消化”後，產生固定長度的輸出。常見的密碼學雜湊運算，像是 SHA2、SHA3 或 Blake2 等，經運算會產生長度介於 256 ~ 512 位的輸出。
一個函式 H(.) 要被稱作“密碼學”雜湊函式，必須滿足一些安全性的要求。這些要求有很多，不過我們主要聚焦在以下三個方面：
抗-原像攻擊 Pre-image resistance （或俗稱“單向性”）：給定輸出 Y=H(X)，想要找到對應的輸入 X 使得 H(X)=Y 是一件“極度費時”的工作。（這裡當然存在許多例外，但最棒的部分在於，不論 X 屬於什麼分佈，找到 X 的時間成本和暴力搜尋相同。）
抗-次原像攻擊：這和前者有些微的差別。給定輸入 X，對於攻擊者來說，要找到另一個 X' 使得 H(X)=H(X') 是非常困難的。
抗-碰撞：很難找到兩個輸入 X1, X2，使得 H(X1)=H(X2)。要注意的是，這個假設的條件比 抗-次原像攻擊還要嚴苛。因為攻擊者可以從無垠的選擇中尋找任意兩個輸入。
我們相信所有本文提到的雜湊函式示例都能提供上述的所有特性。換言之，沒有任何可行的（甚至是概念上的）方法能破解它。當然這種情況也是會變的，如果破解的方法被找到，我們當然會立即停用雜湊函式（稍後會討論關於量子計算攻擊的特例）。
我們的目標是使用雜湊函式構造數字簽名方案，因此簡要回顧數字簽名這個詞能帶來很大的幫助。
數字簽名方法源於公鑰的使用，使用者（簽署人）生成一對金鑰：公鑰和私鑰。使用者自行保管私鑰，並能夠用私鑰“簽署”任何訊息，從而產生相應的數字簽名。任何一個持有公鑰的人都能驗證該訊息正確性和相關簽名。
從安全的角度來說，我們希望簽名是不可偽造的，或是說“存在不可偽造性”。這意味著攻擊者（沒有私鑰控制權的人）無法在某段訊息上偽造你的簽名。
Lamport 一次性簽名
在 1979 年，一位名叫 Leslie Lamport 的數學家發明了世界上第一個基於雜湊函式的簽名。Lamport 發現只要使用簡單的雜湊函式，或是單向函式，就可以構建出非常強大的數字簽名方法。
強大的前提是，使用者只需要做一次簽名的動作就能保證安全性！後續會做更詳細的闡述。
為了更好的討論，我們假設以下條件：一個雜湊函式，它能接受 256 位的輸入併產生 256 位的輸出； SHA256 雜湊函式就是個絕佳的示範工具；我們也需要能產生隨機輸入的方法。
假設我們的目標是對 256 位的訊息進行簽名。要得到我們需要的金鑰，首先需要生成隨機的 512 個位字串，每個位字串長度為 256 位。為了便於理解，我們將這些字串列為兩個獨立的表，並以符號代指：
sk0= sk10, sk20, ...,sk2560
sk1= sk11, sk21, ...,sk2561
我們以列表 (sk~0~, sk~1~) 表示用來簽名的 金鑰。接下來為了生成公鑰，我們將隨機的位字串透過 H(.) 進行雜湊運算，得到公鑰如下表：
pk0= H(sk10), H(sk20), ...,H(sk2560)
pk1= H(sk11), H(sk21), ...,H(sk2561)
現在我們可以將公鑰 (pk~0~,pk~1~) 公佈給所有人知道。比如說，我們可以把公鑰發給朋友，嵌入證書中，或是釋出在 Keybase 上。
接著我們使用金鑰對 256 位訊息 M 進行簽名。首先我們得將訊息 M 重現為獨立的 256 位元（Bit，又稱“位元”）：
M1, M2, ..., M256 ∈ {0, 1}
簽名演算法的其餘部分非常簡單。我們從訊息 M 的第 1 位至第 256 位，逐一相應在金鑰列表中的其中一個金鑰上取出字串。而所選金鑰取決於我們要簽名的訊息每一位（bit）的值。
具體一點地說，對於 i = [1,256]，如果第 i 位的訊息位元 Mi = 0，我們會從 sk0 表中選擇第 i 個字元 (ski0) ，作為我們簽名的一部分；如果第 i 位的訊息位元 Mi = 1，我們則從 sk1 表進行前述過程（即，如果我們要對訊息 M 中的第 3 位進行簽名，而該位值為 0，則使用 sk0 中的第三位，sk03，作為我們簽名的一部分）。對每個訊息位元完成此操作後，我們將選中的字串連線，得到簽名。
過程如圖示說明，因為部分過程化簡，金鑰和訊息長度只有 8 個 bit（位元）。要注意的是，每個色塊代表的都是不同的隨機 256 位字串。
當某個使用者（已經知道公鑰 (pk0, pk1)）收到訊息 M 和簽名，她能夠輕易地驗證這個簽名。我們以 si 表示簽名中第 i 個組成部分，使用者能夠檢查相應的訊息 Mi 並計算雜湊值 H(si) 。如果 Mi = 0 ，則雜湊值必須匹配公鑰 pk0 中的元素；如果 Mi = 1 ，則雜湊值必須匹配公鑰 pk1 中的元素。
如果簽名中的每個元素經過雜湊運算後，都能找到對應的正確部分的公鑰，我們就會說這個簽名是有效的。以下是驗證過程圖示，簽名中至少有一個簽名元素：
如果你開始覺得 Lamport 的計劃有些瘋狂，你既是對的，也是錯的。
首先探討下這個數字簽名方法的弊端。我們會發現， Lamport 方法的簽名和金鑰實在太大了，大約有數千 bits。而且更要命的是，這個方法存在嚴重的安全侷限：每個金鑰只能被用來簽名一個訊息，所以 Lamport 方法作為“一次性簽名” 在這裡被拿來舉例。
這種安全侷限為什麼存在呢？回想一下， Lamport 簽名表明了在各個訊息位元上可能的兩個金鑰之一。假如只需要簽署一條資訊，這個簽名方法完全沒問題。然而，如果我簽署了兩條在每一個對應位置 i 的 bit 值都不同的訊息，然後連同金鑰一起傳送出去，這可能導致大問題！
假設攻擊者從不同的訊息得到兩個有效的簽名，她便能夠發起 “混合搭配（mix and match）”攻擊，成功偽造簽署第三條我從未簽名過的資訊。以下圖示說明這個攻擊過程：
這個問題的嚴重程度取決於你簽名的訊息的相異程度，以及有多少訊息被攻擊者給截獲了。但總的來說，這肯定不是件好事。
讓我們總結一下 Lamport 簽名方法；它很簡單、快速，但它在實際應用上還有很多不足之處。或許我們可以做一點最佳化？
從一次性簽名到多次簽名：基於默克爾樹 (Merkle's tree) 的簽名
Lamport 簽名方法是個好的開端，但是無法用單一金鑰簽名多條資訊，是它最大的弊端。Martin Hellman 的學生 Ralph Merkle 由此得到大量啟發，他很快地想到了一個聰明的解決辦法。
雖然我們不打算在這裡展開解釋默克爾方法的步驟，我們還是來試著理清 Ralph 的想法。
我們現在的目標是用 Lamport 簽名方法簽署 N 條資訊。最直觀的方法是，以最初的 Lamport 方法生成 N 個不同的金鑰對，然後將所有公鑰關聯起來，集合成一個超巨大的 mega-key。（mega-key是我現編的術語。）
如果簽名者繼續拿著這麼一把金鑰集合，她就可以對 N 條不同訊息進行簽名，嚴格上來講這也只是一把 Lamport 金鑰。看起來，這樣就解決了金鑰重用的問題。驗證者也有對應的公鑰能夠驗證所有收到的訊息。沒有任何的 Lamport 金鑰被使用兩次。
很明顯的，這種方法很糟糕，因為時間成本太高了。
具體地說，上述這種天真的方法中，為了達到要求的簽名次數，簽名者必須分發比普通 Lamport 公鑰還要大數倍的公鑰（簽名者還要繼續拿著同樣巨大的私鑰）。人們很可能會對這種結果感到不滿，也會反思有沒有辦法避免這種負作用產生。接下來，讓我們進入 Merkle 方法。
Merkle 方法希望能找到一個能簽署多條不同訊息的方法，同時避免公鑰的成本線性激增。Merkle 方法的實現如下：
1.首先，生成 N 個獨立的 Lamport 金鑰，我們以 (PK1, SK1), ..., (PKN, SKN) 表示之。
2.接下來，將每一個公鑰分別放到 Merkle hash tree （見下圖），並計算根節點雜湊值。這個根節點就會成為Merkle簽名方法中的 “主公鑰”。
3.簽名者報關全部的 Lamport 金鑰（公鑰和私鑰），用於簽名。
關於 Merkle tree 的更多描述請點選這裡。概略地說，Merkle 方法提供了一種能收集不同的值，並用一個 “根” 雜湊（例子中使用的雜湊函式，長度為 256 bits）代表所收集的值的方法。給出這個根雜湊，就能簡單“證明” 某個元素存在於這個給出的雜湊樹。而且這個證明的大小和葉節點數量成對數關係。
-Merkle tree，來自維基百科的解釋。Lamport 公鑰被放進葉節點中，然後根節點成為主公鑰。-
要簽名的時候，簽名者從 Merkle tree 中直接選擇公鑰，並用對應的 Lamport 金鑰簽名。接著她將得到的簽名結果連線 Lamport 公鑰並附上“Merkle 證明”。Merkle root 可以來佐證該默克爾樹中包含選中的公鑰（即整個方法使用的公鑰）。最後簽名者將整個集合當作訊息簽名傳送出去。
（驗證者只要直接將這個“簽名”分別解壓為 Lamport 簽名、 Lamport 公鑰、 Merkle 證明，就能進行驗證。驗證者能夠依靠拿到的 Lamport 公鑰驗證 Lamport 簽名，並用 Merkle 證明這把公鑰的確存在於 Merkle tree 中。只要滿足這三個條件，驗證者就能確信簽名是有效的。）
這個方法的缺點是會將“簽名”大小增加兩倍以上。不過，現在 Merkle 方法主要的公鑰只是一串簡單的雜湊值，使得這個方法比上面提到的原始 Lamport 方法更為簡潔。
最後還有個最佳化部分，密碼學強度的偽隨機數發生器能夠輸出生成各式各樣的金鑰，同時“壓縮”金鑰資料本身。這使得原先龐大的位元（顯然是隨機的）能夠轉換為簡短的“種子（seed）”。
很贊啦！
讓簽名和金鑰更有效率一點
Merkle 方法使得一次性簽名轉變為 N 次性簽名。構造這種方法仍然需要基於某些一次性簽名方法，比如 Lamport 方法；但不幸的是，Lamport 方法的（頻寬）成本仍相對高昂。
有兩種主要的方法可以降低這些成本。第一種也是 Merkle 提出的；為了更好的解釋許多強大的簽名方法，我們優先說明這項技術。
回想一下 Lamport 方法，要對一條 256 位的訊息進行簽名，我們需要一個包含 512 個獨立金鑰（和公鑰）位串的向量，簽名本身就是 256 個金鑰位串的集合。（這些數字會被需要簽名的訊息位元啟用，位元可以是 "0" 或 "1" ，因此需要從兩張不同的金鑰表中提取適合的金鑰元素。 ）
這裡引發了新的思考：如果我們不對所有的訊息位元進行簽名，會怎麼樣呢？
更詳細點說，在 Lamport 方法中，我們透過輸出金鑰位串對一條訊息的每個位元進行簽名——無論它的值是什麼。如果我們不要同時簽名一條訊息中 0 和 1 的位元，而是隻簽名 1 的位元，那又會如何呢？這麼做能夠將公鑰和私鑰的大小減半，因為我們可以完全丟掉整條 sk0 列。
現在我們只有單一列位串的金鑰 sk1,...,sk256，對訊息的每個位元 Mi = 1我們都會輸出一個字串 ski；對於訊息的每個位元 Mi = 0我們都會輸出......無（因為許多訊息都會包含很多的 0 位元，這麼做能縮減簽名大小，這些 0 位元將不再帶來任何成本）。
這種方法的明顯缺陷是：它極度不安全，所以請不要這麼做！
舉例來說，假設有個攻擊者觀察到一條已經被簽名的訊息，訊息開頭是“1111...”。現在攻擊者想要在不破壞簽名的情況下，將訊息編輯成“0000...”，只需要刪掉這條簽名中的幾個組成部分即可！簡言之，雖然要將 0 位元“翻轉” 成 1 位元很困難，但反之要將 1 換成 0 就非常簡單了。
現在有了個解決辦法，而且它非常巧妙。
讓我們接著瞧瞧。雖然無法避免攻擊者將訊息中的 1 改成 0 ，但我們能發現這些改動。只要將一個簡單的“校驗和（checksum）”附加到訊息上，然後將訊息和校驗和一起簽名。對於簽名驗證者來說，她必須驗證整份簽名的兩個值，也需要確定收到的校驗和是正確的。
我們使用的校驗和非常小：它由簡單的二進位制整陣列成，表示原始訊息中的所有 0 位元數。
如果攻擊者試圖修改訊息內容（或是校驗和），使得部分 1 位元變成 0 位元，並沒有手段可以阻止她。但是這種攻擊會增加訊息中的 0 位元數，這會使得校驗和無效，驗證者從而會拒絕這個簽名。
當然，機智的攻擊者可能還會試圖混淆校驗和（校驗和也和訊息一起被簽名），增加校驗和的整數值來匹配她篡改的位元數。然而最關鍵的是，因為校驗和是二進位制整數，如果要增加校驗和的值，攻擊者勢必得將一些 0 位元轉換成 1 位元。又因為校驗和也被簽過名，這種簽名方法從源頭阻止這種轉換（將 0 換成 1），因此攻擊者無法得逞。
（如果你繼續記錄下去，的確會增加被簽名的“訊息”的大小。在我們的例子中，一條 256 位的訊息的校驗和，需要額外的 8 位元及增加相應的簽名成本。不過，如果這條訊息包含許多 0 位元，這麼做對於縮減簽名大小仍然非常有效。）
原文連結: https://blog.cryptographyengineering.com/2018/04/07/hash-based-signatures-an-illustrated-primer/
作者: Matthew Green
翻譯&校對: Ian Liu & 阿劍
