比特幣行情 比特幣行情
Ctrl+D 比特幣行情
ads
首頁 > 狗狗幣 > Info

區塊鏈:密碼學初探:隱藏信息的藝術——區塊鏈技術引卷之十一

Author:

Time:1900/1/1 0:00:00

通證通研究院×FENBUSHIDIGITAL聯合出品

文:宋雙杰,CFA;孫含儒

特別顧問:沈波;Rin;JX

導讀

密碼學,是一門將信息進行加密處理與傳遞,以及分析加密信息的學科。根據以RSA為代表的公鑰加密體系的出現,可以將密碼學的發展過程分為古典密碼學與現代密碼學兩部分。古典密碼學以“置換法”與“替換法”為基礎,多應用于軍事與情報領域;現代密碼學則建立在數學、計算機與通信科學的基礎上,除了加密信息之外,數字簽名、數據完整性、身份認證等也是現代密碼學的研究課題。

摘要

置換法依照一定的規則,改變原始信息中的字母排列順序;替換法將原始信息中的字母按照一定的規則替換成其他字母。置換法與替換法的安全性較差,古阿拉伯的學者們開創了破譯加密信息的科學——密碼分析學,通過頻率分析的方法破解替換式加密法。

在長達一千多年的時間里,古典密碼學以置換法與替換法為基礎不斷演進。以維吉尼亞密碼為代表的多字母表替換式加密法輪流使用多個不同的替換式密碼表,依次對明文中的字母進行加密。第二次世界大戰時德軍使用的“恩尼格瑪”是一種基于復雜的多表替換加密原理的機械式密碼機,但最終由于自身加密算法的缺陷,被圖靈設計的“炸彈”攻克。

置換式與替換式加密法的弱點在于沒能完全消除密文中有關明文的某些特征,保留了明文中的某些信息。奧古斯特·柯克霍夫在19世紀提出的柯克霍夫原則概括性地總結了加密算法應遵循的設計原則:即使加密系統的各個環節都是公開知識,只要密鑰未被泄漏,加密系統都應該是安全的。

加密算法的安全性問題本質在于:如何降低攻擊者在了解加密算法,并擁有足夠長的密文片段的前提下,猜測出正確密鑰的可能性?1948年,香農創立了信息論,并在次年的一篇論文中從數學的角度討論了加密系統,人們開始從科學的角度探究密碼學的奧秘。

風險提示:量子計算技術的潛在威脅

目錄

1隱匿法

2加密法

3持續千年的智力競賽:加密與解密

4古典密碼學的圣杯

5攻克“恩尼格瑪”

正文

密碼學,是一門將信息進行加密處理與傳遞,以及分析加密信息的學科。“密碼學”一詞的詞源來自古希臘語“隱藏”和“書寫”,意為“秘密書寫”,其歷史幾乎與人類有文字記載的文明一樣悠久。古希伯來學者在公元前六世紀左右就掌握了“單字母表替換式加密法”,在之后的兩千五百多年里,古典密碼學在替換式加密法的基礎之上不斷發展演進。古典密碼學多應用于軍事與情報領域,而微型計算機與現代密碼學的發展能夠保護普通人的日常通信免受第三方的窺探。現代密碼學建立在數學、計算機科學與通信科學的基礎上,除了信息的加密與解密之外,數字簽名、數據完整性、身份認證等也是現代密碼學的研究課題。今天人們日常生活中的網絡支付、電子商務、電子貨幣等都是密碼學這一人類兩千多年來智慧結晶的應用。

上海市數據隱私安全計算企業重點實驗室參與完成論文被密碼學頂級會議PKC收錄:近日,上海市數據隱私安全計算企業重點實驗室謝翔博士聯合香港大學學者共同合作的論文《Compact Zero-Knowledge Proofs for Threshold ECDSA with Trustless Setup》被公鑰密碼學領域國際頂級會議PKC 2021錄用,該會議將在北京時間2021年5月9日至13日于線上舉行。PKC是國際密碼學會(IACR)主辦的專注于公鑰密碼學方向的旗艦會議,每一年舉辦一次,今年是第24屆,該會議一直是學術界和工業界共同關注的焦點。

本次上海市數據隱私安全計算企業重點實驗室參與完成的論文亮點在于零知識證明(ZKP)方向的研究。在理論層面,我們提出的零知識證明包括HSM群中的離散對數關系和Castagnos-Laguillaumie(CL)密文的格式良好性。在實際應用層面,我們利用零知識證明改進了兩方ECDSA和門限ECDSA的性能。

上海市數據隱私安全計算企業重點實驗室以矩陣元科研中堅力量為基礎,匯集國內密碼學專家、學者組建而成。研究內容為針對數據融合與協同計算基礎設施建設過程中保護數據安全與隱私的基礎理論技術。[2021/4/7 19:55:55]

密碼學的概念與人們平時登陸網站、使用銀行賬戶的“密碼”并不相同。這些用于身份認證的“密碼”,更準確的翻譯是“通行詞”或“通行碼”,它是現代密碼學的諸多應用之一,請讀者注意區分兩者的區別。

受限于篇幅,有關密碼學以及密碼學在區塊鏈中應用的內容將分兩篇專題介紹。

1

隱匿法

隱匿法的歷史非常久遠,可以追溯到公元前5世紀古希臘與波斯帝國的戰爭年代。公元前480年,波斯艦隊在“萬王之王”薛西斯一世的率領下秘密集結,準備對希臘發起進攻,然而這一秘密行動被一位遭到流放、居住在波斯的希臘人狄馬圖拉斯發現了。他將波斯軍隊準備進攻希臘的消息寫在木板上,并用一層蠟將文字遮住,成功騙過了路途中的波斯衛兵,將信息傳回了希臘。希臘城邦聯合起來,抵御住了波斯人的突襲。而遭遇挫敗之后,曾經盛極一時的波斯阿契美尼德王朝也開始走向衰退。

盡管簡單地“將信息隱藏起來”與我們今天熟知的密碼學相差甚遠,被稱為“隱匿法”的秘密書寫方式卻標志著人們開始探索信息保密的方式。

2

加密法

隱匿法僅僅將信息藏匿起來,一旦藏匿的方式暴露,或是負責傳達信息的信使叛變,信息安全也無從保證。加密法則注重隱藏信息本身的含義,信息的發出方與接收方事先約定,將信息按照一定的規則進行轉譯,接收方在收到后遵循約定的規則就可以還原原始信息,而即使信息被第三方截獲,如果不知道轉譯規則,也無法還原出原始信息。

加密法的出現標志著古典密碼學的開端。在上面的例子中,未經加密的原始信息稱為明文,按照特定的規則對明文進行轉譯后得到的信息稱為密文,這個規則稱為加密算法。古典密碼學的加密算法大多是以字母、單詞或是短語為基本單位,又可分為置換法和替換法兩大類。

瑞士密碼學家Christian Cachin:Ripple網絡中沒有共識:瑞士密碼學家、伯爾尼大學計算機科學家Christian Cachin在其博客文章“Ripple網絡中沒有共識”中表示,對Ripple協議的技術分析表明,在陳述的假設下,其既不能確保安全,也不能確保其活動性。文章稱,借助其模型可證明,即使在極端溫和的對抗條件下,Ripple的協議也無法達成共識,并且可能妨礙安全性和活力。尤其是,網絡可以在Ripple聲明的UNL重疊的標準條件下,且在只有極小部分的惡意節點的情況下分叉。在網絡忽略或延遲正確節點之間的消息的時間段內,惡意節點可能只是向正確的節點發送沖突消息。其還演示了即使所有節點都具有相同的UNL并且只有一個拜占庭節點,Ripple的共識協議也可能會失去活力。如果發生這種情況,則必須手動重新啟動系統。文章得出結論稱,Ripple網絡的共識協議很脆弱,無法確保計算機科學和區塊鏈從業人員普遍理解的共識。[2020/12/3 22:55:52]

置換法依照一定的規則,改變原始信息中的字母排列順序。公元前5世紀,斯巴達軍隊采用一種名為“密碼棒”的工具對信息進行加密。發信人將長條形的羊皮紙帶纏繞在一根木棒上,將信息橫向書寫,最后將羊皮紙解下。收信人將信紙纏繞在同樣直徑的木棒上,就能夠還原信息。而羊皮紙上的文字看起來是無意義的,并且用尺寸不相同的木棒也無法還原出原始信息。

但只要了解這種密碼的加密方式,就能很容易地解讀密文。從密文的第一個字母開始,每數到它之后的第N個字母,記下該字母。記錄到密文結尾后,再從第二個字母開始重復這樣的操作,以此類推,很快就可以還原明文信息。其中N取決于木棒的直徑,寫下N個字母后,紙帶正好繞木棒一圈,選擇不同的N,同樣的明文經過加密得到的密文也不相同。發信人和收信人要事先約定好同樣的N,收信人才能還原密文。同時N不能被第三方知曉,才能保證加密通信的安全。這里的N稱為密鑰,是加密通信的參與方共同享有的秘密知識,用于加密和解密信息。

替換法將原始信息中的字母按照一定的規則替換成其他字母。據傳,凱撒大帝使用替換式加密法寫作書信。凱撒大帝將信息中的每個字母后移三位,例如A替換成D,Y替換成B,這種加密法稱為凱撒挪移式加密法。在這個例子中,密文相比明文,每個字母都被后移了3位,密鑰可以用3表示。密鑰可能的取值范圍為1~25的自然數,稱為密鑰空間。明文里所有可能出現的字母的集合稱為明文空間,密文里可能出現的字母集合稱為密文空間,替換法中的密鑰可以表示為明文空間到密文空間的一個映射,在古典密碼學中又稱為密碼表。密文空間可以與明文空間相同,例如凱撒密碼中,密文的字母仍然是26個拉丁字母。密文空間也可以是明文空間的超集,例如在密文中混入一些無效字符,以干擾試圖破譯密碼的行動。密文空間還可以與明文空間完全不相關,例如在柯南道爾所著的福爾摩斯系列的《跳舞的人》中,罪犯用26種形態各異的跳舞的小人來替換英文字母。

公元8世紀,阿拉伯哈里發帝國的第二個世襲王朝——阿拔斯王朝在巴格達定都,其建立之初的一百年是伊斯蘭文明的黃金時代。據記載,阿拔斯王朝的官員們使用替換式加密法保護機密的行政事務、稅收數據,相信這能夠幫助他們建立一個廉潔、高效的政府。巴士拉的語言學家卡里爾撰寫了《加密信息手冊》,使用排列組合對阿拉伯語單詞的加密法進行分析。此外,阿拉伯的學者們還開創了破譯加密信息的科學——密碼分析學。

聲音 | 觀點:密碼學人才短缺,影響了馬來西亞的區塊鏈發展:私人投資公司MW Partners Group Holdings Pte Ltd顧問Mark Pui表示,密碼學領域的人才短缺,拖累了馬來西亞數字賬本技術的發展。

Mark聲稱:“我認為,現實是我們沒有密碼技術,這影響了我們領導區塊鏈技術發展的能力。在馬來西亞和全世界,區塊鏈技術的應用仍然有限。但在發展方面,我們落后于其他所有人,因為我們沒有技能,沒有深厚的密碼學技能。”(The Malaysian Reserve)[2019/11/29]

3

持續千年的智力競賽:加密與解密

古典密碼學多用于軍事、、外交領域重要情報的傳遞,希望刺探這些秘密的人自然不在少數。阿拉伯學者們在統計語言學資料時發現,在樣本容量較大,有意義的阿拉伯語文本中,每個字母出現的頻率是不一樣的。字母a和字母l在阿拉伯語中出現頻率最高,因為“al”是阿拉伯語中的定冠詞,相當于英語的“the”,此外,元音的出現頻率也比較高。這些成果很快被運用到密文分析中。

之前介紹的替換式加密法中,明文中的所有字母都遵循同一套規則進行替換,這樣的加密法稱為單字母表替換式加密法。公元9世紀,阿拉伯科學家肯迪在《解譯加密信息》一書中闡述了對這種加密法的解譯方式。如果能確定原文所使用的語言,首先列舉出密文中出現的所有字母,統計它們各自出現的頻率并排序,對照該語言中字母出現的頻率順序,就可以開始嘗試對密文進行分析,這種方法稱為頻率分析法。頻率分析還可統計某種語言中特定的字母組合出現的頻率,如英文中的“ee”,以及某個字母前后特定字母出現的頻率,如英文中字母“q”之后一定跟隨”u”等。直到數百年后,中世紀的歐洲學者才掌握這一方法,并且決定了兩位女王的命運。

1586年,英格蘭政府對天主教的迫害日益加劇,安東尼·貝平頓與幾位同黨密謀策反,計劃救出被伊麗莎白女王軟禁的蘇格蘭女王、伊麗莎白女王的表妹、信仰天主教的瑪麗女王,并暗殺伊麗莎白女王。貝平頓通過密使傳遞使用替換式加密法加密的書信,與瑪麗女王商討暗殺計劃。貝平頓設計的更加復雜的替換式加密法使用23個符號替換除j、v、w之外的英文字母,4個不具有任何意義的混淆符號,表示下一個字母連續出現兩次的“dowbleth”符號,以及若干個符號替換常用的單詞,以盡量減少遭到頻率分析法破譯的可能。

但可惜的是,貝平頓信任的密使其實是一位雙面間諜,背地里將他與瑪麗女王的密函交給伊麗莎白女王的國務大臣、間諜頭子沃爾辛厄姆,后者先打開信封,抄寫一份密文,再重新偽造封緘,并將密文交給密碼學家托馬斯·菲利普分析。菲利普通過頻率分析法破譯了密碼,并在瑪麗女王寄出的一封信件后附加了一段偽造的密文,誘使貝平頓說出參與計劃的同伙的名字。暗殺計劃暴露后,瑪麗女王、貝平頓以及其密黨都遭到處決。

以上是一個過于信任加密方法的安全性,以致造成悲劇結局的例子。如何衡量加密通信安全與否是一個重要的問題,加密通信的過程可以劃分為選擇加密方式、約定密鑰、加密明文、傳輸加密信息、還原明文幾個步驟。古典密碼學中,絕大多數加密方式都是替換法、置換法或者兩者的結合,因此加密方式幾乎不是秘密,試圖對密文進行分析的人可以通過嘗試所有可能的密鑰進行解譯,當某個密鑰還原出的明文出現了有意義的單詞,就說明找到了正確密鑰。因此,密鑰空間越大,意味著破譯者需要嘗試的密鑰數就越多,密碼就越安全。凱撒挪移式加密法只有25個可能的密鑰,安全性非常差。

現場 | 密碼學專家楊光:實現高TPS需要解決兩個問題 可驗證計算是有效途徑:金色財經現場報道,全球區塊鏈開發者大會 GBDC 2018于香港正式召開。密碼學專家楊光表示,今年“雙十一”淘寶運算的峰值256000筆, 區塊鏈如果要達到10000萬TPS,實現比淘寶4倍的TPS是需要具備諸多條件的。理想條件下帶寬無限、傳輸沒有延遲,可以非常快的達成共識。而這種即使如此如果實現百萬TPS,還有解決兩個問題:一是單個節點的處理能力、二是區塊鏈數據增長較快。密碼學專家楊光介紹了可驗證計算的方式以解決實現TPS的問題,著重介紹非交互是的可驗證計算。[2018/12/16]

奧古斯特·柯克霍夫在19世紀提出的柯克霍夫原則概括性地總結了加密算法應遵循的設計原則:即使加密系統的各個環節都是公開知識,只要密鑰未被泄漏,加密系統都應該是安全的。換一個方式來說,加密系統的安全性應依賴于密鑰的保密,而不是加密算法的保密。

除此之外,加密算法自身可能也存在安全性漏洞,雖然密鑰空間非常龐大,但破譯者也能夠通過分析密文的某些特征,縮小可能的密鑰范圍。明文的目的一般是傳遞某些信息,因而是有意義的,存在某些語言學或統計學上的特征,而密文則一定程度地保留了這些特征,如單字母表替換式加密法保留了不同字母出現的頻率特征。為了消除這些頻率特征,一些增強的替換式加密法被發明出來,但仍未能解決替換式加密法的缺陷。例如同音替換式加密法將出現頻率較高的字母對應多個不同的密文,從而使密文中各個字母出現的頻率相近,但字母組合的頻率信息仍然沒有完全消除,仍存在被破譯的可能。法國國王路易十四用來加密機密文件的“大密碼”采用替換字母對的方式,兩個世紀以來都沒有遭到破譯。19世紀末,人們發現大密碼的密文中出現的數字數量接近676,即兩個字母組成的字母對可能的數量,從而猜到了其加密方式,并用頻率分析破譯了它。

瑪麗女王的例子還說明,信息傳遞的途徑并非絕對安全。由于通信的雙方需要事先約定同樣的密鑰,如果傳遞密鑰的方式不安全,整個加密通信系統也形同虛設,信息安全保衛戰就是“密鑰保衛戰”。

早在15世紀初,文藝復興時期的佛羅倫薩藝術家阿爾伯蒂已經認識到了單字母表加密法在頻率分析法面前不堪一擊,他提出了一套新的加密方法,即輪流使用多張密碼表,依次對明文中的字母進行加密。這一方法由法國外交官維吉尼亞所發揚光大,發明了“維吉尼亞加密法”。維吉尼亞加密法采用26套不同的密碼表,對應密鑰為0~25的凱撒挪移式密碼表,并以從A~Z的英文字母表示。加密的過程是,選擇一個密鑰單詞,例如KEY,然后按照密鑰單詞中的字母順序,依次對明文字母按照相應的密碼表進行加密,第一個字母使用“K”對應的密碼表替換,第二個字母使用“E”,第三個用“Y”,第四個再回到“K”,以此循環直至加密結束。這一類加密法稱為多字母表替換式加密法,同樣的明文字母可能會被加密成不同的密文,相同的密文字母不一定對應相同的明文,給破譯者帶來很大的干擾。維吉尼亞加密法的密鑰空間幾乎是無限的,一度被視為不可破譯的,是一千年以來古典密碼學的重大突破。

美國國家標準和技術研究所的研究人員宣布 密碼學中隨機數的方面出現突破:美國國家標準和技術研究所的研究人員最近宣布,在密碼學最重要的一個“隨機數的產生”方面取得了突破。這種實驗性的新技術可能會對網絡安全產生巨大影響。在以電子方式運行現代世界的“1”和“0”的數字面紗后面,隨機數字每天都要在加密過程中進行數千億次的排序,這些過程通過不斷擴大的互聯網為全球提供數據。[2018/4/19]

但英國發明家查理`巴貝奇不認為破譯維吉尼亞密碼是一項不可能完成的任務。當人們開始了解維吉尼亞密碼的加密算法,它的致命弱點也隨之浮現。維吉尼亞密碼用于加密的基礎密碼表只有26種,而且都是已知的凱撒密碼表。維吉尼亞密碼加密明文使用密碼表的順序是固定的,因此同一個明文單詞,被加密成的密文僅有有限種可能。可能的密文種類數取決于密鑰單詞的長度。并且位置相差密鑰單詞長度的所有字母都是使用同一張密碼表進行替換的。巴貝奇發現,維吉尼亞密碼的密文每過一部分,就會出現重復的字母組合,這意味著兩個可能:一,不同的明文片段被密鑰單詞的不同部分加密成了相同的密文;二、同樣的明文片段恰好由密鑰單詞在同樣的起始位置進行加密,形成了相同的密文。如果重復的字母組合足夠長,第一種情形出現的可能性就遠遠小于第二種。第二種情況還揭露一個事實:密鑰單詞長度一定是重復的字母組合位置相差數的因子。巴貝奇記錄下所有重復的密文字母組合位置之差,以及它們的所有因子,其中出現最多的因子就是密鑰單詞可能的長度。合位置之差,以及它們的所有因子,其中出現最多的因子就是密鑰單詞可能的長度。

知道了密鑰單詞長度這一重要信息,巴貝奇把密文分成N組分別由N個單字母表加密的片段。盡管這些零散的片段對應的明文是沒有意義的,但只要這個片段出自完整的、有意義的信息,那么它的字母頻率分布仍然遵守書寫信息所使用語言的規律。使用頻率分析法,維吉尼亞密碼就可以被破譯。加密者為了方便記憶,通常喜歡選取有意義的密鑰單詞,但這也使密碼變得更加不安全。

4

古典密碼學的圣杯

維吉尼亞密碼法看起來擁有龐大的密鑰空間,如果使用26個英文字母的排列組合作為密鑰單詞,僅長度為6的密鑰單詞就有超過3億種可能,為什么還是能夠被破解呢?維吉尼亞密碼法的缺陷就是循環使用固定的密碼表對明文加密,一旦循環長度被破譯者分析出來,整個加密算法就變的和單密碼表加密無異。為了增強維吉尼亞密碼的安全性,可以選用非常長的密鑰單詞,這樣一來,密文中出現重復字母組合的可能性就降低了很多,并且使用同一套密碼表加密的字母個數也隨之減少,猜測密鑰單詞長度和頻率分析法就失效了。

將這個理論發揮到極致,就是著名的“一次一密”加密法,這種加密法廣泛地運用在外交、軍事等需要不計代價地保證通信秘密的場合。“一次一密”,即每發送一條信息,就更換一個新的密鑰單詞,密鑰單詞的長度和要發送信息的長度相當,而且是隨機生成的,不包含任何有意義的單詞。秘密通信的雙方各持有一本密碼本,每進行一次通信,就撕下密碼本的一頁,使用下一頁的密鑰。從理論上來說,只要密碼本沒有泄露,即使破譯者截獲了某次通信的明文和密文,仍然無法破譯下次通信的密文,“一次一密”是真正安全的加密方式,被譽為古典密碼學的圣杯。

第二次世界大戰時,德軍使用的“恩尼格瑪”密碼機是一種近似“一次一密”的加密機械。由于“一次一密“加密法需要對每一條信息使用隨機的與明文等長度的密鑰進行加密以保證安全性,因此就需要事先編纂一本密碼本。而到了近代以后,戰爭期間情報部門每天需要處理海量的消息,使用這種密碼本,不僅不容易查閱密鑰,被敵人截獲的可能性也高出不少。

1918年,德國發明家亞瑟·雪畢伍斯發明了一種使用轉子密碼盤和機械結構的密碼機,并分為商用和軍用的版本。恩尼格瑪使用鍵盤輸入明文字母,輸入信號經過三個編碼器經過一系列別換,最終會點亮另一個鍵盤相應密文字母上的燈泡。最先接收輸入信號的編碼器每輸入一個字母,就會轉動一次,當它轉動完一周,下一個編碼器就會轉動一次,以此類推,三個安裝好的編碼器一共有26×26×26種不同的狀態,每一種狀態對應一個密碼表,在開始加密時,可以選擇任意一種狀態作為初始狀態,用來加密明文的“密鑰單詞”也隨著改變。除此之外,編碼器位置可以互換,輸入鍵盤和第一個編碼器之間還有一個稱為接線板的裝置,可以互換六對字母的輸入信號,有大約一千億種不同的互換方式。恩尼格瑪是歷史上最為可靠的機械式密碼機之一,但在英國傳奇數學家阿蘭·圖靈和布萊切利公園的盟軍密碼工作者的努力下,德國軍隊使用的部分型號恩尼格瑪密碼機未能免遭被破解的命運,德軍也為過于信任恩尼格瑪的安全性付出了慘重的代價,恩尼格瑪,是古典密碼學最后的輝煌。未能免遭被破解的命運,德軍也為過于信任恩尼格瑪的安全性付出了慘重的代價,恩尼格瑪,是古典密碼學最后的輝煌。

5

攻克“恩尼格瑪”

阿蘭·圖靈,今天人們以他的名字命名計算機科學領域的最高榮譽獎項。圖靈建立了計算機器的通用模型“圖靈機”,提出了“算法”的概念,還是第一個利用計算機器破解加密算法的人。

恩尼格瑪密碼機能夠由操作員設置的部分包括三個編碼器的位置、編碼器的起始位置、接線板互換的字母設置,密鑰空間超過10^16。德軍情報部門會事先編制一本密碼本,每天更換一次密鑰。由于恩尼格瑪曾有商用的版本,盟軍對它的構造原理與加密方式有一定的了解,加上盟軍繳獲的幾臺密碼機,恩尼格瑪的加密算法可謂無處可遁,但不知道密鑰的話,破譯德軍的加密情報仍然無從談起。

密碼分析學中,破譯方嘗試破解加密系統的行為稱為攻擊。根據柯克霍夫原則,假設加密系統除了密鑰之外的一切都是公開信息,攻擊實際上就是猜測密鑰的行為。根據攻擊者掌握的有關加密系統的信息量的多少,有以下攻擊類型:

惟密文攻擊:攻擊者只擁有關于密文的信息

已知明文攻擊:攻擊者擁有某些明文片段和對應的密文片段的信息

選擇明文攻擊:攻擊者可以獲得任意明文片段對應的密文信息

選擇密文攻擊:攻擊者可以獲得任意密文片段對應的明文信息

如果一個加密系統對已知明文攻擊是安全的,那么即使攻擊者截獲了一些密文和對應的明文,仍然無法解譯新的密文。單字母表和維吉尼亞加密法對于后三種攻擊方式都不安全。如果明文是有意義的文本,它們對于惟密文攻擊也是不安全的,通過頻率分析法就能夠輕松破解。“一次一密”,即密鑰長度等于明文長度的多字母表替換式加密法是對所有攻擊安全的。香農在“一次一密”法出現后30年創立了信息論,并從數學的角度證明了其安全性。而恩尼格瑪的安全性介于一次一密和維吉尼亞加密法之間,下面將簡要地說明圖靈破解恩尼格瑪的方法。

恩尼格瑪的插線板最多可以對換六對字母的信號,一個對換過程可以表示為

三個編碼器從左到右記為,,,相對初始狀態的位置記為,,,則插線板與編碼器對原始信號的共同作用可表示為

到這里為止,恩尼格瑪的設計都還中規中矩。發報員在鍵盤上按下按鍵,字母會被轉化為數字信號,經過處理后變成密文在密文鍵盤相應的位置點亮燈泡。那如果要解密怎么辦呢?密碼燈只能展示密文字母,而不能用做輸入。收到加密信息的一方需要與加密使用相同的鍵盤輸入密文解密,也就是要設計一種能夠同時進行加密和解密的電路,對任意明文字母以及對應的密文=()滿足:

雪比伍斯的方法是在三個編碼器之后,再加上一塊反射板,其作用是將最左邊一塊編碼器的輸出觸點兩兩連接起來,將其輸出信號反射回三個編碼器,再穿過接線板,連接到密文燈泡。記反射板變換為,它由十三對不同字母的對換復合而成,滿足

恩尼格瑪在某個特定編碼器狀態下的加密過程就可以表示為

對于惟密文攻擊,恩尼格瑪幾乎是牢不可破的。德軍每天會更換密鑰,每則密鑰加密的明文數量有限。密鑰的長度為17576,比大多數明文長度都要長,因而頻率分析法對恩尼格瑪也不起作用。但是對于已知明文攻擊,反射板設計的危害就體現出來了。盟軍繳獲了德軍的幾臺恩尼格瑪密碼機,并對一些已知的明文和密文進行對比,發現德軍公文的格式較為固定,經常在固定的位置出現同樣的單詞。比如德軍每天發送的天氣預報中會出現wetter這一單詞。圖靈還發現,有時明文和密文之間會出現一種特殊的循環結構,這有助于識別編碼器的狀態信息。假設已知明文為wetter,對應的密文如下:

可以看出這樣的循環是在的作用下產生的,與接線板設置無關。圖靈利用這一點,便可以不考慮接線板的接法,他使用三臺相同的恩尼格瑪密碼機,隨意設置第一臺的編碼器位置,記這個位置為,將第二臺設置為1,第三臺設置為3,并同步改變三臺密碼機的編碼器設置。將第一臺密碼機的輸出連接到第二臺的輸入,第二臺的輸出連接到第三臺的輸入,以此類推,從而模擬出同樣的加密過程。如果編碼器設置正確,就可以形成相同的循環回路。現在還不知道字母被接線板替換成了哪個字母,圖靈想到,連接兩臺密碼機所有對應的字母觸點,逐一嘗試可能的編碼器位置,只要有一個回路連通,就說明存在一個字母經過三臺密碼機被加密成它自身。這時的編碼器位置雖然不一定是正確的,但只要使用篩選出的編碼器位置還原明文,使用頻率分析逐個檢驗就可以破解接線板的設置了。

圖靈的設想成功地將搜尋密鑰的工作簡化了幾個數量級,英國圖表機械工廠根據圖靈的設計建造出了擁有十二臺密碼機的解密機器“炸彈”,可以分析長度為十二的循環結構。到了1942年底,布萊切利公園一共擁有49臺“炸彈”,最快在一小時內就可以找出德軍的當日密鑰,對盟軍占據情報上的優勢提供了極大的幫助。

要破解恩尼格瑪,已知明文與密文的對應片段、三個編碼器的內部線路都是不可缺少的。二戰期間,英國皇家空軍使用“栽培法”引誘德國海軍發送包含特定信息的密文。英國空軍在特定的地點布置水雷,故意讓德軍發送有關該地點坐標的情報,攔截下密文送往布萊切利公園,這也是一種選擇明文攻擊。

替換式加密算法與加密機械的弱點在于沒能完全消除密文中有關明文的某些特征,保留了明文中的某些信息,例如單字母表替換式加密法保留了明文語言中字母的頻率信息。有些則是設計上的缺陷,例如恩尼格瑪。德軍在二戰后期增加了編碼器的數量、接線板對換的字母對數量,卻沒意識到反射器才是根本缺陷。一些古典加密算法已經開始消除密文中反映的頻率信息,如同音替換式加密法,但始終沒能觸及加密算法安全問題的本質:如何降低攻擊者在了解加密算法,并擁有足夠長的密文片段的前提下,猜測出正確密鑰的可能性?

1948年,克勞德·香農發表了著名的論文《通信的數學理論》,開創了一門新的學科:信息論。隔年,香農發表了《加密系統的通信理論》(CommunicationTheoryofSecretarySystem),首先使用數學工具對加密系統進行分析。香農的理論使密碼學得以成為真正的科學,也標志著現代密碼學的開端。

參考文獻:

TheCodeBook,SimonSingh(1999)

TheCodeBreakers,DavidKahn(1996)

附注:

因一些原因,本文中的一些名詞標注并不是十分精準,主要如:通證、數字通證、數字currency、貨幣、token、Crowdsale等,讀者如有疑問,可來電來函共同探討。

本文為通證通研究院原創。未經授權,禁止擅自轉載。

Tags:區塊鏈PPLPLEripple區塊鏈dapp開發pdfAPPLEPLEX幣ripple幣最新行情

狗狗幣
LIBRA:G7:Libra威脅全球金融穩定 將制定“最高”的監管標準

據路透社報道,七國集團稱Facebook的Libra這樣的加密貨幣對全球金融的穩定構成了威脅。G7已成立了一個專門的工作組負責審查加密貨幣相關問題,該小組稱需要制定“最高”標準的監管措施,以最大.

1900/1/1 0:00:00
USD:“巴菲特午餐”20年首次取消 幣圈應聲暴跌

中國基金報記者凌云 巴菲特午餐突然被取消?不過這一次,是孫宇晨“鴿”了。7月23日凌晨,波場TRON創始人孫宇晨突然在個人微博上發布消息稱,“本人因突發腎結石正于醫院治療,因故取消與巴菲特先生的.

1900/1/1 0:00:00
KKT:超級大牛市將至?“幣圈紐交所”Bakkt正式開啟用戶測試 預計本季度上線

“同時擁有紐交所母公司背景、雄厚資金、監管合規等優勢的Bakkt,將對加密貨幣市場中的其他參與者帶來重要一擊,從而極大改變比特幣交易量的占比.

1900/1/1 0:00:00
COI:KuCoin上線Dapp.com (DAPPT)!

親愛的KuCoin用戶:KuCoin現已上線項目Dapp.com(DAPPT)并支持交易對:DAPPT/BTC和DAPPT/USDT.

1900/1/1 0:00:00
USD:交易穩定幣,限時30天享0手續費!

尊敬的用戶, 為慶祝HUSDToken正式上線,火幣全球站將推出為期兩周的《交易穩定幣,限時兩周享0手續費!》活動.

1900/1/1 0:00:00
USD:美元穩定幣HUSD Token達“破產豁免”級 或成USDT避雷首選

北京時間22日晚間,關乎USDT發展命運的聽證會即將到來。本次聽證會重點聚焦在,USDT發行方Tether涉嫌挪用9億美元USDT準備金,幫Bitfinex補足虧空.

1900/1/1 0:00:00
ads