【文章內容簡介】 1xm c c p??? 。 m 。 天津科技大學 2020屆本科生畢業(yè)論文 12 密碼的攻擊方法 密碼攻擊者分析密碼攻擊密碼的方法主要有三種：窮舉攻擊、統(tǒng)計分析攻擊和數(shù)學分析攻擊 [13]。 第一種 窮舉分析攻擊 ， 是嘗試一切 密鑰的可能性 對所獲得的密文解密，一直到找到正確的密文為止，或者將全部可能的明文通過一個固定的密鑰 加密，一直到找到與所獲得的密文相同的明文為止，理論上來講對于任何的密碼都能通過這樣的方式破解只要 有足夠多的資源。 第二種 統(tǒng)計分析攻擊 ， 是利用 前人對明文和密文總結 統(tǒng)計 的一定規(guī)律來破解密碼，很多的古典密碼都無法抵御這種攻擊的方法 ，比如分析密 文中字母與字母組出現(xiàn)的次數(shù) 或者其它的統(tǒng)計參數(shù)，對于對抗這種攻擊的有效方式就是使密文中找不到明文的統(tǒng)計特性，如此一來，密文中就沒有明文的痕跡了，從而抵抗了統(tǒng)計分析攻擊的可能，而這一點也成為了近代密碼的一項基本要求 [5]。 最后一種 數(shù)學分析攻擊 ，是想要破譯 密碼的人通過 數(shù)學分析的方法來分析密碼， 針對 密碼學一些基本的數(shù)學知識的特征，找到破解密碼的 數(shù)學解決方案 [5]。對于各類 主要的密 碼攻擊方式，其中數(shù)學分析攻擊是最具有難度的，需要選取具有堅實數(shù)學基礎，同時還要十分 復雜 難解的加解密算法 ， 才有可能與其對抗。 對于密碼的分析者或者說破譯人而言，可以利用數(shù)據(jù)信息的資源來分類，將密碼的破解類型劃 分為四種：僅知道密文的攻擊，已經知道明文的攻擊，選取明文來攻擊或者選取 密文來攻擊 [5]。僅知道密文的攻擊就是通過了解分析截獲的密文來破解密碼，因為此時自由密文可以作為資源來使用，所以這也是對密碼破譯者最不利的一種情況。所謂的已經知道明文的攻擊，就是指密碼的破譯人通過已經知道的某一些明文和密文對應著來破解， 比如說計算機程序檔經過加密后的密文中有大量的諸如“ IF”，“ BEGIN”，“ END”，“ THEN”等詞，而這些詞匯會非常規(guī)律地出現(xiàn)在密文之中，密碼的破譯者可以十分合理的推測出它們，所以近代密 碼學認為只有能經受住已知明文攻擊的密碼才會是可取的密碼。選取明文來攻擊就是在選取明文并且獲得相對應的密文來攻擊， 這是十分有利的情況，比如說計算機的數(shù)據(jù)庫和文件系統(tǒng)就十分容易遭受這樣的攻擊 [5]，因為用戶通過隨意的選擇明文并且獲得相對應的密文數(shù)據(jù)庫和密文文件。最后一種類型也就是選擇密文來攻擊，這種情況對破譯密碼的人來說也是 非常有利的，破譯者通過選擇密文并且獲得相對應的明文，再進行破解密碼的工作。最后的這種攻擊方式主要是用來攻擊公開密鑰密碼體制，尤其是攻擊其數(shù)字簽名。假如有一個密碼是無論密碼的分析人獲得了多少的密文和明文并使用了任何的技術方法對其進行攻擊都不能被破解，就稱其為絕對不可破譯的，這種情況的出現(xiàn)需要滿足三個條件： 密鑰是隨機序列 密鑰最短也要和明文是一樣長的長度 一個密鑰就只可能是用一次，理論上這種密碼是存在的，最為著名的就是“一次一密”密碼， 密鑰是一次性使用的，也正是因為這個原因導致 密鑰管理十分困難， 所以 實際 上是不天津科技大學 2020屆本科生畢業(yè)論文 13 能 廣泛使用的 [5]。所以，總的來說只要有充足的信息 就能破譯實際上可以使用的任何密碼。 密碼的設計 由于通訊、計算機以及網(wǎng)絡的技術 發(fā)展，使計算機網(wǎng)絡得到了廣泛應用 [4]，同時也將全世界的計算機連在了一起，由此形成了一種巨大的計算能力從而形成了非常大的一種破解密碼的能力，是最初十分安全的密碼變得不再安全。有學者 曾發(fā)表論文，認為從信息論的角度出發(fā)，對密鑰、加密、密碼以及信息源進行詳細地數(shù)學分析，使用唯一解距離及不確定性測試各類密碼體制的安全性能 [6]，并且闡述純密碼、理論保密、 實際保密等相關重要的概念，將密碼置于夯實的數(shù)學基礎上。同時闡明自己的觀點，提議采取混淆、擴散及乘積迭代的方法 [6]，使設計出來的密碼更安全?；煜龑嶋H上就是讓密鑰與密文的關聯(lián)變得復雜化，從而可以使明文密文及密文 密鑰之間的聯(lián)系減少也就是降低了它們之間的相關性，統(tǒng)計相關性 越小統(tǒng)計分析中的數(shù)據(jù)信息就越沒有作用，從而提高了密碼的安全性能； 所 說的擴散是將明文中每位明文和密鑰形成在密文中最大程度的影響，即密文中的每一位都可以成為明文和密鑰的一個函數(shù)，也 就達到了完備性。一般來說設計一個比較復雜的密碼是十分困難的，但是設計一 個相對簡單的密碼就很容易了，所以對 簡單的密碼使用乘積迭代的方法，將其簡單密碼進行組合迭代，然后獲取一個預期的混淆及擴散，最后就能擁有 一個相對安全的密碼 [6]。其實設計一個相對比較安全的密碼就是需要尋找一個非常復雜的難解的問題，利用這一問題就能設計出比較理想的密碼了。因為一個實用的理想的密碼應該是一個不害怕公開加密算法的密碼，也就是說一種密碼的設計應該遵守公開設計的原則，這樣才能使設計出來的密碼 不會因為加密算法的暴露而功虧一簣 ， 只需要將密鑰保密即可 ，算法公開的密碼才能更適應未來的環(huán)境。但是，密碼中加密算法的公 開原則也并不是適用于所有的領域的，比如各國的軍事政治核心，這類的密碼就都不公開加密算法，所以設計密碼和使用密碼的正確方式還是在公開原則下對已經測試過安全性能的密碼使用保密算法的方式更為穩(wěn)妥。 密碼學既是一門科學也是一門技術，運用科學的知識和理論將其運用到實際中，數(shù)據(jù)信息通過加密形成密文存儲在計算機的文件之中，或者傳輸在網(wǎng)絡信道之中，并只會給合法的用戶分配密鑰，當然這一切都是在密鑰的控制下進行，實用又安全，尤其能適用于現(xiàn)在的網(wǎng)絡安全中。 天津科技大學 2020屆本科生畢業(yè)論文 14 3 橢圓曲線 概述 橢圓曲線的定義及點的加法運算 橢圓曲線 其實 并不是橢圓 形狀，只是因為橢圓曲線的 方程和計算橢圓周長的方程類似， 所以稱它為橢圓曲線， 橢圓曲線的方程是： 2 3 21 3 2 4 6y a x y a y x a x a x a? ? ? ? ? ? 其中 , , , , , ( )1 2 3 4 5 6a a a a a a F F? 是 一 個 域，而 F 域既可以是一個有理數(shù)域也可以是一個復數(shù)域還可以是有限域 ()GFp ，通常將滿足上述方程的數(shù) (, )xy 稱為 F 域中橢圓曲線 E 上的點 [4]。 假設 P 點和 Q 是點橢圓曲線上的兩個點并在橢圓曲線上定義加法運算 +PQR? ， R 表示通過連接 P 點和 Q 點的直線 與橢圓曲線 E 相交，交點關于 x 軸對稱的點稱為 R 點。如圖 31。 P Q R 圖 31 點 加 運 算 特別地，如果 P 點和 Q 點是重合的， R 就表示 P 點的切線與橢圓曲 線 E 的交點關于 x 軸對稱的點，即 2P Q P P P R? ? ? ? ?。 這里定義的加法運算需要引進一個零元素，將 0 定義為一個無窮點即0??（ ， ） ，那么 天津科技大學 2020屆本科生畢業(yè)論文 15 0 + 0 = 0 0 0? ? ? ? ? ?（ ， ） （ ， ） 并且 0 , + = 0 ,P P P? ? ? ? ?（ ） （ x,y ） （ x,y ） + （ ） （ x,y ）， 假設 ( , )11Px y 和 ( , )22Qx y 是解點，如果 ,1 2 1 2x x y y? ?? 就有 ( , )+ Q ( , )= 01 1 2 2P x y x y， 當 ( , )11Px y 和 ( , )22Qx y 不相等的時候就有 ( , ) + Q ( , ) = ( , )1 1 2 2 3 3P x y x y R x y， 其中 23 1 2x x x?? ? ? ， ()3 1 3 1y x x y?? ? ?， ( ) / ( )2 1 2 1y y x x? ? ? ?， 如果 P 點和 Q 點是重合的，那么 2 231xx???， ()3 1 3 1y x x y?? ? ?， 2(3 ) / (2 )11x a y??? 。 由此可知橢圓曲線 E 在有限域 F 上的加法運算，構成了加法交換群并且加法單位元為 0[4]。 有限域上的 橢圓曲線 對有理 數(shù)、實數(shù)、復數(shù)等常見的數(shù)系和它們基本特征的抽象稱為 域， 是由一個集合 和加法乘法兩種運算來組成的 [4]。 一個集合域，域中除 0 以外的數(shù)位如果滿足以下的特性： 域對加法封閉，并對加法運算構成加法交換群； 域 對乘法封閉，并對乘法運算構成乘法交換群； 使分配律成 立，對域中任意的數(shù)字 ,abc都有 ()a b c a c b c? ? ? ? ? ?成立，并且這個集合是有限集合，那就稱這個域為有限域。 有限域中含有元素的個數(shù)被 稱為這個有限域的階。如果在有限域 F 上定義出一條橢圓曲線 E ，那么橢圓曲線 E 的個數(shù)就稱為在有限域 F 上橢圓曲線 E 的階。 橢圓曲線 的離散 對數(shù)問題 橢圓曲線離散對數(shù)問題就是指在有限域 F 上定義出一條橢圓曲 線 E ，在 E 上給定一個基點 P 并計算出階 N [4]即 0NP? 。 天津科技大學 2020屆本科生畢業(yè)論文 16 然后在橢圓曲線 E 上尋找任意一點 Q ， 在 [0, 1]N? 的范 圍內找一個正整數(shù) k 使 =QkP 成立，這時將正整數(shù) k 稱為點 Q 對點 P 的橢圓離散對數(shù)即將 k 表示為 logkQp? 。 已知橢圓曲線 E 的 離散對數(shù) k 和 E 上的一個基點 P 可以比較容易將點 Q 計算出來，但是如果已知點 Q 和 E 上的一個基點 P 想要計算出 離散對數(shù) k 是十分難的 ， 以至于迄今為止都 沒有有效的方法來計算， 同時也正是因為有這樣難解 的問題存在， Koblitz 和 Miller 就在這個基礎上建立了橢圓曲線密碼體制 ECC 而這也正是橢圓曲線密碼的加密原理 [4]。 天津科技大學 2020屆本科生畢業(yè)論文 17 4 橢圓曲線 密 碼體 制 橢圓曲線 密 碼體 制的概念 橢圓曲線 密 碼體 制是屬于 公 鑰 密 碼體 制 中的一種 ， 它 主要的 數(shù)學 理論 基 礎 是源于 數(shù)論 的相關知識，它是通過有限域中 橢圓曲線上 的 點 構成的 Aebel 加法群，在 Aebel 群 中 計算 橢圓對數(shù) [4] 。 現(xiàn) 在 國際 上比較 流行的密 碼體 制 都是以 三 種難解的 理論 為依據(jù)而設計的，其中 一 種 是基于大整 數(shù)因 子分解 問題 設計的 比 如 RSA 公鑰密碼體制，還有一種 是基于 離散對數(shù) 的難解問題而設計的 比如 ELGamal 公鑰密碼體制，最后一種就 是同樣基于離散對數(shù)問題設計的 橢圓曲線密碼體制 [4]。 下面簡述一下橢圓曲線的離散對數(shù)問題，首先我們在有限域 Fp 上選取一條橢圓曲線 E ， p 是 ()EFp 上的點， p 是素數(shù) n ，那么 集合 ? ?, , 2 ,3 , ,( 1 )P P P P n P? ? ??? ? 是 利用 P 生成的橢圓曲線循環(huán)子群， 其中的 素數(shù) p ，橢圓曲線 E ，點 p 和階 n 構成 一個 公開 的 參數(shù)組 [4]。在區(qū)間 [1, 1]n? 內隨機 地選取一個 正整數(shù) d 作為算法中的私鑰 ，相 對 應的公鑰 就是 Q dP? 。 而這種需要通過 公開 的 參數(shù)組和公鑰 Q 求 得 私鑰 d 的問題就是橢圓曲線 的離散對數(shù)問題 簡稱 ECDLP[4] (The elliptic curve discrete logarithm problem) [4]。 下面將詳細地 介紹橢圓曲線 上 生成 密鑰對 、 加密和 解密 的具體過程 。 以二進制域作為例子，構造橢圓曲線具體見下表 ： 天津科技大學 2020屆本科生畢業(yè)論文 18 表 41 在二 進 制域上 隨 機 的生成 橢圓曲線 在二 進 制域2mF上： 輸 入： 一個 正整 數(shù) m 和 1比特 雜湊 函 數(shù) [4]H 。 輸 出：種子2, mS ab F?， 定 義 一條 橢圓曲線 [4] 2 3 2:E y xy x ax b? ? ? ?。 1．令 ( 1) /s m l??????， lms??? 。 2. S選 取 一 個 隨 機 的 二 進 制 串，其 長 度 g1bit? 。 算 ()h HS? ，令 0b 是 h的 最 右 邊 ?比 特 ?所 得 長 度 為 的 二 進 制 串。 z S是 與 二 進 制 表 示 相 等 的 整 數(shù)。 i 從 1到 s ， 執(zhí) 行： is 為 整 數(shù) ( )mod2gzi? 的 g 位二 進 制表示。 算 ()iib H s? 。 0 1 0|| || || ||b b b b? ??? 。 0b? ， 則 跳至步 驟 2。 任意的 2maF?。 ( , , )Sab 。 橢圓曲線 的 參數(shù)組 參數(shù)組的定義 橢圓曲線 的 參數(shù)組 是 描述 有限域 qF 上定義的 橢圓 曲線 [4] E ， E 上的 基點()qp EF? 和 階 n ， 其中選取的參數(shù)需要抵御全部 已知的密碼攻擊 使 ECDLP 的安全性高于其他