密码学 第六章 香农理论
第六章 香农理论
香农(Shannon )1949年在贝尔系统技术期刊上发表了一篇标题为“保密系统的通信理论”的论文,该论文对密码学的科学研究有重大影响。
密码学 第六章 香农理论
如果给定一个密码体制,则关于它的明文、密文与密钥的联合概率分布为
P (m , c , k ) 。由给定密码体制的联合概率分布可以确定该体制的各种边际分布与条件分布,并由此确定一系列信息的度量。 常用边际分布与条件分布如下:
●
明文与密钥的联合概率分布为 P (m , k ) =
c ∈C
●
∑P (m , c , k ) ,
m ∈M , k ∈K 明文与密文的联合概率分布为 P (m , c ) =
k ∈K
●
∑P (m , c , k ) ,
, c C
明文的概率分布为 P (m ) =
k ∈K
●
∑P (m , k ) ,
M
密钥 (∈
●
P () ,
∈K
密文(=
m
c ∈
条件概率分布为
●
明文和密钥的条件概率分布为 P (c /m , k ) =
P (m , k , c )
P (m , k )
●
密文关于明文的条件概率分布为 P (c /m ) =
P (m , c )
P (m )
●
明文关于密文的条件概率分布为 P (m /c ) =
P (m , c )
P (c )
●
密钥关于密文的条件概率分布为 P (k /c ) =
P (k , c )
P (c )
说明:
[1]
尽管lim x lb x =0,即允许x =0,但因为在熵的定义中,当P i =0时,
x →0
lb P i 无定义,所以假设定义6.2中的和是在所有P i ≠0的下标i 上进行
的。
[2]
熵定义中对数的底通常用2,因为lb P (其中a 为常数),i =log a P i ∙lb a 所以计算熵时,若改变对数的底,熵的值只相差一个常数因子。
m ∈M
●
密文概率分布相关的熵为 H (C ) =-∑P (c ) lb P (c )
c ∈C
●
明文与密文联合概率分布相关的熵为
H (M , C ) =-
m ∈M c ∈C
∑∑P (m , c ) lb P (m , c )
6. 4 多余度和唯一解码量
● 把熵的结果应用到密码体制,可以证明在密码体制的组成部分之间存在一
对于某一密码体制保密性的评估,需要一种测度方法。用于讨论密码体制保密性的基本方法有两类:计算保密性研究和无条件保密性研究。 计算保密性研究
计算保密性是涉及破译一个密码体制所需计算能力的一种指标。 如果定义一个密码体制是计算上保密的,则指破译这个体制的最好算法
需要至少N 次运算,而N 是一个非常大的数。
● 目前,还没有一种密码体制被证明是“计算上保密的”。实际中所称的
“计算上保密的”仅指攻破该体制的已知最好方法需要的计算机时间过
大。
● 另一种提供“计算保密性”的方法是把一个密码体制的保密性转换为一
些已经研究过的非常困难问题。
现有明文m i 和m j ,即密文c k ,由于完全保密,有 P (c k m i ) =P (c k ) =P (c k m j )
其中
P (c k m i ) =
l ∈K ∑P (l ) ,
∑P (x ) , E (m i , l ) =c k E (m j , x ) =c k P (c k m j ) =
x ∈K
P (l ), P (x ) 分别是l , x 密钥的先验概率,即
将m i 变为c k 的所有密钥的概率之和 = 将m j 变为c k 的所有密钥的概率之
密码学 第六章 香农理论
第六章 香农理论
香农(Shannon )1949年在贝尔系统技术期刊上发表了一篇标题为“保密系统的通信理论”的论文,该论文对密码学的科学研究有重大影响。
密码学 第六章 香农理论
如果给定一个密码体制,则关于它的明文、密文与密钥的联合概率分布为
P (m , c , k ) 。由给定密码体制的联合概率分布可以确定该体制的各种边际分布与条件分布,并由此确定一系列信息的度量。 常用边际分布与条件分布如下:
●
明文与密钥的联合概率分布为 P (m , k ) =
c ∈C
●
∑P (m , c , k ) ,
m ∈M , k ∈K 明文与密文的联合概率分布为 P (m , c ) =
k ∈K
●
∑P (m , c , k ) ,
, c C
明文的概率分布为 P (m ) =
k ∈K
●
∑P (m , k ) ,
M
密钥 (∈
●
P () ,
∈K
密文(=
m
c ∈
条件概率分布为
●
明文和密钥的条件概率分布为 P (c /m , k ) =
P (m , k , c )
P (m , k )
●
密文关于明文的条件概率分布为 P (c /m ) =
P (m , c )
P (m )
●
明文关于密文的条件概率分布为 P (m /c ) =
P (m , c )
P (c )
●
密钥关于密文的条件概率分布为 P (k /c ) =
P (k , c )
P (c )
说明:
[1]
尽管lim x lb x =0,即允许x =0,但因为在熵的定义中,当P i =0时,
x →0
lb P i 无定义,所以假设定义6.2中的和是在所有P i ≠0的下标i 上进行
的。
[2]
熵定义中对数的底通常用2,因为lb P (其中a 为常数),i =log a P i ∙lb a 所以计算熵时,若改变对数的底,熵的值只相差一个常数因子。
m ∈M
●
密文概率分布相关的熵为 H (C ) =-∑P (c ) lb P (c )
c ∈C
●
明文与密文联合概率分布相关的熵为
H (M , C ) =-
m ∈M c ∈C
∑∑P (m , c ) lb P (m , c )
6. 4 多余度和唯一解码量
● 把熵的结果应用到密码体制,可以证明在密码体制的组成部分之间存在一
对于某一密码体制保密性的评估,需要一种测度方法。用于讨论密码体制保密性的基本方法有两类:计算保密性研究和无条件保密性研究。 计算保密性研究
计算保密性是涉及破译一个密码体制所需计算能力的一种指标。 如果定义一个密码体制是计算上保密的,则指破译这个体制的最好算法
需要至少N 次运算,而N 是一个非常大的数。
● 目前,还没有一种密码体制被证明是“计算上保密的”。实际中所称的
“计算上保密的”仅指攻破该体制的已知最好方法需要的计算机时间过
大。
● 另一种提供“计算保密性”的方法是把一个密码体制的保密性转换为一
些已经研究过的非常困难问题。
现有明文m i 和m j ,即密文c k ,由于完全保密,有 P (c k m i ) =P (c k ) =P (c k m j )
其中
P (c k m i ) =
l ∈K ∑P (l ) ,
∑P (x ) , E (m i , l ) =c k E (m j , x ) =c k P (c k m j ) =
x ∈K
P (l ), P (x ) 分别是l , x 密钥的先验概率,即
将m i 变为c k 的所有密钥的概率之和 = 将m j 变为c k 的所有密钥的概率之