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

1、第第7 7章：信息论与密码体制的安全性测度章：信息论与密码体制的安全性测度Shannon 的信息论和保密码通信理论的信息论和保密码通信理论1. 信息论与密码学的发展信息论与密码学的发展u古典密码学：古典密码学：密码专家常常根据自己的感觉和经验密码专家常常根据自己的感觉和经验进行密码设计和分析，密码设计中的技巧性和经验进行密码设计和分析，密码设计中的技巧性和经验性很强性很强. .l ShannonShannon：美国工程师：美国工程师 19481948年发表年发表 “ “A Mathematical Theory of A Mathematical Theory of ommunication”

2、ommunication”，标志信息论的诞生，标志信息论的诞生 19491949年发表年发表 “ “Communication Theory of Communication Theory of Secrecy system”Secrecy system”，以信息论为基础，用概率统计，以信息论为基础，用概率统计为数学手段对保密通信问题进行了分析。为数学手段对保密通信问题进行了分析。由香农提出的保密系统模型目前仍然是现代密码学由香农提出的保密系统模型目前仍然是现代密码学的基本模型的基本模型. . 19731973年，美国国家标准局（年，美国国家标准局（NBSNBS）发布了公开征集）发布了公开征集

3、标准分组密码算法标准分组密码算法(DES)(DES)的决定的决定 公钥密码学建立：公钥密码学建立：19761976年，年，Diffie Diffie 和和 Hellman Hellman 提出了提出了公钥公钥密码设计思想密码设计思想u 公开公开DESDES算法和公钥密码学的建立标志着现代密码算法和公钥密码学的建立标志着现代密码学的开始学的开始 美国在美国在20002000年公布了高级加密标准年公布了高级加密标准(AES-(AES-Advanced Encryption Standard), Advanced Encryption Standard), 欧洲在欧洲在20002000年年1 1月也

4、推出了月也推出了欧洲加密标准评选欧洲加密标准评选计划，在计划，在20032003年年2 2月月2727日公布了各个算法标准日公布了各个算法标准2. Shannon 的信息论与信息传输理论的信息论与信息传输理论 Shannon通信系统 Shannon通信系统通信系统: :信源：信源：产生信息的来源产生信息的来源编码：编码：把信息变为信号的运算以适合在信道中的传输把信息变为信号的运算以适合在信道中的传输信道：信道：用来从发射者到接收者之间传输信号的介质用来从发射者到接收者之间传输信号的介质译码：译码：把信号变为信息的运算把信号变为信息的运算信宿：信宿：信息传输的归宿和目的地，信息接收人或仪器信息传

5、输的归宿和目的地，信息接收人或仪器 编码编码译码译码信宿信宿信源信源信道信道干扰源干扰源3. 信息安全与密码学信息安全与密码学 密码学密码学(Cryptology):是研究密码系统或通信信息是研究密码系统或通信信息安全的一门科学。它主要包括两个分支安全的一门科学。它主要包括两个分支: :密码编码学密码编码学和密码分析学。和密码分析学。u 密码编码学密码编码学(Cryptography):寻找确保信息保密寻找确保信息保密或信息得到认证的方法或信息得到认证的方法u 密码分析学密码分析学(Cryptanalytics): 主要是研究破译主要是研究破译加密信息或消息的伪造加密信息或消息的伪造密码技术革

6、新是信息安全的关键技术密码技术革新是信息安全的关键技术. .ShannonShannon保密通信系统保密通信系统 公开信道公开信道m 信源)(mECk加密器kK密钥源m信宿)( CEmk1解密器kK 密钥源 密码分析者密钥信道密钥信道Cn明文明文(Plaintext):没有加密的消息没有加密的消息n密文密文(Ciphertext):加密后的消息加密后的消息n加密算法加密算法(Encryption):将明文变换成密文的过程将明文变换成密文的过程n解密算法解密算法(Decryption): 将密文恢复成明文的过程将密文恢复成明文的过程加密和解密过程通常在一组密钥加密和解密过程通常在一组密钥(key

7、)(key)的控制下进的控制下进行，密钥分别称为行，密钥分别称为加密密钥加密密钥和和解密密钥解密密钥。 基本概念基本概念密码体制系是一个五元组密码体制系是一个五元组（P,C,K,E,D)满足条件：满足条件： （1）P是可能明文的有限集；（明文空间）是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间）是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；（密钥空间）是一切可能密钥构成的有限集；（密钥空间） （4）任意）任意k K，有一个加密算法，有一个加密算法 ek E 和相应的和相应的解密算法解密算法dk D ，使得，使得ek :PC 和和dk :C P

8、分别为加密解密函数，分别为加密解密函数， 满足满足dk(ek(x)=x ，这里，这里 x P。密码体系形式化描述密码体系形式化描述加密算法足够强大：加密算法足够强大：仅知密文很难破译出明文仅知密文很难破译出明文基于密钥的安全性，而不是基于算法的安全性：基于密钥的安全性，而不是基于算法的安全性：基于密文基于密文和加和加/解密算法很难破译出明文解密算法很难破译出明文算法开放性：算法开放性：开放算法，便于实现开放算法，便于实现加密的安全性问题加密的安全性问题n理论安全和实际安全理论安全和实际安全n理论安全，或无条件安全：理论安全，或无条件安全： 攻击者无论截获多少密文，都无法得到足够的信息来唯一地决

9、定明攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。文。Shannon用理论证明：欲达理论安全，加密密钥长度必须大于用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密，等于明文长度，密钥只用一次，用完即丢，即一次一密，One-time Pad，不实用。，不实用。n实际安全，或计算上安全：实际安全，或计算上安全： 如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系在有限的资源范围内，攻击者都不能通过系统地分析方法

10、来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行统，则称这个系统是计算上安全的或破译这个系统是计算上不可行（Computationally Infeasible）。）。 n无条件保密性也叫无条件保密性也叫完善保密性完善保密性。一个保密系统具有。一个保密系统具有完善保密性，是指攻击者在有无限的攻击时间和资完善保密性，是指攻击者在有无限的攻击时间和资源下无法破译此系统。源下无法破译此系统。Shannon在理论上证明了在在理论上证明了在唯密文攻击条件下完善保密性的系统是存在的。唯密文攻击条件下完善保密性的系统是存在的。“一次一密一次一密”(one-time pad) 保密系统保密系

11、统:u假设密钥空间大于或等于明文空间，密钥空间的各个分量是统计独立假设密钥空间大于或等于明文空间，密钥空间的各个分量是统计独立的，并且是等概率地选取，对不同的明文用不同的密钥进行加密。在的，并且是等概率地选取，对不同的明文用不同的密钥进行加密。在此假设条件下，仅从密文得不到明文的任何信息此假设条件下，仅从密文得不到明文的任何信息u“一次一密一次一密”保密系统在理论上被认为是不可破译的。即使密码分析保密系统在理论上被认为是不可破译的。即使密码分析者知道了和一段密文相对应的明文，他也仅仅得到了这一段的密钥，者知道了和一段密文相对应的明文，他也仅仅得到了这一段的密钥，由于密钥空间大于或等于明文空间，

12、由于密钥空间大于或等于明文空间，密钥不重复使用密钥不重复使用，因此，已知密，因此，已知密钥对其他密文并不适用钥对其他密文并不适用u但是，进行大量的明文加密，产生如此多的一但是，进行大量的明文加密，产生如此多的一次一密的密钥十分困难，密钥的管理和通信双次一密的密钥十分困难，密钥的管理和通信双方的沟通也有困难。实际的加密系统是通过双方的沟通也有困难。实际的加密系统是通过双方共享重复使用的有限长度的主密钥，利用算方共享重复使用的有限长度的主密钥，利用算法复杂性产生伪随机数进行加密法复杂性产生伪随机数进行加密所以：一次一密（所以：一次一密（one-time pad）方）方案不实用。案不实用。u熵的密码

13、意义：熵的密码意义： 如果如果H(M)=0,则表示该信息不含任何不确定性，因则表示该信息不含任何不确定性，因此，该信息或该事件百分之百会发生。从通信的角度此，该信息或该事件百分之百会发生。从通信的角度看，既然该信息百分之百会发生，意义就不大，没有看，既然该信息百分之百会发生，意义就不大，没有必要再发送。必要再发送。 反之，如果反之，如果H(M)很大，则表示信息的不确定性很很大，则表示信息的不确定性很大，从而收方收到该信息时，其信息量就相当大（重大，从而收方收到该信息时，其信息量就相当大（重要）了。要）了。 从安全角度看，如果信息的熵值不大，即不确定从安全角度看，如果信息的熵值不大，即不确定性太

14、小，此条件提供攻击者很大的概率可以猜中该信性太小，此条件提供攻击者很大的概率可以猜中该信息，从密码技术角度来说，就易破解；反之，息，从密码技术角度来说，就易破解；反之，熵值越熵值越大，越难破解大，越难破解。 4. 熵与密码学熵与密码学 n从信息论的观点看，一个保密系统（从信息论的观点看，一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果）称为完善的无条件的保密系统，如果H( (P)=)=H( (P| |C) )。（知道密文与不知道密文时，（知道密文与不知道密文时，关于明文的熵大小一样）关于明文的熵大小一样）n对于完善保密系统，也有对于完善保密系统，也有H( (K)=)=H( (

15、K| |C) )。u密码体制的熵密码体制的熵u从从ShannonShannon理论知道，仅当可能的密钥数目至少与可理论知道，仅当可能的密钥数目至少与可能的消息数目一样多时，它完全保密才是可能的。换能的消息数目一样多时，它完全保密才是可能的。换句话说，密钥至少必须与消息本身一样长，并且没有句话说，密钥至少必须与消息本身一样长，并且没有密钥被重复使用时，这就是一次一密体制。密钥被重复使用时，这就是一次一密体制。u所以可以说，密码体制的熵可用密钥空间大小的量度。所以可以说，密码体制的熵可用密钥空间大小的量度。即密钥的数目为即密钥的数目为K的密码体制的熵为：的密码体制的熵为：H（K）=log2Ku一般

16、而言，一个密码体制的熵越大，不确定性越大，一般而言，一个密码体制的熵越大，不确定性越大，破译它就越困难。破译它就越困难。u所以，要构造一个完善保密系统，其密钥量的对数所以，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集（密钥空间为均匀分布的条件下）必须不小于明文集的熵的熵5. 互信息量与保密性 从密文从密文C中提取关于明文中提取关于明文P的信息为：的信息为： ( ;)( )(/)I P CH PH P C (7.4.1) 或从密文中提取密钥信息：( ; )( )(/)I K CH KH K C (7.4.2) 因此，(P/C)和(K/C)越大，攻击者从密文

17、中获得明文或密钥信息越少。(/)0H P CK (7.4.3) 于是 ( ;)( )( /)( )I PCKHP HP CKHP (7.4.4) 对于合法用户，知道密钥和密文，就可以得到对于合法用户，知道密钥和密文，就可以得到明文，即：明文，即：说明对于合法用户，知道密钥和密文的情况下，就说明对于合法用户，知道密钥和密文的情况下，就可以得到全部明文！可以得到全部明文！ (7.4.) 说明：密钥空间越大，从密文中可以提取说明：密钥空间越大，从密文中可以提取的关于明文的信息量就越小。对于完善保的关于明文的信息量就越小。对于完善保密系统，有：密系统，有： (;)0I P C (7.4.) 当密钥空间

18、大于明文空间，即()( )H KH P (7.4.) 定理：对任意密码系统，有定理：对任意密码系统，有)()(),(KHPHCPI. 唯一解距离唯一解距离 设给定长密文序列： 12, , ,NNC c ccY 其中为密文字母表。根据条件熵的性质：其中为密文字母表。根据条件熵的性质： 12112/ , , ,/ , , ,NNH K c ccH K c cc (7.4.) 易知，随着的增大，密钥疑义度(K/C)减小。 唯一解距离唯一解距离V0是指攻击者在进行唯密文攻击时必处是指攻击者在进行唯密文攻击时必处理的密文量的理论下界：理的密文量的理论下界：亦即截获的密文越多， 从中提取的 关于密钥的信息就越多。 当疑义度减小到零， 即 (/)0H K C 时 ( ; )( )( / )( )I K CH KH K CH K (7.4.9) 密钥被完全确定，从而实现破译。如果令00( )IHH P (7.4.10) 代表明文信息变差， 其中 (