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