第56讲伪密钥和唯一解距离pt课件

1、2021-11-1213.2 伪密钥和唯一解距离伪密钥和唯一解距离王王 滨滨20052005年年3 3月月9 92021-11-122 定理定理3.1 设设b1,则有则有 且ij ,都有; 0)(ixp(2) 当且仅当i;1)(nxpinxhblog)(,都有(1)(0xh;log nbniibixpxp1)(log)(3) 当且仅当存在nii1:使得1)(ixp0)(xh上节内容回顾上节内容回顾1()( )log( )nibiih xp xp x 熵熵:2021-11-123上节内容回顾上节内容回顾 定理定理3.3)|()(),(yxhyhyxh 推论推论3.1)()|(xhyxh且等号成立

2、且等号成立x与与y独立独立. 定理定理3.2:)()(),(yhxhyxh且等号成立且等号成立x与与y独立独立.nimjjijiyxpyxpyxh11),(log),(),(联合熵联合熵:nimjjijiyxpyxpyxh11)|(log),()|(条件熵条件熵: 结论结论:0)|()()|()();(xyhyhyxhxhyxi且等号成立且等号成立x与与y独立独立. 平均互信息平均互信息:),()()();(yxhyhxhyxi2021-11-1243.2 伪密钥和唯一解距离伪密钥和唯一解距离 主要内容: 利用shannon信息论,研究密文、明文和密钥的信息量。 分析唯密文攻击条件下要唯一确定

3、密钥时至少需要的密文长度。2021-11-125 定理定理3.4 设设m,k,c分别是明文空间、密钥空分别是明文空间、密钥空间和密文空间上的随机变量，则有间和密文空间上的随机变量，则有 截获密文后密钥的未知信息量等于截获密文后密钥的未知信息量等于明文与密钥明文与密钥总总的未知信息量减去从已知的密文中获得的信息量。的未知信息量减去从已知的密文中获得的信息量。)()()()|(chmhkhckh直观含义直观含义:2021-11-126 定理定理3.4 设设m,k,c分别是明文空间、密钥空分别是明文空间、密钥空间和密文空间上的随机变量，则有间和密文空间上的随机变量，则有 根据条件熵与联合熵之间的关系

4、根据条件熵与联合熵之间的关系,有有)()()()|(chmhkhckh证明证明: 由于知道密文和密钥由于知道密文和密钥,自然也知道明文自然也知道明文,因而密钥因而密钥和密文都知道时提供的信息量和密文都知道时提供的信息量h(k,c)等于密钥、密等于密钥、密文和明文都知道时提供的信息量文和明文都知道时提供的信息量h(k,m,c),即即下证之下证之.)(),()|(chckhckh),(),(mckhckh由由 和和条件熵条件熵与与联合熵联合熵的关系知的关系知0),( |(ckmh同理同理,有有),(),(mckhmkh,故由密钥与明文独立知故由密钥与明文独立知(|)(,)( )h k ch k c

5、h c)(),(chmkh)(),(chmckh)()()(chmhkh),(ckh),(),(ckhmckh),( |(ckmh2021-11-127 截获密文截获密文c后后,就可将密钥唯一确定就可将密钥唯一确定等价于等价于 下面根据这个条件下面根据这个条件,计算至少需要多少密文才能计算至少需要多少密文才能将密钥将密钥唯一确定唯一确定. 将密钥将密钥唯一确定唯一确定所需要的最少的密文的数量所需要的最少的密文的数量,就称为该密码体制的就称为该密码体制的唯一解距离唯一解距离. 要求唯一解距离要求唯一解距离,需要首先计算计算出需要首先计算计算出n长明文长明文m的熵的熵h(m)和和n长密文的熵长密文

6、的熵h(c).)()()()|(chmhkhckh 定理定理3.4说明说明:0)()()(chmhkh 截获密文截获密文c后后,就可将密钥唯一确定就可将密钥唯一确定等价于等价于 0)|(ckh2021-11-128 (a) n长密文熵的计算长密文熵的计算 我们需要做一个合理的假设我们需要做一个合理的假设: 假设假设: 密文是随机的密文是随机的! 设密文字母表为设密文字母表为y,则则n长密文长密文就是由字母表就是由字母表y中中n 个字母个字母 组成的密文字母串组成的密文字母串 .nyyy,21nnyyyy21)(结论结论: : 设设n长密文服从均匀分布长密文服从均匀分布,则则n长密文的熵为长密文

7、的熵为 |log)(ynch证明证明: : 因因n长密文共有长密文共有 个个,从而由从而由n长密文服从长密文服从均匀分布和熵的性质知均匀分布和熵的性质知 ny |log|log)(ynychn2021-11-129 如何刻划明文本身包含的未知信息量呢如何刻划明文本身包含的未知信息量呢?我们我们 给出如下的定义：给出如下的定义： 设明文字母表为设明文字母表为x,则则n长明文长明文就是由字母表就是由字母表x中中n 个字母个字母 组成的明文字母串组成的明文字母串 .nxxx,21nnxxxx21)( (b) n长明文熵的计算长明文熵的计算2021-11-1210 定义定义3.5 3.5 （2 2）设

8、设l是一种语言是一种语言,则称则称21logllhrx 为该为该语言语言l的冗余度的冗余度(redundancy) .定义定义3.53.5 (1) 设设l是一种语言是一种语言,则称则称nxhhnnl)(lim)( 为该为该语言语言l的的(单字母单字母)熵熵.因此因此, ,当当n n很大时很大时, ,近似有近似有lnnrxnxh|log)()(2021-11-1211例例1 如果由如果由64个二进制数构成的某类密钥个二进制数构成的某类密钥 的的熵平均是熵平均是56比特比特,则该类密钥的熵为则该类密钥的熵为0.875比特比特.例例2 如果由如果由64个二进制数构成的某类密钥的个二进制数构成的某类密

9、钥的熵平均是熵平均是56比特比特,则该类密钥的冗余度是则该类密钥的冗余度是 1 - 0.875 = 0.125 比特比特即即:平均每个密钥比特有平均每个密钥比特有0.125个比特是多余的个比特是多余的.2021-11-1212 下面转到分析需要截获多少密文才能将密钥下面转到分析需要截获多少密文才能将密钥唯一确定的问题唯一确定的问题.2021-11-1213 定义定义3.63.6 称将密钥唯一确定所平均需要的最称将密钥唯一确定所平均需要的最少的密文的数量为该密码体制的少的密文的数量为该密码体制的唯一解码量唯一解码量. 唯一解码量也称为唯一解码量也称为唯一解距离唯一解距离. 将密钥唯一确定等价于将

10、密钥唯一确定等价于h(k|c)=0.下面根据定下面根据定理理3.4的结论的结论计算一个密码体制的唯一解码量计算一个密码体制的唯一解码量.)()()()|(chmhkhckh2021-11-12140)|()()()()()(ckhyhxhkhnn 当截获当截获n长明文长明文x(n)对应的对应的 n长密文长密文y(n)后后,就可将密钥的信息全部确定就可将密钥的信息全部确定等价于等价于 现设现设 ,|yx 则有则有从而从而即即)()()()()(khxhyhnnllnnnrrxnynxhyh)|(log|log)()()()(lrkhn)( 也就是说也就是说,当截获当截获 个密文字母后个密文字母后

11、,就可就可 将密钥的信息全部确定将密钥的信息全部确定.lrkhn)(2021-11-1215lrkhn)( 设已知密文设已知密文c(n)及对应的明文及对应的明文m(n).由于明文由于明文m(n)是已知的是已知的,因而此时该明文的熵因而此时该明文的熵h(m(n)=0,因而因而rl=1.这就是说这就是说,当当n=h(k)/rl=128时时,就可将密钥的信就可将密钥的信息唯一确定息唯一确定.即此时唯一解距离为即此时唯一解距离为128. 结论结论: 设明文的设明文的(单字母单字母)冗余度为冗余度为,则所有密码则所有密码体制的唯一解距离均为体制的唯一解距离均为 lr 例例: : 对于具有对于具有128比

12、特密钥的密码体制比特密钥的密码体制,平均需要平均需要128比特的已知明文比特的已知明文,就能将密钥唯一确定就能将密钥唯一确定. 其中已知明文就是已知一个密文和它对应的明文其中已知明文就是已知一个密文和它对应的明文.解毕解毕解解:2021-11-1216 几点说明几点说明: （1）由于唯一解距离量是用熵推出来的，因而它）由于唯一解距离量是用熵推出来的，因而它只是将密钥唯一确定所只是将密钥唯一确定所平均平均需要的密文长度。需要的密文长度。 由于明文熵是每份明文所包含的信息量关于所有由于明文熵是每份明文所包含的信息量关于所有明文的平均值，因而有时需要的密文数量少，有时明文的平均值，因而有时需要的密文

13、数量少，有时需要的数量多，但其平均值就是唯一解码距离。需要的数量多，但其平均值就是唯一解码距离。 （2）明文熵不同，唯一解距离也不同。）明文熵不同，唯一解距离也不同。 明文熵就是你在攻击过程中每个字母所能利用明文熵就是你在攻击过程中每个字母所能利用的信息量。的信息量。 （3）如何确定唯一密钥？确定过程实际上能否实）如何确定唯一密钥？确定过程实际上能否实现，这里并不关心。现，这里并不关心。一般而言，穷举攻击所需的平一般而言，穷举攻击所需的平均密文量就是该密码体制的唯一解距离。均密文量就是该密码体制的唯一解距离。2021-11-1217 伪密钥伪密钥 首先介绍首先介绍候选密钥候选密钥、伪密钥伪密钥

14、和和等效密钥等效密钥的概念。的概念。 候选密钥：候选密钥：攻击者在求解正确密钥时，求出的攻击者在求解正确密钥时，求出的可能密钥都称为候选密钥。可能密钥都称为候选密钥。 平均来看平均来看,当得到的密文数量小于唯一解距离时当得到的密文数量小于唯一解距离时,候选密钥未必只有一个候选密钥未必只有一个,此时此时,就会有多个候选密钥就会有多个候选密钥. 伪密钥：伪密钥：攻击者得到的候选密钥中的错误密钥攻击者得到的候选密钥中的错误密钥称为伪密钥称为伪密钥. 等效密钥：等效密钥：如果两个密钥对所有明文的加密结如果两个密钥对所有明文的加密结果都相同果都相同,则称这两个密钥为等效密钥则称这两个密钥为等效密钥.)(

15、1mek)(2mek 两个等效密钥两个等效密钥k1和和k2对应的加密函数对应的加密函数 和和 就是一个函数就是一个函数,因而它们的加密效果完全相同因而它们的加密效果完全相同.2021-11-12183.1 密码体制的数学模型密码体制的数学模型 密码体制由明文空间、密文空间、密钥空间和密码算法四部分构成。 被加密的明文服从明文空间上的一个概率分布pm(x)； 被使用的密钥服从密钥空间上的一个概率分布pk(x); 密文也服从密文空间上的一个概率分布pc(x)；. 注意: 密钥的分布与明文的分布独立!2021-11-12193.3 密码体制的完善保密性密码体制的完善保密性 定义定义3.73.7( (

16、完善保密性完善保密性) ) 对一个密码体制而言，对一个密码体制而言，如果明文与密文独立，即对所有明文空间中的任一如果明文与密文独立，即对所有明文空间中的任一点点 x 和密文空间中的任一点和密文空间中的任一点 y ,都有都有)()|(xmpycxmpm则称该密码体制具有则称该密码体制具有完善保密性完善保密性(perfect secrecy).或或称该密码体制是称该密码体制是完全保密完全保密的。的。 等价刻划等价刻划: :一个密码体制具有完善保密性当且仅一个密码体制具有完善保密性当且仅当对所有明文空间中的任一点当对所有明文空间中的任一点 x 和密文空间中的任和密文空间中的任一点一点 y ,都有都有)()|(ycpxmycpc2021-11-1220 完善保密性的信息论刻划完善保密性的信息论刻划: : 条件熵刻划条件熵刻划: :完善保密性等价于完善保密性等价于)()|(mhcmh 互信息刻划互信息刻划: :完善保密性等价于完善保密性等价于0);(cmi 下面在(