《系统结构》PPT课件.ppt

第 2章对称密码 密码学的历史已有 4000多年 古埃及人曾把象形文字写在石碑上 密码学是一门研究秘密信息的隐写技 术的学科 密码学技术可以使消息的内容对 (除发 送者和接收者以外 )的所有人保密 . 可以使接收者验证消息的正确性 是解决计算机与通信安全问题重要技 术之一 . 密码学 密码学的发展 第 1阶段： 1949年以前。 第 2阶段：从 1949年到 1975年。 标志： 1949年 Shannon发表的 保密系统的信息理论 一文。 第 3阶段： 1976年至今。 标志： 1976年 Diffie和 Hellman发 表了 密码学新方向 一文。 Shannon模型 密码的基本术语 密码技术（ Cryptography） 把可 理解的消息变换成不可理解消息，同 时又可恢复原消息的方法和原理的一 门科学或艺术。 明文（ plaintext ） -变换前的原始消 息 密文（ ciphertext） -变换后的消息 密码（ cipher ） -用于改变消息的替 换或变换算法 密钥（ key ） -用于密码变换的，只 有发送者或接收者拥有的秘密消息 编码（ encipher /encode） -把 明文变为密文的过程 译码（ decipher /decode) 把 密文变为明文的过程 密码分析（ cryptanalysis /codebreaking) 在没有密钥的情况下，破解密文的 原理与方法 . 密码学（ cryptology ） -包括加 密理论与解密理论的学科 如果将加密过程看成是一个数学函 数 F的话 ， 则密文 C可以表示为： C = F （ P， K ） 这个函数具有两个自变量 P和 K， 在函数 F的作用下得到密文。在已知 密钥 K1、 K2、加密算法 E和解密算法 D时，则加密和解密过程可以表示如 下： EK1 （ P ） = C D K2（ C ） = P 显然为使明文加密后能被解密必 须有： P = D K2 （ E K1（ P ） = P 在实际加密和解密时 ， 根据加密 算法的特点 ， K1与 K2的值可以不同 ， 也可以相同 。 密码系统的攻击方法 穷举法 :又称强力攻击或者穷搜攻 击，是指分析者一次试遍密钥空 间中的所有的蜜钥来获取明文的 一种手段 典型的例子 1977年 DES密码的破 译 密码系统的攻击方法 统计分析攻击：密码分析者利用 明文和密文的概率统计规律，从 而找出符合规律的相应明文的方 法，如 Caesar密码 数学分析攻击：密码分析者对密 码特征中表现出的数学特征，通 过数学求解的方法来获取最后明 文。如公钥密码 RSA 密码系统的攻击方法 密码分析 密码分析 ：从密文推导出明文或密 钥 。 密码分析：常用的方法有以下 4类： 惟密文攻击（ cybertext only attack）； 已知明文攻击（ known plaintext attack）； 选择明文攻击（ chosen plaintext attack）； 选择密文攻击（ chosen ciphertext attack）。 惟密文攻击 密码分析者知道一些消息的密文 （加密算法相同），并且试图恢 复尽可能多的消息明文，并进一 步试图推算出加密消息的密钥 （以便通过密钥得出更多的消息 明文 。 已知明文攻击 密码分析者不仅知道一些消息的 密文，也知道与这些密文对应的 明文，并试图推导出加密密钥或 算法（该算法可对采用同一密钥 加密的所有新消息进行解密。 ) 选择明文攻击 密码分析者不仅知道一些消息的 密文以及与之对应的明文，而且 可以选择被加密的明文（这种选 择可能导致产生更多关于密钥的 信息），并试图推导出加密密钥 或算法（该算法可对采用同一密 钥加密的所有新消息进行解密）。 选择密文攻击 密码分析者能够选择不同的密文 并能得到对应的明文，密码分析 的目的是推导出密钥 。 古典密码的 分类 代替密码 置换密码 代数密码 代替密码 对于一个密码体制，如果构造一 个或多个密文字母表，使得明文 中不同位置的同一个明文字母与 密文字母表中的字母或字母组相 对应，这种密码体制为代替密码 体制。 它主要分为单表代替密码、多表 代替密码、多字母代替密码 置换密码 又称换位密码，换位就是将明文 中字母的位置重新排列。最简单 的换位就是逆序法，即将明文中 的字母倒过来输出。例如 明文 ： computer system 密文 ： metsys retupmoc 这种方法太简单 ， 非常容易破密。 下面介绍一种稍复杂的换位方 法 列换位法。 使用列换位法，首先要将明文排成一个 矩阵，然后按列进行输出。为此要解 决两个问题： 排成的矩阵的宽度 有多少列； 排成矩阵后，各列按什么样的顺序输 出。 为此，要引入一个密钥 k，它既可定义 矩阵的宽度，又可以定义各列的输出 顺序。例如 k=computer，则这个单 词的长度（ 8）就是明文矩阵的宽度， 而该密钥中各字母按字母序出现的次 序，就是输出的列的顺序。表 6.3为按 密钥对明文“ WHAT YOU CAN LEARN FROM THIS BOOK”的排列。 按密钥对明文“ WHAT YOU CAN LEARN FROM THIS BOOK”的排列 代数密码 利用代数数学知识对明文进行加 密的方式，如 Vernam密码 简单异或 异或运算具有如下特点： 0 0 = 0 0 1 = 1 1 0 = 1 1 1 = 0 a a = 0 即两个运算数相同，结果为 0；不同，结 果为 1。 + + + + + 恺撒密码 (Caesar) 恺撒密码 (Caesar) 恺撒密码 (Caesar) C=(m+k)mod26 恺撒密码的一般形式 一般形式，可以把 Caesar cipher 中字母移动的位数由 3变为 1-25中的 任何一个 密码分析 可以简单的实验每个密钥（穷密钥搜索） 给定一些密文，实验每个密钥。 LIZHZLVKWRUHSODFHOHWWHUV Original ciphertext KHYGYKUJVQTGRNCEGNGVVGTU try shift of 1 JGXFXJTIUPSFQMBDFMFUUFST try shift of 2 IFWEWISHTOREPLACELETTERS try shift of 3 * plaintext HEVDVHRGSNQDOKZBDKDSSDQR try shift of 4 MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 eg. break ciphertext GCUA VQ DTGCM 维吉尼亚密码（ Vigennere) 法国密码学家 Vigenere以 他自己的名字命名的维吉利亚密 码，在 1586年发明的，是一种 典型的多表代替密码，其明文、 密文构成的方阵为 Vigenere 方 阵 制作的方阵下表所示： 例如：明文为 data security， 密钥为 best 按密钥的长度将明文分解若干节。 这里 best的长度为 4，故将明文 分解为表 6.2所示的样子 对每一节明文，利用密钥 best进 行变换。以明文“ d”为例，变化 的方法是：由于 d处于 b列，因此 在维吉利亚方阵的第 d行 b列中 找。于是得到如下密文： C=Ek(M)=EELT TIUN SMLR Vigenere方阵的数学公式表达为 设明文为 m=m1m2m n , 密钥 k=k1k2k n,密文 c=c1c2c n, 则 ci=Ek(mi)=(mi+ki)mod26,其中 i=1,2,n Vigenere 密码可以看成是 Caesar密码的 推广 维吉尼亚密码（ Vigennere) 可以看出，越安全的密码使用起来越 复杂 因此，在有些场合还可以看到单码替 换密码 随着破译单码密码的技术提高， 使得 vigenre cipher 逐渐被各国使 用 1854年，首次被 Charles Babbage 攻破，但没有公开 Friedrich Kasiski 于 1863年攻破并发表了 此密码的各 种变形被沿用到 20世纪 普莱费厄（ Playfair）密码 Playfair密码是由 Charles Wheatstone于 1854年发明的，其名 称以他的朋友 Playfair命名。 英国陆军在第一次世界大战，美国 陆军在第二次世界大战期间大量使用 的一种二字母组代替密码。 它将明文中的双字母组合作为一个 单元对待，该加密法是基于一个关键 词的，该关键词填写在一个 5*5的矩 阵中（去出重复字母和字母 j），通过 该矩阵完成对明文、密文的加密、解 密过程。 对明文加密规则如下： 1 若 m1 m2在同一行，对应密文 c1 c2 分别是紧靠 m1 m2 右端的字母。其中第一 列被看做是最后一列的右方。 2 若 m1 m2在同一列，对应密文 c1 c2 分别是紧靠 m1 m2 下方的字母。其中第一 行被看做是最后一行的下方。 3 若 m1 m2不在同一行，不在同一列， 则 c1 c2是由 m1 m2确定的矩形的其他两角 的字母，并且 c1和 m1， c2和 m2同行。 4 若 m1 m2相同，则插入一个事先约定 的字母，比如 X 。 5 若明文字母数为奇数时，则在明文的 末端添加某个事先约定的字母作为填充。 解密算法 Playfair解密算法首先将密钥填写在 一个 5*5的矩阵中（去出重复字母和 字母 j），矩阵中其它未用到的字母 按顺序填在矩阵剩余位置中，根据替 换矩阵由密文得到明文。 1 若 c1 c2在同一行，对应明文 m1 m2分别是紧靠 c1 c2 左端的字母。其 中最后一列被看做是第一列的左方。 2 若 c1 c2在同一列，对应明文 m1 m2分别是紧靠 c1 c2 上方的字母。其 中最后一行被看做是第一行的上方。 3 若 c1 c2不在同一行，不在同一 列，则 m1 m2是由 m1 m2确定的矩形的 其他两角的字母，并且 c1和 m1， c2 和 m2同行。 举例说明 Vernam密码 它是一种代数密码，明文、密文、 密钥都用二进制表示 M=m1,m2m n K=k1,k1k n C=c1,c2c n 加密 ci=mi ki i=1,2n 解密 mi=ci ki i=1,2,.n 因为加密和解密都是模 2加，所 以为代数运算 对合运算 Vernam经不起明文的攻击 如果密钥有重复的， Vernam密 码是不安全的 一种极端情况 一次一密 1. 密钥是随机的 2. 密钥至少和明文一样长 3. 一个密钥只用一次 一次一密绝对是不可译的，但 它不实用，但它又给密码设计 指出一个方向，人们用序列密 码逼近一次一密 序列密码 序列密码是一类非常重要的密码体制，又称 为流密码。在流密码中，将明文消息按一定 长度分组（长度较小），然后对各组用相关 但不同的密钥进行加密，产生相应的密文， 相同的明文分组会因在明文序列中的位置不 同而对应于不同的密文分组。 优点： 第一，在硬件实施上，流密码的速度一般要 比分组密码快，而且不需要有很复杂的硬件 电路： 第二，在某些情况下（例如对某些电信上的 应用），当缓冲不足或必须对收到的字符进 行逐一处理时，流密码就显得更加必要和恰 当； 第三，流密码有较理想的数学分析工具，如 代数方法等。 第四，流密码能较好地隐藏明文的统计特征。 序列密码 目前关于流密码的理论和技术已取得 长足的发展。同时密码学家也提出了 大量的流密码算法，有些算法已被广 泛地应用于移动通信、军事外交等领 域。 它是由 Vernam发展而来的，包括 RC4和 SEAL算法 序列密码 序列密码主要取决于密钥序列的 安全，如果与密钥是随机的，咋 就成为一次一密密码，理论上不 可破。序列密码的加密和解密运 算简单，主要是模 2加。 基于线性移位寄存器 LFSR的序列密码 线性反馈移位寄存器 LFSR，简称移 位寄存器，其形成密码算法主要是利 用反馈移位寄存器的工作原理来生成 密钥序列。 N阶反馈移位寄存器模型 如下：这是一个左移一位寄存器，寄 存器没运动一次， n阶移位寄存器的 内容就向 n-1阶进一次，即第 2阶的内 容 S1传给第 1阶作为 s0，依次类推， 第 n阶的内容传给第 n-1阶，最后 n阶 的内容由反馈函数 f(s0,s1,s2,s n-1)传送。 如果它是线性的，则此寄存器称为线 性移位寄存器 N阶反馈移位寄存器 f(s0,s1,s n-1) s0 s1 Sn-2 Sn-1 - 输出 图中 s0,s1,.组成左移移位寄存器，并 称每一时刻移位寄存器的取值的一个 状态 f(s0,s1.s n-1)为反馈函数，如为线性 的，可写成 f(s0,s1,s n-1)=g0s0+g1s1+g n-1sn-1 其中 g0,g1,g n-1为反馈系数 在二进制中 +为 ，反馈系数 gi GF(2)如果 gi=0,表示式中 gisi不存 在，因此 si不连接，同理 gi=1,表示 si 连接，故 gi的作用相当于一个开关 ,如 图所示： s0 s1 Sn-2 Sn-1 + + + - - g1 g2 gn-1 g0=1 gn=1 形式地：用 xi与 si相对应，则根 据反馈函数得到一个关于 x的多 项式： g(x)=gnxn+gn-1xn-1+g 1x1+g0 称 g(x)为线性移位寄存器的连接 多项式 例题： 一个上 GF(2)的 5阶移位寄存器， 其反馈多项式为 f(x)=1+x+x4 ,初 始状态为 s0=(10110)，则其状态 序列与输出序列是什么 ? 由反馈多项式可以表示出连接多项 式 g(x)=1+x+x4+x5 ,由反馈多项 式可知 g0=g1=g4=1,则反馈可表示 为 f(x)=s0 s1 s4, 如图： s0 s1 s2 s3 s4 g1=1 g0=1 g4=1 g5-=1 状态 10110 01101 11010 10100 01001 10010 输出 1 0 0 1 0 1 状态 00101 01011 10110 01101 输出 1 0 1 0 该线性反馈寄存器的状态序列和输出序列的周 期为 8 输出序列为 10010110 N级线性移位寄存器最多有 2n个 不同的状态，若其初始状态为 0， 其后状态恒为 0.若初始状态不为 0， 其后状态也不为 0，因此 n级线性 反馈寄存器的状态周期小于或等 于 2n-1,其输出序列的周期小于或 等于 2n-1 只要选择合适的连接多项式便 可使线性移位寄存器的状态周 期达到 2n-1,此时的输出序列为 m序列 M序列的优点 1. 具有良好的随机性 2. 0和 1出现的次数接近相等，都 为 2n-1 RC4 RC4序列密码是美国 RSA数据安 全公司在 1987年设计的一种序列 密码，直到 1994年有人破获，在 1997年该公司公布了 RC4的算法。 该算法密钥 40为，在 Interner网 上 32小时可破获 RC4 它是一种基于非线性数据表的交 换序列密码，它以一个足够大的 数据表为基础，对表进行非线性 变换，产生非线性的密钥序列 RC4使用 256个字节的 S表和两个指针 （ I和 J） S表的值为 S0,S1,S 255是 0， 1.255 的一个排列 I 、 J的处置为 0 我们把 RC4算法看成一个有限的状态 自动机，把 S表和 I、 J的具体取值作 为 RC4的一个状态 T=,对状态 T进行非 线性变换，产生新的状态，并且输出 密钥序列中的一个字节 K RC4的下一个状态函数如下 1. I=0,J=0 2. I=(I+1) MOD256 3. J=(J+SI )MOD 256 4. 交换 SI和 SJ RC4的输出函数如下 1. h=(si+sj) mod 256 2. K=sh 在使用 RC4加解密之前，首先 对 S表初始化 对 S表进行线性填充 1、 S0=0,S1=1,S255=255 2、用密钥填充另一个 256字节的 R表 R0,R1,R255, 如果密钥的长度 小于 R表的长度，则一次重复填充， 直到 R表填满 3、 J=0 4、对 I=0到 255重复一下操作 J=J+si+RI 交换 SI和 SJ RC4的算法优点 算法简单、高效，特别适合软 件实现，目前应用非常广泛 注意 ，对 S表初始化的过程实质上 是 对 S表进行随机化处理 的过程，只 有当这一个过程完成后，才能计算 产生密钥序列，否则将是不安全的