第七章 密碼體制的安全性測度.ppt

第7章 信息論與密碼體制的安全性測度 Shannon的信息論和保密碼通信理論 1 信息論與密碼學(xué)的發(fā)展古典密碼學(xué) 密碼專家常常根據(jù)自己的感覺和經(jīng)驗(yàn)進(jìn)行密碼設(shè)計(jì)和分析 密碼設(shè)計(jì)中的技巧性和經(jīng)驗(yàn)性很強(qiáng) Shannon 美國工程師1948年發(fā)表 AMathematicalTheoryofommunication 標(biāo)志信息論的誕生1949年發(fā)表 CommunicationTheoryofSecrecysystem 以信息論為基礎(chǔ) 用概率統(tǒng)計(jì)為數(shù)學(xué)手段對保密通信問題進(jìn)行了分析 由香農(nóng)提出的保密系統(tǒng)模型目前仍然是現(xiàn)代密碼學(xué)的基本模型 1973年 美國國家標(biāo)準(zhǔn)局 NBS 發(fā)布了公開征集標(biāo)準(zhǔn)分組密碼算法 DES 的決定公鑰密碼學(xué)建立 1976年 Diffie和Hellman提出了公鑰密碼設(shè)計(jì)思想公開DES算法和公鑰密碼學(xué)的建立標(biāo)志著現(xiàn)代密碼學(xué)的開始 美國在2000年公布了高級加密標(biāo)準(zhǔn) AES AdvancedEncryptionStandard 歐洲在2000年1月也推出了歐洲加密標(biāo)準(zhǔn)評選計(jì)劃 在2003年2月27日公布了各個(gè)算法標(biāo)準(zhǔn) 2 Shannon的信息論與信息傳輸理論 Shannon通信系統(tǒng) Shannon通信系統(tǒng) 信源 產(chǎn)生信息的來源編碼 把信息變?yōu)樾盘柕倪\(yùn)算以適合在信道中的傳輸信道 用來從發(fā)射者到接收者之間傳輸信號的介質(zhì)譯碼 把信號變?yōu)樾畔⒌倪\(yùn)算信宿 信息傳輸?shù)臍w宿和目的地 信息接收人或儀器 3 信息安全與密碼學(xué)密碼學(xué) Cryptology 是研究密碼系統(tǒng)或通信信息安全的一門科學(xué) 它主要包括兩個(gè)分支 密碼編碼學(xué)和密碼分析學(xué) 密碼編碼學(xué) Cryptography 尋找確保信息保密或信息得到認(rèn)證的方法密碼分析學(xué) Cryptanalytics 主要是研究破譯加密信息或消息的偽造密碼技術(shù)革新是信息安全的關(guān)鍵技術(shù) Shannon保密通信系統(tǒng) 明文 Plaintext 沒有加密的消息密文 Ciphertext 加密后的消息加密算法 Encryption 將明文變換成密文的過程解密算法 Decryption 將密文恢復(fù)成明文的過程加密和解密過程通常在一組密鑰 key 的控制下進(jìn)行 密鑰分別稱為加密密鑰和解密密鑰 基本概念 密碼體制系是一個(gè)五元組 P C K E D 滿足條件 1 P是可能明文的有限集 明文空間 2 C是可能密文的有限集 密文空間 3 K是一切可能密鑰構(gòu)成的有限集 密鑰空間 4 任意k K 有一個(gè)加密算法ek E和相應(yīng)的解密算法dk D 使得ek P C和dk C P分別為加密解密函數(shù) 滿足dk ek x x 這里x P 密碼體系形式化描述 加密算法足夠強(qiáng)大 僅知密文很難破譯出明文基于密鑰的安全性 而不是基于算法的安全性 基于密文和加 解密算法很難破譯出明文算法開放性 開放算法 便于實(shí)現(xiàn) 加密的安全性問題 理論安全和實(shí)際安全理論安全 或無條件安全 攻擊者無論截獲多少密文 都無法得到足夠的信息來唯一地決定明文 Shannon用理論證明 欲達(dá)理論安全 加密密鑰長度必須大于等于明文長度 密鑰只用一次 用完即丟 即一次一密 One timePad 不實(shí)用 實(shí)際安全 或計(jì)算上安全 如果攻擊者擁有無限資源 任何密碼系統(tǒng)都是可以被破譯的 但是 在有限的資源范圍內(nèi) 攻擊者都不能通過系統(tǒng)地分析方法來破解系統(tǒng) 則稱這個(gè)系統(tǒng)是計(jì)算上安全的或破譯這個(gè)系統(tǒng)是計(jì)算上不可行 ComputationallyInfeasible 無條件保密性也叫完善保密性 一個(gè)保密系統(tǒng)具有完善保密性 是指攻擊者在有無限的攻擊時(shí)間和資源下無法破譯此系統(tǒng) Shannon在理論上證明了在唯密文攻擊條件下完善保密性的系統(tǒng)是存在的 一次一密 one timepad 保密系統(tǒng) 假設(shè)密鑰空間大于或等于明文空間 密鑰空間的各個(gè)分量是統(tǒng)計(jì)獨(dú)立的 并且是等概率地選取 對不同的明文用不同的密鑰進(jìn)行加密 在此假設(shè)條件下 僅從密文得不到明文的任何信息 一次一密 保密系統(tǒng)在理論上被認(rèn)為是不可破譯的 即使密碼分析者知道了和一段密文相對應(yīng)的明文 他也僅僅得到了這一段的密鑰 由于密鑰空間大于或等于明文空間 密鑰不重復(fù)使用 因此 已知密鑰對其他密文并不適用 但是 進(jìn)行大量的明文加密 產(chǎn)生如此多的一次一密的密鑰十分困難 密鑰的管理和通信雙方的溝通也有困難 實(shí)際的加密系統(tǒng)是通過雙方共享重復(fù)使用的有限長度的主密鑰 利用算法復(fù)雜性產(chǎn)生偽隨機(jī)數(shù)進(jìn)行加密 所以 一次一密 one timepad 方案不實(shí)用 熵的密碼意義 如果H M 0 則表示該信息不含任何不確定性 因此 該信息或該事件百分之百會發(fā)生 從通信的角度看 既然該信息百分之百會發(fā)生 意義就不大 沒有必要再發(fā)送 反之 如果H M 很大 則表示信息的不確定性很大 從而收方收到該信息時(shí) 其信息量就相當(dāng)大 重要 了 從安全角度看 如果信息的熵值不大 即不確定性太小 此條件提供攻擊者很大的概率可以猜中該信息 從密碼技術(shù)角度來說 就易破解 反之 熵值越大 越難破解 4 熵與密碼學(xué) 從信息論的觀點(diǎn)看 一個(gè)保密系統(tǒng) P C K E D 稱為完善的無條件的保密系統(tǒng) 如果H P H P C 知道密文與不知道密文時(shí) 關(guān)于明文的熵大小一樣 對于完善保密系統(tǒng) 也有H K H K C 密碼體制的熵從Shannon理論知道 僅當(dāng)可能的密鑰數(shù)目至少與可能的消息數(shù)目一樣多時(shí) 它完全保密才是可能的 換句話說 密鑰至少必須與消息本身一樣長 并且沒有密鑰被重復(fù)使用時(shí) 這就是一次一密體制 所以可以說 密碼體制的熵可用密鑰空間大小來度量 即密鑰的數(shù)目為K的密碼體制的熵為 H K log2K一般而言 一個(gè)密碼體制的熵越大 不確定性越大 破譯它就越困難 所以 要構(gòu)造一個(gè)完善保密系統(tǒng) 其密鑰量的數(shù)目 密鑰空間為均勻分布的條件下 必須不小于明文集的熵 5 互信息量與保密性 從密文C中提取關(guān)于明文P的信息為 7 4 1 或從密文中提取密鑰信息 7 4 2 因此 P C 和 K C 越大 攻擊者從密文中獲得明文或密鑰信息越少 7 4 3 于是 7 4 4 對于合法用戶 知道密鑰和密文 就可以得到明文 即 說明對于合法用戶 知道密鑰和密文的情況下 就可以得到全部明文 7 4 說明 密鑰空間越大 從密文中可以提取的關(guān)于明文的信息量就越小 對于完善保密系統(tǒng) 有 7 4 當(dāng)密鑰空間大于明文空間 即 7 4 定理 對任意密碼系統(tǒng) 有 唯一解距離 設(shè)給定 長密文序列 其中 為密文字母表 根據(jù)條件熵的性質(zhì) 7 4 易知 隨著 的增大 密鑰疑義度 K C 減小 唯一解距離 設(shè)V0是指攻