密码学的信息论基础[zhuzhuzhuzhu课件.ppt

1、第第3章章 密码学的信息论基础密码学的信息论基础密码体制密码体制（Cryptosystem）是一个五元组（）是一个五元组（P，C，K，E，D），满足条件：），满足条件：（1）M 是可能明文的有限集（明文空间）；是可能明文的有限集（明文空间）；（2）C 是可能密文的有限集（密文空间）；是可能密文的有限集（密文空间）；（3）K是一切可能密钥构成的有限集（密钥空间）；是一切可能密钥构成的有限集（密钥空间）；（4）任意）任意 kK，有一个加密算法，有一个加密算法 ekE 和相应的和相应的解密算法解密算法 dkD，使得，使得 ek MC 和和dk CM 分别为加密、解密函数，满足分别为加密、解密函数，满

2、足 dk（ek（m）=m，这里，这里，mM。一、一、保密系统的数学模型保密系统的数学模型 第第3章章 密码学的信息论基础密码学的信息论基础 信源信源信宿信宿加密加密Ec解密解密D非法接非法接入者入者密码分析密码分析员员(窃听窃听)密钥源密钥源 k1密钥源密钥源 k2秘密信道秘密信道公共信道公共信道主动攻击主动攻击 c被动攻击被动攻击 第第3章章 密码学的信息论基础密码学的信息论基础 通信系统模型通信系统模型I(U;V)=H(U)I(M;C)=0 I(M;KC)=H(M)信源信源信宿信宿信源信源编码编码加密加密信源信源译码译码解密解密信道信道编码编码信道信道译码译码信道信道干扰干扰噪声噪声M C

3、 KU V 任何知道明文空间和密钥空间的概率分布任何知道明文空间和密钥空间的概率分布的人，都可计算密文空间的概率分布的人，都可计算密文空间的概率分布p(c)以以及明文空间关于密文空间的概率分布及明文空间关于密文空间的概率分布p(p|c)。可见，可见，密文空间的统计特性由明文空间和密文空间的统计特性由明文空间和密钥空间的统计特性完全决定。密钥空间的统计特性完全决定。第第3章章 密码学的信息论基础密码学的信息论基础二、完善保密性二、完善保密性密码系统各部分的熵之间的一些基本关系：密码系统各部分的熵之间的一些基本关系：明文熵为明文熵为 H（P）密文熵为密文熵为 H（C）密钥熵为密钥熵为H（K）明文含

4、糊度明文含糊度H（P|C）密钥含糊度密钥含糊度H（K|C）第第3章章 密码学的信息论基础密码学的信息论基础定理定理 3.4 设（设（P，C，K，e，d）是一个密码系统，则）是一个密码系统，则 H（K|C）=H（K）+H（P）-H（C）第第3章章 密码学的信息论基础密码学的信息论基础定义定义 3.3 一个保密系统（一个保密系统（P，C，K，e，d），如果），如果H（P|C）=H（P）或）或 I（P；C）=0，则该保，则该保密系统称为是密系统称为是完善完善的或的或无条件无条件的保密系统的保密系统第第3章章 密码学的信息论基础密码学的信息论基础定理定理 3.5 I（P；C）H（P）-H（K）。）。第

5、第3章章 密码学的信息论基础密码学的信息论基础第第3章章 密码学的信息论基础密码学的信息论基础三、理论安全性和实际安全性三、理论安全性和实际安全性 明文含糊度明文含糊度H(P|C):明文未被密文泄露的信息量明文未被密文泄露的信息量 或观察到密文后明文还保留的不确定度或观察到密文后明文还保留的不确定度密钥含糊度密钥含糊度H(K|C):密钥未被密文泄露的信息量密钥未被密文泄露的信息量 或观察到密文后密钥还保留的不确定度或观察到密文后密钥还保留的不确定度I(P;C)=0 I(P;KC)=H(P)第第3章章 密码学的信息论基础密码学的信息论基础三、理论安全性和实际安全性三、理论安全性和实际安全性 1、

6、理论安全性理论安全性 H(K)第第3章章 密码学的信息论基础密码学的信息论基础定义定义 3.4 假如假如 L 是一种自然语言，语言是一种自然语言，语言 L 的熵定义为的熵定义为 语言语言 L 的的多余度多余度定义为定义为其中其中 A 表示语言表示语言 L 的字母集，的字母集，表示表示 A 中字母的个数，中字母的个数，An表示所有明文表示所有明文 n字母报构成的集。字母报构成的集。HL表示了语言表示了语言 L 的每的每个字母的平均信息比特数，个字母的平均信息比特数，RL度量了度量了“多余字母多余字母”的比例的比例或理解为某种语言中平均每个字母的多余度。或理解为某种语言中平均每个字母的多余度。n)

7、(AHlimHnnL2LLlogH-1R 定理定理 3.6 密钥含糊度有下界密钥含糊度有下界H（K|CS）H（K）-SRLlog2S 表示接收到的密文序列长度表示接收到的密文序列长度RL表示明文语言的冗余度表示明文语言的冗余度表示明文和密文空间中符号或字母的数目。表示明文和密文空间中符号或字母的数目。第第3章章 密码学的信息论基础密码学的信息论基础定理定理 3.7 当明文由一个离散独立信源产生时，如果当明文由一个离散独立信源产生时，如果SH（K）|（log2-H（M）)密钥的含糊度能变为零。密钥的含糊度能变为零。第第3章章 密码学的信息论基础密码学的信息论基础理论保密性：理论保密性：一个密码系统，如果对手有无限的资源可利用，而一个密码系统，如果对手有无限的资源可利用，而在截获任意多密报下仍不能被破译，则它在理论上在截获任意多密报下仍不能被破译，则它在理论上是保密的是保密的 第第3章章 密码学的信息论基础密码学的信息论基础2、实际安全性实际安全性 计算上安全计算上安全破译密文的代价超过被加密信息的价值破译密文的代价超过被加密信息的价值破译密文所花时间超过被加密信息的有效期破译密文所花时间超过被加密信息的有效期第第3章章 密码学的信息论基础密码学的信息论基础