警告：及其不可靠的密碼學(xué)文章，可能很愚蠢，寫到哪算哪

應(yīng)用密碼學(xué)（也許是整個(gè)計(jì)算機(jī)科學(xué)）中最困難的一件事就是解釋為什么我們所使用的工具是正確的。我們從前人那里獲得了一個(gè)珍貴的籃子，里面裝滿了有用的算法。對(duì)那些實(shí)踐主義者來(lái)說(shuō)，直接拿這些算法來(lái)用也是很合理的。但有的時(shí)候，這種做法讓我們好奇為什么這些算法要這么做。我們此時(shí)不如仔細(xì)想想這些算法到底在干什么，以及在發(fā)明者想出這些算法的時(shí)候，他們腦子里又是怎么思考的。

在這一篇文章中我想聊聊簽名算法，具體來(lái)說(shuō)是Schnorr簽名，以及一些相關(guān)的算法，比如ECDSA（橢圓曲線數(shù)字簽名算法）。這些簽名算法有不少有趣的性質(zhì)，使得他們?cè)诿艽a學(xué)構(gòu)造中比較特殊。了解Schnorr簽名的本質(zhì)也有助于理解一系列最近的工作，包括像Dilithium這樣的抗量子協(xié)議——我們會(huì)在下一篇文章中討論這個(gè)協(xié)議。

這條推特給了我寫這篇文章的動(dòng)機(jī)：

比起直接把Schnorr簽名丟給你，我打算用一些更彎彎繞繞的方法來(lái)介紹。我們從最基本的組成部分開始（包括一個(gè)身份識(shí)別方案的基本概念），然后一點(diǎn)點(diǎn)搭建Schnorr簽名的框架。

身份識(shí)別方案：最有用的磚頭

如果你想理解Schnorr簽名，你首先得了解的是它們根本不是真正為簽名設(shè)計(jì)的，至少一開始不是。Schnorr協(xié)議最初被設(shè)計(jì)為一種交互式識(shí)別方案，可以“扁平化”為我們熟悉和喜愛的簽名方案。

一個(gè)身份識(shí)別方案由用于生成包含公鑰和私鑰的“密鑰對(duì)”的密鑰生成算法以及使用這些密鑰的交互協(xié)議（“識(shí)別協(xié)議”）組成。公鑰代表其所有者的身份，可以分發(fā)給任何人。私鑰則自然是秘密的。我們假設(shè)它是由其所有者存儲(chǔ)的，之后所有者可以使用它來(lái)證明它“擁有”公鑰。

識(shí)別協(xié)議本身在兩方之間交互運(yùn)行——這意味著雙方將交換多個(gè)消息。我們經(jīng)常將這些參與方稱為“證明者”（Prover）和“驗(yàn)證者”（Verifier），許多舊論文曾經(jīng)給他們起了可愛的名字，例如“Peggy”和“Victor”。我覺得這有點(diǎn)矯情，但在這次討論中我會(huì)沿用，因?yàn)槲移鸩怀龈玫拿?。（譯者注：這就像傳統(tǒng)密碼協(xié)議演示中的Alice和Bob，只不過(guò)那里是A和B，這里是P和V）

要開始識(shí)別協(xié)議，Victor必須獲得Peggy公鑰的副本。Peggy擁有她的私鑰。該協(xié)議的目標(biāo)是讓Victor決定他是否信任Peggy：

請(qǐng)注意，這種“所有權(quán)證明”不需要100%完美。我們只要求它以極高的概率是正確的。粗略地說(shuō)，我們要確保如果Peggy真的擁有鑰匙，那么Victor將永遠(yuǎn)相信這一事實(shí)。與此同時(shí)，冒充Peggy的人——即不知道她的私鑰——應(yīng)該無(wú)法說(shuō)服Victor，這件事發(fā)生的概率應(yīng)該非常?。梢院雎圆挥?jì)的）。

（為什么我們?cè)试S冒充者以這種微小概率成功？事實(shí)證明，這對(duì)于任何識(shí)別協(xié)議來(lái)說(shuō)基本上都是不可避免的。這是因?yàn)镻eggy發(fā)送給Victor的消息大小必須是有限的，顯然至少必須存在一個(gè)會(huì)讓Victor接受的“成功”響應(yīng)（真實(shí)的Peggy給出的消息）。因此，總會(huì)有這么一個(gè)壞人，他瞎猜一個(gè)字符串，還真猜中了。只要Peggy發(fā)送的位數(shù)相當(dāng)大，那么這樣一個(gè)“愚蠢”的壞人就應(yīng)該幾乎永遠(yuǎn)不會(huì)成功，但這個(gè)概率永遠(yuǎn)不是零。）

上面的描述幾乎足以解釋識(shí)別方案的安全目標(biāo)，但還不夠完整。如果是的話，那么就會(huì)有一個(gè)非常簡(jiǎn)單（但顯然很糟糕）的協(xié)議來(lái)解決這個(gè)問(wèn)題：證明者可以簡(jiǎn)單地將其私鑰傳輸給驗(yàn)證者，驗(yàn)證者可以測(cè)試它是否與公鑰匹配：

如果我們只關(guān)心在一個(gè)只有一個(gè)驗(yàn)證者且只需要運(yùn)行協(xié)議一次的世界中證明所有權(quán)的基本問(wèn)題，那么上面的協(xié)議就可以正常工作！不幸的是，在現(xiàn)實(shí)世界中，我們經(jīng)常需要向多個(gè)不同的驗(yàn)證者證明身份，或者反復(fù)說(shuō)服同一個(gè)驗(yàn)證者。上述稻草人提案的問(wèn)題在于，在一次執(zhí)行結(jié)束時(shí)，Victor已經(jīng)知道了Peggy的私鑰（就像任何其他碰巧竊聽了他們通信的人一樣）。這意味著Victor或任何竊聽者現(xiàn)在都能夠在以后的互動(dòng)中冒充Peggy。

對(duì)于識(shí)別協(xié)議來(lái)說(shuō)，這相當(dāng)壞。為了解決這個(gè)問(wèn)題，一個(gè)真正有用的身份識(shí)別協(xié)議應(yīng)該至少添加一個(gè)額外的安全要求：在完成這個(gè)協(xié)議后，Victor（或竊聽者）不應(yīng)該獲得向另一個(gè)驗(yàn)證者模仿Peggy身份的能力。上述協(xié)議顯然不符合這一要求，因?yàn)閂ictor現(xiàn)在將擁有Peggy曾經(jīng)擁有的所有秘密信息。

這一要求也有助于解釋為什么識(shí)別協(xié)議（必然）是交互式的，或者至少是有狀態(tài)的：即使Victor沒有收到Peggy的密鑰，他仍然可以記錄Peggy在與他執(zhí)行協(xié)議期間發(fā)送的任何消息。如果協(xié)議是完全非交互式的（也就是說(shuō)，它只包含從Peggy到Victor的一條消息），那么Victor稍后可以向其他驗(yàn)證者“重播”他錄制的消息，從而讓那個(gè)人相信他實(shí)際上是Peggy。許多協(xié)議都遇到了這個(gè)問(wèn)題，包括一些老舊的車鑰匙。

這一問(wèn)題的經(jīng)典解決方案是將設(shè)計(jì)一種由多個(gè)交互動(dòng)作組成的挑戰(zhàn)-響應(yīng)結(jié)構(gòu)識(shí)別協(xié)議。在這種方法中，Victor首先向Peggy發(fā)送一些隨機(jī)的“挑戰(zhàn)”消息，然后Peggy對(duì)應(yīng)地生成她的響應(yīng)。如果惡意的Victor試圖向不同的驗(yàn)證者冒充Peggy，比如說(shuō)Veronica，則Veronica很可能發(fā)送不同的挑戰(zhàn)值，因此Victor將無(wú)法使用Peggy的原始響應(yīng)來(lái)回應(yīng)Veronica的新挑戰(zhàn)。

（雖然通常需要交互，但在某些情況下，我們似乎可以通過(guò)“從環(huán)境中提取挑戰(zhàn)”來(lái)“繞過(guò)”這一要求。例如，現(xiàn)實(shí)世界的協(xié)議有時(shí)會(huì)將識(shí)別協(xié)議“綁定”到時(shí)間戳、交易詳細(xì)信息或驗(yàn)證者的姓名等元數(shù)據(jù)。這并不能嚴(yán)格防止重播攻擊——單消息協(xié)議的重播總是可能的！——但它可以幫助驗(yàn)證者檢測(cè)并拒絕此類重播。例如，Veronica可能不會(huì)接受過(guò)時(shí)的消息。我更愿意這么說(shuō)，廣義上來(lái)看，這些協(xié)議仍然是交互式的。只是交互的第一步[例如，查詢時(shí)鐘的時(shí)間戳]現(xiàn)在被移到了協(xié)議之外。）

我們?nèi)绾螛?gòu)造身份識(shí)別方案？

現(xiàn)在我們認(rèn)識(shí)了識(shí)別方案，顯而易見的問(wèn)題是如何構(gòu)建一個(gè)識(shí)別方案。

可能最簡(jiǎn)單的想法是使用某種單向函數(shù)作為地基。這些函數(shù)的關(guān)鍵特征是它們?cè)谝粋€(gè)方向上計(jì)算起來(lái)“容易”（例如，對(duì)于某些字符串 x ，可以非常有效地計(jì)算函數(shù) F(x) 。）同時(shí)，單向函數(shù)很難求逆：這意味著給定某個(gè)隨機(jī)輸入字符串 x 的 F(x) —讓我們假設(shè) $x$ 是128位字符串—應(yīng)該需要大量的計(jì)算工作才能恢復(fù) x。

選擇單向函數(shù)是因?yàn)槲覀冇泻芏嗫捎玫膯雾?xiàng)函數(shù)構(gòu)造，包括密碼學(xué)哈希函數(shù)以及更奇特的數(shù)論構(gòu)造。理論密碼學(xué)家也更偏愛這一假設(shè)，因?yàn)榇祟惡瘮?shù)的存在被認(rèn)為是我們擁有的最“合理”的密碼假設(shè)之一，這意味著它們比更奇特的假設(shè)更有可能存在。（譯者注：我們現(xiàn)在對(duì)于單項(xiàng)函數(shù)“存在”以及對(duì)其的構(gòu)造是基于假設(shè)的，即“我們猜測(cè)它是對(duì)的”。大部分密碼學(xué)協(xié)議都基于這樣或那樣的假設(shè)，在此之中單向函數(shù)是人們認(rèn)為“比較可能是真的”的那一種。）

問(wèn)題在于，從簡(jiǎn)單的單向函數(shù)構(gòu)建識(shí)別協(xié)議并不容易。一個(gè)比較容易想到的起點(diǎn)是Peggy通過(guò)選擇隨機(jī)字符串 sk?（例如，128位隨機(jī)字符串）來(lái)構(gòu)建她的秘密密鑰，然后將她的公鑰計(jì)算為 pk=F(sk)。

現(xiàn)在要進(jìn)行身份識(shí)別協(xié)議，Peggy會(huì)……嗯……好吧，目前還不清楚她會(huì)做什么。

“顯而易見”的答案是Peggy將她的秘密密鑰 sk 發(fā)送給Victor，然后Victor可以檢查 pk=F(sk)。但由于之前提到的原因，這是壞的：只要Peggy與他進(jìn)行了一次協(xié)議，Victor就可以冒充Peggy。解決這個(gè)問(wèn)題可不簡(jiǎn)單。

當(dāng)然，有一些聰明的解決方案，但每種解決方案都有一些限制和成本?！懊耖g傳說(shuō)”[1]方法的運(yùn)作方式如下：

1. Peggy沒有選擇一個(gè)秘密字符串，而是選擇了N個(gè)不同的秘密字符串 sk1,…,sk_N?作為她的“秘密密鑰”。

2. 她現(xiàn)在將她的“公鑰”設(shè)置 為 pk=F(sk1),…,F(sk_N)。

3. 在識(shí)別協(xié)議中，Victor將向Peggy提出挑戰(zhàn)，要求她提供Peggy字符串一個(gè)大小為 k 的子集（這里 k 比 N 小得多。）

4. Peggy將發(fā)回適當(dāng)?shù)?k 個(gè)秘密字符串列表。

5. Victor將根據(jù)Peggy公鑰中的適當(dāng)位置檢查每個(gè)字符串。

這里的想法是，在運(yùn)行該協(xié)議一次后，Victor知道了Peggy的一些但不是全部秘密字符串。如果Victor然后嘗試向另一個(gè)人（例如維羅妮卡）冒充Peggy，那么維羅妮卡會(huì)選擇她自己的大小為 k?的子集供Victor做出響應(yīng)。如果這個(gè)子集與Victor在與Peggy互動(dòng)時(shí)選擇的子集相同，那么Victor就會(huì)成功：否則，Victor將無(wú)法回答維羅妮卡的挑戰(zhàn)。通過(guò)仔細(xì)選擇 N 和 k 的值，我們可以確保這種概率非常小。[2]

該提案的一個(gè)明顯問(wèn)題是，如果Victor能夠說(shuō)服Peggy與他一起多次運(yùn)行該協(xié)議，它很快就會(huì)崩潰。

如果Victor可以向Peggy發(fā)送幾個(gè)不同的挑戰(zhàn)，他將了解到超過(guò) k 個(gè)Peggy的秘密字符串。隨著Victor學(xué)習(xí)的字符串?dāng)?shù)量的增加，Victor回答維羅妮卡詢問(wèn)的能力將顯著提高：最終他幾乎可以一直模仿Peggy。有一些聰明的方法可以解決這個(gè)問(wèn)題，同時(shí)仍然使用簡(jiǎn)單的單向函數(shù)，但它們?cè)趲捄陀?jì)算方面往往相對(duì)“高級(jí)”并且成本高昂。（我保證會(huì)在其他文章中討論它們。）

Schnorr

到目前為止，我們有一個(gè)動(dòng)機(jī)：我們希望構(gòu)建一個(gè)多用途的識(shí)別協(xié)議——從某種意義上說(shuō)，Peggy可以與Victor（或其他驗(yàn)證者）多次運(yùn)行該協(xié)議，而不會(huì)失去安全性。同時(shí)，這種方法也是高效的,Peggy不必與Victor交換大量數(shù)據(jù)或擁有大量公鑰。

現(xiàn)在已經(jīng)出現(xiàn)了大量的身份識(shí)別協(xié)議。Schnorr的協(xié)議甚至也不是完全原創(chuàng)的?！癝chnorr”只恰好是我們通常用于滿足這一特定要求的一類高效協(xié)議的名稱。

當(dāng)Twitter還不叫X的時(shí)候，我問(wèn)是否有人可以用兩條或更少的推文描述Schnorr協(xié)議的基本原理。我承認(rèn)我正在尋找一個(gè)特定的答案，我從Chris Peikert那里得到了它：

我真的很喜歡Chris對(duì)Schnorr協(xié)議的解釋，我已經(jīng)迫不及待想把這個(gè)解釋進(jìn)一步展開了。我保證你只需要一點(diǎn)中學(xué)代數(shù)和一個(gè)“魔盒”就能理解它。我們稍后會(huì)揭開這個(gè)魔盒的秘密。

讓我們一步一步地解開這個(gè)謎語(yǔ)。

首先，Chris建議Peggy必須選擇“一條隨機(jī)直線”?；叵胍幌滦W(xué)代數(shù)，直線的方程是 y=mx+b，其中 “m” 是直線的斜率，“b” 是其y軸截距。因此，Chris實(shí)際上要求我們選擇一對(duì)隨機(jī)數(shù) (m,b)。（你可以假裝這些是某個(gè)范圍內(nèi)的實(shí)數(shù)。但是我們會(huì)把它當(dāng)做一個(gè)非常大的有限域中的元素，這將解決許多問(wèn)題。）

這里我們讓 “m” 作為Peggy的密鑰，她會(huì)選擇一次并永遠(yuǎn)保持不變。Peggy每次運(yùn)行協(xié)議時(shí)都會(huì)選擇一個(gè)新的隨機(jī)值 “b” 。至關(guān)重要的是，Peggy會(huì)將這兩個(gè)數(shù)字放入Chris的一對(duì)魔盒中，然后將它們發(fā)送給Victor。

最后，Victor的挑戰(zhàn)是讓Peggy在他選擇的一個(gè)特定（隨機(jī)）點(diǎn) x?處計(jì)算對(duì)應(yīng)的 y。這對(duì)于Peggy來(lái)說(shuō)很容易，她可以使用她的線性方程計(jì)算相應(yīng)的值y?，F(xiàn)在Victor擁有一個(gè)點(diǎn) (x,y)，如果Peggy回答正確的話，該點(diǎn)應(yīng)該位于?(m,b) 定義的直線上。他只需要使用“魔盒”來(lái)驗(yàn)證這一事實(shí)即可。

這是整個(gè)協(xié)議：

顯然這不是一個(gè)真正的協(xié)議，因?yàn)樗枰Хú拍苓\(yùn)行。話雖如此，它仍然有一些不錯(cuò)的功能。

關(guān)于該協(xié)議，我們可以觀察到的第一件事是，如果最終檢查通過(guò)了，那么Victor應(yīng)該有理由相信他真的在與Peggy交談。我在此給出一個(gè)直觀的（非正式的?。┱撟C。我們注意到，要完成協(xié)議，Peggy必須回答Victor選擇的任何隨機(jī)x的查詢。如果Peggy或冒充Peggy的人能夠以高概率對(duì)Victor可能選擇的任何隨機(jī)點(diǎn)x執(zhí)行此操作，那么直觀上她可以（至少在她自己的頭腦中）為第二個(gè)隨機(jī)點(diǎn)x'計(jì)算類似的響應(yīng)。給定兩個(gè)在同一條線上的點(diǎn) (x,y)、(x′,y′)，很容易計(jì)算秘密斜率 m?。因此，能夠輕松計(jì)算線上點(diǎn)的人幾乎肯定知道Peggy的密鑰。（這不是證明！這只是一種直覺。但真正的證明使用了類似的原理。[3]）（譯者注：這里原為腳注2，疑為原作者筆誤）

那么現(xiàn)在，問(wèn)題回到了Victor在與Peggy運(yùn)行協(xié)議后了解到了什么。

如果我們忽略協(xié)議里的魔法盒子，Victor在協(xié)議結(jié)束時(shí)“學(xué)習(xí)”的唯一東西就是碰巧位于Peggy選擇的隨機(jī)線上的單個(gè)點(diǎn) (x,y) 。幸運(yùn)的是，這并沒有透露太多關(guān)于這條線的信息，特別是，它并沒有透露太多關(guān)于她的私鑰（斜率）的信息。原因是，對(duì)于Peggy可能選擇作為關(guān)鍵的每個(gè)可能的斜率值m，都存在一個(gè)值b，該值生成一條與 (x,y) 相交的線。我們可以用幾個(gè)不同的例子來(lái)形象地說(shuō)明這一點(diǎn)：

如果Victor看到同一條線上兩個(gè)不同的點(diǎn)，協(xié)議就會(huì)出問(wèn)題。幸運(yùn)的是，這種情況永遠(yuǎn)不會(huì)發(fā)生，因?yàn)镻eggy每次運(yùn)行協(xié)議時(shí)都會(huì)選擇不同的線（通過(guò)選擇新的b值）。（如果她忘記這樣做，那將是一場(chǎng)可怕的災(zāi)難！）

這些魔盒的存在顯然讓安全性變得有些微妙，因?yàn)楝F(xiàn)在Victor可以使用“魔盒”進(jìn)行各種測(cè)試，測(cè)試 m、b?的不同值，看看是否能找到匹配的線。但幸運(yùn)的是，這些盒子是“魔法”的，從某種意義上說(shuō)，Victor真正能做的就是測(cè)試一個(gè)點(diǎn)是否在線上：由于m有許多可能的值，這意味著暴力窮舉將花費(fèi)太長(zhǎng)時(shí)間，不太現(xiàn)實(shí)。

現(xiàn)在，你可能會(huì)問(wèn)：為什么要一條線？為什么不是一個(gè)平面，或者一個(gè)8次多項(xiàng)式？

答案非常簡(jiǎn)單：直線恰好是滿足我們需求的最簡(jiǎn)單的數(shù)學(xué)結(jié)構(gòu)之一。我們需要一個(gè)方程，我們可以“安全”地揭示一個(gè)解，而無(wú)需完全給出方程的項(xiàng)。高階多項(xiàng)式和平面方程也具有這種功能（實(shí)際上我們可以揭示這些結(jié)構(gòu)中的更多點(diǎn)），但每個(gè)方程都有一個(gè)更大、更復(fù)雜的方程，需要更魔法的“魔盒”。

我們?nèi)绾沃馈澳Ш小笔欠褡銐蚰Хǎ?/h1>

通常當(dāng)人們學(xué)習(xí)Schnorr時(shí)，他們不會(huì)學(xué)習(xí)有關(guān)魔盒的知識(shí)。事實(shí)上，他們通常會(huì)看到一堆關(guān)于循環(huán)群的無(wú)聊細(xì)節(jié)。

這種方法的問(wèn)題在于，它沒有告訴我們，我們到底需要這個(gè)魔盒滿足什么性質(zhì)。這帶來(lái)了不少問(wèn)題，因?yàn)槲覀儾⒉皇侵挥幸粋€(gè)特定的盒子可以用來(lái)實(shí)現(xiàn)此類協(xié)議。事實(shí)上，最好將該協(xié)議視為一個(gè)類似于程序設(shè)計(jì)中泛型的概念，可以用不同的“魔盒”來(lái)實(shí)例化。

因此：我將嘗試一種不同的方法。我不會(huì)提供給你一個(gè)能被當(dāng)做魔盒使用的妙妙工具，而是嘗試找出我們的魔盒必須具有哪些屬性。（譯者注：提供一個(gè)接口（interface, trait）而非實(shí)例（concrete type））

模擬Peggy

安全的識(shí)別協(xié)議本質(zhì)上有三個(gè)要求。首先，協(xié)議需要正確（Correctness）——這意味著Victor在與Peggy進(jìn)行正確的互動(dòng)后始終相信Peggy的身份。其次，它必須是有效的（Soundness），這意味著只有Peggy（而不是模仿者）才能說(shuō)服Victor接受。

我們對(duì)上面的這兩個(gè)屬性進(jìn)行了非正式的論證。值得注意的是，這些論點(diǎn)中的每一個(gè)都主要依賴于這樣一個(gè)事實(shí)：我們的魔盒確實(shí)有魔法——即Victor可以可靠地“測(cè)試”Peggy提供的魔盒。有效性還要求壞人無(wú)法“拆開”Peggy的魔盒并獲取她的秘密斜率 m，這對(duì)于任何單向函數(shù)都應(yīng)該成立。

但這些論點(diǎn)并沒有徹底討論盒子必須有多安全。如果攻擊者能夠了解一部分的 m?和 b 呢？為了解決這些問(wèn)題，我們需要考慮第三個(gè)要求。

這個(gè)要求是，Victor在與Peggy一起運(yùn)行協(xié)議后，不應(yīng)該學(xué)到任何除了他從Peggy的公鑰中已經(jīng)知道的之外的東西。這個(gè)論點(diǎn)確實(shí)需要我們證明這些盒子非常魔法——也就是說(shuō)，除了Victor可以從黑盒測(cè)試中獲得的信息之外，它們不會(huì)泄露任何有關(guān)其內(nèi)部秘密的有用信息。

回想一下，我們?cè)谶@里基本擔(dān)心的是Victor將與Peggy一起運(yùn)行該協(xié)議，可能會(huì)運(yùn)行多次。在每次運(yùn)行協(xié)議結(jié)束時(shí)，Victor都會(huì)學(xué)到一份“記錄”。該記錄的內(nèi)容是1)一個(gè)包含 “b” 的魔盒，2)Victor選擇的挑戰(zhàn)值 x，以及3)Peggy回答的響應(yīng) y。我們還將假設(shè)Victor“誠(chéng)實(shí)”地隨機(jī)選擇了值 x，因此實(shí)際上他從Peggy那里獲得的只有兩個(gè)有趣的值。

我們可能會(huì)問(wèn)的一個(gè)問(wèn)題是：假設(shè)Victor想做一些壞事，比如假裝是Peggy，那么這份記錄中的信息對(duì)Victor有多大用處？

理想情況下，答案應(yīng)該是“一點(diǎn)用處都沒有”。

論證這一點(diǎn)的巧妙方法是證明Victor可以完美地“模擬”這些筆錄，甚至根本不需要與Peggy交談。因此，論證如下：如果Victor（就他自己）可以制作一份與他從Peggy交談中得到的記錄相同的記錄，那么他從Peggy那里得到真實(shí)的記錄到底“學(xué)到”了什么？顯然的答案是：啥都沒有。

因此，讓我們花點(diǎn)時(shí)間考慮一下Victor如何（完全由他自己）在不與Peggy交談的情況下制作一份“假”記錄。我們回顧一下上面的“魔盒”協(xié)議：

模擬記錄的一個(gè)比較容易想到的（錯(cuò)誤）想法是Victor可以首先選擇一些隨機(jī)值 b，并將其放入一個(gè)全新的“魔盒”中。然后他可以隨機(jī)選擇 x，就像在真實(shí)協(xié)議中一樣。但這個(gè)簡(jiǎn)單的嘗試很快就會(huì)失?。篤ictor將很難計(jì)算 y=mx+b，因?yàn)樗恢繮eggy的秘密密鑰 m。正如我們所討論的，他最好的嘗試是猜測(cè)不同的值并測(cè)試它們，這將花費(fèi)很長(zhǎng)時(shí)間（如果字段很大）。

顯然這種方法行不通。但請(qǐng)注意，Victor不一定需要“按順序”偽造這份記錄。另一種想法是，Victor可以嘗試通過(guò)以不同的順序執(zhí)行協(xié)議來(lái)制作假記錄。具體來(lái)說(shuō)：

1.Victor可以選擇一個(gè)隨機(jī) x，就像在真實(shí)協(xié)議中一樣。 2.現(xiàn)在他也可以隨機(jī)選擇值 y。請(qǐng)注意，對(duì)于每個(gè) “m”，都會(huì)存在一條穿過(guò) (x,y)的線。 3.但現(xiàn)在Victor遇到了一個(gè)問(wèn)題：為了完成協(xié)議，他需要制作一個(gè)包含 “b” 的新盒子，使得b=y?mx。

僅根據(jù)他所掌握的信息，Victor沒有很好的方法來(lái)計(jì)算 b。因此，為了滿足第三個(gè)要求，我們必須要求我們的魔盒具有全新的功能。具體來(lái)說(shuō)，我們可以想象有某種方法可以從現(xiàn)有的魔盒中“制造”出新的魔盒，使得新的魔盒包含一個(gè)計(jì)算值。這相當(dāng)于反轉(zhuǎn)線性方程，然后對(duì)“盒裝”值執(zhí)行乘法和減法，這樣我們最終得到：

“好吧?！蹦阋苍S會(huì)問(wèn)，“這是什么東西？怎么就多出來(lái)這一個(gè)奇怪的要求？“嗯，當(dāng)然是這樣。但請(qǐng)記住，我們一開始就說(shuō)了需要具有特殊功能的魔法盒子?，F(xiàn)在我只是添加一項(xiàng)神奇的能力。誰(shuí)能說(shuō)我不能做到這一點(diǎn)？

回想一下，生成的記錄必須與Victor從Peggy那里得到的記錄在統(tǒng)計(jì)上相似。很容易證明文字值 (x,y,b)?在兩個(gè)版本中都具有相同的分布。我們“制造的神奇盒子”的統(tǒng)計(jì)分布有點(diǎn)復(fù)雜，因?yàn)槲覀兩踔敛恢馈坝昧硪粋€(gè)盒子制造一個(gè)盒子”到底意味著什么？我們目前暫時(shí)只是指定制造的產(chǎn)品必須與真實(shí)協(xié)議中創(chuàng)建的產(chǎn)品“看起來(lái)”相同。

當(dāng)然，在現(xiàn)實(shí)世界中這很重要。我們需要確保我們的神奇盒子對(duì)象具有必要的功能，這些功能是（1）測(cè)試給定 (x，y)?是否在某條線上，以及（2）從一個(gè)包含 “m” 的盒子和點(diǎn) (x，y)?制造出一個(gè)新的包含“b”的盒子，同時(shí)確保制造的盒子與普通方法制作的魔盒相同。

如何制造一個(gè)魔盒

一個(gè)簡(jiǎn)單的想法可能是將秘密值 m 和 b 分別放入標(biāo)準(zhǔn)單向函數(shù)中，然后發(fā)送 F(m)?和 F(b)?。這顯然達(dá)到了隱藏這兩個(gè)值的目的：不幸的是，它不允許我們對(duì)它們做太多其他事情。

事實(shí)上，簡(jiǎn)單的單向函數(shù)的最大問(wèn)題是你只能用它們做一件事。也就是說(shuō)：你可以生成一個(gè)秘密 x，你可以計(jì)算單向函數(shù) F(x)，然后你可以將 x 透露給其他人來(lái)驗(yàn)證。一旦你做到了這一點(diǎn)，秘密就“消失了”。這使得簡(jiǎn)單的單向函數(shù)功能相當(dāng)有限。

但是，如果 F?是一種不同類型的單向函數(shù)，具有一些附加功能呢？

在20世紀(jì)80年代初，許多研究人員正在考慮這種單向函數(shù)。更具體地說(shuō)，Tahir Elgamal等研究人員正在研究Whitfield Diffie和Martin Hellman提出的一種當(dāng)時(shí)新的“候選”單向函數(shù)，用于他們的同名密鑰交換協(xié)議。

（譯者注：下面還是要進(jìn)入“一堆關(guān)于循環(huán)群的無(wú)聊細(xì)節(jié)”，缺少相關(guān)代數(shù)知識(shí)背景的讀者，可以暫時(shí)先認(rèn)為這里的所有運(yùn)算都是在整數(shù)上“字面意思”，不考慮群的性質(zhì)。并且讀者可能需要一定的代數(shù)知識(shí)來(lái)理解以下內(nèi)容。）

具體來(lái)說(shuō)：設(shè) p 是定義有限域的某個(gè)大的公開素?cái)?shù)。并讓 g 成為該域中包含的具有素?cái)?shù)階 q?的大循環(huán)子群的“生成器”。[4]（譯者注：此處原為腳注3，疑為原作者筆誤。但這樣子文中就沒有腳注3的位置了，不知3應(yīng)該放在哪里。）如果這些值選擇適當(dāng)，我們可以定義一個(gè)函數(shù) F(x)?如下：

這個(gè)函數(shù)的優(yōu)點(diǎn)在于，如果適當(dāng)選擇 g 和 p，則(1)很容易計(jì)算該函數(shù)（使用快速冪），但(2)求函數(shù)的逆通常來(lái)說(shuō)很困難。具體來(lái)說(shuō)，只要 x?是從 中選擇的，從F(x)?中恢復(fù) x?就等價(jià)于求解離散對(duì)數(shù)問(wèn)題。

但這個(gè)函數(shù)最特別的地方在于它具有很好的代數(shù)性質(zhì)。具體來(lái)說(shuō)，給定使用上述函數(shù)計(jì)算的 F(a)和 F(b)，我們可以輕松計(jì)算 ?。這是因?yàn)椋?/p>

類似地，給定 F(a)?和已知的標(biāo)量 c，我們可以計(jì)算 ：

我們還可以將這些功能結(jié)合起來(lái)。給定 F(m),F(b) 以及 x，我們可以計(jì)算 F(y)，其中。這條神奇的性質(zhì)允許我們?cè)凇半[藏”于單向函數(shù)內(nèi)的值上計(jì)算線性方程，在此之后我們可以將計(jì)算結(jié)果與其他人交給我們的y進(jìn)行比較：

這為我們提供了實(shí)現(xiàn)上一節(jié)中Chris協(xié)議所需的魔盒。最終協(xié)議如下所示：

合適的循環(huán)群也可以用某些橢圓曲線來(lái)構(gòu)建，例如NISTP-256和secp256k1曲線（用于比特幣中的Schnorr簽名）以及EdDSA標(biāo)準(zhǔn)（在Ed25519 Edwards曲線中實(shí)現(xiàn)的Schnorr簽名）。在橢圓曲線上冪乘被標(biāo)量點(diǎn)乘代替，但核心原理是完全相同的。

對(duì)于大多數(shù)人來(lái)說(shuō)，此時(shí)您可能已經(jīng)心滿意足。您可能已經(jīng)接受我的主張，即這些基于“離散對(duì)數(shù)”的單向函數(shù)足以隱藏值 (m,b)，因此它們就像魔盒一樣。

但你不應(yīng)該滿足于此！這個(gè)協(xié)議事實(shí)上還有很多問(wèn)題要解決。畢竟，冪函數(shù)和模函數(shù)并不是神奇的盒子。它們是真實(shí)的“東西”，可能會(huì)泄露有關(guān) “m” 和 “b” 的信息。尤其在多次運(yùn)行協(xié)議后，Victor將了解到許多關(guān)于這些值的信息。

為了有力地說(shuō)明盒子不會(huì)泄漏，我們必須使用我在之前討論的直覺。具體來(lái)說(shuō)，我們需要證明，只要給出Peggy的公鑰 ，就可以在不與Peggy本人交談的情況下“模擬”記錄?；叵胍幌?，在上面的討論中，我們使用的方法是首先選擇一個(gè)隨機(jī)點(diǎn) (x，y)，然后“制造”一個(gè)盒子，如下所示：

在我們的設(shè)置中，這相當(dāng)于直接從 和 (x,y) 計(jì)算 。我們可以這樣做：

（如果更嚴(yán)謹(jǐn)一點(diǎn)來(lái)說(shuō)，這里我們用除法作為簡(jiǎn)寫來(lái)表示乘以對(duì)應(yīng)的的乘法逆元。）

很容易看出，只要 (x,y) 是隨機(jī)選擇的，b=y?mx?就與真實(shí)協(xié)議分布相同。（譯者注：這里的“很容易看出”事實(shí)上是一次性密碼本的性質(zhì)）在這種情況下，?也將均勻分布，因?yàn)槊總€(gè)b和群上的元素之間存在一對(duì)一的映射。這是這個(gè)特殊魔盒的一個(gè)極其方便的功能。因此，我們可以認(rèn)為這個(gè)原語(yǔ)（循環(huán)群）滿足我們所有的安全要求。

從身份驗(yàn)證協(xié)議到簽名：Fiat-Shamir

雖然到目前為止這篇文章是關(guān)于身份識(shí)別協(xié)議的，但你會(huì)注意到現(xiàn)在使用交互式ID協(xié)議的人相對(duì)較少。在工程上，“Schnorr”這個(gè)名字幾乎總是指簽名方案。Schnorr簽名如今非常常見：它們被用在比特幣中，構(gòu)成了EdDSA等方案的基礎(chǔ)。

當(dāng)然，我花這么多時(shí)間在識(shí)別協(xié)議上是有原因的。這個(gè)原因是一種叫做Fiat-Shamir啟發(fā)式算法的美麗“技巧”，它使我們能夠毫不費(fèi)力地把三步識(shí)別協(xié)議（通常稱為“西格瑪協(xié)議”，基于大寫希臘字母的形狀）變成非交互式簽名。

我們簡(jiǎn)單聊聊它是怎么做到的。

Fiat和Shamir的主要想法是，Victor在三步協(xié)議中并沒有做什么事情：他的主要任務(wù)只是選擇一個(gè)隨機(jī)挑戰(zhàn)。當(dāng)然，如果Peggy可以自己選擇一個(gè)隨機(jī)挑戰(zhàn)，也許以某種方式基于她選擇的“信息”，那么她就可以完全消除與Victor互動(dòng)的需要。

在這個(gè)新場(chǎng)景中，Peggy將自己計(jì)算整個(gè)記錄，并且她可以簡(jiǎn)單地將她與自己運(yùn)行的協(xié)議的記錄交給Victor。假設(shè)挑戰(zhàn)值 x?可以“緊密”綁定到一條消息，那么這就可以將諸如Schnorr識(shí)別協(xié)議之類的交互協(xié)議轉(zhuǎn)換為簽名方案。

一個(gè)簡(jiǎn)單的想法是獲取消息 M，并將挑戰(zhàn)計(jì)算為 x=H(M)。

當(dāng)然，正如我們?cè)谏厦嬉呀?jīng)看到的，這是一個(gè)非常糟糕的想法。如果允許Peggy知道挑戰(zhàn)值 x，那么即使她不知道密鑰，她也可以使用上一節(jié)中描述的方法簡(jiǎn)單地“模擬”協(xié)議執(zhí)行記錄。由此產(chǎn)生的簽名將毫無(wú)價(jià)值。

因此，為了讓Peggy自己選擇挑戰(zhàn)值 x，她需要一種生成 x?的策略，該策略（1）只能在她“承諾”了包含 b?的第一個(gè)魔盒后才能執(zhí)行，并且（2）不允許她預(yù)測(cè)或“操控”她在此過(guò)程結(jié)束時(shí)獲得的 x 值。

Fiat和Shamir的關(guān)鍵結(jié)論是，如果Peggy擁有足夠強(qiáng)的哈希函數(shù) H，她就可以做到這一點(diǎn)。他們的想法如下。首先，Peggy將產(chǎn)生她的值 b．然后，她會(huì)將其放入正常協(xié)議中的“魔盒”中（如上面實(shí)例中的 ）。最后，她將 m 和 b?對(duì)應(yīng)的盒子以及一條可選的“消息” M 代入哈希函數(shù)：

最后，她按部就班地計(jì)算協(xié)議的其余部分，并將記錄? 交給Victor，他可以通過(guò)重新計(jì)算哈希函數(shù)來(lái)獲取 x?并驗(yàn)證 y?來(lái)檢查該記錄的正確性（如原始協(xié)議中所示。）

（這種方法的一個(gè)變體是Peggy給Victor一個(gè)稍微不同的記錄：這里她將 (M,x,y)?發(fā)送給Victor，Victor現(xiàn)在計(jì)算? 并測(cè)試是否有 。這個(gè)方案的正確性留給讀者思考。）

這整套邏輯成立的前提是，Peggy必須很難“操縱”這個(gè)哈希函數(shù)，使得她能找到輸入和輸出之間的一些對(duì)應(yīng)關(guān)系。在實(shí)踐中，這需要一個(gè)哈希函數(shù)，其中輸入和輸出之間的“關(guān)系”滿足我們所說(shuō)的回避性：很難找到有助于模擬協(xié)議的兩個(gè)點(diǎn)。

在實(shí)踐中，我們經(jīng)常在安全證明中把哈希函數(shù)看成是隨機(jī)函數(shù)，這意味著輸出與輸入無(wú)關(guān)。由于又長(zhǎng)又無(wú)聊的原因，這個(gè)模型有點(diǎn)虛偽。無(wú)論如何我們?nèi)匀皇褂盟?。（譯者注：這里應(yīng)該是指隨機(jī)預(yù)言機(jī)模型[Random Oracle]。這一模型經(jīng)常被用來(lái)在證明中替代哈希函數(shù)，但一部分近來(lái)的研究批評(píng)這一替代不能成立。）

還有別的魔盒么？

如上所述，“魔盒Schnorr”方案的一個(gè)關(guān)鍵要求是盒子本身必須由某種單向函數(shù)實(shí)例化：也就是說(shuō)，必須沒有有效的算法可以從盒子內(nèi)恢復(fù)Peggy的隨機(jī)密鑰，除非使用暴力窮舉，或使用一些差不多昂貴的（超多項(xiàng)式時(shí)間）攻擊。

上面給出的循環(huán)群滿足了這個(gè)要求，前提是離散對(duì)數(shù)問(wèn)題（DLP）在用于計(jì)算它的特定群中是困難的。假設(shè)攻擊者只有一臺(tái)經(jīng)典計(jì)算機(jī)，我們推測(cè)該假設(shè)對(duì)于基于有限域或某些橢圓曲線構(gòu)造的足夠大的群成立。

但你的對(duì)手何必是一臺(tái)經(jīng)典計(jì)算機(jī)。我們確實(shí)該為此動(dòng)動(dòng)腦筋。巧的是，只要有量子計(jì)算機(jī)，離散對(duì)數(shù)問(wèn)題并不是特別難解決。在量子計(jì)算機(jī)上，存在基于Shor算法求解DLP（和ECDLP）的高效量子算法。

在我的下一篇文章中，我將討論其中一個(gè)方案，即Dilithium簽名方案，并準(zhǔn)確展示它與Schnorr簽名的關(guān)系。

欲知后事如何，請(qǐng)看下集。

文章最初發(fā)布于To Schnorr and beyond (Part 1) – A Few Thoughts on Cryptographic Engineering (cryptographyengineering.com)，原作者為 Matthew Green。本文為翻譯。

1. “民間傳說(shuō)”在密碼學(xué)里指沒人知道到底是誰(shuí)第一個(gè)想到的這個(gè)方案。在這個(gè)例子中這些想法是由RalphMerkle等人在另一個(gè)語(yǔ)境（一次性簽名）中提出來(lái)的。 ??

2. 由于有 個(gè)不同的子集可供選擇，只要仔細(xì)選擇N和k，Veronica選擇與Victor完全相同的子集（允許他正確回答她的挑戰(zhàn)）的概率就可以變得非常小。（例如，N=128和k=30時(shí)，因此壞人Victor幾乎永遠(yuǎn)不會(huì)成功。） ??

3. 在真實(shí)的證明中，我們實(shí)際上依賴于一種稱為“倒帶”的屬性。在這里我們可以聲明，如果存在某種算法（更具體地說(shuō)，一種高效的概率性圖靈機(jī)），只要給定Peggy的公鑰，就可以高概率地冒充Peggy：那么一定有可能從這個(gè)算法中“提取”Peggy的秘密值 $m$。我們依賴這樣一個(gè)事實(shí)：如果我們有這樣一個(gè)圖靈機(jī)，我們可以（至少）運(yùn)行它兩次，同時(shí)輸入相同的隨機(jī)磁帶，但指定兩個(gè)不同的 x 挑戰(zhàn)。如果這樣的算法在一般情況下以一定的概率成功，那么我們應(yīng)該能夠獲得兩個(gè)不同的點(diǎn) (x,y),(x’,y’) ，然后我們可以求解(m,b)。 ??

4. 我在這里指定一個(gè)素?cái)?shù)階子群并不是因?yàn)樗墙^對(duì)必要的，而是因?yàn)閷?duì)于一個(gè)質(zhì)數(shù) $q$ 來(lái)說(shuō)，能用 ?來(lái)定義這些群元素很方便。要構(gòu)造這樣的群，必須選擇素?cái)?shù) q、p，使得 p=2q+1?。這保證了在由域 Fp?定義的較大群中存在 q?階子群。（譯者注：這是因?yàn)?Fp?里一個(gè)元素的階一定是 p?1?的因子[證明留待讀者自行完成]，因?yàn)?p?1=2q，任意一個(gè)子群的階大概率要么是 2，要么是 q） ??