信息安全导论 印润远 第3章 信息论与数学基础

《信息安全导论 印润远 第3章 信息论与数学基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章信息论与数学基础3.1信息论3.2复杂性理论3.3数论3.4因子分解3.5素数生成元3.6有限域上的离散对数思考题返回目录3.1信息论3.1.1熵和不确定性3.1.2语言信息率3.1.3密码体制的安全性3.1.4唯一解距离3.1.5信息论的运用3.1.6混乱和散布返回本章首页3.1.1熵和不确定性信息论中一条消息的信息量的定义为：对消息的所有可能含义进行编码时所需要的最少的比特数。一条消息M中的信息量可通过它的熵来度量，表示为H（M）。通常，一条消息或随机变量χ的熵是：返回本节其中：P(χ)表示随机变量χ的概率分布，B为χ的分布

2、空间。一条消息的熵也表示它的不确定性。即当消息被加密成密文时，为了获取明文，需要解密的明文的比特数。例如，如果密文块“QHP＊5M”要么是“男”，要么是“女”，那么此消息的不确定性是1。密码分析者恢复出此消息，仅需恰当的1比特。返回本节3.1.2语言信息率对一个给定的语言，其语言信息率是：其中，N是消息的长度，在N相当大时，标准英语的语言信息率（r值）在1.0比特/字母与1.5比特/字母之间如果在一种语言中有L个字母，其语言绝对信息率是：返回本节对英语而言，它有26个字母，其语言绝对信息率是log226=4.7比特/字母。这里，英语的

3、实际信息率大大低于其绝对信息率并不惊奇。英语是一种高多余度的语言。一种语言的多余度称为D，定义为：D=R-r返回本节3.1.3密码体制的安全性密码分析者利用自然语言的多余度来减少可能的明文数目。语言的多余度越大，它就越容易被攻击。许多正在使用的密码装置在加密明文前，都要用一个压缩程序减少明文大小，其原因就在于此。压缩（明文）可降低消息的多余度。密码体制的熵是密钥空间大小的量度。密钥的数目K取以2为底的对数可估计其大小：返回本节3.1.4唯一解距离唯一解距离是指，当进行强力攻击时，可能解密出唯一有意义的明文所需要的最少密文量。一般而言，

4、唯一解距离越长，密码体制越好。对绝大多数对称密码体制而言，唯一解距离被定义为密码体制的熵除以语言的多余度：U＝H（K）/D返回本节例如，对有56比特密钥和用ASCII字符表示的英文消息来说，DES的唯一解距离是：56/3.5＝16大约16个ASCII字符，或56比特。唯一解距离不是对密码分析需要多少密文的度量，而是对存在唯一合理的密码分析解所需要的密文数量的指标。返回本节3.1.5信息论的运用很少有实际的算法密码分析上是绝对不可破译的。各式各样的特点起着破译已加密信息的突破作用。然而，类似于信息论方面的考虑有时是有用的。例如，为了使一

5、个确立的算法增加安全性，建议一个密钥变化其间隔或周期，以加大唯一解距离的值。返回本节3.1.6混乱和散布（1）混乱用于掩盖明文和密文之间的关系。这可以挫败通过研究密文以获取多余度和统计模式。通过代替可做到这点。一个简单的代替密码，如凯撒移位密码，其中每一个确定的明文字符被一个密文字符代替。现代的代换密码更复杂，一个长长的明文块被代替成一个不同的密文块，并且代替的机制随明文中的每一比特发生变化。返回本节（2）散布是通过将明文多余度分散到密文中使之分散开来。产生散布最简单的方法是通过换位（也称为置换）。一个简单的换位密码，如列换位体制，只

6、简单地重新排列明文字符。现代密码也做这种类型转换，但它们也利用其他能将部分消息散布到整个消息的散布类型。返回本节3.2复杂性理论3.2.1算法的复杂性3.2.2问题的复杂性3.2.3NP－完全问题返回本章首页3.2.1算法的复杂性一个算法的计算复杂性由两个变量来度量：（1）T（时间复杂性）。（2）S（空间复杂性或所需存储空间）。T和S一般表示为n的函数。n是输入的尺寸。返回本节通常，一个算法的计算复杂性的数量级用称之为“大O”的符号来表示。计算复杂性的数量级是这种类型的函数：当n变大时，增长得最快的函数；所有常数和较低阶形式的函数忽略

7、不计。例如，一个所给的算法的复杂性是4n2+7n+12，那么，其计算复杂性是n2阶的，表示为O(n2)。表3.1不同算法族运行时间与n的关系复杂度所需运算所需时间（106运算/秒）常数O(1)11微秒线性O(n)1061秒二次方O(n2)101211.6天三次方O(n3)101832000天指数O(2n)10301303宇宙年龄的10301006倍返回本节3.2.2问题的复杂性依照求解问题所需的时间，复杂理论也将各种问题区分成下面几类：（1）P问题：代表那些能够在多项式时间内可解的问题。（2）NP问题：多项式时间内可验证的问题。（3）

8、NP—完全问题：是NP问题中的一些特殊问题，NP中的所有问题都可以转换成NP-完全问题，只要NP—完全问题解决了，其他问题都可以解决。返回本节（4）PSPACE问题：它是较NP复杂度更高一级的问题，但PSPACE＝NP是