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

回首近幾年，我有幸經(jīng)歷了兩個(gè)相互沖突、卻又令人著迷的時(shí)代潮流變遷。第一個(gè)潮流變遷是：專家學(xué)者們耗費(fèi)四十年設(shè)計(jì)的密碼學(xué)，終于派上用場(chǎng)；從信息加密、電話安全、到加密數(shù)字貨幣，我們可以在生活的方方面面發(fā)現(xiàn)使用密碼學(xué)的例子。

第二個(gè)潮流變遷是：所有密碼學(xué)家已經(jīng)做好準(zhǔn)備，迎接以上美好的幻滅。

正文開始之前我得重申一下，本文所講的不是所謂量子計(jì)算啟示錄（末日預(yù)言），也不是要講 21 世紀(jì)密碼學(xué)的成功。我們要談?wù)摰氖橇硪患闯啥ň值氖虑椤艽a學(xué)有史以來(lái)最簡(jiǎn)單的（也是最酷炫的）技術(shù)之一：基于散列函數(shù)的簽名。

在 20 世紀(jì) 70 年代末，Leslie Lamport 發(fā)明了基于哈希函數(shù)（Hash Function，又稱散列函數(shù)）的簽名 ，并經(jīng)過(guò) Ralph Merkle 等人進(jìn)一步改進(jìn)。而后的很多年，這被視為密碼學(xué)領(lǐng)域一灘有趣的“死水”，因?yàn)槌讼鄳?yīng)地產(chǎn)生冗長(zhǎng)的（對(duì)比其他復(fù)雜方案）簽名，基于哈希函數(shù)的簽名好像沒有什么作用。然而近幾年來(lái)，這項(xiàng)技術(shù)似乎有了復(fù)蘇的跡象。這很大程度歸因于它的特性——不同于其他基于RSA或離散對(duì)數(shù)假設(shè)的簽名，哈希函數(shù)簽名被視為可以抵抗量子計(jì)算攻擊（如 Shor‘s 算法）。

首先，我們進(jìn)行一些背景介紹。

背景：哈希函數(shù)和簽名方法

在正式介紹哈希函數(shù)簽名之前，首先你得知道密碼學(xué)中的哈希函數(shù)是什么。哈希函數(shù)可以接受一串字符（任意長(zhǎng)度）作為輸入，經(jīng)過(guò)“消化”后，產(chǎn)生固定長(zhǎng)度的輸出。常見的密碼學(xué)哈希運(yùn)算，像是 SHA2、SHA3 或 Blake2 等，經(jīng)運(yùn)算會(huì)產(chǎn)生長(zhǎng)度介于 256 ~ 512 位的輸出。

一個(gè)函數(shù) H（。） 要被稱作“密碼學(xué)”哈希函數(shù)，必須滿足一些安全性的要求。這些要求有很多，不過(guò)我們主要聚焦在以下三個(gè)方面：

抗-原像攻擊 Pre-image resistance （或俗稱“單向性”）：給定輸出 Y=H（X），想要找到對(duì)應(yīng)的輸入 X 使得 H（X）=Y 是一件“極度費(fèi)時(shí)”的工作。（這里當(dāng)然存在許多例外，但最棒的部分在于，不論 X 屬于什么分布，找到 X 的時(shí)間成本和暴力搜尋相同。）

抗-次原像攻擊：這和前者有些微的差別。給定輸入 X，對(duì)于攻擊者來(lái)說(shuō)，要找到另一個(gè) X’ 使得 H（X）=H（X‘） 是非常困難的。

抗-碰撞：很難找到兩個(gè)輸入 X1， X2，使得 H（X1）=H（X2）。要注意的是，這個(gè)假設(shè)的條件比 抗-次原像攻擊還要嚴(yán)苛。因?yàn)楣粽呖梢詮臒o(wú)垠的選擇中尋找任意兩個(gè)輸入。

我們相信所有本文提到的哈希函數(shù)示例都能提供上述的所有特性。換言之，沒有任何可行的（甚至是概念上的）方法能破解它。當(dāng)然這種情況也是會(huì)變的，如果破解的方法被找到，我們當(dāng)然會(huì)立即停用哈希函數(shù)（稍后會(huì)討論關(guān)于量子計(jì)算攻擊的特例）。

我們的目標(biāo)是使用哈希函數(shù)構(gòu)造數(shù)字簽名方案，因此簡(jiǎn)要回顧數(shù)字簽名這個(gè)詞能帶來(lái)很大的幫助。

數(shù)字簽名方法源于公鑰的使用，使用者（簽署人）生成一對(duì)密鑰：公鑰和私鑰。使用者自行保管私鑰，并能夠用私鑰“簽署”任何消息，從而產(chǎn)生相應(yīng)的數(shù)字簽名。任何一個(gè)持有公鑰的人都能驗(yàn)證該消息正確性和相關(guān)簽名。

從安全的角度來(lái)說(shuō)，我們希望簽名是不可偽造的，或是說(shuō)“存在不可偽造性”。這意味著攻擊者（沒有私鑰控制權(quán)的人）無(wú)法在某段消息上偽造你的簽名。

Lamport 一次性簽名

在 1979 年，一位名叫 Leslie Lamport 的數(shù)學(xué)家發(fā)明了世界上第一個(gè)基于哈希函數(shù)的簽名。Lamport 發(fā)現(xiàn)只要使用簡(jiǎn)單的哈希函數(shù)，或是單向函數(shù)，就可以構(gòu)建出非常強(qiáng)大的數(shù)字簽名方法。

強(qiáng)大的前提是，用戶只需要做一次簽名的動(dòng)作就能保證安全性！后續(xù)會(huì)做更詳細(xì)的闡述。

為了更好的討論，我們假設(shè)以下條件：一個(gè)哈希函數(shù)，它能接受 256 位的輸入并產(chǎn)生 256 位的輸出； SHA256 哈希函數(shù)就是個(gè)絕佳的示范工具；我們也需要能產(chǎn)生隨機(jī)輸入的方法。

假設(shè)我們的目標(biāo)是對(duì) 256 位的消息進(jìn)行簽名。要得到我們需要的密鑰，首先需要生成隨機(jī)的 512 個(gè)位字符串，每個(gè)位字符串長(zhǎng)度為 256 位。為了便于理解，我們將這些字串列為兩個(gè)獨(dú)立的表，并以符號(hào)代指：

sk0= sk10， sk20， 。..，sk2560

sk1= sk11， sk21， 。..，sk2561

我們以列表 （sk~0~， sk~1~） 表示用來(lái)簽名的 密鑰。接下來(lái)為了生成公鑰，我們將隨機(jī)的位字符串通過(guò) H（。） 進(jìn)行哈希運(yùn)算，得到公鑰如下表：

pk0= H（sk10）， H（sk20）， 。..，H（sk2560）

pk1= H（sk11）， H（sk21）， 。..，H（sk2561）

現(xiàn)在我們可以將公鑰 （pk~0~，pk~1~） 公布給所有人知道。比如說(shuō)，我們可以把公鑰發(fā)給朋友，嵌入證書中，或是發(fā)布在 Keybase 上。

接著我們使用密鑰對(duì) 256 位消息 M 進(jìn)行簽名。首先我們得將消息 M 重現(xiàn)為獨(dú)立的 256 位元（Bit，又稱“比特”）：

M1， M2， 。..， M256 ∈ {0， 1}

簽名算法的其余部分非常簡(jiǎn)單。我們從消息 M 的第 1 位至第 256 位，逐一相應(yīng)在密鑰列表中的其中一個(gè)密鑰上取出字符串。而所選密鑰取決于我們要簽名的消息每一位（bit）的值。

具體一點(diǎn)地說(shuō)，對(duì)于 i = ［1，256］，如果第 i 位的消息位元 Mi = 0，我們會(huì)從 sk0 表中選擇第 i 個(gè)字符 （ski0） ，作為我們簽名的一部分；如果第 i 位的消息位元 Mi = 1，我們則從 sk1 表進(jìn)行前述過(guò)程（即，如果我們要對(duì)消息 M 中的第 3 位進(jìn)行簽名，而該位值為 0，則使用 sk0 中的第三位，sk03，作為我們簽名的一部分）。對(duì)每個(gè)消息位元完成此操作后，我們將選中的字符串連接，得到簽名。

過(guò)程如圖示說(shuō)明，因?yàn)椴糠诌^(guò)程化簡(jiǎn)，密鑰和消息長(zhǎng)度只有 8 個(gè) bit（位元）。要注意的是，每個(gè)色塊代表的都是不同的隨機(jī) 256 位字符串。

當(dāng)某個(gè)用戶（已經(jīng)知道公鑰 （pk0， pk1））收到消息 M 和簽名，她能夠輕易地驗(yàn)證這個(gè)簽名。我們以 si 表示簽名中第 i 個(gè)組成部分，用戶能夠檢查相應(yīng)的消息 Mi 并計(jì)算哈希值 H（si） 。如果 Mi = 0 ，則哈希值必須匹配公鑰 pk0 中的元素；如果 Mi = 1 ，則哈希值必須匹配公鑰 pk1 中的元素。

如果簽名中的每個(gè)元素經(jīng)過(guò)哈希運(yùn)算后，都能找到對(duì)應(yīng)的正確部分的公鑰，我們就會(huì)說(shuō)這個(gè)簽名是有效的。以下是驗(yàn)證過(guò)程圖示，簽名中至少有一個(gè)簽名元素：

如果你開始覺得 Lamport 的計(jì)劃有些瘋狂，你既是對(duì)的，也是錯(cuò)的。

首先探討下這個(gè)數(shù)字簽名方法的弊端。我們會(huì)發(fā)現(xiàn)， Lamport 方法的簽名和密鑰實(shí)在太大了，大約有數(shù)千 bits。而且更要命的是，這個(gè)方法存在嚴(yán)重的安全局限：每個(gè)密鑰只能被用來(lái)簽名一個(gè)消息，所以 Lamport 方法作為“一次性簽名” 在這里被拿來(lái)舉例。

這種安全局限為什么存在呢？回想一下， Lamport 簽名表明了在各個(gè)消息位元上可能的兩個(gè)密鑰之一。假如只需要簽署一條信息，這個(gè)簽名方法完全沒問(wèn)題。然而，如果我簽署了兩條在每一個(gè)對(duì)應(yīng)位置 i 的 bit 值都不同的消息，然后連同密鑰一起發(fā)送出去，這可能導(dǎo)致大問(wèn)題！

假設(shè)攻擊者從不同的消息得到兩個(gè)有效的簽名，她便能夠發(fā)起 “混合搭配（mix and match）”攻擊，成功偽造簽署第三條我從未簽名過(guò)的信息。以下圖示說(shuō)明這個(gè)攻擊過(guò)程：

這個(gè)問(wèn)題的嚴(yán)重程度取決于你簽名的消息的相異程度，以及有多少消息被攻擊者給截獲了。但總的來(lái)說(shuō)，這肯定不是件好事。

讓我們總結(jié)一下 Lamport 簽名方法；它很簡(jiǎn)單、快速，但它在實(shí)際應(yīng)用上還有很多不足之處。或許我們可以做一點(diǎn)優(yōu)化？

從一次性簽名到多次簽名：基于默克爾樹 （Merkle’s tree） 的簽名

Lamport 簽名方法是個(gè)好的開端，但是無(wú)法用單一密鑰簽名多條信息，是它最大的弊端。Martin Hellman 的學(xué)生 Ralph Merkle 由此得到大量啟發(fā)，他很快地想到了一個(gè)聰明的解決辦法。

雖然我們不打算在這里展開解釋默克爾方法的步驟，我們還是來(lái)試著理清 Ralph 的想法。

我們現(xiàn)在的目標(biāo)是用 Lamport 簽名方法簽署 N 條信息。最直觀的方法是，以最初的 Lamport 方法生成 N 個(gè)不同的密鑰對(duì)，然后將所有公鑰關(guān)聯(lián)起來(lái)，集合成一個(gè)超巨大的 mega-key。（mega-key是我現(xiàn)編的術(shù)語(yǔ)。）

如果簽名者繼續(xù)拿著這么一把密鑰集合，她就可以對(duì) N 條不同消息進(jìn)行簽名，嚴(yán)格上來(lái)講這也只是一把 Lamport 密鑰?？雌饋?lái)，這樣就解決了密鑰重用的問(wèn)題。驗(yàn)證者也有對(duì)應(yīng)的公鑰能夠驗(yàn)證所有收到的消息。沒有任何的 Lamport 密鑰被使用兩次。

很明顯的，這種方法很糟糕，因?yàn)闀r(shí)間成本太高了。

具體地說(shuō)，上述這種天真的方法中，為了達(dá)到要求的簽名次數(shù)，簽名者必須分發(fā)比普通 Lamport 公鑰還要大數(shù)倍的公鑰（簽名者還要繼續(xù)拿著同樣巨大的私鑰）。人們很可能會(huì)對(duì)這種結(jié)果感到不滿，也會(huì)反思有沒有辦法避免這種負(fù)作用產(chǎn)生。接下來(lái)，讓我們進(jìn)入 Merkle 方法。

Merkle 方法希望能找到一個(gè)能簽署多條不同消息的方法，同時(shí)避免公鑰的成本線性激增。Merkle 方法的實(shí)現(xiàn)如下：

1.首先，生成 N 個(gè)獨(dú)立的 Lamport 密鑰，我們以 （PK1， SK1）， 。..， （PKN， SKN） 表示之。

2.接下來(lái)，將每一個(gè)公鑰分別放到 Merkle hash tree （見下圖），并計(jì)算根節(jié)點(diǎn)哈希值。這個(gè)根節(jié)點(diǎn)就會(huì)成為Merkle簽名方法中的 “主公鑰”。

3.簽名者報(bào)關(guān)全部的 Lamport 密鑰（公鑰和私鑰），用于簽名。

關(guān)于 Merkle tree 的更多描述請(qǐng)點(diǎn)擊這里。概略地說(shuō)，Merkle 方法提供了一種能收集不同的值，并用一個(gè) “根” 哈希（例子中使用的哈希函數(shù)，長(zhǎng)度為 256 bits）代表所收集的值的方法。給出這個(gè)根哈希，就能簡(jiǎn)單“證明” 某個(gè)元素存在于這個(gè)給出的哈希樹。而且這個(gè)證明的大小和葉節(jié)點(diǎn)數(shù)量成對(duì)數(shù)關(guān)系。

-Merkle tree，來(lái)自維基百科的解釋。Lamport 公鑰被放進(jìn)葉節(jié)點(diǎn)中，然后根節(jié)點(diǎn)成為主公鑰。-

要簽名的時(shí)候，簽名者從 Merkle tree 中直接選擇公鑰，并用對(duì)應(yīng)的 Lamport 密鑰簽名。接著她將得到的簽名結(jié)果連接 Lamport 公鑰并附上“Merkle 證明”。Merkle root 可以來(lái)佐證該默克爾樹中包含選中的公鑰（即整個(gè)方法使用的公鑰）。最后簽名者將整個(gè)集合當(dāng)作消息簽名發(fā)送出去。

（驗(yàn)證者只要直接將這個(gè)“簽名”分別解壓為 Lamport 簽名、 Lamport 公鑰、 Merkle 證明，就能進(jìn)行驗(yàn)證。驗(yàn)證者能夠依靠拿到的 Lamport 公鑰驗(yàn)證 Lamport 簽名，并用 Merkle 證明這把公鑰的確存在于 Merkle tree 中。只要滿足這三個(gè)條件，驗(yàn)證者就能確信簽名是有效的。）

這個(gè)方法的缺點(diǎn)是會(huì)將“簽名”大小增加兩倍以上。不過(guò)，現(xiàn)在 Merkle 方法主要的公鑰只是一串簡(jiǎn)單的哈希值，使得這個(gè)方法比上面提到的原始 Lamport 方法更為簡(jiǎn)潔。

最后還有個(gè)優(yōu)化部分，密碼學(xué)強(qiáng)度的偽隨機(jī)數(shù)發(fā)生器能夠輸出生成各式各樣的密鑰，同時(shí)“壓縮”密鑰數(shù)據(jù)本身。這使得原先龐大的位元（顯然是隨機(jī)的）能夠轉(zhuǎn)換為簡(jiǎn)短的“種子（seed）”。

很贊啦！

讓簽名和密鑰更有效率一點(diǎn)

Merkle 方法使得一次性簽名轉(zhuǎn)變?yōu)?N 次性簽名。構(gòu)造這種方法仍然需要基于某些一次性簽名方法，比如 Lamport 方法；但不幸的是，Lamport 方法的（帶寬）成本仍相對(duì)高昂。

有兩種主要的方法可以降低這些成本。第一種也是 Merkle 提出的；為了更好的解釋許多強(qiáng)大的簽名方法，我們優(yōu)先說(shuō)明這項(xiàng)技術(shù)。

回想一下 Lamport 方法，要對(duì)一條 256 位的消息進(jìn)行簽名，我們需要一個(gè)包含 512 個(gè)獨(dú)立密鑰（和公鑰）位串的向量，簽名本身就是 256 個(gè)密鑰位串的集合。（這些數(shù)字會(huì)被需要簽名的消息位元激活，位元可以是 “0” 或 “1” ，因此需要從兩張不同的密鑰表中提取適合的密鑰元素。 ）

這里引發(fā)了新的思考：如果我們不對(duì)所有的消息位元進(jìn)行簽名，會(huì)怎么樣呢？

更詳細(xì)點(diǎn)說(shuō)，在 Lamport 方法中，我們通過(guò)輸出密鑰位串對(duì)一條消息的每個(gè)位元進(jìn)行簽名——無(wú)論它的值是什么。如果我們不要同時(shí)簽名一條消息中 0 和 1 的位元，而是只簽名 1 的位元，那又會(huì)如何呢？這么做能夠?qū)⒐€和私鑰的大小減半，因?yàn)槲覀兛梢酝耆珌G掉整條 sk0 列。

現(xiàn)在我們只有單一列位串的密鑰 sk1，。..，sk256，對(duì)消息的每個(gè)位元 Mi = 1我們都會(huì)輸出一個(gè)字符串 ski；對(duì)于消息的每個(gè)位元 Mi = 0我們都會(huì)輸出。..。..無(wú)（因?yàn)樵S多消息都會(huì)包含很多的 0 位元，這么做能縮減簽名大小，這些 0 位元將不再帶來(lái)任何成本）。

這種方法的明顯缺陷是：它極度不安全，所以請(qǐng)不要這么做！

舉例來(lái)說(shuō)，假設(shè)有個(gè)攻擊者觀察到一條已經(jīng)被簽名的消息，消息開頭是“1111.。.”?，F(xiàn)在攻擊者想要在不破壞簽名的情況下，將消息編輯成“0000.。.”，只需要?jiǎng)h掉這條簽名中的幾個(gè)組成部分即可！簡(jiǎn)言之，雖然要將 0 位元“翻轉(zhuǎn)” 成 1 位元很困難，但反之要將 1 換成 0 就非常簡(jiǎn)單了。

現(xiàn)在有了個(gè)解決辦法，而且它非常巧妙。

讓我們接著瞧瞧。雖然無(wú)法避免攻擊者將消息中的 1 改成 0 ，但我們能發(fā)現(xiàn)這些改動(dòng)。只要將一個(gè)簡(jiǎn)單的“校驗(yàn)和（checksum）”附加到消息上，然后將消息和校驗(yàn)和一起簽名。對(duì)于簽名驗(yàn)證者來(lái)說(shuō)，她必須驗(yàn)證整份簽名的兩個(gè)值，也需要確定收到的校驗(yàn)和是正確的。

我們使用的校驗(yàn)和非常?。核珊?jiǎn)單的二進(jìn)制整數(shù)組成，表示原始消息中的所有 0 位元數(shù)。

如果攻擊者試圖修改消息內(nèi)容（或是校驗(yàn)和），使得部分 1 位元變成 0 位元，并沒有手段可以阻止她。但是這種攻擊會(huì)增加消息中的 0 位元數(shù)，這會(huì)使得校驗(yàn)和無(wú)效，驗(yàn)證者從而會(huì)拒絕這個(gè)簽名。

當(dāng)然，機(jī)智的攻擊者可能還會(huì)試圖混淆校驗(yàn)和（校驗(yàn)和也和消息一起被簽名），增加校驗(yàn)和的整數(shù)值來(lái)匹配她篡改的位元數(shù)。然而最關(guān)鍵的是，因?yàn)樾ｒ?yàn)和是二進(jìn)制整數(shù)，如果要增加校驗(yàn)和的值，攻擊者勢(shì)必得將一些 0 位元轉(zhuǎn)換成 1 位元。又因?yàn)樾ｒ?yàn)和也被簽過(guò)名，這種簽名方法從源頭阻止這種轉(zhuǎn)換（將 0 換成 1），因此攻擊者無(wú)法得逞。

（如果你繼續(xù)記錄下去，的確會(huì)增加被簽名的“消息”的大小。在我們的例子中，一條 256 位的消息的校驗(yàn)和，需要額外的 8 位元及增加相應(yīng)的簽名成本。不過(guò)，如果這條消息包含許多 0 位元，這么做對(duì)于縮減簽名大小仍然非常有效。）