第七章 密码体制的安全性测度.ppt

第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是指攻