如果你有一定的數學基礎及網絡知識的話(大概是理科的高中至大學程度)，這是一篇很好的密碼學科普文章。作者指出了一個要點：密碼學關注的重點是如何在各種情況下滿足信息安全的需要，而不是單純地研發最強大的加密或者破解算法。

理論上最強大的加密算法其實一早就被提出了，而且原理非常簡單，那就是用隨機數組成的一次性密碼本(one time pad)進行加密，不知道密碼的話，根本沒有任何數學分析手段能夠破解(是已被證明沒有破解而不是尚未發現/極難破解)。但密碼學並沒有因此而終結，因為這種方法在很多情況下是不實用的，也就是說理論上不能破解的加密算法並不足以提供絕對的信息安全，甚至在保障信息安全的作用上遠不如某些理論上沒那麼保險的加密算法(比如RSA)。為甚麼會這樣？看完這篇文章後你可以自己思考一下。

==========================

身份驗證、中間人攻擊和數字簽名：淺談密碼學

Matrix67
http://www.matrix67.com/blog/archives/1120

說到「密碼學」，大多數人的第一念頭或許是Morse電碼、Ceasar移位密碼、同音替換密碼之類的東西。這些東西在各類小說中都已是老面孔了，「字母e在英文中出現頻率最高」這一最基本的破密碼方法已經是耳熟能詳了。幾天前和網易的雲風聊了一下，突然體會到了密碼學的真諦。密碼學關注更多的並不是加密解密的各種數學算法，而是在已有數學算法上如何實現各種安全需求。防止消息洩露只是眾多安全問題中的冰山一角，而這個問題本身又有很多複雜的變化。

當我們談到「消息洩露」時，我們頭腦中想到的往往是，在信息傳輸過程中如何防止第三方截獲。當然，小偷防是防不住的，不過我能保證他偷到東西也沒用。雙方只需要事先約定一套加密函數和解密函數，以密文的方式進行傳輸，這樣便能很好地防止消息洩露。但有時候，「消息洩露」的內涵複雜得多，加密解密的傳統方法並不適用。考慮這麼一個問題：10個人坐在一起談天，突然他們想知道他們的平均年薪，但又都不願意透露自己的工資數額。有沒有什麼辦法讓他們能夠得出答案，並且不用擔心自己的年薪被曝光？事實上，最簡單的解決辦法不需要依賴任何密碼學知識：第一個人隨便想一個大數，比如880516。然後他在紙條上寫下這個數與自己的年薪之和，傳給第二個人；第二個人再在這個數上加上他的年薪數額，寫在另一張紙條上傳給第三個人；直到最後一個人把紙條傳回第一個人後，第一個人把紙條上的數減去只有自己知道的那個880516，便得到了全部10個人的工資和。

這樣的智力題還有很多很多。另一種關於防止信息洩露的場景則是，我不告訴你某樣事情，卻又要讓你相信我知道這件事情。我曾經介紹過這麼一個問題：給定一個圖，假如我找到了一條Hamilton回路，我如何才能讓你相信我確實知道答案，而又不告訴你答案是什麼？一個基於概率的算法是，我隨意構造一個同構圖，然後由你來發問：要麼讓我證明這的確是一個同構圖（給出頂點的對應關係），要麼指出這個同構圖上的Hamilton回路。充分多次測試後，你有充足的理由相信我的確找到了Hamilton回路，但你依舊不知道具體的答案。

可以看到，密碼學不僅僅研究加密解密的數學算法。更多的時候，密碼學研究保護信息安全的策略，我們可以稱之為「協議」。在已有的數學模型基礎上，我們往往忽略具體的數學實現方法，轉而專注地研究借助這些數學工具能夠構建的安全措施。除了消息保密性以外，密碼學還研究一些更加有趣的問題。下面我們看另外三種常見的信息安全問題。

首先是關於身份驗證的問題：我如何才能知道你真的是你。身份驗證是密碼學關注的一個大問題。接頭暗號、帳號密碼都是解決身份鑒別問題的辦法。在互聯網上，「用戶名/密碼」模式是最常見的用戶身份鑒別模式。但這裡出現了一個前面沒有出現過的嚴峻問題：如何防止第三方截獲？有人可能會脫口而出：為何不像前面一樣，把密碼加個密發出去？現在的網站一般都用md5的方法對密碼進行「單向加密」：客戶端計算密碼的md5值並發送出去，服務器接收到該md5值並與自己機器上預先算出來的md5結果進行比較。數據以md5的形式進行傳輸，即使被第三方截獲也能保證密碼安全。其實，這種方法仍然是不可靠的，原因在於，鑒別問題和消息洩露問題有著本質的區別。在前面的消息傳輸一例中，為了防止第三方截取者，我們採用了消息加密的方法，避免第三者獲取原始信息；而這裡，第三方截取者根本就不需要知道你的原始信息是什麼，只要照著你發的信息發就是了。如果我想假冒你，只要知道了密碼的md5值就可以模擬發送相同的數據包；這個md5值就已經成為了開門的鑰匙，你的真實密碼是什麼對我根本不重要。

這樣一來，身份驗證似乎永遠不可能做到了——第三者一旦截獲你發送的信息就可以完全模擬你。解決這個問題的小技巧就是，讓用戶每次發送的驗證信息都不一樣。例如，每次需要身份驗證時，服務器隨機生成一個字符串，發送給客戶端；然後客戶端把輸入的密碼和該字符串連接起來一起md5，再傳回去看這個md5值與服務器端的計算結果是否相符。那為什麼各大網站沒有這麼做呢？主要原因估計是因為，每次身份驗證都要算一次md5會大大增加服務器的壓力。

留心你周圍的事物，你會發現，這種「一次性密碼」是經常使用的。我有兩張銀行卡，一張農行的，一張交行的。交行的網銀需要綁定手機，每次網上消費時系統會給你手機發送一段隨機代碼叫你輸入，因此除非你倒霉到卡號、密碼和手機同時丟失，否則你的網銀賬戶永遠是安全的。農行使用的是「口令卡」，每個人的口令卡都不相同。卡片背後有幾十個小格子，每一個格子刮開來就是一個代碼。網上交易時，系統會叫你輸入某行某列的格子中的數，你便把那一格刮開來看。這些「活動密碼」手段有效地防止了網絡竊聽。

我編了一個記日記的軟件給自己用。進入這個軟件時需要輸入密碼，密碼是年份模23加上月份的平方的三倍，再乘以日期的自然對數小數點後第三位，減去小時數的倒數的余切值的最高兩位。瞟到我密碼的人會發現，等我離開後偷偷打開日記軟件，剛才的密碼不管用了。

信息安全這檔子事永遠是防不勝防。上面這個「活動密碼」協議就安全了嗎？可以看到，除非你是真的知道用戶名密碼，否則你不可能騙過主機；同時，數據傳輸用的md5算法，這是不可逆的，竊聽者無法恢復原數據。但是，再往前一追溯，漏洞就出來了：用戶註冊時提交的那個密碼又是怎樣傳輸的呢？顯然，這時再用md5來傳輸是不行的，因為md5不可逆，主機算不出你的真實密碼是多少，「活動密碼」方案就用不成了；直接用明文傳輸呢，被第三者竊聽的危險又出來了，哪天賬戶被盜了後打死你也想不出密碼在最開始商定的時候就被洩露了。這樣看來，用戶設定密碼時只能進行加密傳輸了。然而，加密傳輸必然又要事先約定加密方式，而這個加密方式的商定過程本身又有洩露的風險，這就又回到了原來的問題上。有可能避免密鑰的交換麼？如果是朋友之間的通信，把兩人已知的小秘密用作密鑰（例如約定密鑰為甲方的生日乘以乙方的手機號）或許能讓人放心許多，但在網絡中，特別是用戶與主機的會話中，這顯然是不現實的。這樣看來，信息安全問題似乎是沒法解決了。
為了解決這個「圈」，我們需要想一個絕對邪的辦法……如果我不告訴任何人解密的算法不就行了麼？這就需要一種全新的加密方法，知道密鑰的人可以加密，但卻不能解密，密文只有在我這兒才能解密。這樣的話，就連給我發消息的那個人也只會加密不會解密，安全性得到了極大的提高；即使密鑰被竊聽了，第三者也讀不出原始消息。

是否有可能告訴一個人加密算法，但他卻無從獲知解密算法呢？乍看之下這貌似是不可能的。對於一種加密方法，似乎總會存在一種對應的解密算法：你加我就減，你左移我就右移，你替換過去我就替換回來，加密解密步驟正好互逆。雖然難以置信，但這種不可逆的「不對稱密碼」的確是存在的。RSA算法就是這樣一種算法，任何人都可以知道該怎麼加密，但讓你知道了怎麼加密你也不會進行解密，密文只有到了我手裡才解得開。也就是說，這種算法有一個可以公開的「公開加密鑰匙」，和一個只有自己才有的「私人解密鑰匙」。這種神奇的「公鑰加密術」的基本思想其實很簡單：構造公鑰只需要把兩個大質數相乘，但要想獲得私鑰必須進行大數分解，而後者目前還沒有什麼有效的算法。這一「正行容易逆行難」的思想就是RSA算法的核心。網上對RSA算法的描述太多了，但在這裡我還是想簡單的描述一下。

選取兩個大質數p和q。算出n=pq。算出φ(n)=(p-1)(q-1)。找一個數小於φ(n)的數e，使得e與φ(n)互質。n和e就可以作為公鑰公開了。假設明文m是一個小於n的數。只要擁有公鑰n和e，任何人都可以根據公式c=m^e mod n算出密文c（可以二分加速）。但是呢，你會發現你解不回去了……因為只知道n、e和c，你是不能反過來求出m的。

那我們該怎麼算m的值呢？只需要求出一個滿足ed≡1 (mod φ(n))的d後，我們就可以直接用公式m=c^d mod n求得明文。利用擴展的輾轉相除，我們可以很容易求出滿足要求的d。但是φ(n)的值只有我才知道，別人是不知道的（如果想要破解出來必須得把n分解成p和q），因此這個d值就是一個只有我自己才知道的解密鑰匙。下面我們來說明上述解密算法的正確性。由於ed-1能被(p-1)(q-1)整除，它必然也能被(p-1)整除，因此m^ed可以表示成m^(k(p-1)+1)，其中k是某個適當的整數。現在，假設m是p的倍數，那直接就有m^(ed)≡0^(ed)≡0≡m (mod p)；否則，m和p一定互質，根據Fermat小定理有m^(p-1)≡1(mod p)，於是m^(ed) = m^(k(p-1)+1) = [m^(p-1)]^k * m ≡ 1^k * m ≡ m (mod p)。同理，當模數為q時也總有m^(ed)≡m。既然p整除m^(ed)-m，q也整除m^(ed)-m，並且p和q都是質數，那麼一定有m^(ed)≡m (mod pq)，即m^(ed)≡m (mod n)。這個m^(ed)就等於我們前面的c^d。

現在我們得到了兩個函數F和G，其中F(m)=c，而G©=m。大家都知道函數F是什麼，但是卻求不出函數G，這個函數G就是只有我自己知道的私人鑰匙，函數F則是公之於眾的公共鑰匙。

這一套算法最大的意義就是省去了隱患多多的「密鑰交換」這一步。以後大家發送加密消息前再也不需要暗中約定密碼算法了。每個人都自己找兩個幾十幾百位長的質數，生成公鑰n和e公佈到網上去。如果A要和B通信，A直接用B的公鑰進行加密，然後把密文傳給B；A不會害怕第三者截獲消息，因為這個密碼只有B才能解得開。同樣地，B想要回復A的話，只需要用A的公鑰加密，然後把消息發送給A即可。在服務端與客戶端的信息交流中更適合使用公鑰加密術，因為服務端向所有客戶端公告其公共鑰匙更加方便，更加合理。用戶需要設定密碼時，傳輸請求前只需要把要提交的數據用服務端的公開密鑰進行加密即可，這樣既不用交換密鑰，又不必擔心第三者的竊聽，因為這個數據只有服務端才能解開。

事情還沒有結束呢！我們前面假設，大家公開公鑰的方式是「發佈在一個眾人可信的網站上」，這種假設是有原因的。需要臨時交換雙方公鑰的通話協議是不安全的，這裡面存在一個戲劇性的漏洞。舉個例子，假如A和B認為，任何網站都是不可靠的，他們從未並且今後也不會在網上公佈自己的公鑰。為了加密通信，A需要親自告訴B他的公鑰，B也需要親自告訴A自己的公鑰。收到公鑰後，雙方便用對方的公鑰加密進行數據傳輸。因為用這個公鑰加密後，只有對方才能解開密碼，因此雙方都認為這條通信線路是安全的。其實，他倆的麻煩大了。這條線路並不是安全的，第三者可以用一種很搞笑的方式來竊聽消息。假設有一個人C知道A和B之間將有一次加密通話。C劫持了A和B之間的通訊線路。現在，A把他的公鑰發給B，這個公鑰傳到一半時被C攔截下來，於是C獲得了A的公鑰；C再把他自己的公鑰發給B，讓B把C的公鑰錯當成A的公鑰。同樣地，B把他自己的公鑰發給A，被C攔截下來。C把自己的公鑰發給A，讓A以為那是B的公鑰。以後，每當A給B發加密消息時，A其實是用C的公鑰在加密；C把A的消息解密後，再用B的公鑰加密後傳給B。類似地，一旦B給A發送消息，C都可以將消息解密，並用A的公鑰進行加密後傳過去。此時，A和B都以為自己在用對方的公鑰加密，並都能用自己的私有鑰匙解開對方傳來的密文；殊不知，這中間有人僅僅用了一點彫蟲小技，無聲無息地竊走了所有的信息。C正是利用了公鑰加密術「誰都可以加密」的性質，結結實實地玩弄了A和B。這種攻擊方法叫做「中間人攻擊」。

這讓我想起了經典的國際象棋騙術。一個象棋白癡宣稱自己是個大牛。為了證實這一點，他將要與兩位大師同時對弈。他說，我先下後下都能贏。於是，在與大師A的對弈中他為白方，與大師B對戰則執黑。結果呢，兩盤比賽下來居然都打成了平手。怎麼回事呢？其實那個象棋白癡耍了個小伎倆，他把大師A走的棋記了下來，跑到另一邊去下給B看，又把B的應著原封不動地搬到了和A的棋局上。來來回回搞了半天，他自己只起了個傳遞信息的作用，真正在對弈的是兩個大師。

怎樣防止這種中間人攻擊呢？中間人之所以能夠得逞，關鍵就是，無論是網絡通話還是國際象棋，雙方總是一先一後地發送信息。不過，在網絡通訊中，我們有一種很特別的辦法，他可以迫使中間人無法再扮演「即時翻譯」的角色。首先，A把想說的話（最好是能夠證明自己身份的話）進行加密，同時B也完成相同的工作。然後，A把他的加密消息的前面一半傳給B，B收到後也把他的密文的一半傳給A；A再把剩下的部份傳給B，之後B也把他的密文的另一半回傳給A。此時，A和B分別用自己的私鑰進行解密，查看對方發來的消息。這帶給中間人C一個不可逾越的障礙：兩段密文要合在一起才能解開，中間人拿著其中一半密文，那是一點辦法都沒有。此時，中間人陷入了一個非常窘迫的境地，他只有兩條路可選：要麼硬著頭皮把這半截密文發給B，當B得到全部密文後會發現用他自己的私鑰根本解不開，從而意識到中間有人搗亂；要麼就忽略這半截密文，自己編幾句A想跟B說的話，用B的公鑰加密並發一半給B。如此一來，中間人需要編造所有A和B之間的對話，這需要相當厚的臉皮，風險異常之大，要不了多久便會露出馬腳。

RSA算法還有一個特別的應用。注意到公鑰和私鑰所對應的兩個函數是互逆的，因此如果我用私鑰來加密，用公鑰同樣可以恢復原來的數據。但是，用我自己的密鑰加密，然後大家都可解密，這有什麼用處呢？不妨來看看這樣「加密」後的效果吧：第一，貌似是最荒謬的，大家都可以看到源文件；第二，很關鍵的，大家只能夠看源文件，但不能改動它；第三，滿足上述兩個要求的文件別人是做不出來的。

這些性質正好完美地描述出「簽名」的實質。為了防止釣魚網站騙取你的賬戶和密碼，正牌的那個服務器需要發送一條消息，以證明自己確實是唯一的服務提供商。為此，你可以發送一個隨機字符串過去，要求服務器用它的私鑰加密。服務器傳回他加密過的字符串後，若你用他的公鑰解密能恢復出原來的字符串，則說明對方一定是正宗的服務提供商。只有擁有私鑰的人才能做到這一點，別人是無法偽造這個「簽名」的。

數字簽名還有一些其它的特殊變化。考慮這樣一種情況，我有一份秘密文件需要簽名，但我不希望簽名者看到這份文件的內容。這種看似很不合理的情況確有發生。例如在證人保護計劃中，我是一個特工，我需要保護一個非常可愛的無辜小MM。為了把她安置到一個偏遠的安全地，我需要讓上級簽署各種通行證明文件；但為了安全起見，我不希望把安全地的位置洩露給任何人。為此，我希望我的上級對文件進行簽名，但保證他們完全不知道文件內容是什麼。滿足這種要求的簽名協議叫做「盲簽名」。為了得到一種「盲簽名」算法，考慮用RSA進行簽名的本質：假設待簽名的文本為（不超過模數n的）t，則我們實質上希望得到t^d mod n，其中n是模數，d是簽名者的私人鑰匙。我們的目的是，對文本t進行干擾（例如在t上面加一個大數，或者乘一個大數，或者取t的倒數的正弦值的-π次方的自然對數），讓簽名者不知道t是什麼；但簽名者簽名之後，我們還能除去剛才的干擾因子，還原為t^d mod n。因此，我們需要想一個奇妙的辦法，讓被干擾的文本簽名後，干擾因子頭上的「d」正好消失了。回憶之前講過的結論m^(ed)≡m (mod n)，我們立即想到了盲簽名算法：我把明文t乘上一個隨機數k的e次方（e是公開鑰匙），把t*(k^e)傳給簽名人。注意我們選取的k一定要與n互質，否則k是大質數p或q的倍數，「干擾」的結果必然為0。這下，簽名人當然不可能知道t是什麼，因為他不知道隨機數k是多少。他對t*(k^e)進行簽名，傳回來的結果即為t^d * k^(ed) mod n。但k^(ed)模n就等於k，於是這個簽名結果實際上就是t^d * k mod n。現在，我只需要把該結果除以只有我才知道的k（即乘以它在模n剩餘類環中的逆元，這個逆元保證存在，因為k和n互質），即得到了我需要的簽名文件t^d mod n。

盲簽名協議並不是只有特工才可能用到的東西，它的應用範圍其實相當廣。在生活中，我們每個人都可能用到過盲簽名。一個最常用的例子就是投票協議——中央機構需要確定每張選票都來自合格的選舉人，並且每個人最多投了一次票；但同時選舉人又不希望在投票過程中洩露自己的選票內容。但是，為了檢查選票的來源是否可靠，中央機構必然要鑒別每張選票所屬的投票人。怎麼辦呢？此時，盲簽名協議就派上用場了。每個選舉人在自己的選票前面加上一個隨機字符串作為前綴（防止以後被暴力破解），然後乘上隨機數k的e次方，再連同一份（未被干擾的）身份證明，一同遞交給中央機構。中央機構檢查身份證明，確認這張（被干擾過的）選票來自合格的選舉人。然後中央機構給這張選票簽名，回傳給選舉人。選舉人將簽名結果除以k，用中央機構的公鑰檢查看簽名是否有效，隨機字符串是否和自己當初設定的一樣。接著投票人匿名提交這份由中央機構簽過名的（且不帶干擾因子的）選票。中央機構收到選票，用公鑰解密看簽名是否有效。這樣，中央機構既可以確信每張選票都來自合格的投票人，嚴格實行一人一票制度，又不能追查出任何一個投票者的選票內容。

更複雜的盲簽名協議來源於這樣一種特殊情況：恐怖分子答應供出炸彈的位置，前提條件是需要得到一系列保證無罪逃脫的簽名文件，包括新身份、新護照，以及總統親自簽署的免起訴書和安全離境的通行證。同時，恐怖分子又需要確信政府不能知道他的新身份和潛逃地。這需要政府在不知道文件內容的情況下簽署協議。這與剛才所談的盲簽名有什麼區別呢？一個巨大的區別就是，要求盲簽名的不是特工，而是壞蛋，政府在沒有看到文件之前不能隨意簽名。萬一恐怖分子要求盲簽名的文件實際上是一份要求政府保護全體恐怖分子的安全，保證所有人永不被通緝永不被起訴，並無償提供恐怖組織基地和巨額資助等不平等條約該咋辦？因此，這裡需要一種比盲簽名要求更高的協議：簽名者不能看到文件內容，但要相信文件的內容是什麼。

看起來這似乎是辦不到的，但事實上這是有可能的。我們有一個非常簡單的辦法，它是一個基於概率的協議。恐怖分子可以起草十份文件，每份文件裡都包含了一個不同的新身份和潛逃地。然後恐怖分子用十個不同的隨機數對這十份文件進行干擾，傳給政府。政府選取其中的九份文件，向恐怖分子索要干擾因子。恐怖分子把對應的那九個k值傳過去，政府對其進行解密，從而看到這九份文件都是符合要求的文件（只是文件中具體的身份名字和潛逃地點不一樣）。政府對最後一個文件進行簽名，並把簽名結果回遞給恐怖分子。恐怖分子除去干擾因子，得到他需要的簽名文件。這樣，恐怖分子可以保證政府不知道他的新身份和潛逃地，同時政府也能保證恐怖分子不會耍詐。恐怖分子只有1/10的概率可以騙到政府，顯然不值得恐怖分子去冒這個險。為安全起見，「10」這個數字還可以任意加大。

前面我們看到，簽名具有不可偽造性，因此簽名者可以很好的證明自己的身份。事實上，由於簽名是不可偽造的，因此簽名還有一個重要的功用。當一個人對某份文件進行簽名後，這份文件便具有了法律效應：你今後無法再否認你簽過這份文件，因為別人是不能偽造簽名文件的。簽名的這種性質叫做「抗抵賴性」。

在實際生活中，簽名的抗抵賴性用的最多的場合就是簽合同了。為了防止一方今後毀約，雙方可以要求對方在合同上簽名。此後，合同簽署人的行為將受到這個簽名文件的限制。一旦簽名者想毀約，利益受到侵害的人便可以拿著這份合同大鬧法庭，高舉這份文件大叫「當初他簽過名的」。

當簽名用於抗抵賴時，新的問題產生了。簽名的法律效應是如此之高，以至於人們往往不敢隨意簽名。一份合同往往同時規定了雙方的權利和義務，並需要雙方都在上面簽名。第一個在上面簽字的人就會覺得很虧：萬一我簽了字後對方突然翻臉耍賴不簽了咋辦？即使合同上規定「合同僅在雙方均簽署之後才有效」，這個問題仍然存在，因為後簽名者將具有絕對的主動權，他想什麼時候簽就什麼時候簽，而只有他的簽名才具有決定意義。因此很多時候，雙方都希望能夠在對方簽名之後自己再簽名，從而獲得一些安全感。這裡我們來探討一個有趣的問題：有沒有什麼辦法能夠讓雙方同時簽約，使得雙方簽名時都能確保自己的利益安全？

如果我們談論的是傳統意義上的簽名，同時簽名當然是有可能辦到的：雙方只需要拿起各自的筆，同時在文件上寫下自己的名字即可。當然，事實上肯定不會有人這麼做。試想這樣一個荒唐的畫面：兩個西裝筆挺的人擠在一起，兩隻手臂磕磕碰碰地交錯在一起，然後雙方同時喊「三、二、一」並一起開始寫字……比起自己丟掉的臉面，自己先簽名所帶來的憂慮還算個屁啊。

有沒有體面一些的，不那麼荒唐的同時簽字法呢？這裡有一個很有啟發性的辦法。合同雙方面對面地坐在桌子的兩端。其中一個人在合同上寫下自己姓名的第一個字母，然後傳給坐在對面的第二個人；第二個人寫下他自己名字的第一個字母，然後又回遞給第一個人；第一個人簽下自己名字的第二個字母，又交給對方要求對方寫下自己的第二個字母……以此類推，直到雙方都簽署完自己的名字為止。為了讓雙方能夠「同時」簽完，名字較長的人偶爾可能需要連續寫下兩三個字母。

雙方都願意履行這一協議，因為在這個協議下雙方是一點一點地簽完整個文件的。第一個寫字的人不會覺得自己很虧，因為寫下一個字母是遠不具備法律效應的；如果對方拒絕簽他的第一個字母，我可以當即撕毀合同。雖然他們都不知道，究竟要寫多少個字母才算簽字，但大家都保持自己簽下的名字長度與對方基本相當，因此不會擔心對方突然放棄協議。就在這種互動的心理過程中，簽名的法律效應一點一點地增強，直到最後雙方寫完自己的名字。

但是，這個辦法不能用於數字簽名。利用RSA算法進行簽名是一個整體的過程，不能分成一部分一部分地進行。能不能把合同拆成若幹份，然後雙方一份一份地逐個簽名呢？當然不行。如果某一份合同裡有一個至關重要的義務性條款，後簽名的人等對方簽到這裡後便可以立即終止簽名，從而謀取利益。那麼，能不能規定「僅當你把所有n個部份的文件都簽過了才算簽」呢？這意味著最後一次簽名才具有最終的決定意義，說穿了不過是把安全問題轉移到了「誰簽最後這一下」，問題實質上並未改變。其實，我們的解決辦法相當簡單。我們可以耍一個小花招，從本質上模擬上面的「逐字母簽名法」。

首先，第一個人簽署這樣一份文件：「我願意以1%的概率接受該合同」。第二個人檢查第一個人的簽名，然後在上面附加一句「我願意以2%的概率接受這份合同」，並進行簽名，回交給第一個人。第一個人檢查對方已經簽名，然後繼續將這個條文升級為「我願意以3%的概率簽署該合同」並簽名。雙方來來回回簽100次，直到最後第一個人簽「我願意以99%的概率簽署這份合同」，然後輪到第二個人簽署「我接受該合同」，最後再輪到第一個人簽署「我接受該合同」。

注意，這個「接受概率」是有實際意義的。如果在第一個人第一次簽完文件後，第二個人立即放棄繼續簽署，法官可能會要求雙方進行一次公開抽籤測試，選取一個不超過100的正整數。如果這個數恰好為1，那麼簽署這句話的人就相當於簽署了這份合同。類似地，我們也可以約定，當一人聲稱將以百分之p-1的概率接受此合同，另一人聲明以百分之p的概率接受時，法官可以要求雙方共同生成一個1至100的整數：如果它不超過p-1則雙方都接受，如果它的值比p大則雙方都不接受，若它的值正好等於p則合同僅被後者接受。因此，這種協議實質上是用概率法再現了「逐字母簽名法」的核心思想，將法律效應的問題進行量化，使得率先簽名的潛在危險減小到了原來的百分之一。

這個協議看似有些可笑，但實際上是可行的。0.01是一個很小的數，雙方都能接受，心理上都有保障。況且，簽合同的雙方通常並沒有抵賴的企圖，他們只是希望雙方能夠同時簽署協議罷了。但是從密碼學協議的角度來看，利用概率進行聲明簽署的做法確實不那麼美觀，它讓人感覺有些跳出了密碼學的理論範圍，無法用密碼學的語言符號進行規範。有人可能希望我們利用一些密碼學手段來實現這種「小步進簽名」。比如，雙方可以把自己簽名後的文件加一個密，然後兩人一位一位地輪流宣讀自己的密鑰。具體地說，A可以想一個大數a，把自己簽名後的文件異或a之後傳給B；B也可以生成一個同樣長的數b，異或自己簽名後的合同後傳給A。然後，A把a的第一位告訴給B，B把b的第一位告訴A；A再把a的第二位告訴B，同時B宣佈b的第二位……直到A、B兩人獲得對方的全部密鑰。事實上，即使你不知道對方的密鑰，你也可以枚舉對方的密鑰進行暴力破解，只不過這個難度是密鑰長度的指數級別。雙方逐位交換密鑰，目的就在於同步減小暴力破解所需的人力、物力和時間。這樣，如果中途有人退出協議，兩人枚舉出對方簽名後的文件的難度是相當的，這對雙方都很公平。不過，這個協議並不能阻止某人撒謊。其中一方發送的可能根本就不是自己的合同簽名，或者宣佈自己的密鑰時是隨便亂叫的；但在整個協議完成之前，對方完全無法察覺出來。協議的思路是好的，不過在我們進一步完善這個協議之前，該協議沒有任何使用價值。

回想起前面提到的恐怖分子一例。那個例子是很有啟發性的，其思想可以廣泛用於實現各種「反作弊」協議。我們可以把上面的協議稍作修改：A把合同拆成兩份，然後分別進行簽名，並聲明「僅當某人可以同時提供簽名合同的兩部份才能證明我簽署了這份合同」。然後，A生成兩個大隨機數a1和a2，把前一半簽名合同異或a1，把後一半簽名合同異或a2。A把兩份干擾後的簽名合同都傳給B。B隨機要求查看其中一部分合同的內容，向A索取a1或a2。A把B索要的密鑰傳給B，向B證明他之前傳過去的是真實的合同內容。類似地，B也把自己的合同拆成前後兩半並分別簽名，然後異或兩個不同的大數傳給A，並按照A的要求宣佈其中一個大數。此時，雙方都只擁有對方一半的簽名合同，並相信另一半（自己無法解開的）合同是真實的。但根據聲明，只有一半合同是不算數的，對方必須同時擁有兩部份簽名合同才行。接下來，雙方又像剛才那樣逐位報出剩下那一半合同所對應的大隨機數，直到對方獲得全部密鑰為止。

合同內容的真實性是保證了，但這仍然不能防止某個人在協議後期虛報自己的密鑰。因此，我們還需要想一個辦法，讓雙方在逐位報數階段中不能作假。為此，我們希望雙方都能知道對方密鑰的其中一部分信息，以便驗證對方宣讀的密鑰的真實性。上述協議中，我們之所以會被對方欺騙，原因就在於對方知道我現在知道了什麼不知道什麼。要是有辦法能夠收到對方的其中一個大數，卻不讓對方知道我收到了哪個大數的話就好了。這樣的話，對方不得不老老實實地宣佈這兩個大數各是多少，因為他不知道我手裡有哪一個數。

我們稱這種特殊的數據傳送方式叫做「不經意傳輸」(oblivious transfer)，意即我自己也不知道傳過去了什麼。上面這種傳輸需求有一個更確切的名字，叫做「1-2不經意傳輸」。在1-2不經意傳輸中，信息發送者可以準備兩個不同的消息m1和m2（比方說，簽名合同的前一半和後一半），接收人可以索要並獲取m1和m2中的其中一個，但信息發送者不知道他要的是哪一個。實現不經意傳輸的方式非常巧妙。算法需要再一次用到RSA公鑰加密術。首先，發送者生成兩對不同的公私鑰，並公開兩個公鑰。不妨稱這兩個公鑰分別為公鑰1和公鑰2。假設接收人希望知道m1，但不希望發送人知道他想要的是m1。接收人生成一個隨機數k，再用公鑰1對k進行加密，傳給發送者。發送者用他的兩個私鑰對這個加密後的k進行解密，用私鑰1解密得到k1，用私鑰2解密得到k2。顯然，只有k1是和k相等的，k2則是一串毫無意義的數。但發送者不知道接收人加密時用的哪個公鑰，因此他不知道他算出來的哪個k才是真的k。發送人把m1和k1進行異或，把m2和k2進行異或，把兩個異或值傳給接收人。顯然，接收人只能算出m1而無法推測出m2（因為他不知道私鑰2，從而推不出k2的值），同時發送人也不知道他能算出哪一個。發送人有一種辦法可以作弊：他可以只發送其中一個真實的異或值（而編造另一個異或值），或者用k1和k2對同一個消息進行異或。不過這需要發送者能夠猜出信息接收者最初選的是公鑰1還是公鑰2。如果接收人用公鑰1對k加密，但最後得到的卻是m2（或者什麼都沒得到），那發送人的企圖就被識破了。

有了1-2不經意傳輸協議，我們之前的同步簽名問題就徹底解決了。為了讓協議更安全，我們還可以讓雙方各生成n份合同的拷貝，使得成功欺騙的概率僅為1/2^n。一個完整的同步簽名協議如下：

A、B雙方各生成帶編號的n份一模一樣的合同，把每份合同拆成前後兩半並分別簽名。約定僅當對方同時獲得了同一編號的兩部分簽名合同，合同才算被簽署。A生成2n個大數，對他的2n份文件進行異或，然後全部傳給B。B也做相同的事情。接下來，借助不經意傳輸，A向B索取其中的n個大數（對每個文件索要其中一個大數），類似地B也向A索取其中n個大數。此時，雙方都能確定對方發來的文件是真實的，並且雙方都不知道對方擁有了自己的每份文件的哪一半。接下來，A報出他自己的2n個大數中每一個數的第一位，然後B也報出他的每個數的第一位；然後，A報出每個數的第二位，B也報出每個數的第二位……直到雙方報完所有數為止。

在上述協議的任一階段裡，A和B都不敢作假。發送虛假文件會在不經意傳輸完成後立即被發現，被欺騙者可以立即終止協議。虛報自己的大數也會穿幫，因為對方有其中一半的大數可用於核對，而你不知道他有哪一些大數。雙方逐漸獲得越來越多的大數位數，推測對方簽名文件的難度同步減小，直到完全獲得對方的簽名文件。

我們以這個比較複雜的密碼學協議來結束這篇一萬多字的文章，目的是想展示一下密碼學的科學性和複雜性。我們從身份驗證說到了RSA算法，再談到中間人攻擊及其解決辦法，最後講了數字簽名和兩種特殊的簽名方式——盲簽名和同步簽名。但這還遠不到我想說的東西的一半。雲風給我推薦了《應用密碼學》，我當天晚上就在網上買了，第二天就抱到了文學史課上去看。從這本書裡面我學到了好多好多科學的東西。還是那句話，密碼學並不專注於數字層面的加密解密方法，而是專注於解決各種安全問題的方法。就像信息學中的算法一樣，密碼學協議中的算法也相當有趣，有些算法簡潔實用，巧妙得有如神來之筆。信息傳輸的算法，其牛B性不亞於信息處理的算法。接下來我還想更新一些有趣好玩的密碼學協議，相信大家會感興趣的。