文档介绍：§ 伪密钥和唯一解距离
王滨
2005年3月9
11/30/2018
1
设b>1,则有
且
,都有
(2) 当且仅当
,都有
(1)
(3) 当且仅当存在
使得
上节内容回顾
熵:
11/30/2018
2
上节内容回顾
且等号成立
X与Y独立.
:
且等号成立
X与Y独立.
联合熵:
条件熵:
结论:
且等号成立
X与Y独立.
平均互信息:
11/30/2018
3
§ 伪密钥和唯一解距离
主要内容:
利用Shannon信息论,研究密文、明文和密钥的信息量。
分析唯密文攻击条件下要唯一确定密钥时至少需要的密文长度。
11/30/2018
4
设M,K,C分别是明文空间、密钥空间和密文空间上的随机变量,则有
截获密文后密钥的未知信息量等于明文与密钥总的未知信息量减去从已知的密文中获得的信息量。
直观含义:
11/30/2018
5
设M,K,C分别是明文空间、密钥空间和密文空间上的随机变量,则有
根据条件熵与联合熵之间的关系,有
证明:
由于知道密文和密钥,自然也知道明文,因而密钥和密文都知道时提供的信息量H(K,C)等于密钥、密文和明文都知道时提供的信息量H(K,M,C),即
下证之.
由和条件熵与联合熵的关系知
同理,有
,故由密钥与明文独立知
11/30/2018
6
截获密文C后,就可将密钥唯一确定等价于
下面根据这个条件,计算至少需要多少密文才能将密钥唯一确定.
将密钥唯一确定所需要的最少的密文的数量,就称为该密码体制的唯一解距离.
要求唯一解距离,需要首先计算计算出n长明文M的熵H(M)和n长密文的熵H(C).
:
截获密文C后,就可将密钥唯一确定等价于
11/30/2018
7
(A) n长密文熵的计算
我们需要做一个合理的假设:
假设: 密文是随机的!
设密文字母表为Y,则n长密文就是由字母表Y中n 个字母组成的密文字母串.
结论: 设n长密文服从均匀分布,则n长密文的熵为
证明:
因n长密文共有个,从而由n长密文服从均匀分布和熵的性质知
11/30/2018
8
如何刻划明文本身包含的未知信息量呢?我们给出如下的定义:
设明文字母表为X,则n长明文就是由字母表X中n 个字母组成的明文字母串.
(B) n长明文熵的计算
11/30/2018
9
(2)设L是一种语言,则称
为该语言L的冗余度(Redundancy) .
(1) 设L是一种语言,则称
为该语言L的(单字母)熵.
因此,当n很大时,近似有
11/30/2018
10