密码学基础课件：第五讲 完善保密理论

1、第五讲 完善保密理论完善保密的定义和性质Shannon定理乘积密码完善保密的定义把保密性放到数学框架中，给出准确的定义完善保密的定义考虑以前的故事凯撒密码是不是完善保密呢？维吉尼亚密码是不是完善保密呢？公平游戏是不是完善保密呢？仿射变换是不是完善保密呢？致桑道夫伯爵的信是不是完善保密的呢？。完善保密是不是只考虑了密文和明文的关系？或者说只是关于扩散原则的考虑？违反直觉的结论违反直觉的结论违反直觉的结论我们在前面的故事中已经知道移位密码是单表代换，无法对抗频率分析那么为什么移位密码具有完善保密性呢？注意攻击者对移位密码的攻击是在完全不关心密钥的情况下做出的，也就是说无论密钥是等概率均匀随机选取还

2、是只选一个，对频率分析都是没有用处的。完善保密理论是关于单个密文的从定义中可以看到，是对任意的一个x和一个y来考虑安全性，而不是大量密文。那么完善保密理论的实际用途在哪里？一次一密体制一次一密可以看到一次一密是关于n个“字符”（比特）的体制任意给一个密文，在密钥均匀随机选择的条件下，这个密文显然可能是任意的明文，所以一次一密是完善保密的意味着该体制加密的n比特密文在任何统计分析下是安全的。但是同一个密钥的使用不能超过n个比特。移位密码的完善保密在移位密码中，如果每个字符都用不同的随机均匀选择的密钥加密，统计分析是无效的。或者说，如果采用维吉尼亚密码体制，并且要求密钥词无限长，均匀随机选择，可以

3、实现完善保密。Shannon定理“”的证明：Shannon定理初步分析1.完善保密要求明密文空间独立，即明文x可以加密为任意的密文y2.对有效密文空间C，因为条件1，有|K|=|C|3.在同一密钥下，不同的x必然加密为不同的y，有|C|=|P|(单射)Shannon定理评论：一个密钥确定了P和C之间的一个映射。|K|和|C|相同，则不同密钥下一个明文对应不同的密文Shannon定理评论完善保密条件下会有多个密钥把一个明文x映射为一个密文Y吗？例如，增加6号密钥，映射为(M1,E1), (M2,E3), (M3,E2), (M4,E5), (M5, E4)，那么给定E1，6个密钥均匀选，明文是M

4、1的概率最高Shannon定理评论但是可以增加6-10号密钥，并且使得6-10号密钥单独使用时是完善保密的。Shannon定理Shannon定理评论固定E1，5个密钥是等概率选择的固定M1,E1，只有一个密钥Double密钥的情况也是可以的，只不过|K|变大了Shannon定理评论|K|大了并不好Shannon定理评论使用完善保密的加密方案是不必要的。只要在实践上是不可破译的密码方案就可以实用了：如某方案在200年内，使用最快的可用的超级计算机，也不能以大于10-30的概率攻破。计算安全性如果使用最好的算法攻破一个密码体制需要至少N次操作，这里的N是一个特定的非常大的数字，我们可以定义这个密码

5、体制是计算安全的。没有一个已知的实际的密码体制在这个定义下可以被证明安全。人们经常经过几种特定的攻击类型来研究计算上的安全性。对一种类型的攻击是安全的，并不表示对其他类型的攻击是安全的。可证明安全性将密码体制的安全性归结为某个经过深入研究的数学难题。这种途径只是说明了安全和另一个问题是相关的，并没有完全证明是安全的。这和证明一个问题是NP完全的有些类似：证明给定的问题和任何其他的NP完全问题的难度是一样的，但没有完全证明这个问题的计算难度。无条件安全性对攻击者的计算量没有限制。即使提供了无穷的计算资源，也是无法被攻破的。讨论安全性时，与攻击类型（手段）有关完善保密的密码体制满足无条件安全性乘积

6、密码报务员克劳森使用了两种加密方法带提示词的凯撒密码乘积密码乘积密码的可交换性改变加密流程的先后顺序克劳森的方法是否具有可交换性？单表代换的方法是否具有幂等性？幂等体制移位，代换，仿射，Hill，维吉尼亚，置换单独使用都是幂等的可交换体制设乘法密码体制为加密体制S,仿射密码体制为T，则ST是可交换的体制不是幂等的体制设单表代换体制S，置换体制T，则ST加密体制可以不是幂等的例如字符集ABCD，代换密钥为(CBDA)，置换（1，3，2），明文AAC，那么1.S:CCD; T:BDC2.S:BAD; T:BDA此时从AA映射到BD使用单表代换是做不到的，所以不可能用一次ST来完成。Claude S

7、hannon was born on April 30, 1916 in the town of Gaylord, Michigan.By the 1980s, Shannon began having problems with his memory and he was later diagnosed with Alzheimers disease.In his final years he was “good-natured as usual” and enjoyed daily visits with his wife, Betsy.Eventually his body failed

8、 and he passed away in February 2001.A Mathematical Theory of Communication. Bell Syst. Tech. J.,27:379-423, 1948Communication Theory of Secrecy Systems. Bell Syst.Tech. J., 28:656-715,1949信息论与密码学 信息论与密码学 通信系统与密码系统。消息的加密与破译和信息论密切相关。 通信系统：用信息论观点研究存在随机干扰时通信系统中的信息传输问题Shannon在1948年发表的“通信的数学理论” 。在有扰条件下，发送的消息m在噪声干扰下变为m，一般mm。接收者的任务是从收到的m试图恢复原来的消息。为了使这成为可能，发送者常常要对消息进行编码，按一定规则增加一些多余数字，以便在出错时使接收者能对其进行检测或纠正。 信息论与密码学 密码系统：对消息m的加密变换的作用类似于向消息注入噪声。密文c就相当于经过有扰信道得到的接收消息。密码分析员就相当于有扰信道下原接收者。所不同的是，这种干扰不是信