區(qū)塊鏈行業(yè)技術(shù)引卷之十一：密碼學(xué)初探隱藏信息的藝術(shù)

第頁(yè)目錄古典密碼學(xué)：秘密與情報(bào)的交織 4隱匿法 4加密法 4持續(xù)千年的智力競(jìng)賽：加密與解密 5古典密碼學(xué)的圣杯 8攻克“恩尼格瑪” 9圖表目錄圖表1：貝平頓與瑪麗女王使用的替換式密碼表 6圖表2：恩尼格瑪?shù)木幋a器（轉(zhuǎn)子）結(jié)構(gòu)示意 9圖表3：恩尼格瑪加密原理示意 9圖表4：“炸彈”操作員 12“密碼學(xué)”一詞的詞源來(lái)自古希臘語(yǔ)“隱藏計(jì)算機(jī)科學(xué)與通信科學(xué)的基礎(chǔ)上，除了信息的加密與解密之外，數(shù)“密碼”“通行詞”或受限于篇幅，有關(guān)密碼學(xué)以及密碼學(xué)在區(qū)塊鏈中應(yīng)用的內(nèi)容將分兩篇專(zhuān)題介紹。古典密碼學(xué)：秘密與情報(bào)的交織隱匿法5世紀(jì)古希臘與波480年，波斯艦隊(duì)在“萬(wàn)王之王”薛西斯一世的率領(lǐng)下秘密集結(jié)，準(zhǔn)備對(duì)希臘發(fā)起進(jìn)攻，然而這一秘密行動(dòng)被一位遭到流放、居住在波斯的希臘人狄馬圖拉斯發(fā)現(xiàn)了。他將成功騙過(guò)了路途中的波斯衛(wèi)兵，將信息傳回了希臘。希臘城邦聯(lián)合起來(lái)，抵御住了波斯人的突襲。而遭遇挫敗之后，曾經(jīng)盛極一時(shí)的波斯阿契美尼德王朝也開(kāi)始走向衰退。盡管簡(jiǎn)單地“將信息隱藏起來(lái)”與我們今天熟知的密碼學(xué)相差甚遠(yuǎn)，被稱(chēng)為“隱匿法”的秘密書(shū)寫(xiě)方式卻標(biāo)志著人們開(kāi)始探索信息保密的方式。加密法隱藏信r也無(wú)法還原出原始信息。加密法的出現(xiàn)標(biāo)志著古典密碼學(xué)的開(kāi)端明文加密算法。古典密碼學(xué)的加密算法大多是以字母、單詞或是短語(yǔ)為基本單位，又可分為置換法（Transpositionciphers）和替換法（Substitutionciphers）兩大類(lèi)。 元5世紀(jì)，斯巴達(dá)軍隊(duì)采用一種名為“密碼棒”（Scytale）的工具對(duì)信息進(jìn)行加密。發(fā)信人將長(zhǎng)條形的羊皮紙帶纏繞在一根木棒上，將信息橫向書(shū)寫(xiě)，最后將羊皮紙解下。收信人將信紙纏繞在同樣直徑的木棒上，就能夠還原信息。而羊皮紙上的文字看起來(lái)是無(wú)意義的，并且用尺寸不相同的木棒也無(wú)法還原出原始信息。但只要了解這種密碼的加密方式，就能很容易地解讀密文。從第N個(gè)NNN，同樣的明文經(jīng)過(guò)N，NN稱(chēng)為密鑰秘密知識(shí)ygAr3位，密鑰3表示。密鑰可能的取1～25（0密明文空間密碼表。密（theAdventureofDancingMen）26種形態(tài)各異的跳舞的小人來(lái)替換英文字母。8世紀(jì)，阿拉伯哈里發(fā)帝國(guó)的第二個(gè)世襲王朝——阿拔斯據(jù)記載，阿拔斯王朝的官員們使用替換式加密法保護(hù)機(jī)密的行政事務(wù)、稅收數(shù)據(jù)，相信這能夠幫助他們建立一個(gè)廉潔、高效的政府。（Bookfcs，使用排列組合對(duì)阿拉伯語(yǔ)單詞的加密法進(jìn)行分析。此外，阿拉伯的學(xué)者們還開(kāi)創(chuàng)了破譯加密信息的科學(xué)持續(xù)千年的智力競(jìng)賽：加密與解密古典密碼學(xué)多用于軍事、政治、外交領(lǐng)域重要情報(bào)的傳遞，希望刺探這些秘密的人自然不在少數(shù)。阿拉伯學(xué)者們?cè)诮y(tǒng)計(jì)語(yǔ)言學(xué)資樣本容量較大有意義的al在阿拉伯語(yǔ)中出現(xiàn)頻率最的定冠詞，相當(dāng)于英語(yǔ)的“the”，此外，元音的出現(xiàn)頻率也比較高。這些成果很快被運(yùn)用到密文分析中。密鑰單字母表替換式加密法9世紀(jì)，阿拉伯科學(xué)家肯迪（Al-Kindi）在《解譯加密信息》（ManuscriptfortheDecipheringCryptographicMessages）一書(shū)中闡率并排序，對(duì)照該語(yǔ)言中字母出現(xiàn)的頻率順序，就可以開(kāi)始嘗試對(duì)密文進(jìn)行分析，這種方法稱(chēng)為頻率分析法。頻率分析還可統(tǒng)計(jì)某種語(yǔ)言中特定的字母組合出現(xiàn)的頻率，如英文中的“ee”，以及某個(gè)字”u”等。直到數(shù)百年后，中世紀(jì)的歐洲學(xué)者才掌握這一方法，并且決定了兩位女王的命運(yùn)。1586年，英格蘭政府對(duì)天主教的迫害日益加劇，安東尼·貝平頓（AnthonyBabington）與幾位同黨密謀策反，計(jì)劃救出被伊麗莎白23j、v、w之外的英文字母，4個(gè)不具有任何意義的混淆符號(hào)，表示下一個(gè)字母連續(xù)出現(xiàn)兩次的圖表1：貝平頓與瑪麗女王使用的替換式密碼表資料來(lái)源：《碼書(shū)》，通證通研究院但可惜的是，貝平頓信任的密使其實(shí)是一位雙面間諜，背地里將他與瑪麗女王的密函交給伊麗莎白女王的國(guó)務(wù)大臣、間諜頭子沃爾辛厄姆，后者先打開(kāi)信封，抄寫(xiě)一份密文，再重新偽造封緘，并將密文交給密碼學(xué)家托馬斯·誘使貝平頓說(shuō)出參與計(jì)劃的同伙的名字。暗殺計(jì)劃暴露后，瑪麗女王、貝平頓以及其密黨都遭到處決。以上是一個(gè)過(guò)于信任加密方法的安全性，以致造成悲劇結(jié)局的例子。如何衡量加密通信安全與否是一個(gè)重要的問(wèn)題，加密通信的過(guò)程可以劃分為因此，密鑰空間越大，意味著破譯者需要嘗試的密鑰數(shù)就越多，密25奧古斯特·19世紀(jì)提出的（Kerckhoff's統(tǒng)的各個(gè)環(huán)節(jié)都是公開(kāi)知識(shí)（ce，只要密鑰未被泄除此之外，加密算法自身可能也存在安全性漏洞，雖然密鑰空間非常龐大，但破譯者也能夠通過(guò)分析密文的某些特征，縮小可能的密鑰范圍。明文的目的一般是傳遞某些信息，因而是有意義的存在某些語(yǔ)言學(xué)或統(tǒng)計(jì)學(xué)上的特征，而密文則一定程度地保留了這為了消除這些頻率特征，一些增強(qiáng)的替換式加密法被發(fā)明出來(lái)，但仍未能解決替換式加密法的缺陷。例如同音替換式加密法（homophonicsubstitutioncipher）將出現(xiàn)頻率較高的字母對(duì)應(yīng)多個(gè)采用替換字母19676，即兩個(gè)字母組成的字母對(duì)可能的數(shù)量，從而猜到了其加密方式，并用頻率分析破譯了它。信息傳遞的途徑并非絕對(duì)安全同樣的密鑰“密鑰保衛(wèi)戰(zhàn)”。15世紀(jì)初，文藝復(fù)興時(shí)期的佛羅倫薩藝術(shù)家阿爾伯蒂已經(jīng)認(rèn)識(shí)到了單字母表加密法在頻率分析法面前不堪一擊，他提出了一套新的加密方法，即輪流使用多張密碼表，依次對(duì)明文中的字母“維吉尼亞加密法”26套不同的密碼表，對(duì)應(yīng)密0～25A～Z的英文字母表示?！癊”，第三個(gè)用·（CharlesBabbage）不認(rèn)為破譯維吉26（以及它自身的因子）就是密鑰單詞可能的長(zhǎng)度。知道了密鑰單詞長(zhǎng)度（N）這一重要信息，巴貝奇把密文NN個(gè)單字母表加密的片段。盡管這些零散的片段對(duì)應(yīng)的明文是沒(méi)有意義的，但只要這個(gè)片段出自完整的、有意義的使用頻率分析法，維吉尼亞密碼就可以被破譯。加密者為了方便記憶，通常喜歡選取有意義的密鑰單詞，但這也使密碼變得更加不安全。古典密碼學(xué)的圣杯26個(gè)6的密鑰單詞就有超3億種可能，為什么還是能夠被破解呢？維吉尼亞密碼法的缺陷將這個(gè)理論發(fā)揮到極致，就是著名的“一次一密”加密法（one-edr一次一密”是真正安全的加密方式，被譽(yù)為古典密碼學(xué)的圣杯?！耙淮我幻堋凹?918·（Arthur發(fā)明了×26×26種不同的狀態(tài)，每一種狀態(tài)對(duì)應(yīng)一個(gè)密和布萊切利公園（BletchleyPark）的盟圖表2：恩尼格瑪?shù)木幋a器（轉(zhuǎn)子）結(jié)構(gòu)示意資料來(lái)源：網(wǎng)絡(luò)圖片，通證通研究院圖表3：恩尼格瑪加密原理示意資料來(lái)源：網(wǎng)絡(luò)圖片，通證通研究院攻克“恩尼格瑪”（6種可能（17576種可能0密鑰空間&'密碼分析學(xué)中，破譯方嘗試破解加密系統(tǒng)的行為稱(chēng)為攻擊。根攻擊實(shí)際上就是猜測(cè)密鑰惟密文攻擊（ciphertextonlyattack）：攻擊者只擁有關(guān)于密文的信息已知明文攻擊（knownplaintextattack）：攻擊者擁有某些明文片段和對(duì)應(yīng)的密文片段的信息選擇明文攻擊（chosenplaintextattack）：攻擊者可以獲得任意明文片段對(duì)應(yīng)的密文信息nt在“一次一密”30，260～250～25的全排列??),??&??，定義了一個(gè)集合(0,1,25)→集合(0,1,25的一一映射????(??)=??5.例如，維吉尼亞加密法的第??個(gè)密碼表就可表示為)=??+??(??????26).恩尼格瑪?shù)牟寰€板最多可以對(duì)換六對(duì)字母的信號(hào)，一個(gè)對(duì)換過(guò)程可以表示為??, ??≠??,??>,???)=??, ??=????, ??=??插線板變換??=>D,D>E,E...>F,F,&≠+..≠'≠&.≠'∈??=,...每個(gè)編碼器具有一個(gè)初始狀態(tài)，每經(jīng)過(guò)一次旋轉(zhuǎn)，它表示的密碼表會(huì)發(fā)生改變。記（最右邊）編碼器的初始狀態(tài)為??)=(??),??&,...,??+-)它把字母0變換為1變換為??&……10變換為?1(????????（26格后又回到初始狀態(tài)）的操作可表示為=??M&??)????(??) =??+1(??????26)=??M7??)??7=??7(NOP+')三個(gè)編碼器從左到右記為??,??,??，相對(duì)初始狀態(tài)的位置記為??,??,??，則插線板與編碼器對(duì)原始信號(hào)的共同作用可表示為U=>?V??到這里為止，恩尼格瑪?shù)脑O(shè)計(jì)都還中規(guī)中矩。發(fā)報(bào)員在鍵盤(pán)上按下按鍵，字母會(huì)被轉(zhuǎn)化為數(shù)字信號(hào)，經(jīng)過(guò)處理后變成密文在密文鍵盤(pán)相應(yīng)的位置點(diǎn)亮燈泡。那如果要解密怎么辦呢？密碼燈只能展示密文字母，而不能用做輸入。收到加密信息的一方需要與加密使用相同的鍵盤(pán)輸入密文解密，也就是要設(shè)計(jì)一種能夠同時(shí)進(jìn)行加密和解密的電路，對(duì)任意明文字母??以及對(duì)應(yīng)的密文??=??(??)滿足：??(??)=??,??(??(??))=??,即??+=??,??表示恒等變換雪比伍斯的方法是在三個(gè)編碼器之后，再加上一塊反射板，其作用是將最左邊一塊編碼器的輸出觸點(diǎn)兩兩連接起來(lái)，將其輸出信號(hào)反射回三個(gè)編碼器，再穿過(guò)接線板，連接到密文燈泡。記反射板變換為??，它由十三對(duì)不同字母的對(duì)換復(fù)合而成，滿足??+=??恩尼格瑪在某個(gè)特定編碼器狀態(tài)下的加密過(guò)程就可以表示為>,?,V=??M&??M&??M&M&??>?V??V ? >對(duì)于任意的明文字母??，以及對(duì)應(yīng)的密文??=>,?,V??)，如果保>,?,V??) =>,?,V>,?,V??)=??M&??M&??M&M&??>?V????)V ? >=??注意到反射板的特性是連接兩個(gè)不同的觸點(diǎn)，因此恩尼格瑪不會(huì)將一個(gè)明文字母加密成它自身。這表明??>,?,V同樣可以表示為十三對(duì)不同字母的對(duì)換過(guò)程的復(fù)合，雖然這個(gè)特性使加解密過(guò)程可以使用同一個(gè)輸入鍵盤(pán)完成，但大大削弱了加密體系的安全性。圖靈也正是利用反射板的設(shè)計(jì)缺陷攻破了恩尼格瑪?shù)姆烙?。?duì)于惟密文攻擊，恩尼格瑪幾乎是牢不可破的。德軍每天會(huì)更換密鑰，每則密鑰加密的明文數(shù)量有限。密鑰的長(zhǎng)度為17576，比大多數(shù)明文長(zhǎng)度都要長(zhǎng)，因而頻率分析法對(duì)恩尼格瑪也不起作用。但是對(duì)于已知明文攻擊，反射板設(shè)計(jì)的危害就體現(xiàn)出來(lái)了。盟軍繳獲了德軍的幾臺(tái)恩尼格瑪密碼機(jī)，并對(duì)一些已知的明文和密文進(jìn)行對(duì)比，發(fā)現(xiàn)德軍公文的格式較為固定，經(jīng)常在固定的位置出現(xiàn)同樣的單詞。比如德軍每天發(fā)送的天氣預(yù)報(bào)中會(huì)出現(xiàn)wetter（德語(yǔ)，天氣）這一單詞。圖靈還發(fā)現(xiàn)，有時(shí)明文和密文之間會(huì)出現(xiàn)一種特殊的循環(huán)結(jié)構(gòu)，這有助于識(shí)別編碼器的狀態(tài)信息。假設(shè)已知明文為wetter，對(duì)應(yīng)的密文（以大寫(xiě)字母表示）如下：????????????????????????恩尼格瑪把第一個(gè)字母??加密成??加密成第四個(gè)字母??又加密成????????????=676???+26???+??(????????e(22) =4(??)??eg&(4) =19(??)??egi(19) =22(??)jk jklD jklm22→4→19→22由于恩尼格瑪不會(huì)將一個(gè)明文字母加密成相同的密文，給盟軍分析密文提供了兩點(diǎn)幫助。首先，盟軍在猜測(cè)某些固定單詞的位置時(shí)，如果發(fā)現(xiàn)有些明文字母和對(duì)應(yīng)位置的密文相同，那么就可以排除這種可能。其次，這個(gè)特點(diǎn)保證只要已知明文與密文對(duì)應(yīng)的片段足夠長(zhǎng)，總是可以找到類(lèi)似的循環(huán)結(jié)構(gòu)。圖靈還發(fā)現(xiàn)，這種循環(huán)結(jié)構(gòu)與接線板的設(shè)置無(wú)關(guān)。把編碼器和反射板對(duì)字符的變換記為??e=??M&??M&M&??>?Ve=??M&e??V ? >1000億種可能，但是它的本質(zhì)是一個(gè)單字母表>??可寫(xiě)成??M&??e??(22) =4?=qk qklD qklm??++→??p→??&r→

??++可以看出這樣的循環(huán)是在??的作用下產(chǎn)生的，與接線板設(shè)置無(wú)關(guān)。圖靈利用這一點(diǎn)，便可以不考慮接線板的接法，他使用三臺(tái)相同的恩尼格瑪密碼機(jī)，隨意設(shè)置第一臺(tái)的編碼器位置，記這個(gè)位置為??+??+第二臺(tái)的輸出連接到第三臺(tái)的輸入，以此類(lèi)推，從而模擬出同樣的加密過(guò)程。如果編碼器設(shè)置正確，就可以形成相同的循環(huán)回路?，F(xiàn)在還不知道字母??被接線板替換成了哪個(gè)字母，圖靈想到，連接兩臺(tái)密碼機(jī)所有對(duì)應(yīng)的字母觸點(diǎn)，逐一嘗試可能的編碼器位置，只要有一個(gè)回路連通，就說(shuō)明存在一個(gè)字母經(jīng)過(guò)三臺(tái)密碼機(jī)被加密成它自身。這時(shí)的編碼器位置雖然不一定是正確的，但只要使用篩選出的編碼器位置還原明文，使用頻率分析逐個(gè)檢驗(yàn)就可以破解接線板的設(shè)置了。MachineryFactory）根據(jù)圖靈的設(shè)計(jì)建造出了擁有十二臺(tái)密碼機(jī)的解密機(jī)器“炸彈”194249臺(tái)“炸彈”，圖表4：“炸彈”操作員資料來(lái)源：網(wǎng)絡(luò)圖片，通證通研究院要破解恩尼格瑪，已知明文與密文的對(duì)應(yīng)片段、三個(gè)編碼器的內(nèi)部線路都是不可缺少的。二戰(zhàn)期間，英國(guó)皇家空軍使用“栽培法”（gardening）引誘德國(guó)海軍發(fā)送包含特定信息的密文。英國(guó)空軍在特定的地點(diǎn)布置水雷，故意讓德軍發(fā)送有關(guān)該地點(diǎn)坐標(biāo)的情報(bào)，攔截下密文送往布萊切利公園，這也是一種選擇明文攻擊。替換式加密算法與加密機(jī)械的弱點(diǎn)在于沒(méi)