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

第第7 7章：信息论与密码体制的安全性测度章：信息论与密码体制的安全性测度Shannon 的信息论和保密码通信理论的信息论和保密码通信理论1. 信息论与密码学的发展信息论与密码学的发展u古典密码学：古典密码学：密密码专家常常根据自己的感家常常根据自己的感觉和和经验进行密行密码设计和分析，密和分析，密码设计中的技巧性和中的技巧性和经验性很性很强强. .l ShannonShannon：美国工程师：美国工程师 19481948年发表年发表 “A Mathematical Theory of A Mathematical Theory of ommunicationommunication”，标志信息论的诞生，标志信息论的诞生 19491949年发表年发表 “Communication Theory of Secrecy Communication Theory of Secrecy systemsystem”，以信息论为基础，用概率统计为数学手段，以信息论为基础，用概率统计为数学手段对保密通信问题进行了分析对保密通信问题进行了分析由香农提出的保密系统模型目前仍然是现代密码学的由香农提出的保密系统模型目前仍然是现代密码学的基本模型基本模型. .• 19731973年，美国国家年，美国国家标准局（准局（NBSNBS））发布了公开征集布了公开征集标准分准分组密密码算法算法(DES)(DES)的决定的决定• 公钥密码学建立：公钥密码学建立：19761976年，年，Diffie Diffie 和和 Hellman Hellman 提提出了出了公公钥密码设计思想密码设计思想u 公开公开DESDES算法和公算法和公钥密密码学的建立学的建立标志着志着现代密代密码学的开始学的开始• 美国在美国在20002000年公布了高年公布了高级加密加密标准准(AES-Advanced (AES-Advanced Encryption Standard), Encryption Standard), 欧洲在欧洲在20002000年年1 1月也推出了月也推出了欧洲加密标准评选欧洲加密标准评选计划，在划，在20032003年年2 2月月2727日公布了各日公布了各个算法个算法标准准2. Shannon 的信息论与信息传输理论的信息论与信息传输理论 Shannon通信系统 Shannon通信系统通信系统: :信源：信源：产生信息的来源产生信息的来源编码：编码：把信息变为信号的运算以适合在信道中的传输把信息变为信号的运算以适合在信道中的传输信道：信道：用来从发射者到接收者之间传输信号的介质用来从发射者到接收者之间传输信号的介质译码：译码：把信号变为信息的运算把信号变为信息的运算信宿：信宿：信息传输的归宿和目的地，信息接收人或仪器信息传输的归宿和目的地，信息接收人或仪器 编码编码译码译码信宿信宿信源信源信道信道干扰源干扰源3. 信息安全与密码学信息安全与密码学 密码学密码学(Cryptology):是研究密码系统或通信信息是研究密码系统或通信信息安全的一门科学。

它主要包括两个分支安全的一门科学它主要包括两个分支: :密码编码学密码编码学和密码分析学和密码分析学u密码编码学密码编码学(Cryptography):寻找确保信息保密寻找确保信息保密或信息得到认证的方法或信息得到认证的方法u密码分析学密码分析学(Cryptanalytics): 主要是研究破译主要是研究破译加密信息或消息的伪造加密信息或消息的伪造密码技术革新是信息安全的关键技术密码技术革新是信息安全的关键技术. .ShannonShannon保密通信系统保密通信系统 公开信道公开信道密钥信道密钥信道n明文明文(Plaintext):没有加密的消息没有加密的消息n密文密文(Ciphertext):加密后的消息加密后的消息n加密算法加密算法(Encryption):将明文将明文变换成密文的成密文的过程程n解密算法解密算法(Decryption): 将密文恢复成明文的将密文恢复成明文的过程程加密和解密加密和解密过程通常在一程通常在一组密密钥(key)(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。

密码体系形式化描述密码体系形式化描述§加密算法足够强大：加密算法足够强大：仅知密文很难破译出明文仅知密文很难破译出明文§基于密钥的安全性，而不是基于算法的安全性：基于密钥的安全性，而不是基于算法的安全性：基于密文和基于密文和加加/解密算法很难破译出明文解密算法很难破译出明文§算法开放性：算法开放性：开放算法，便于实现开放算法，便于实现加密的安全性问题加密的安全性问题n理论安全和实际安全理论安全和实际安全n理论安全，或无条件安全：理论安全，或无条件安全： 攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文Shannon用理论证明：欲达理论安全，加密密钥长度必须大于等于用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密，明文长度，密钥只用一次，用完即丢，即一次一密，One-time Pad，不实用n实际安全，或计算上安全：实际安全，或计算上安全： 如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行则称这个系统是计算上安全的或破译这个系统是计算上不可行（（Computationally Infeasible）。

n无条件保密性也叫无条件保密性也叫完善保密性完善保密性一个保密系统具有一个保密系统具有完善保密性，是指攻击者在有无限的攻击时间和资完善保密性，是指攻击者在有无限的攻击时间和资源下无法破译此系统源下无法破译此系统Shannon在理论上证明了在在理论上证明了在唯密文攻击条件下完善保密性的系统是存在的唯密文攻击条件下完善保密性的系统是存在的一次一密一次一密”(one-time pad) 保密系统保密系统:u假设密钥空间大于或等于明文空间，密钥空间的各个分量是统计独立假设密钥空间大于或等于明文空间，密钥空间的各个分量是统计独立的，并且是等概率地选取，对不同的明文用不同的密钥进行加密在的，并且是等概率地选取，对不同的明文用不同的密钥进行加密在此假设条件下，仅从密文得不到明文的任何信息此假设条件下，仅从密文得不到明文的任何信息u“一次一密一次一密”保密系统在理论上被认为是不可破译的即使密码分析保密系统在理论上被认为是不可破译的即使密码分析者知道了和一段密文相对应的明文，他也仅仅得到了这一段的密钥，者知道了和一段密文相对应的明文，他也仅仅得到了这一段的密钥，由于密钥空间大于或等于明文空间，由于密钥空间大于或等于明文空间，密钥不重复使用密钥不重复使用，因此，已知密，因此，已知密钥对其他密文并不适用钥对其他密文并不适用u但是，进行大量的明文加密，产生如此多的一但是，进行大量的明文加密，产生如此多的一次一密的密钥十分困难，密钥的管理和通信双次一密的密钥十分困难，密钥的管理和通信双方的沟通也有困难。

实际的加密系统是通过双方的沟通也有困难实际的加密系统是通过双方共享重复使用的有限长度的主密钥，利用算方共享重复使用的有限长度的主密钥，利用算法复杂性产生伪随机数进行加密法复杂性产生伪随机数进行加密所以：一次一密（所以：一次一密（one-time pad）方）方案不实用案不实用u熵的密码意义：熵的密码意义： 如如果果H(M)=0,则则表表示示该该信信息息不不含含任任何何不不确确定定性性，，因因此此，，该该信信息息或或该该事事件件百百分分之之百百会会发发生生从从通通信信的的角角度度看看，，既既然然该该信信息息百百分分之之百百会会发发生生，，意意义义就就不不大大，，没没有有必必要要再再发送 反之，如果反之，如果H(M)很大，则表示信息的不确定性很很大，则表示信息的不确定性很大，从而收方收到该信息时，其信息量就相当大（重要）大，从而收方收到该信息时，其信息量就相当大（重要）了 从安全角度看，如果信息的熵值不大，即不确定性从安全角度看，如果信息的熵值不大，即不确定性太小，此条件提供攻击者很大的概率可以猜中该信息，太小，此条件提供攻击者很大的概率可以猜中该信息，从密码技术角度来说，就易破解；反之，从密码技术角度来说，就易破解；反之，熵值越大，越熵值越大，越难破解难破解。

4. 熵与密码学熵与密码学 n从信息论的观点看，一个保密系统（从信息论的观点看，一个保密系统（P，，C，，K，，E，，D）称为完善的无条件的保密系统，如果）称为完善的无条件的保密系统，如果H( (P)=)=H( (P| |C) )知道密文与不知道密文时，关（知道密文与不知道密文时，关于明文的熵大小一样）于明文的熵大小一样）n对于完善保密系统，也有对于完善保密系统，也有H( (K)=)=H( (K| |C) )u密码体制的熵密码体制的熵u从从ShannonShannon理论知道，仅当可能的密钥数目至少与可理论知道，仅当可能的密钥数目至少与可能的消息数目一样多时，它完全保密才是可能的换能的消息数目一样多时，它完全保密才是可能的换句话说，密钥至少必须与消息本身一样长，并且没有句话说，密钥至少必须与消息本身一样长，并且没有密钥被重复使用时，这就是一次一密体制密钥被重复使用时，这就是一次一密体制u所以可以说，密码体制的熵可用密钥空间大小的量度所以可以说，密码体制的熵可用密钥空间大小的量度即密钥的数目为即密钥的数目为K的密码体制的熵为：的密码体制的熵为：H（（K））=log2Ku一般而言，一个密码体制的熵越大，不确定性越大，一般而言，一个密码体制的熵越大，不确定性越大，破译它就越困难。

破译它就越困难u所以，要构造一个完善保密系统，其密钥量的对数所以，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集（密钥空间为均匀分布的条件下）必须不小于明文集的熵的熵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是指攻击者在进行唯密文攻击时必处是指攻击者在进行唯密文攻击时必处理的密文量的理论下界：理的密文量的理论下界：亦即截获的密文越多， 从中提取的 关于密钥的信息就越多 当疑义度减小到零， 即 时 (7.4.9) 密钥被完全确定，从而实现破译如果令 (7.4.10) 代表明文信息变差， 其中 和 分别代表明文熵和明文最大熵， 可以证明， 唯一解距离 (7.4.11) 密码分析攻击有密码分析攻击有6类类 惟密文攻击惟密文攻击 已知明文攻击已知明文攻击 选择明文攻击选择明文攻击 自适应选择明文攻击自适应选择明文攻击 选择密文攻击选择密文攻击 选择密钥攻击选择密钥攻击 分析方法分析方法 数学方法数学方法 边信道攻击边信道攻击 数学方法数学方法 穷举搜索穷举搜索 统计分析统计分析 逆向推理逆向推理 线性分析线性分析 差分分析差分分析 相关分析相关分析 边信道攻击边信道攻击 时间攻击时间攻击 能量攻击能量攻击 电磁攻击电磁攻击 故障攻击故障攻击 。