文中所講的數字簽名技術，就是我們在密碼學中保證身份同一性所用到的最重要的工具。身份同一性的意思即是，如何證明某條消息就是“我”發出的，別人不能偽造，我也不能抵賴。雖然數字簽名技術也會用到成對的密鑰對，但與我們所說的公鑰密碼學重點卻有所不同。（2）可以將本文視為思考密碼學工具的一個教程或者范本，能耐心讀下去，也就明白了密碼學是怎么樣一回事、我們在密碼學中是如何思考的。

回首近幾年，我有幸經歷了兩個相互沖突、卻又令人著迷的時代潮流變遷。第一個潮流變遷是：專家學者們耗費四十年設計的密碼學，終于派上用場；從信息加密、電話安全、到加密數字貨幣，我們可以在生活的方方面面發現使用密碼學的例子。

第二個潮流變遷是：所有密碼學家已經做好準備，迎接以上美好的幻滅。

正文開始之前我得重申一下，本文所講的不是所謂量子計算啟示錄（末日預言），也不是要講 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 位元，這么做對于縮減簽名大小仍然非常有效。）