北邮精品课程-现代密码学课件 现代密码学第二讲：密码学的信息论基础

《北邮精品课程-现代密码学课件 现代密码学第二讲：密码学的信息论基础》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1密码学的信息论基础《现代密码学》第二讲上讲内容回顾密码学分类密码学与信息安全的关系本章主要内容Shannon的通信保密系统熵和无条件保密分组密码设计思想4Shannon通信保密系统C.E.Shannon（香农）----信息论之父1948,Amathematicaltheoryofcommunication,奠定了现代信息论的基础.1949,Communicationtheoryofsecrecysystems,定义了保密系统的数学模型,将密码学由艺术转化为一门科学.5Shannon通信保密系统Shannon的保密通信系

2、统模型Shannon通信保密系统非对称密码体制7Shannon通信保密系统一个密码体制是一个六元组：（P,C,K1,K2,E,D)其中，P--明文空间C--密文空间K1--加密密钥空间K2--解密密钥空间E--加密变换D--解密变换8Shannon通信保密系统一个加密变换是一个下列形式的映射：E:M×K1→C一般对于给定的k∈K1,把E(*,k)记为Ek;一个解密变换是一个与加密E变换相对应的映射：D:C×K2→M对于给定的k’∈K2,也把D(*,k’)记为Dk’.9Shannon通信保密系统重要原则：对任一k∈K1,都

3、能找到k’∈K2，使得Dk’(Ek(m))=m，mM.10熵和无条件保密定义设随机变量X={xi

4、i=1,2,…,n},xi出现的概率为Pr(xi)≧0,且,则X的不确定性或熵定义为.熵H(X)表示集X中出现一个事件平均所需的信息量(观察前)；或集X中每出现一个事件平均所给出的信息量(观测后).熵和无条件保密规定log20=0，采用以2为底的对数时，相应的信息单位称作比特从编码的角度来考虑，熵可以理解成用最优的二进制编码形式表示X所需的比特数若集X为均匀分布时，即p(xi)=1/n,n≧i≧1,则H(X)=log2n

5、,且若H(X)≧0,当X为确定性的事件时,即X概率分布为Pr(X=a)=1,则H(X)=0.12熵和无条件保密定义：设X={xi

6、i=1,2,…,n},xi出现的概率为p(xi)≥0，且∑i=1,…,np(xi)=1;Y={yi

7、i=1,2,…,m},yi出现的概率为p(yi)≥0，且∑i=1,…,mp(yi)=1;则集X相对于集Y的条件熵定义为熵和无条件保密若将X视为一个系统的输入空间，Y视为系统的输出空间，在通信中，通常将条件熵H(X

8、Y)称作含糊度，X和Y之间的平均互信息定义为：I(X,Y)=H(X)-H(X

9、Y)

10、它表示X熵减少量。14熵和无条件保密定义完善保密的（无条件保密的）密码系统（P,C,K,E,D）系统满足或.艺术科学假设攻击者有无限计算资源，仍然不能从密文得到明文任何信息.一次一密算法由GilbertVernam于1917年用于报文消息的自动加密和解密，30年后由Shannon证明它不可攻破.15熵和无条件保密一次一密系统：设n是大于等于1的正整数，P=C=K={0,1}n,对于密钥K∈K,,K={k1,k2,…,kn}.设明文P={p1,p2,…,pn},密文C={c1,c2,…,cn}.加密:EK(P)=(p1⊕k

11、1,p2⊕k2,…,pn⊕kn),解密:DK(C)=(c1⊕k1,c2⊕k2,…,cn⊕kn).分组密码设计思想Ci与pj和kj（j=1,…,5,i≠j）无关分组密码：密文的每一比特与明文每一比特和密钥每一比特相关分组17分组密码设计思想一迭代结构（乘积密码）18分组密码设计思想如果密码体制不是幂等的(F2≠F),那么多次迭代有可能提高密码体制的安全性.采用迭代结构的优点：软、硬件实现节省了代码（硬件）资源.19分组密码设计思想二混淆：明文/密钥和密文之间的关系复杂设算法为凯撒密码（即密文和密钥及明文成线性关系）：则已知

12、一对明密文字符，密钥信息即得Ek(m)=m+k(mod26)，mM；WHY？Ek(m)=(m+k)*k(mod26)，mM；？？？分组密码设计思想三扩散：明文/密钥的每一个比特都影响密文的每一个比特WHY？分组密码设计思想密钥不可重复使用22分组密码设计思想事例：珍珠港事件日本人偷袭珍珠港得手以后，山本五十六又制订了中途岛作战计划。美军太平洋舰队新任司令尼米兹的手里有一个密码破译小组，虽然有些情报还不能够完全破译，但是这个小组发现当日军开始向中途岛进发的时候，在日军来往的电报中，经常出现的“AF”这两个字母，究竟

13、指什么？一时难以敲定。初步的判断，这可能是日军下一步要进攻的目标，但是究竟是哪呢？也有人猜出来是中途岛，但是不能确定。美军情报官让中途岛的美军，给太平洋舰队的总部发一份电报，内容是“本岛淡水设备发生故障。”日军截获并破译了这封电报，同时向它的司令部大本营报告。美军截获日军法网大本营的电报“AF很可能缺少淡水。”于是确