第七章 密碼體制的安全性測(cè)度.ppt

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