计算机系统安全课件 第3章 信息论与数学基础

第3章信息论与数学基础第3章信息论与数学基础3.1信息论3.2复杂性理论3.3数论3.4因子分解3.5素数生成元3.6有限域上的离散对数返回目录第3章信息论与数学基础3.1信息论3.1.1熵和不确定性3.1.2语言信息率3.1.3密码体制的安全性3.1.4唯一解距离3.1.5信息论的运用3.1.6混乱和散布返回本章首页第3章信息论与数学基础3.1.1熵和不确定性信息论中一条消息的信息量的定义为：对消息的所有可能含义进行编码时所需要的最少的比特数。一条消息M中的信息量可通过它的熵来度量，表示为H（M）。通常，一条消息或随机变量χ的熵是：返回本节P(x)p(x)logH(x)x2第3章信息论与数学基础其中：P(χ)表示随机变量χ的概率分布B为χ的分布空间。一条消息的熵也表示它的不确定性。即当消息被加密成密文时，为了获取明文，需要解密的明文的比特数。如果H(M)=0，则表示该信息不含任何不确定性，该消息百分之百会发生。如果H(M)很大，则表示该信息的不确定性很大。从安全的角度来看，明文的熵值不大，则不确定性太小，这样攻击者有很大的概率猜中该信息。返回本节P(x)p(x)logH(x)x2第3章信息论与数学基础3.1.2语言信息率对一个给定的语言，其语言信息率是：其中，N是消息的长度，在N相当大时，标准英语的语言信息率（r值）在1.0比特/字母与1.5比特/字母之间（香农的估计值是1.2bit）如果在一种语言中有L个字母，其语言绝对信息率是：NMHr/)(LR2log返回本节第3章信息论与数学基础对英语而言，它有26个字母，其语言绝对信息率是log226=4.7比特/字母。英语的实际信息率（1.2）大大低于其绝对信息率并不惊奇。英语是一种高多余度（4.7-1.2=3.5比特/字母）的语言。一种语言的多余度称为D，定义为：D=R-r返回本节第3章信息论与数学基础3.1.3密码体制的安全性密码分析者利用自然语言的多余度来减少可能的明文数目。语言的多余度越大，它就越容易被攻击。攻击者通过分析关于明文p的统计信息，明文会从所有可能的明文集合中暴露出来。因此，许多正在使用的密码装置在加密明文前，都要用一个压缩程序减少明文大小，其原因就在于此。压缩（明文）可降低消息的多余度。密码体制的熵是密钥空间大小的量度。密钥的数目K取以2为底的对数可估计其大小：KKH2log)(返回本节一个密码体系的熵越大，破译它的难度就越大。第3章信息论与数学基础3.1.4唯一解距离唯一解距离是指，当进行强力攻击时，可能解密出唯一有意义的明文所需要的最少密文量。一般而言，唯一解距离越长，密码体制越好。对绝大多数对称密码体制而言，唯一解距离被定义为密码体制的熵除以语言的多余度：U＝H（K）/D返回本节第3章信息论与数学基础例如，对有56比特密钥和用ASCII字符表示的英文消息来说，DES（数据加密标准）的唯一解距离是：56/3.5＝16大约16个ASCII字符，或56比特。唯一解距离不是对密码分析需要多少密文的度量，而是对存在唯一合理的密码分析解所需要的密文数量的指标。返回本节第3章信息论与数学基础唯一解距离与多余度成反比，当多余度接近于零时（唯一解距离接近无穷大，也就是解密出唯一有意义的明文所需要的最少密文接近无穷大），即使一个普通的密码体制也可能是不可破译的。返回本节第3章信息论与数学基础3.1.5信息论的运用很少有实际的算法密码分析上是绝对不可破译的。各式各样的特点起着破译已加密信息的突破作用。然而，类似于信息论方面的考虑有时是有用的。例如，为了使一个确立的算法增加安全性，建议一个密钥变化其间隔或周期，以加大唯一解距离的值。返回本节第3章信息论与数学基础3.1.6混乱和散布（1）混乱用于掩盖明文和密文之间的关系。这可以挫败通过研究密文以获取多余度和统计模式。通过代替可做到这点。一个简单的代替密码，如凯撒移位密码，其中每一个确定的明文字符被一个密文字符代替。现代的代换密码更复杂，一个长长的明文块被代替成一个不同的密文块，并且代替的机制随明文中的每一比特发生变化。返回本节13简单字符的加密、解密（凯撒移位）加密的思想是：将每个字母C加（或减）一序数k，即用它后的第k个字母代替，变换式公式：c=c+k例如序数k为5，这时“A”“F”，“a”“f”，“B”“G”…当加序数后的字母超过“Z”或“z”则c=c+k-26例如：YouaregoodDtzfwjltti解密为加密的逆过程将每个字母C减（或加）一序数k，即c=c-k,例如序数k为5，这时“Z”“U”，“z”“u”，“Y”“T”…当加序数后的字母小于“A”或“a”则c=c-k+2614voidmain(){charc;while((c=getchar())!='\n'){if((c='a'&&c='z')||(c='A'&&c='Z')){c=c+4;if(c'Z'&&c='Z'+4||c'z')c=c-26;}printf(%c,c);}}加密程序：15voidmain(){charc;while((c=getchar())!='\n'){if((c='a'&&c='z')||(c='A'&&c='Z')){c=c-4;if(c'A'||c'a'&&c='a'-4)c=c+26;}printf(%c,c);}}解密程序：第3章信息论与数学基础（2）散布通过将明文多余度分散到密文中使之分散开来。产生散布最简单的方法是通过换位（也称为置换）。一个简单的换位密码，如列换位体制，只简单地重新排列明文字符。现代密码也做这种类型转换，但它们也利用其他能将部分消息散布到整个消息的散布类型。返回本节第3章信息论与数学基础3.2复杂性理论3.2.1算法的复杂性3.2.2问题的复杂性3.2.3NP－完全问题返回本章首页第3章信息论与数学基础3.2.1算法的复杂性密码体制的强度由破译它所需的计算能力确定的，所需计算能力越大，密码体制越安全。一个算法的计算复杂性由两个变量来度量：（1）T（时间复杂性）。（2）S（空间复杂性或所需存储空间）。T和S一般表示为n的函数。n是输入的尺寸。返回本节第3章信息论与数学基础通常，一个算法的计算复杂性的数量级用称之为“大O”的符号来表示。计算复杂性的数量级是这种类型的函数：当n变大时，增长得最快的函数；所有常数和较低阶形式的函数忽略不计。例如，一个所给的算法的复杂性是4n2+7n+12，那么，其计算复杂性是n2阶的，表示为O(n2)。第3章信息论与数学基础表3.1不同算法族运行时间与n的关系复杂度所需运算所需时间（106运算/秒）常数O(1)11微秒线性O(n)1061秒二次方O(n2)101211.6天三次方O(n3)101832000年指数O(2n)10301303宇宙年龄的10301006倍返回本节第3章信息论与数学基础密码强力攻击的时间复杂性是与可能的密钥总数成比例的，它是密钥长度的指数函数。如果密钥长度为n，则强力攻击的复杂性是O(2n)。对于56bit密钥的复杂性是256（2285年）。返回本节第3章信息论与数学基础3.2.2问题的复杂性复杂性理论，按照解决问题时所需最少的时间及最小的空间，归纳成不同类别的复杂度问题。多项式时间，在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。（O(n)问题。）------易处理问题超多项式时间，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。-----难解问题指数时间（Exponentialtime）就是一例。返回本节第3章信息论与数学基础3.2.2问题的复杂性依照求解问题所需的时间，复杂理论也将各种问题区分成下面几类：（1）P问题：代表那些能够在多项式时间(与时间复杂度有关)内可解的问题。（2）NP问题：多项式时间内可验证（猜出）的问题。（找不到多项式时间算法解的问题）（3）NP—完全问题：是NP问题中的一些特殊问题，NP中的所有问题都可以转换成NP-完全问题，只要NP—完全问题解决了，其他问题都可以解决。是NP问题中最困难的问题。返回本节第3章信息论与数学基础（4）PSPACE问题：它是较NP复杂度更高一级的问题，但PSPACE＝NP是否成立仍是没有被解决的问题。（5）EXPTIME问题：复杂度最高的称为EXPTIME，EXPTIME问题需要指数的时间才能解决。EXPTIME已被证明不等于P。返回本节第3章信息论与数学基础3.2.3NP－完全问题*例举一些NP完全问题：（1）整数分解问题任何整数都可以分解成标准形式：m=，pi是素数，ei∈N当m较小时，这个问题不太困难，例如6＝2×3，100＝22×52。但当m较大时，此问题就变得非常困难了。nieiip1返回本节第3章信息论与数学基础（2）背包问题背包问题是这样的一个问题：已知长度为k的圆形背包及长度分别为a1，a2，…，an的n个圆形物品。假定这些物品的半径和背包半径相同，要求从n个物品中选出若干个正好装满这个背包。第3章信息论与数学基础把背包问题抽象成数学模型，称为子集合问题：设有长度为n的向量A=（a1，a2，…，an），任意给定一个正整数k，寻找有没有一些恰好等于k，即求方程：的解向量x=(x1，x2，…，xn）其中xi=0或1。当n比较小的时候，可以用穷举法求得解向量，但当n比较大时，穷举法就不可行了。背包问题是NP－完全问题。kaxinii1第3章信息论与数学基础（3）离散对数问题设x，r，n是正整数，已知x，r和n，可以很快地求得反过来，如果已知y，χ和n，求r使得：成立，这便是离散对数问题。离散对数问题也是NP－完全问题。)(modnxyr)(modnxyr返回本节第3章信息论与数学基础3.3数论3.3.1模运算3.3.2素数3.3.3最大公因子3.3.4取模数求逆元3.3.5费马小定理3.3.6欧拉函数3.3.7中国剩余定理3.3.8二次剩余3.3.9勒让德符号3.3.10雅可比符号3.3.11Blum整数3.3.12生成元3.3.13有限域3.3.14GF上的计算返回本章首页第3章信息论与数学基础3.3.1模运算模运算是这样一个问题，举例来说，如果小刘说她10:00会回家，而她迟到了13个小时，那么她什么时候回家的呢？这就是模12运算：(10＋13)mod12＝11另一种写法是：10＋13≡11(mod12)返回本节第3章信息论与数学基础本质上，如果a=b+kn对某一些整数k成立，那么a≡b(modn)。如果a和b是正的，且a小于n，那么可将a看作b被n整除后的余数。通常，a和b被n整除时有相同的余数。有时，b被叫做模n的余数。有时a被叫做与b模n同余。（“≡”表示同余）。第3章信息论与数学基础从0~n-1的整数组成的集合构成了模n的“完全剩余集”。这意味着，对每一个整数a，它的模n的余项是从0~n-1的某个整数。a模n的运算给出了a的余数，这样的余数是从0~n-1的某个整数。这种运算称为模变换。例如，5mod3=2。第3章信息论与数学基础密码学用了许多模n运算，因为像计算离散对数和平方根这样的问题是困难的，而模运算可将所有中间结果和最后结果限制在一个范围内，所以用它进行计算比较容易。计算数a的乘方并对其取模：它可分成一系列的乘法和除法（取模）。有方法使它运算得更快。naxmod第3章信息论与数学基础例如，如果要计算，不要运用直接计算的方法进行7次乘法和一个大数的模化简运算,相反，应进行三次较小的乘法和三次较小的模化简运算:依此类推：namod8nnnamod)mod)mod((222nnnnanamod)mod)mod)mod(((mod222216返回本节第3章信息论与数学基础3.3.2素数素数：比1大，其因子只有1和它本身，没有其他可以整除它。2是一个素数，其他素数诸如73，2521，236