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

第3章 信息论与数学基础 3.1 信息论 3.2 复杂性理论 3.3 数论 3.4 因子分解 3.5 素数生成元 3.6 有限域上的离散对数 返回目录 第3章 信息论与数学基础 3.1.1 熵和不确定性 3.1.2 语言信息率 3.1.3 密码体制的安全性 3.1.4 唯一解距离 3.1.5 信息论的运用 3.1.6 混乱和散布 返回本章首页 第3章 信息论与数学基础 信息论中一条消息的信息量的定义为：对消 息的所有可能含义进行编码时所需要的最少 的比特数。 一条消息M中的信息量可通过它的熵来度量 ，表示为H（M）。通常，一条消息或随机 变量的熵是： 返回本节 第3章 信息论与数学基础 其中：P()表示随机变量的概率分布 B为的分布空间。 一条消息的熵也表示它的不确定性。即当消息被加密 成密文时，为了获取明文，需要解密的明文的比特数 。 如果H(M)=0，则表示该信息不含任何不确定性，该消 息百分之百会发生。如果H(M)很大，则表示该信息的 不确定性很大。 从安全的角度来看，明文的熵值不大，则不确定性太 小，这样攻击者有很大的概率猜中该信息。 返回本节 第3章 信息论与数学基础 对一个给定的语言，其语言信息率是： 其中，N是消息的长度，在N相当大时，标准 英语的语言信息率（r值）在1.0比特/字母与 1.5比特/字母之间 （香农的估计值是1.2bit） 如果在一种语言中有L个字母，其语言绝对信 息率是： 返回本节 第3章 信息论与数学基础 对英语而言，它有26个字母，其语言绝对信 息率是log226=4.7比特/字母。英语的实际信 息率（1.2）大大低于其绝对信息率并不惊奇 。英语是一种高多余度（4.7-1.2=3.5比特/字 母）的语言。 一种语言的多余度称为D，定义为：D=R-r 返回本节 第3章 信息论与数学基础 密码分析者利用自然语言的多余度来减少可能的明文 数目。语言的多余度越大，它就越容易被攻击。 攻击者通过分析关于明文p的统计信息，明文会从所有 可能的明文集合中暴露出来。 因此，许多正在使用的密码装置在加密明文前，都要 用一个压缩程序减少明文大小，其原因就在于此。压 缩（明文）可降低消息的多余度。 密码体制的熵是密钥空间大小的量度。密钥的数目K取 以2为底的对数可估计其大小： 返回本节 一个密码体系的熵越大，破译它的难度就越大。 第3章 信息论与数学基础 唯一解距离是指，当进行强力攻击时，可能解 密出唯一有意义的明文所需要的最少密文量。 一般而言，唯一解距离越长，密码体制越好。 对绝大多数对称密码体制而言，唯一解距离被 定义为密码体制的熵除以语言的多余度： UH（K）/D 返回本节 第3章 信息论与数学基础 例如，对有56比特密钥和用ASCII字符表示的英文 消息来说，DES（数据加密标准）的唯一解距离 是： 56/3.516 大约16个ASCII字符，或56比特。 唯一解距离不是对密码分析需要多少密文的度量 ，而是对存在唯一合理的密码分析解所需要的密 文数量的指标。 返回本节 第3章 信息论与数学基础 唯一解距离与多余度成反比，当多余度接近于 零时（唯一解距离接近无穷大，也就是解密出 唯一有意义的明文所需要的最少密文接近无穷 大），即使一个普通的密码体制也可能是不可 破译的。 返回本节 第3章 信息论与数学基础 很少有实际的算法密码分析上是绝对不可破译 的。各式各样的特点起着破译已加密信息的突 破作用。然而，类似于信息论方面的考虑有时 是有用的。 例如，为了使一个确立的算法增加安全性，建 议一个密钥变化其间隔或周期，以加大唯一解 距离的值。 返回本节 第3章 信息论与数学基础 （1）混乱 用于掩盖明文和密文之间的关系。这可以挫败 通过研究密文以获取多余度和统计模式。通过 代替可做到这点。一个简单的代替密码，如凯 撒移位密码，其中每一个确定的明文字符被一 个密文字符代替。现代的代换密码更复杂，一 个长长的明文块被代替成一个不同的密文块， 并且代替的机制随明文中的每一比特发生变化 。 返回本节 13 简单字符的加密、解密（凯撒移位） 加密的思想是： 将每个字母C加（或减）一序数k，即用它后的第k个字母 代替，变换式公式： c=c+k 例如序数k为5，这时 “A”“F”， “a”“f”， “B”“G” 当加序数后的字母超过“Z”或“z”则 c=c+k -26 例如：You are good Dtz fwj ltti 解密为加密的逆过程 将每个字母C减（或加）一序数k，即 c=c-k, 例如序数k为5，这时 “Z”“U”， “z”“u”， “Y”“T” 当加序数后的字母小于“A”或“a”则 c=c-k +26 14 void main() char c; while(c=getchar()!=n) if(c=a printf(“%c“,c); 加密程序： 15 void main() char c; while(c=getchar()!=n) if(c=a printf(“%c“,c); 解密程序： 第3章 信息论与数学基础 （2）散布 通过将明文多余度分散到密文中使之分散开来。 产生散布最简单的方法是通过换位（也称为置换 ）。一个简单的换位密码，如列换位体制，只简 单地重新排列明文字符。现代密码也做这种类型 转换，但它们也利用其他能将部分消息散布到整 个消息的散布类型。 返回本节 第3章 信息论与数学基础 3.2.1 算法的复杂性 3.2.2 问题的复杂性 3.2.3 NP完全问题 返回本章首页 第3章 信息论与数学基础 密码体制的强度由破译它所需的计算能力确 定的，所需计算能力越大，密码体制越安全 。 一个算法的计算复杂性由两个变量来度量： （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) 106 1秒 二次方 O (n2) 1012 11.6天 三次方 O (n3) 1018 32 000年 指数 O (2 n)10 301 303 宇宙年龄的 10 301 006倍 返回本节 第3章 信息论与数学基础 密码强力攻击的时间复杂性是与可能的密钥总数成比 例的，它是密钥长度的指数函数。 如果密钥长度为n，则强力攻击的复杂性是O(2n)。 对于56bit密钥的复杂性是256（2285年）。 返回本节 第3章 信息论与数学基础 复杂性理论，按照解决问题时所需最少的时间及 最小的空间，归纳成不同类别的复杂度问题。 多项式时间，在计算复杂度理论中，指的是一个 问题的计算时间m(n)不大于问题大小n的多项式倍 数。（O(n)问题。）-易处理问题 超多项式时间，表示任何多项式时间的输入数目 只要够大，超多项式时间所需的解题时间终究会 大大超过任何多项式时间的问题。-难解问题 指数时间（Exponential time）就是一例。 返回本节 第3章 信息论与数学基础 依照求解问题所需的时间，复杂理论也将各种问题区 分成下面几类： （1）P问题：代表那些能够在多项式时间(与时间复杂度 有关)内可解的问题。 （2）NP问题：多项式时间内可验证（猜出）的问题。（ 找不到多项式时间算法解的问题） （3）NP完全问题：是NP问题中的一些特殊问题，NP 中的所有问题都可以转换成NP-完全问题，只要NP完 全问题解决了，其他问题都可以解决。是NP问题中最 困难的问题。 返回本节 第3章 信息论与数学基础 （4）PSPACE问题：它是较NP复杂度更高一级的问题 ，但PSPACENP是否成立仍是没有被解决的问题 。 （5）EXPTIME问题：复杂度最高的称为EXPTIME， EXPTIME问题需要指数的时间才能解决。 EXPTIME已被证明不等于P。 返回本节 第3章 信息论与数学基础 例举一些NP完全问题： （1）整数分解问题 任何整数都可以分解成标准形式： m= ，pi是素数，ei N 当m较小时，这个问题不太困难，例如6 23，1002252。 但当m较大时，此问题就变得非常困难了。 返回本节 第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完全问题。 第3章 信息论与数学基础 （3）离散对数问题 设x，r，n是正整数，已知x，r和n，可以很快 地求得 反过来，如果已知y，和n，求r使得： 成立，这便是离散对数问题。离散对数问题也 是NP完全问题。 返回本节 第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.11 Blum整数 3.3.12 生成元 3.3.13 有限域 3.3.14 GF上的计算 返回本章首页 第3章 信息论与数学基础 模运算是这样一个问题，举例来说，如果小刘 说她10:00会回家，而她迟到了13个小时，那 么她什么时候回家的呢？这就是模12运算： (1013)mod 1211 另一种写法是： 101311(mod 12) 返回本节 第3章 信息论与数学基础 本质上，如果a=b+kn对某一些整数k成立，那 么ab(mod n)。如果a和b是正的，且a小于n， 那么可将a看作b被n整除后的余数。 通常，a和b被n整除时有相同的余数。有时， b被叫做模n的余数。有时a被叫做与b模n同余 。（“”表示同余）。 第3章 信息论与数学基础 从0n-1的整数组成的集合构成了模n的“完全 剩余集”。这意味着，对每一个整数a ，它的 模n的余项是从0n-1的某个整数。 a模n的运算给出了a的余数，这样的余数是从 0n-1的某个整数。这种运算称为模变换。例 如，5 mod 3=2。 第3章 信息论与数学基础 密码学用了许多模n运算，因为像计算离散 对数和平方根这样的问题是困难的，而模运 算可将所有中间结果和最后结果限制在一个 范围内，所以用它进行计算比较容易。 计算数a的乘方并对其取模： 它可分成一系列的乘法和除法（取模）。有 方法使它运算得更快。 第3章 信息论与数学基础 例如，如果要计算 ，不要运用直接计算的方 法进行7次乘法和一个大数的模化简运算, 相反，应进行三次较小的乘法和三次较小的模化 简运算: 依此类推： 返回本节 第3章 信息论与数学基础 素数：比1大，其因子只有1和它本身，没有 其他可以整除它。 2是一个素数，其他素数诸如73，2 521，2 365 347 734 339，和2756 839-1等。 素数是无限的，密码学常用大的素数（512比 特，甚至更长）。 任意整数a1，都可以唯一的因式分解为素数 的乘积。 返回本节 第3章 信息论与数学基础 两个数互素是指：当它们除了1之外没有共同的因子； 换而言之，如果a和n的最大因子等于1，那么写作： gcd(a，n)=1或写成 (a，n)=1 数15和28是互素的，15和27不是，而13和500是。 一个素数与它的倍数以外的任何其他数都是互素的。 确定一个大数的素因子不是一件容易的事。 如果每个整数都表示成素数乘积的形式，就可以很容 易的求出两个正整数的最大公约数。 返回本节 37 辗转相除法(欧几里德算法)求两个整数的最大公约数、最小公倍数。 分析：求最大公约数的算法如下： 1）对于已知两数m，n，使得mn。 2）m除以n得余数r。 3）若r=0，则n为求得的最大公约数 ，算法结束；否则执行4）。 4）mn，nr，再重复执行2）。 （最小公倍数=两个整数之积/最大公 约数）。 算法的N-S流程图如右图，实现 的程序代码如下： 38 void main() int n,m,nm,r,t; scanf(“%d%d“, nm=n*m; if (m 0且z = 1，那么 p 不是素数。 （5）设j = j+1。如果j b且z = p-1，设z = z 2 mod p ，然后回到步骤（4）。 （6）如果j = b且z = p-1, 那么 p 不是素数。 返回本节 第3章 信息论与数学基础 另一种更简单的测试是由Lehmann独立研究 出的。下面是迭代数设置为100的这个算法： （1）选择一个待测的随机数。 （2）确信不能被任何小素数整除。测试2，3， 5，7和11将显著地提高这个算法的速度。 （3）选择100个1和n - 1之间的随机数a1，a2， ，a100。 返回本节 第3章 信息论与数学基础 （4）对所有的ai= a1，a2，a100 ， 计算ai (n-1)/2： 如果对所有的i, ai (n-1)/2 =1( mod n)，那n可 能是合数。 如果对任一个i, ai (n-1)/21或-1( mod n)，那 么n是合数。 如果对所有i, ai (n-1)/2=1或-1( mod n)，但并 非对所有i 均等于1，那么n 是素数。 返回本节 第3章 信息论与数学基础 许多关于RSA的文献都建议对于和应该用强素 数。这些强素数是满足某些特性的素数。使得 用某些特殊的因子分解的方式对它们的乘积进 行分解是困难的。某些建议的性质如下： p-1和q-1的最大公因子应该较小。 p-1和q-1都应有大的素因子，分别记为p和q 。 返回本节 第3章 信息论与数学基础 p-1和q-1都应有大的素因子，分别记为p”和 q”。 (p-1)/2和(q-1)/2都应该是素数。 在此仍然推荐使用强素数，即使它们不会使 因子分解更简单些。虽然它使得产生素数更困 难，但它是无害的。 返回本节 第3章 信息论与数学基础 1. 离散对数基本定义 给定一个质数p，和有限域Zp上的一个本原