【安全课件】第5,6讲--伪密钥和唯一解距离

2019/10/11§3.2伪密钥和唯一解距离王滨2005年3月92019/10/12定理3.1设b1,则有且ij,都有;0)(ixp(2)当且仅当i;1)(nxpinXHblog)(,都有(1))(0XH;lognbniibixpxp1)(log)((3)当且仅当存在nii1:使得1)(ixp0)(XH上节内容回顾1()()log()nibiiHXpxpx熵:2019/10/13上节内容回顾定理3.3)|()(),(YXHYHYXH推论3.1)()|(XHYXH且等号成立X与Y独立.定理3.2:)()(),(YHXHYXH且等号成立X与Y独立.nimjjijiyxpyxpYXH11),(log),(),(联合熵:nimjjijiyxpyxpYXH11)|(log),()|(条件熵:结论:0)|()()|()();(XYHYHYXHXHYXI且等号成立X与Y独立.平均互信息:),()()();(YXHYHXHYXI2019/10/14§3.2伪密钥和唯一解距离主要内容:•利用Shannon信息论,研究密文、明文和密钥的信息量。•分析唯密文攻击条件下要唯一确定密钥时至少需要的密文长度。2019/10/15定理3.4设M,K,C分别是明文空间、密钥空间和密文空间上的随机变量，则有截获密文后密钥的未知信息量等于明文与密钥总的未知信息量减去从已知的密文中获得的信息量。)()()()|(CHMHKHCKH直观含义:2019/10/16定理3.4设M,K,C分别是明文空间、密钥空间和密文空间上的随机变量，则有根据条件熵与联合熵之间的关系,有)()()()|(CHMHKHCKH证明:由于知道密文和密钥,自然也知道明文,因而密钥和密文都知道时提供的信息量H(K,C)等于密钥、密文和明文都知道时提供的信息量H(K,M,C),即下证之.)(),()|(CHCKHCKH),,(),(MCKHCKH由和条件熵与联合熵的关系知0)),(|(CKMH同理,有),,(),(MCKHMKH,故由密钥与明文独立知(|)(,)()HKCHKCHC)(),(CHMKH)(),,(CHMCKH)()()(CHMHKH),(CKH),(),,(CKHMCKH)),(|(CKMH2019/10/17截获密文C后,就可将密钥唯一确定等价于下面根据这个条件,计算至少需要多少密文才能将密钥唯一确定.将密钥唯一确定所需要的最少的密文的数量,就称为该密码体制的唯一解距离.要求唯一解距离,需要首先计算计算出n长明文M的熵H(M)和n长密文的熵H(C).)()()()|(CHMHKHCKH定理3.4说明:0)()()(CHMHKH截获密文C后,就可将密钥唯一确定等价于0)|(CKH2019/10/18(A)n长密文熵的计算我们需要做一个合理的假设:假设:密文是随机的!设密文字母表为Y,则n长密文就是由字母表Y中n个字母组成的密文字母串.nyyy,,,21nnyyyY21)(结论:设n长密文服从均匀分布,则n长密文的熵为||log)(YnCH证明:因n长密文共有个,从而由n长密文服从均匀分布和熵的性质知nY||||log||log)(YnYCHn2019/10/19如何刻划明文本身包含的未知信息量呢?我们给出如下的定义：设明文字母表为X,则n长明文就是由字母表X中n个字母组成的明文字母串.nxxx,,,21nnxxxX21)((B)n长明文熵的计算2019/10/110定义3.5（2）设L是一种语言,则称21logLLHRX为该语言L的冗余度(Redundancy).定义3.5(1)设L是一种语言,则称nXHHnnL)(lim)(为该语言L的(单字母)熵.因此,当n很大时,近似有LnnRXnXH||log)()(2019/10/111例1如果由64个二进制数构成的某类密钥的熵平均是56比特,则该类密钥的熵为0.875比特.例2如果由64个二进制数构成的某类密钥的熵平均是56比特,则该类密钥的冗余度是1-0.875=0.125比特即:平均每个密钥比特有0.125个比特是多余的.2019/10/112下面转到分析需要截获多少密文才能将密钥唯一确定的问题.2019/10/113定义3.6称将密钥唯一确定所平均需要的最少的密文的数量为该密码体制的唯一解码量.唯一解码量也称为唯一解距离.将密钥唯一确定等价于H(K|C)=0.下面根据定理3.4的结论计算一个密码体制的唯一解码量.)()()()|(CHMHKHCKH2019/10/1140)|()()()()()(CKHYHXHKHnn当截获n长明文X(n)对应的n长密文Y(n)后,就可将密钥的信息全部确定等价于现设,||||YX则有从而即)()()()()(KHXHYHnnLLnnnRRXnYnXHYH)||(log||log)()()()(LRKHn)(也就是说,当截获个密文字母后,就可将密钥的信息全部确定.LRKHn)(2019/10/115LRKHn)(设已知密文C(n)及对应的明文M(n).由于明文M(n)是已知的,因而此时该明文的熵H(M(n))=0,因而RL=1.这就是说,当n=H(K)/RL=128时,就可将密钥的信息唯一确定.即此时唯一解距离为128.结论:设明文的(单字母)冗余度为,则所有密码体制的唯一解距离均为LR例:对于具有128比特密钥的密码体制,平均需要128比特的已知明文,就能将密钥唯一确定.其中已知明文就是已知一个密文和它对应的明文.解毕解:2019/10/116几点说明:（1）由于唯一解距离量是用熵推出来的，因而它只是将密钥唯一确定所平均需要的密文长度。由于明文熵是每份明文所包含的信息量关于所有明文的平均值，因而有时需要的密文数量少，有时需要的数量多，但其平均值就是唯一解码距离。（2）明文熵不同，唯一解距离也不同。明文熵就是你在攻击过程中每个字母所能利用的信息量。（3）如何确定唯一密钥？确定过程实际上能否实现，这里并不关心。一般而言，穷举攻击所需的平均密文量就是该密码体制的唯一解距离。2019/10/117伪密钥首先介绍候选密钥、伪密钥和等效密钥的概念。候选密钥：攻击者在求解正确密钥时，求出的可能密钥都称为候选密钥。平均来看,当得到的密文数量小于唯一解距离时,候选密钥未必只有一个,此时,就会有多个候选密钥.伪密钥：攻击者得到的候选密钥中的错误密钥称为伪密钥.等效密钥：如果两个密钥对所有明文的加密结果都相同,则称这两个密钥为等效密钥.)(1mEk)(2mEk两个等效密钥k1和k2对应的加密函数和就是一个函数,因而它们的加密效果完全相同.2019/10/118§3.1密码体制的数学模型密码体制由明文空间、密文空间、密钥空间和密码算法四部分构成。被加密的明文服从明文空间上的一个概率分布pm(x)；被使用的密钥服从密钥空间上的一个概率分布pk(x);密文也服从密文空间上的一个概率分布pc(x)；.注意:密钥的分布与明文的分布独立!2019/10/119§3.3密码体制的完善保密性定义3.7(完善保密性)对一个密码体制而言，如果明文与密文独立，即对所有明文空间中的任一点x和密文空间中的任一点y,都有)()|(xmpycxmpm则称该密码体制具有完善保密性(Perfectsecrecy).或称该密码体制是完全保密的。等价刻划:一个密码体制具有完善保密性当且仅当对所有明文空间中的任一点x和密文空间中的任一点y,都有)()|(ycpxmycpc2019/10/120完善保密性的信息论刻划:条件熵刻划:完善保密性等价于)()|(MHCMH互信息刻划:完善保密性等价于0);(CMI下面在(1)明文空间、密文空间和密钥空间的点的个数相等;(2)密文在密文空间中出现的概率都0这两个条件下给出完全保密的密码体制的充要条件.2019/10/121定理3.6设E(k,m)是一个密码体制的加密算法,且其明文空间M、密钥空间K和密文空间C中的点数相同，则该密码体制具有完善保密性当且仅当(1)密钥服从均匀分布;CyMx,yxEk)(Kk和(2)E(k,m)是拉丁方变换,即对,均存在唯一,使得.同时成立.2019/10/122下节内容•第三章习题课