信息安全专题讲座.ppt

第二章经典密码学 加密通信的模型 Alice 加密机 解密机 Bob 安全信道 密钥源 Oscar x y x k 密码学的目的 Alice和Bob两个人在不安全的信道上进行通信 而破译者Oscar不能理解他们通信的内容 定义 密码体制 它是一个五元组 P C K E D 满足条件 1 P是可能明文的有限集 明文空间 2 C是可能密文的有限集 密文空间 3 K是一切可能密钥构成的有限集 密钥空间 4 任意 有一个加密算法和相应的解密算法 使得和分别为加密解密函数 满足 注 1 Alice要将明文 在不安全信道上发给Bob 设X x1x2 xn 其中 Alice用加密算法ek作yi ek xi 1 i n结果的密文是Y y1y2 yn 在信道上发送 Bob收到后解密 xi dk yi 得到明文X x1x2 xn 2 加密函数ek必须是单射函数 就是一对一的函数 3 若P C 则ek为一个置换 4 好的密钥算法是唯密钥而保密的 5 若Alice和Bob在一次通信中使用相同的密钥 那么这个加密体制为对称的 否则称为非对称的 1 移位密码体制 设P C K Z 26 对 定义同时dk y y k mod26 注1 26个英文字母与模26剩余类集合 0 25 建立一一对应 ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789101112131415161718192021222324252 当k 3时 为Caesar密码 若明文 meetmeafterthetogaparty密文 PHHWPHDIWHOWKHWRJDSDUWB实际算法为 有同时有 d3 y y 3 mod26 3 一个密码体制要是实际可用必须满足的特性 每一个加密函数ek和每一个解密函数dk都能有效地计算 破译者取得密文后 将不能在有效的时间内破解出密钥k或明文x 一个密码体制是安全的必要条件穷举密钥搜索将是不可行的 即密钥空间将是非常大的 2 替换密码体制 设P C Z 26 K是由26个符号0 1 25的所有可能置换组成 任意 定义d y 1 y x 1是 的逆置换 注 1 置换 的表示 2 密钥空间K很大 K 26 4 1026 破译者穷举搜索是不行的 然而 可由统计的方式破译它 3 移位密码体制是替换密码体制的一个特例 它仅含26个置换做为密钥空间 3 仿射密码体制 替换密码的另一个特例就是仿射密码 加密函数取形式为要求唯一解的充要条件是gcd a 26 1该体制描述为 设P C Z 26 对定义ek x ax b mod26 和dk y a 1 y b mod26 例子 设k 7 3 注意到7 1 mod26 15 加密函数是ek x 7x 3 相应的解密函数是dk y 15 y 3 15y 19 易见dk ek x dk 7x 3 15 7x 3 19 x 45 19 x mod26 若加密明文 hot 首先转换字母h o t成为数字7 14 19 然后加密 解密 4 维吉尼亚密码 Vigenere 设m为一固定的正整数 定义P C K Z 26 m 对一个密钥K k1 k2 km 定义ek x1 x2 xm x1 k1 x2 k2 xm km ydk y1 y2 ym x1 k1 x2 k2 xm km x这里的所有的运算都是在 mod26 中进行的 注 维吉尼亚密码是多表替换体制 分析起来更困难 密钥空间大 如当m 5时 密钥空间所含密钥的数量是 1 1 107 5 Hill密码体制 设 为某个固定的正整数 P C Z 26 m K Z 26 上的m m可逆矩阵 对每一个 定义ek x xK mod26 和dk y yK 1 mod26 注 明文与密文都是m元的向量 x1 x2 xm y1 y2 ym Z 26 为同余类环 在这个环上的可逆矩阵Amxm 是指行列式detAmxm的值 Z 26 它为Z 26 中全体可逆元的集合 Z 26 a Z 26 a 26 1 Z 26 1 3 5 7 9 11 15 17 19 21 23 25 例子 当m 2时 明文元素x x1 x2 密文元素y y1 y2 y1 y2 x1 x2 K 事实上yi为x1 x2的线性组合 y1 11x1 3x2 y2 8x1 7x2 一般 将取m m的矩阵K作为我们的密钥 有y y1 y2 ym x1 x2 xm 换言之 y xK 且有x yK 1若K 可得K 1 若对明文july加密 它分成2个元素 j u l y 分别对应于 9 20 11 24 有 9 20 99 60 72 140 3 4 且 11 24 121 72 88 168 11 22 于是对july加密的结果为DELW 为了解密 Bob计算且因此 得到了正确的明文 july 6 置换密码体制 设m为固定的正整数 P C Z 26 m K是由 1 2 m 的所有置换构成 对一个密钥 K 定义e x1 x2 xm x 1 x m 和d y1 y2 ym y 1 y m 这里 1为 的逆置换 注 这里的加密与解密仅仅用了置换 无代数运算 例子 设m 6 取密钥而 若给定的明文是 cryptography首先找分成6个字母长的明文组 crypto graphy求得的密文是 YTCOPRAHGYPR注 事实上 置换密码是Hill密码的特例 给定一个集合 1 2 m 的置换矩阵 置换矩阵是每一行和每一列刚好在一个 1 而其余元素为 0 的矩阵 对上面例子决定的置换 对应 密码分析 假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥 这个假设称为Kerckhoff原则 最常见的破解类型如下 1 唯密文攻击 Oscar具有密文串y 2 已知明文攻击 Oscar具有明文串x和相应的密文y 3 选择明文攻击 Oscar可获得对加密机的暂时访问 因此他能选择明文串x并构造出相应的密文串y 4 选择密文攻击 Oscar可暂时接近密码机 可选择密文串y 并构造出相应的明文x 5 这一切的目的在于破译出密钥