第 3章 密码学的信息论基础
3.1 保密系统的数学模型
编码器 信 源 m 信 道 信 宿 译码器 m
干扰器
图 3.1 通信系统模型
加密器 信 源 m 信 道 接收者 解密器 m
分析者
图 3.2 保密系统模型
密钥 k
c
c
无噪信道
安全信道
密钥源
加 密
分析者
解 密 接收者 发送者
信 源 k k
m
m mc
图 3.3 Shannon的保密系统模型
? 数学模型
– 样本空间
– 密钥空间
– 密文空间
? ?LlMmmmmmMP lLL ?????? 1,),,( 21 ?
?
?
?? L
l
lLP mpmmmpmp
1
21 )(),,,()( ?
'LYC?
? ?PmmeC kk ?? )(
? ???? kCck kPKC cdpkpcp ))(()()(
? 在给定密文发生的条件下，某个明文发
生的条件概率
? ?
? ?
?
?
?
??
k
k
Cck
kPK
cdmk
KP
P cdpkp
kpmp
cmp
))(()(
)()(
)( )(
3.2 信息量和熵
? 定义 3.1 设随机变量,出现
的概率为 。则 X 的不确
定性或熵（ Entropy）定义为
? ?nixX i,,2,1 ??? ix
?
?
?? n
i
ii xpxp
1
1)(,0)( 且
?
?
??
n
i
ii xpxpXH
1
2 )(lo g)()(
? 反映了集中事件出现的平均不确定性，或为确
定集中出现一个事件平均所需的信息量（观测
之前），或集中每出现一个事件平均给出的信
息量（观测之后）。如果从编码的角度来考虑，
熵也可以理解成用最优的二进制编码形式表示所需的比特数。
? 采用以 2为底的对数时，相应的信息单位称作
比特（ Bit）。
? 如果集 X为均匀分布时，即,
则 。
?,当 X为确定性的事件时，即 X概率
分布为,则 。
00l o g0 2 ??
ninp i ??? 1,/1
nXH 2lo g)( ?
0)( ?XH
1)( ?? aXp 0)( ?XH
? 例 3.1 设有一个密码系统明文空间 的概率分布
为 ；
密钥空间 的概率分布为 。
密文空间,且假定加密函数为
。
可用右边的加密矩阵表示,
则按公式 3.1 和 3.2我们很容易计算出密文空间的概率分布及
关于明文的条件分布,
1） 密文空间的概率分布表如下,
2）明文关于密文的条件分布 表如下,
明文空间的熵为,
类似地可计算
)(?Cp
c 1 2 3 4
1/8 7/16 1/4 3/16
1k
2k
3k
a b
1 2
2 3
3 4
c\m a b
1 1 0
2 1/7 6/7
3 1/4 3/4
4 0 1
? ?baP,?
4/3)(,4/1)( ?? bpap PP
? ?321,,kkkK ? 4/1)()(,2/1)( 321 ??? kpkpkp KKK
? ?4,3,2,1?C
4)(,3)(;3)(,2)(;2)(,1)( 332211 ?????? beaebeaebeae kkkkkk
)( cmp
81.0)3( l o g43243l o g4341l o g41)( 222 ??????PH
85.1)(5.1)( ?? CHKH 且
? 定义 3.2 设, 出现的概率
为 。, 出现
的概率为,则联合事件集
,令 的概率
为,此时 。集 X和 Y的联合熵
定义为
集相对于事件的条件熵定义为
集相对于集的条件熵定义为
? ?nixX i,,2,1 ??? ix
?
?
?? n
i
ii xpxp
1
1)(,0)( 且 ? ?mjyY j,,2,1 ??? jy
?
?
?? m
j
jj ypyp
1
1)(,0)( 且
? ?mjniyxXY ji,,2,1;,,2,1 ?? ??? ji yx
0)( ?ji yxp ? ?
? ?
?n
i
m
j ji
yxp
1 1
1)(
? ?
? ?
??? n
i
m
j
jiji yxpyxpYXHXYH
1 1
2 )(l o g)(),()(
)(l o g)()(
1
2 ji
n
i
jij yxpyxpyXH ?
?
??
)(lo g)()()()()(
1 1
2
1
ji
m
j
n
i
jij
m
j
jj yxpyxpypyXHypYXH ? ??
? ??
???
? 若将 X视作一个系统的输入空间,Y视作
是系统的输出空间。在通信中，通常将
条件熵 H(X|Y)称作含糊度
(Equivocation)，将条件熵 H(Y|X)称为
散布度（ Divergence）,X和 Y之间的平
均互信息 表示 X熵减少量。 )()(),( YXHXHYXI ??
熵的基本特性
? 引理 3.1 （ Jensen不等式） 假定 f是区间 I 上
的一个连续的严格凸函数,。那么
。
当且仅当 时等号成立。
? 定理 3.1 假定 X是有概率分布 的随机
变量，其中,则,当
（即样本点是等概率分布）时取等号，即均匀
分布下集 X的不确定性最大。
niaa in
i
i ?????
?
1,0,1
1
? ?
? ?
???????n
i
n
i
iiii xafxfa
1 1
)( niIx i ??? 1,
nxxx ??? ?21
nppp,,,21 ?
nip i ??? 1,0 nXH 2lo g)( ? ni
np i ??? 1,
1
? 定理 3.2,当且仅当 X
和 Y独立时等号成立。
? 定理 3.3 。
? 推论 3.1,当且仅当 X和 Y
独立时等号成立。
)()(),( YHXHYXH ??
)()()()(),( XYHXHYXHYHYXH ????
)()( XHYXH ?
),( YXI
)(XH
)(YH
),( YXH
)|( XYH
图 3.4 各类熵之间的关系
)|( YXH
3.3 完善保密性
? 定理 3.4 设 是一个密码系统。
则 。
? 定义 3.3 一个保密系统 称为是完善
的或无条件的保密系统，如果
或 。
? 定理 3.5 。
? 由定理 3.5知，完善保密系统存在的必要条件
是,即 。
),,,,( deKCP
)()()()( CHPHKHCKH ???
),,,,( deKCP
)()( PHCPH ?
0),( ?CPI
)()(),( KHPHCPI ??
)()(),(0 KHPHCPI ??? )()( KHPH ?
? 无条件安全的密码系统安全性依赖于每个密钥仅仅用
在一次加密中，在每个消息被传送之前，一个新的密
钥必须被产生。另外，每个消息必须与同样长度的密
钥相伴，这是极其不利的，因为密钥应当在消息之前
被安全传送。这些都给密钥管理带来了严重的问题。
再加上一次一密系统对已知明文攻击非常脆弱。因此
无条件安全的保密系统是很不实用的，也具有很大的局限性，但在军事和外交上很早就使用了这种体制。
? 密码学的历史发展一直在试图设计一个用一个密钥
就可以加密一个相当长的明文串（即一个密钥可用来
加密许多消息）的密码系统，且仍能保持至少计算上
安全。
3.4 理论安全性和实际安全性
H
S
H(K/CS)
H(K/CSMS)
H(MS/CS)
图 3.5 密钥, 消息和密钥显现含糊度作为 S的函数
? 定义 3.4 假如 L是一种自然语言，语言 L
的熵为
语言的多余度定义为
其中 A表示语言 L的字母集，表示 A中字
母的个数,表示所有明文 n－字母报构
成的全体。
n
AHH n
nL
)(l im
???
?2lo g1
L
L
HR ??
?
nA
? 定理 3.6 密钥含糊度有下列下界
其中,S表示接受到的密文序列长度,表示明
文语言的冗余度，表示密文空间中符号或字母
的数目。
? 定理 3.7 当明文由一个离散独立信源产生，
如果
其中 是字母表的大小。
密钥的含糊度能变为零。
?2l o g)()( LS SRKHCKH ??
LR
?
? ?)(l o g)( 2 MHKHS ?? ?
?
? 理论上，当截获的密报量大于唯一解距离时，原则上就可破译。
? 由于自然语言的复杂性，没有任何一种分析方
法能够假定分析者能利用明文语言的全部统计知识,所以，一般破译所需的密文量都远大
于理论值。
? 没有涉及为了得到唯一解需完成多少计算量。
从实际破译来看，有时虽然截获的密文量远大
于唯一解距离，但由于所需的工作量还太大而
难以实现破译。
? 理论保密性是假定密码分析者有无限的时间、设备和
资金的条件下，研究唯密文攻击时密码系统的安全性。
比如一次一密体制。
? 实际安全性又称为计算上的安全性，这个方法关心的
是破译一个具体的密码系统所需的计算量。
? 在实际中，人们说一个密码系统是, 计算上安全的,,
意指利用已有的最好的方法破译该系统所需要的努力
超过了敌手的破译能力（诸如时间、空间、和资金等
资源）或破译该系统的难度等价于解数学上的某个已
知难题
? 估计一个系统的实际保密性
– 密码分析者的计算能力；
– 他所采用的破译算法的有效性。
? Shannon关于设计密码的一些基本观点
– 通过合并简单密码系统而形成它们的, 积,
– 挫败统计分析的观点,
? 在加密之前将语言的一些多余度除去。
? 采用所谓的, 扩散（ Diffusion）, 和, 混淆
（ Confusion）, 这两种加密技术扩散或混淆多
余度。
小结
? 本章主要介绍了 Shannon保密系统的模
型,完善保密性的条件、唯一解距离、
理论安全性和实际安全性等概念和观点，
这些观点至今对密码学的研究仍具有重
要的指导意义。
3.1 保密系统的数学模型
编码器 信 源 m 信 道 信 宿 译码器 m
干扰器
图 3.1 通信系统模型
加密器 信 源 m 信 道 接收者 解密器 m
分析者
图 3.2 保密系统模型
密钥 k
c
c
无噪信道
安全信道
密钥源
加 密
分析者
解 密 接收者 发送者
信 源 k k
m
m mc
图 3.3 Shannon的保密系统模型
? 数学模型
– 样本空间
– 密钥空间
– 密文空间
? ?LlMmmmmmMP lLL ?????? 1,),,( 21 ?
?
?
?? L
l
lLP mpmmmpmp
1
21 )(),,,()( ?
'LYC?
? ?PmmeC kk ?? )(
? ???? kCck kPKC cdpkpcp ))(()()(
? 在给定密文发生的条件下，某个明文发
生的条件概率
? ?
? ?
?
?
?
??
k
k
Cck
kPK
cdmk
KP
P cdpkp
kpmp
cmp
))(()(
)()(
)( )(
3.2 信息量和熵
? 定义 3.1 设随机变量,出现
的概率为 。则 X 的不确
定性或熵（ Entropy）定义为
? ?nixX i,,2,1 ??? ix
?
?
?? n
i
ii xpxp
1
1)(,0)( 且
?
?
??
n
i
ii xpxpXH
1
2 )(lo g)()(
? 反映了集中事件出现的平均不确定性，或为确
定集中出现一个事件平均所需的信息量（观测
之前），或集中每出现一个事件平均给出的信
息量（观测之后）。如果从编码的角度来考虑，
熵也可以理解成用最优的二进制编码形式表示所需的比特数。
? 采用以 2为底的对数时，相应的信息单位称作
比特（ Bit）。
? 如果集 X为均匀分布时，即,
则 。
?,当 X为确定性的事件时，即 X概率
分布为,则 。
00l o g0 2 ??
ninp i ??? 1,/1
nXH 2lo g)( ?
0)( ?XH
1)( ?? aXp 0)( ?XH
? 例 3.1 设有一个密码系统明文空间 的概率分布
为 ；
密钥空间 的概率分布为 。
密文空间,且假定加密函数为
。
可用右边的加密矩阵表示,
则按公式 3.1 和 3.2我们很容易计算出密文空间的概率分布及
关于明文的条件分布,
1） 密文空间的概率分布表如下,
2）明文关于密文的条件分布 表如下,
明文空间的熵为,
类似地可计算
)(?Cp
c 1 2 3 4
1/8 7/16 1/4 3/16
1k
2k
3k
a b
1 2
2 3
3 4
c\m a b
1 1 0
2 1/7 6/7
3 1/4 3/4
4 0 1
? ?baP,?
4/3)(,4/1)( ?? bpap PP
? ?321,,kkkK ? 4/1)()(,2/1)( 321 ??? kpkpkp KKK
? ?4,3,2,1?C
4)(,3)(;3)(,2)(;2)(,1)( 332211 ?????? beaebeaebeae kkkkkk
)( cmp
81.0)3( l o g43243l o g4341l o g41)( 222 ??????PH
85.1)(5.1)( ?? CHKH 且
? 定义 3.2 设, 出现的概率
为 。, 出现
的概率为,则联合事件集
,令 的概率
为,此时 。集 X和 Y的联合熵
定义为
集相对于事件的条件熵定义为
集相对于集的条件熵定义为
? ?nixX i,,2,1 ??? ix
?
?
?? n
i
ii xpxp
1
1)(,0)( 且 ? ?mjyY j,,2,1 ??? jy
?
?
?? m
j
jj ypyp
1
1)(,0)( 且
? ?mjniyxXY ji,,2,1;,,2,1 ?? ??? ji yx
0)( ?ji yxp ? ?
? ?
?n
i
m
j ji
yxp
1 1
1)(
? ?
? ?
??? n
i
m
j
jiji yxpyxpYXHXYH
1 1
2 )(l o g)(),()(
)(l o g)()(
1
2 ji
n
i
jij yxpyxpyXH ?
?
??
)(lo g)()()()()(
1 1
2
1
ji
m
j
n
i
jij
m
j
jj yxpyxpypyXHypYXH ? ??
? ??
???
? 若将 X视作一个系统的输入空间,Y视作
是系统的输出空间。在通信中，通常将
条件熵 H(X|Y)称作含糊度
(Equivocation)，将条件熵 H(Y|X)称为
散布度（ Divergence）,X和 Y之间的平
均互信息 表示 X熵减少量。 )()(),( YXHXHYXI ??
熵的基本特性
? 引理 3.1 （ Jensen不等式） 假定 f是区间 I 上
的一个连续的严格凸函数,。那么
。
当且仅当 时等号成立。
? 定理 3.1 假定 X是有概率分布 的随机
变量，其中,则,当
（即样本点是等概率分布）时取等号，即均匀
分布下集 X的不确定性最大。
niaa in
i
i ?????
?
1,0,1
1
? ?
? ?
???????n
i
n
i
iiii xafxfa
1 1
)( niIx i ??? 1,
nxxx ??? ?21
nppp,,,21 ?
nip i ??? 1,0 nXH 2lo g)( ? ni
np i ??? 1,
1
? 定理 3.2,当且仅当 X
和 Y独立时等号成立。
? 定理 3.3 。
? 推论 3.1,当且仅当 X和 Y
独立时等号成立。
)()(),( YHXHYXH ??
)()()()(),( XYHXHYXHYHYXH ????
)()( XHYXH ?
),( YXI
)(XH
)(YH
),( YXH
)|( XYH
图 3.4 各类熵之间的关系
)|( YXH
3.3 完善保密性
? 定理 3.4 设 是一个密码系统。
则 。
? 定义 3.3 一个保密系统 称为是完善
的或无条件的保密系统，如果
或 。
? 定理 3.5 。
? 由定理 3.5知，完善保密系统存在的必要条件
是,即 。
),,,,( deKCP
)()()()( CHPHKHCKH ???
),,,,( deKCP
)()( PHCPH ?
0),( ?CPI
)()(),( KHPHCPI ??
)()(),(0 KHPHCPI ??? )()( KHPH ?
? 无条件安全的密码系统安全性依赖于每个密钥仅仅用
在一次加密中，在每个消息被传送之前，一个新的密
钥必须被产生。另外，每个消息必须与同样长度的密
钥相伴，这是极其不利的，因为密钥应当在消息之前
被安全传送。这些都给密钥管理带来了严重的问题。
再加上一次一密系统对已知明文攻击非常脆弱。因此
无条件安全的保密系统是很不实用的，也具有很大的局限性，但在军事和外交上很早就使用了这种体制。
? 密码学的历史发展一直在试图设计一个用一个密钥
就可以加密一个相当长的明文串（即一个密钥可用来
加密许多消息）的密码系统，且仍能保持至少计算上
安全。
3.4 理论安全性和实际安全性
H
S
H(K/CS)
H(K/CSMS)
H(MS/CS)
图 3.5 密钥, 消息和密钥显现含糊度作为 S的函数
? 定义 3.4 假如 L是一种自然语言，语言 L
的熵为
语言的多余度定义为
其中 A表示语言 L的字母集，表示 A中字
母的个数,表示所有明文 n－字母报构
成的全体。
n
AHH n
nL
)(l im
???
?2lo g1
L
L
HR ??
?
nA
? 定理 3.6 密钥含糊度有下列下界
其中,S表示接受到的密文序列长度,表示明
文语言的冗余度，表示密文空间中符号或字母
的数目。
? 定理 3.7 当明文由一个离散独立信源产生，
如果
其中 是字母表的大小。
密钥的含糊度能变为零。
?2l o g)()( LS SRKHCKH ??
LR
?
? ?)(l o g)( 2 MHKHS ?? ?
?
? 理论上，当截获的密报量大于唯一解距离时，原则上就可破译。
? 由于自然语言的复杂性，没有任何一种分析方
法能够假定分析者能利用明文语言的全部统计知识,所以，一般破译所需的密文量都远大
于理论值。
? 没有涉及为了得到唯一解需完成多少计算量。
从实际破译来看，有时虽然截获的密文量远大
于唯一解距离，但由于所需的工作量还太大而
难以实现破译。
? 理论保密性是假定密码分析者有无限的时间、设备和
资金的条件下，研究唯密文攻击时密码系统的安全性。
比如一次一密体制。
? 实际安全性又称为计算上的安全性，这个方法关心的
是破译一个具体的密码系统所需的计算量。
? 在实际中，人们说一个密码系统是, 计算上安全的,,
意指利用已有的最好的方法破译该系统所需要的努力
超过了敌手的破译能力（诸如时间、空间、和资金等
资源）或破译该系统的难度等价于解数学上的某个已
知难题
? 估计一个系统的实际保密性
– 密码分析者的计算能力；
– 他所采用的破译算法的有效性。
? Shannon关于设计密码的一些基本观点
– 通过合并简单密码系统而形成它们的, 积,
– 挫败统计分析的观点,
? 在加密之前将语言的一些多余度除去。
? 采用所谓的, 扩散（ Diffusion）, 和, 混淆
（ Confusion）, 这两种加密技术扩散或混淆多
余度。
小结
? 本章主要介绍了 Shannon保密系统的模
型,完善保密性的条件、唯一解距离、
理论安全性和实际安全性等概念和观点，
这些观点至今对密码学的研究仍具有重
要的指导意义。
