《系统结构》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类： 惟密文攻击（cybertextonly attack）； 已知明文攻击（knownplaintext attack）； 选择明文攻击（chosenplaintext attack）； 选择密文攻击（chosenciphertext 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=m1m2mn , 密钥k=k1k2kn,密文c=c1c2cn,则 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,m2mn K=k1,k1kn C=c1,c2cn 加密 ci=mi ki i=1,2n 解密 mi=ci ki i=1,2,.n 因为加密和解密都是模2加，所以为代数运算,对合运算 Vernam经不起明文的攻击 如果密钥有重复的，Vernam密码是不安全的 一种极端情况 一次一密 密钥是随机的 密钥至少和明文一样长 一个密钥只用一次 一次一密绝对是不可译的，但它不实用，但它又给密码设计指出一个方向，人们用序列密码逼近一次一密,序列密码,序列密码是一类非常重要的密码体制，又称为流密码。在流密码中，将明文消息按一定长度分组（长度较小），然后对各组用相关但不同的密钥进行加密，产生相应的密文，相同的明文分组会因在明文序列中的位置不同而对应于不同的密文分组。 优点： 第一，在硬件实施上，流密码的速度一般要比分组密码快，而且不需要有很复杂的硬件电路： 第二，在某些情况下（例如对某些电信上的应用），当缓冲不足或必须对收到的字符进行逐一处理时，流密码就显得更加必要和恰当； 第三，流密码有较理想的数学分析工具，如代数方法等。 第四，流密码能较好地隐藏明文的统计特征。,序列密码,目前关于流密码的理论和技术已取得长足的发展。同时密码学家也提出了大量的流密码算法，有些算法已被广泛地应用于移动通信、军事外交等领域。 它是由Vernam发展而来的，包括RC4和SEAL算法,序列密码,序列密码主要取决于密钥序列的安全，如果与密钥是随机的，咋就成为一次一密密码，理论上不可破。序列密码的加密和解密运算简单，主要是模2加。,基于线性移位寄存器LFSR的序列密码,线性反馈移位寄存器LFSR，简称移位寄存器，其形成密码算法主要是利用反馈移位寄存器的工作原理来生成密钥序列。N阶反馈移位寄存器模型如下：这是一个左移一位寄存器，寄存器没运动一次，n阶移位寄存器的内容就向n-1阶进一次，即第2阶的内容S1传给第1阶作为s0，依次类推，第n阶的内容传给第n-1阶，最后n阶的内容由反馈函数f(s0,s1,s2,sn-1)传送。如果它是线性的，则此寄存器称为线性移位寄存器,N阶反馈移位寄存器,f(s0,s1,sn-1),s0,s1,Sn-2,Sn-1,-,输出,图中s0,s1,组成左移移位寄存器，并称每一时刻移位寄存器的取值的一个状态 f(s0,s1.sn-1)为反馈函数，如为线性的，可写成 f(s0,s1,sn-1)=g0s0+g1s1+gn-1sn-1 其中g0,g1,gn-1为反馈系数 在二进制中+为 ，反馈系数giGF(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+g1x1+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序列的优点 具有良好的随机性 0和1出现的次数接近相等，都为2n-1,RC4,RC4序列密码是美国RSA数