第2章系统结构精选PPT.ppt
第2章系统结构第1页,此课件共59页哦n n密码学的历史已有密码学的历史已有密码学的历史已有密码学的历史已有40004000多年多年多年多年n n古埃及人曾把象形文字写在石碑上古埃及人曾把象形文字写在石碑上古埃及人曾把象形文字写在石碑上古埃及人曾把象形文字写在石碑上n n密码学是一门研究秘密信息的隐写技术的学密码学是一门研究秘密信息的隐写技术的学密码学是一门研究秘密信息的隐写技术的学密码学是一门研究秘密信息的隐写技术的学科科科科n n密码学技术可以使消息的内容对密码学技术可以使消息的内容对密码学技术可以使消息的内容对密码学技术可以使消息的内容对(除发送除发送除发送除发送者和接收者以外者和接收者以外者和接收者以外者和接收者以外)的所有人保密的所有人保密的所有人保密的所有人保密.n n可以使接收者验证消息的正确性可以使接收者验证消息的正确性可以使接收者验证消息的正确性可以使接收者验证消息的正确性n n是解决计算机与通信安全问题重要技术是解决计算机与通信安全问题重要技术是解决计算机与通信安全问题重要技术是解决计算机与通信安全问题重要技术之一之一之一之一.密码学密码学第2页,此课件共59页哦密码学的发展n n第第第第1 1阶段:阶段:阶段:阶段:19491949年以前。年以前。年以前。年以前。n n第第第第2 2阶段:从阶段:从阶段:从阶段:从19491949年到年到年到年到19751975年。年。年。年。l l标志:标志:1949年年Shannon发表的发表的保密系统的信息理论一文。保密系统的信息理论一文。n n第第第第3 3阶段:阶段:阶段:阶段:19761976年至今。年至今。年至今。年至今。l l标志:标志:1976年年Diffie和和Hellman发发表了密码学新方向一文。表了密码学新方向一文。第3页,此课件共59页哦Shannon模型第4页,此课件共59页哦密码的基本术语n n密码技术(密码技术(密码技术(密码技术(CryptographyCryptography)把可理解把可理解把可理解把可理解的消息变换成不可理解消息,同时又可恢的消息变换成不可理解消息,同时又可恢的消息变换成不可理解消息,同时又可恢的消息变换成不可理解消息,同时又可恢复原消息的方法和原理的一门科学或艺术。复原消息的方法和原理的一门科学或艺术。复原消息的方法和原理的一门科学或艺术。复原消息的方法和原理的一门科学或艺术。n n明文(明文(明文(明文(plaintext plaintext)-变换前的原始消息变换前的原始消息变换前的原始消息变换前的原始消息n n密文(密文(密文(密文(ciphertextciphertext)-变换后的消息变换后的消息变换后的消息变换后的消息 n n密码(密码(密码(密码(cipher cipher)-用于改变消息的替换或用于改变消息的替换或用于改变消息的替换或用于改变消息的替换或变换算法变换算法变换算法变换算法n n密钥(密钥(密钥(密钥(key key)-用于密码变换的,只有用于密码变换的,只有用于密码变换的,只有用于密码变换的,只有发送者或接收者拥有的秘密消息发送者或接收者拥有的秘密消息发送者或接收者拥有的秘密消息发送者或接收者拥有的秘密消息第5页,此课件共59页哦n n编码(编码(encipher/encode)-把把明文变为密文的过程明文变为密文的过程n n译码(译码(decipher/decode)把密把密文变为明文的过程文变为明文的过程n n密码分析(密码分析(cryptanalysis/codebreaking)l l在没有密钥的情况下,破解密文的在没有密钥的情况下,破解密文的原理与方法原理与方法.n n密码学(密码学(cryptology)-包括加包括加密理论与解密理论的学科密理论与解密理论的学科第6页,此课件共59页哦n n 如如如如果果果果将将将将加加加加密密密密过过过过程程程程看看看看成成成成是是是是一一一一个个个个数数数数学学学学函函函函数数数数F F的话,则密文的话,则密文的话,则密文的话,则密文C C可以表示为:可以表示为:可以表示为:可以表示为:n n C=F C=F(P P,K K)n n 这个函数具有两个自变量这个函数具有两个自变量这个函数具有两个自变量这个函数具有两个自变量P P和和和和KK,在,在,在,在函数函数函数函数F F的作用下得到密文。在已知密钥的作用下得到密文。在已知密钥的作用下得到密文。在已知密钥的作用下得到密文。在已知密钥K1K1、K2K2、加密算法、加密算法、加密算法、加密算法E E和解密算法和解密算法和解密算法和解密算法D D时,则时,则时,则时,则加密和解密过程可以表示如下:加密和解密过程可以表示如下:加密和解密过程可以表示如下:加密和解密过程可以表示如下:n n E EK1K1 (P P)=C=Cn n D D K2 K2(C C)=P =P n n 显然为使明文加密后能被解密必须有:显然为使明文加密后能被解密必须有:显然为使明文加密后能被解密必须有:显然为使明文加密后能被解密必须有:n n P=DP=D K2 K2 (E E K1 K1(P P)=P=Pn n n n 在在在在实实实实际际际际加加加加密密密密和和和和解解解解密密密密时时时时,根根根根据据据据加加加加密密密密算算算算法法法法的的的的特点,特点,特点,特点,K1K1与与与与K2K2的值可以不同,也可以相同。的值可以不同,也可以相同。的值可以不同,也可以相同。的值可以不同,也可以相同。第7页,此课件共59页哦密码系统的攻击方法n n穷举法:又称强力攻击或者穷搜攻击,是指分析者一次试遍密钥空间中的所有的蜜钥来获取明文的一种手段n n典型的例子1977年DES密码的破译第8页,此课件共59页哦密码系统的攻击方法n n统计分析攻击:密码分析者利用明文和密文的概率统计规律,从而找出符合规律的相应明文的方法,如Caesar密码第9页,此课件共59页哦n n数学分析攻击:密码分析者对密码特征中表现出的数学特征,通过数学求解的方法来获取最后明文。如公钥密码RSA密码系统的攻击方法第10页,此课件共59页哦密码分析n n密码分析密码分析密码分析密码分析 :从密文推导出明文或密钥:从密文推导出明文或密钥:从密文推导出明文或密钥:从密文推导出明文或密钥 。n n密码分析:常用的方法有以下密码分析:常用的方法有以下密码分析:常用的方法有以下密码分析:常用的方法有以下4 4类:类:类:类:l l惟密文攻击(惟密文攻击(cybertextonly attack););l l已知明文攻击已知明文攻击(knownplaintext attack););l l选择明文攻击选择明文攻击(chosenplaintext attack););l l选择密文攻击选择密文攻击(chosenciphertext attack)。)。第11页,此课件共59页哦惟密文攻击n n密码分析者知道一些消息的密文密码分析者知道一些消息的密文(加密算法相同),并且试图恢(加密算法相同),并且试图恢复尽可能多的消息明文,并进一复尽可能多的消息明文,并进一步试图推算出加密消息的密钥步试图推算出加密消息的密钥(以便通过密钥得出更多的消息(以便通过密钥得出更多的消息明文明文。第12页,此课件共59页哦已知明文攻击n n密码分析者不仅知道一些消息的密码分析者不仅知道一些消息的密文,也知道与这些密文对应的密文,也知道与这些密文对应的明文,并试图推导出加密密钥或明文,并试图推导出加密密钥或算法(该算法可对采用同一密钥算法(该算法可对采用同一密钥加密的所有新消息进行解密。加密的所有新消息进行解密。)第13页,此课件共59页哦 选择明文攻击 n n密码分析者不仅知道一些消息的密码分析者不仅知道一些消息的密文以及与之对应的明文,而且密文以及与之对应的明文,而且可以选择被加密的明文(这种选可以选择被加密的明文(这种选择可能导致产生更多关于密钥的择可能导致产生更多关于密钥的信息),并试图推导出加密密钥信息),并试图推导出加密密钥或算法(该算法可对采用同一密或算法(该算法可对采用同一密钥加密的所有新消息进行解密)。钥加密的所有新消息进行解密)。第14页,此课件共59页哦选择密文攻击n n密码分析者能够选择不同的密文密码分析者能够选择不同的密文并能得到对应的明文,密码分析并能得到对应的明文,密码分析的目的是推导出密钥的目的是推导出密钥。第15页,此课件共59页哦古典密码的 分类n n代替密码代替密码n n置换密码置换密码n n代数密码代数密码 第16页,此课件共59页哦代替密码n n对于一个密码体制,如果构造一对于一个密码体制,如果构造一个或多个密文字母表,使得明文个或多个密文字母表,使得明文中不同位置的同一个明文字母与中不同位置的同一个明文字母与密文字母表中的字母或字母组相密文字母表中的字母或字母组相对应,这种密码体制为代替密码对应,这种密码体制为代替密码体制。体制。n n它主要分为单表代替密码、多表它主要分为单表代替密码、多表代替密码、多字母代替密码代替密码、多字母代替密码第17页,此课件共59页哦置换密码n n又称换位密码,换位就是将明文又称换位密码,换位就是将明文中字母的位置重新排列。最简单中字母的位置重新排列。最简单的换位就是逆序法,即将明文中的换位就是逆序法,即将明文中的字母倒过来输出。例如的字母倒过来输出。例如 明文:明文:computer system 密文:密文:metsys retupmoc 这种方法太简单,非常容易破密。这种方法太简单,非常容易破密。下面介绍一种稍复杂的换位方法下面介绍一种稍复杂的换位方法列换位法。列换位法。第18页,此课件共59页哦使用列换位法,首先要将明文排成一个矩阵,使用列换位法,首先要将明文排成一个矩阵,使用列换位法,首先要将明文排成一个矩阵,使用列换位法,首先要将明文排成一个矩阵,然后按列进行输出。为此要解决两个问题:然后按列进行输出。为此要解决两个问题:然后按列进行输出。为此要解决两个问题:然后按列进行输出。为此要解决两个问题:n n 排成的矩阵的宽度排成的矩阵的宽度排成的矩阵的宽度排成的矩阵的宽度有多少列;有多少列;有多少列;有多少列;n n 排成矩阵后,各列按什么样的顺序输排成矩阵后,各列按什么样的顺序输排成矩阵后,各列按什么样的顺序输排成矩阵后,各列按什么样的顺序输出。出。出。出。为此,要引入一个密钥为此,要引入一个密钥为此,要引入一个密钥为此,要引入一个密钥k k,它既可定义矩,它既可定义矩,它既可定义矩,它既可定义矩阵的宽度,又可以定义各列的输出顺序。阵的宽度,又可以定义各列的输出顺序。阵的宽度,又可以定义各列的输出顺序。阵的宽度,又可以定义各列的输出顺序。例如例如例如例如k=computerk=computer,则这个单词的长度,则这个单词的长度,则这个单词的长度,则这个单词的长度(8 8)就是明文矩阵的宽度,而该密钥中)就是明文矩阵的宽度,而该密钥中)就是明文矩阵的宽度,而该密钥中)就是明文矩阵的宽度,而该密钥中各字母按字母序出现的次序,就是输出各字母按字母序出现的次序,就是输出各字母按字母序出现的次序,就是输出各字母按字母序出现的次序,就是输出的列的顺序。表的列的顺序。表的列的顺序。表的列的顺序。表6.36.3为按密钥对明文为按密钥对明文为按密钥对明文为按密钥对明文“WHAT YOU CAN LEARN FROM THIS“WHAT YOU CAN LEARN FROM THIS BOOK”BOOK”的排列。的排列。的排列。的排列。第19页,此课件共59页哦按密钥对明文按密钥对明文按密钥对明文按密钥对明文“WHAT YOU CAN LEARN“WHAT YOU CAN LEARN FROM THIS BOOK”FROM THIS BOOK”的排列的排列的排列的排列第20页,此课件共59页哦代数密码n n利用代数数学知识对明文进行加密的方式,如Vernam密码简单异或简单异或 异或运算具有如下特点:异或运算具有如下特点:0 0=0 0 1=1 1 0=1 1 1=0 a a=0 即两个运算数相同,结果为即两个运算数相同,结果为0;不同,结果为;不同,结果为1。+第21页,此课件共59页哦恺撒密码恺撒密码(Caesar)第22页,此课件共59页哦恺撒密码恺撒密码(Caesar)第23页,此课件共59页哦恺撒密码恺撒密码(Caesar)C=(m+k)mod26第24页,此课件共59页哦恺撒密码的一般形式n n一般形式,可以把一般形式,可以把Caesar cipher Caesar cipher 中字母移动的位数由中字母移动的位数由中字母移动的位数由中字母移动的位数由3 3变为变为变为变为1-251-25中的任中的任中的任中的任何一个何一个何一个何一个第25页,此课件共59页哦密码分析n n可以简单的实验每个密钥(穷密钥搜索)可以简单的实验每个密钥(穷密钥搜索)可以简单的实验每个密钥(穷密钥搜索)可以简单的实验每个密钥(穷密钥搜索)n n给定一些密文,实验每个密钥。给定一些密文,实验每个密钥。给定一些密文,实验每个密钥。给定一些密文,实验每个密钥。LIZHZLVKWRUHSODFHOHWWHUV Original ciphertext LIZHZLVKWRUHSODFHOHWWHUV Original ciphertext KHYGYKUJVQTGRNCEGNGVVGTU try shift of 1 KHYGYKUJVQTGRNCEGNGVVGTU try shift of 1 JGXFXJTIUPSFQMBDFMFUUFST try shift of 2 JGXFXJTIUPSFQMBDFMFUUFST try shift of 2 IFWEWISHTOREPLACELETTERS try shift of 3 IFWEWISHTOREPLACELETTERS try shift of 3*plaintext*plaintext HEVDVHRGSNQDOKZBDKDSSDQR try shift of 4 HEVDVHRGSNQDOKZBDKDSSDQR try shift of 4 MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 n neg.break ciphertext GCUA VQ DTGCM eg.break ciphertext GCUA VQ DTGCM 第26页,此课件共59页哦维吉尼亚密码(Vigennere)法国密码学家法国密码学家Vigenere以以他自己的名字命名的维吉利亚密他自己的名字命名的维吉利亚密码,在码,在1586年发明的,是一种年发明的,是一种典型的多表代替密码,其明文、典型的多表代替密码,其明文、密文构成的方阵为密文构成的方阵为Vigenere 方方阵阵第27页,此课件共59页哦制作的方阵下表所示:制作的方阵下表所示:第28页,此课件共59页哦n n例如:明文为例如:明文为 data security,密密钥为钥为bestn n按密钥的长度将明文分解若干节。按密钥的长度将明文分解若干节。这里这里best的长度为的长度为4,故将明文,故将明文分解为表分解为表6.2所示的样子所示的样子第29页,此课件共59页哦n n对每一节明文,利用密钥对每一节明文,利用密钥best进进行变换。以明文行变换。以明文“d”为例,变为例,变化的方法是:由于化的方法是:由于d处于处于b列,因列,因此在维吉利亚方阵的第此在维吉利亚方阵的第 d行行b列列中找。于是得到如下密文:中找。于是得到如下密文:C=Ek(k(M)=EELT TIUN SMLR第30页,此课件共59页哦Vigenere方阵的数学公式表达为方阵的数学公式表达为n n设明文为设明文为m=m1m2mn,密钥密钥k=k1 1k2kn,密文密文c=c1c2cn,则则 ci i=Ek k(mi i)=(mi i+ki i)mod26,其中其中i=1,2,nn nVigenere 密码可以看成是密码可以看成是Caesar密码的密码的 推广推广第31页,此课件共59页哦维吉尼亚密码(Vigennere)n n可以看出,越安全的密码使用起来越复可以看出,越安全的密码使用起来越复可以看出,越安全的密码使用起来越复可以看出,越安全的密码使用起来越复杂杂杂杂 n n因此,在有些场合还可以看到单码替换因此,在有些场合还可以看到单码替换因此,在有些场合还可以看到单码替换因此,在有些场合还可以看到单码替换密码密码密码密码 n n随着破译单码密码的技术提高,随着破译单码密码的技术提高,随着破译单码密码的技术提高,随着破译单码密码的技术提高,n n使得使得使得使得vigenre cipher vigenre cipher 逐渐被各国使用逐渐被各国使用逐渐被各国使用逐渐被各国使用n n18541854年,首次被年,首次被年,首次被年,首次被 Charles Babbage Charles Babbage 攻攻攻攻破,但没有公开破,但没有公开破,但没有公开破,但没有公开Friedrich Kasiski Friedrich Kasiski 于于于于18631863年攻破并发表了年攻破并发表了年攻破并发表了年攻破并发表了 此密码的各种变形此密码的各种变形此密码的各种变形此密码的各种变形被沿用到被沿用到被沿用到被沿用到2020世纪世纪世纪世纪第32页,此课件共59页哦普莱费厄(Playfair)密码 l l Playfair Playfair密码是由密码是由密码是由密码是由Charles Charles WheatstoneWheatstone于于于于18541854年发明的,其名称年发明的,其名称年发明的,其名称年发明的,其名称以他的朋友以他的朋友以他的朋友以他的朋友PlayfairPlayfair命名。命名。命名。命名。l l 英国陆军在第一次世界大战,美国陆军在英国陆军在第一次世界大战,美国陆军在英国陆军在第一次世界大战,美国陆军在英国陆军在第一次世界大战,美国陆军在第二次世界大战期间大量使用的一种二字母第二次世界大战期间大量使用的一种二字母第二次世界大战期间大量使用的一种二字母第二次世界大战期间大量使用的一种二字母组代替密码。组代替密码。组代替密码。组代替密码。l l 它将明文中的双字母组合作为一个单元它将明文中的双字母组合作为一个单元它将明文中的双字母组合作为一个单元它将明文中的双字母组合作为一个单元对待,该加密法是基于一个关键词的,该对待,该加密法是基于一个关键词的,该对待,该加密法是基于一个关键词的,该对待,该加密法是基于一个关键词的,该关键词填写在一个关键词填写在一个关键词填写在一个关键词填写在一个5*55*5的矩阵中(去出重的矩阵中(去出重的矩阵中(去出重的矩阵中(去出重复字母和字母复字母和字母复字母和字母复字母和字母j j),通过该矩阵完成对明文、),通过该矩阵完成对明文、),通过该矩阵完成对明文、),通过该矩阵完成对明文、密文的加密、解密过程。密文的加密、解密过程。密文的加密、解密过程。密文的加密、解密过程。第33页,此课件共59页哦对明文加密规则如下:n n1 1 若若若若m1 m2m1 m2在同一行,对应密文在同一行,对应密文在同一行,对应密文在同一行,对应密文c1 c2c1 c2分别是紧分别是紧分别是紧分别是紧靠靠靠靠m1 m2 m1 m2 右端的字母。其中第一列被看做是最后一右端的字母。其中第一列被看做是最后一右端的字母。其中第一列被看做是最后一右端的字母。其中第一列被看做是最后一列的右方。列的右方。列的右方。列的右方。2 2 若若若若m1 m2m1 m2在同一列,对应密文在同一列,对应密文在同一列,对应密文在同一列,对应密文c1 c2c1 c2分别是紧分别是紧分别是紧分别是紧靠靠靠靠m1 m2 m1 m2 下方的字母。其中第一行被看做是最后一下方的字母。其中第一行被看做是最后一下方的字母。其中第一行被看做是最后一下方的字母。其中第一行被看做是最后一行的下方。行的下方。行的下方。行的下方。3 3 若若若若m1 m2m1 m2不在同一行,不在同一列,则不在同一行,不在同一列,则不在同一行,不在同一列,则不在同一行,不在同一列,则c1 c2c1 c2是由是由是由是由m1 m2m1 m2确定的矩形的其他两角的字母,并且确定的矩形的其他两角的字母,并且确定的矩形的其他两角的字母,并且确定的矩形的其他两角的字母,并且c1c1和和和和m1m1,c2 c2和和和和m2m2同行。同行。同行。同行。4 4 若若若若m1 m2m1 m2相同,则插入一个事先约定的字母,相同,则插入一个事先约定的字母,相同,则插入一个事先约定的字母,相同,则插入一个事先约定的字母,比如比如比如比如X X。5 5 若明文字母数为奇数时,则在明文的末端添加若明文字母数为奇数时,则在明文的末端添加若明文字母数为奇数时,则在明文的末端添加若明文字母数为奇数时,则在明文的末端添加某个事先约定的字母作为填充。某个事先约定的字母作为填充。某个事先约定的字母作为填充。某个事先约定的字母作为填充。第34页,此课件共59页哦解密算法n nPlayfairPlayfairPlayfairPlayfair解密算法首先将密钥填写在一解密算法首先将密钥填写在一解密算法首先将密钥填写在一解密算法首先将密钥填写在一个个个个5*55*55*55*5的矩阵中(去出重复字母和字母的矩阵中(去出重复字母和字母的矩阵中(去出重复字母和字母的矩阵中(去出重复字母和字母j j j j),矩阵中其它未用到的字母按顺序填),矩阵中其它未用到的字母按顺序填),矩阵中其它未用到的字母按顺序填),矩阵中其它未用到的字母按顺序填在矩阵剩余位置中,根据替换矩阵由密在矩阵剩余位置中,根据替换矩阵由密在矩阵剩余位置中,根据替换矩阵由密在矩阵剩余位置中,根据替换矩阵由密文得到明文。文得到明文。文得到明文。文得到明文。1 1 1 1 若若若若c1 c2c1 c2c1 c2c1 c2在同一行,对应明文在同一行,对应明文在同一行,对应明文在同一行,对应明文m1 m2m1 m2m1 m2m1 m2分别是紧靠分别是紧靠分别是紧靠分别是紧靠c1 c2 c1 c2 c1 c2 c1 c2 左端的字母。其中最左端的字母。其中最左端的字母。其中最左端的字母。其中最后一列被看做是第一列的左方。后一列被看做是第一列的左方。后一列被看做是第一列的左方。后一列被看做是第一列的左方。2 2 2 2 若若若若c1 c2c1 c2c1 c2c1 c2在同一列,对应明文在同一列,对应明文在同一列,对应明文在同一列,对应明文m1 m2m1 m2m1 m2m1 m2分别是紧靠分别是紧靠分别是紧靠分别是紧靠c1 c2 c1 c2 c1 c2 c1 c2 上方的字母。其中最上方的字母。其中最上方的字母。其中最上方的字母。其中最后一行被看做是第一行的上方。后一行被看做是第一行的上方。后一行被看做是第一行的上方。后一行被看做是第一行的上方。3 3 3 3 若若若若c1 c2c1 c2c1 c2c1 c2不在同一行,不在同一列,不在同一行,不在同一列,不在同一行,不在同一列,不在同一行,不在同一列,则则则则m1 m2m1 m2m1 m2m1 m2是由是由是由是由m1 m2m1 m2m1 m2m1 m2确定的矩形的其他两确定的矩形的其他两确定的矩形的其他两确定的矩形的其他两角的字母,并且角的字母,并且角的字母,并且角的字母,并且c1c1c1c1和和和和m1m1m1m1,c2 c2 c2 c2和和和和m2m2m2m2同行。同行。同行。同行。第35页,此课件共59页哦举例说明第36页,此课件共59页哦第37页,此课件共59页哦Vernam密码n n它是一种代数密码,明文、密文、它是一种代数密码,明文、密文、密钥都用二进制表示密钥都用二进制表示n nM=m1 1,m2 2mn n K=k1 1,k1 1kn n n nC=c1 1,c2 2cn nn n加密加密 ci i=mi i ki i i=1,2nn n解密解密 mi i=ci i ki i i=1,2,.nn n因为加密和解密都是模因为加密和解密都是模2加,所加,所以为代数运算以为代数运算第38页,此课件共59页哦n n对合运算对合运算n nVernam经不起明文的攻击经不起明文的攻击n n如果密钥有重复的,如果密钥有重复的,Vernam密密码是不安全的码是不安全的n n一种极端情况一种极端情况 一次一密一次一密1.1.密钥是随机的密钥是随机的2.2.密钥至少和明文一样长密钥至少和明文一样长3.3.一个密钥只用一次一个密钥只用一次n n一次一密绝对是不可译的,但一次一密绝对是不可译的,但它不实用,但它又给密码设计它不实用,但它又给密码设计指出一个方向,人们用序列密指出一个方向,人们用序列密码逼近一次一密码逼近一次一密第39页,此课件共59页哦序列密码n n序列密码是一类非常重要的密码体制,又称为序列密码是一类非常重要的密码体制,又称为序列密码是一类非常重要的密码体制,又称为序列密码是一类非常重要的密码体制,又称为流密码。在流密码中,将明文消息按一定长度流密码。在流密码中,将明文消息按一定长度流密码。在流密码中,将明文消息按一定长度流密码。在流密码中,将明文消息按一定长度分组(长度较小),然后对各组用相关但不同分组(长度较小),然后对各组用相关但不同分组(长度较小),然后对各组用相关但不同分组(长度较小),然后对各组用相关但不同的密钥进行加密,产生相应的密文,相同的明的密钥进行加密,产生相应的密文,相同的明的密钥进行加密,产生相应的密文,相同的明的密钥进行加密,产生相应的密文,相同的明文分组会因在明文序列中的位置不同而对应于文分组会因在明文序列中的位置不同而对应于文分组会因在明文序列中的位置不同而对应于文分组会因在明文序列中的位置不同而对应于不同的密文分组。不同的密文分组。不同的密文分组。不同的密文分组。n n优点:优点:优点:优点:n n第一,在硬件实施上,流密码的速度一般要比分组第一,在硬件实施上,流密码的速度一般要比分组第一,在硬件实施上,流密码的速度一般要比分组第一,在硬件实施上,流密码的速度一般要比分组密码快,而且不需要有很复杂的硬件电路:密码快,而且不需要有很复杂的硬件电路:密码快,而且不需要有很复杂的硬件电路:密码快,而且不需要有很复杂的硬件电路:n n第二,在某些情况下(例如对某些电信上的应用)第二,在某些情况下(例如对某些电信上的应用)第二,在某些情况下(例如对某些电信上的应用)第二,在某些情况下(例如对某些电信上的应用),当缓冲不足或必须对收到的字符进行逐一处理,当缓冲不足或必须对收到的字符进行逐一处理,当缓冲不足或必须对收到的字符进行逐一处理,当缓冲不足或必须对收到的字符进行逐一处理时,流密码就显得更加必要和恰当;时,流密码就显得更加必要和恰当;时,流密码就显得更加必要和恰当;时,流密码就显得更加必要和恰当;n n第三,流密码有较理想的数学分析工具,如代数第三,流密码有较理想的数学分析工具,如代数第三,流密码有较理想的数学分析工具,如代数第三,流密码有较理想的数学分析工具,如代数方法等。方法等。方法等。方法等。n n第四,流密码能较好地隐藏明文的统计特征。第四,流密码能较好地隐藏明文的统计特征。第四,流密码能较好地隐藏明文的统计特征。第四,流密码能较好地隐藏明文的统计特征。第40页,此课件共59页哦序列密码n n目前关于流密码的理论和技术已取得长目前关于流密码的理论和技术已取得长目前关于流密码的理论和技术已取得长目前关于流密码的理论和技术已取得长足的发展。同时密码学家也提出了大量足的发展。同时密码学家也提出了大量足的发展。同时密码学家也提出了大量足的发展。同时密码学家也提出了大量的流密码算法,有些算法已被广泛地应的流密码算法,有些算法已被广泛地应的流密码算法,有些算法已被广泛地应的流密码算法,有些算法已被广泛地应用于移动通信、军事外交等领域。用于移动通信、军事外交等领域。用于移动通信、军事外交等领域。用于移动通信、军事外交等领域。n n它是由它是由它是由它是由VernamVernam发展而来的,包括发展而来的,包括发展而来的,包括发展而来的,包括RC4RC4和和和和SEALSEAL算法算法算法算法第41页,此课件共59页哦序列密码n n序列密码主要取决于密钥序列的序列密码主要取决于密钥序列的安全,如果与密钥是随机的,咋安全,如果与密钥是随机的,咋就成为一次一密密码,理论上不就成为一次一密密码,理论上不可破。序列密码的加密和解密运可破。序列密码的加密和解密运算简单,主要是模算简单,主要是模2加。加。第42页,此课件共59页哦基于线性移位寄存器基于线性移位寄存器LFSRLFSR的序列密码的序列密码n n线性反馈移位寄存器线性反馈移位寄存器线性反馈移位寄存器线性反馈移位寄存器LFSRLFSR,简称移位寄,简称移位寄,简称移位寄,简称移位寄存器,其形成密码算法主要是利用反馈移存器,其形成密码算法主要是利用反馈移存器,其形成密码算法主要是利用反馈移存器,其形成密码算法主要是利用反馈移位寄存器的工作原理来生成密钥序列。位寄存器的工作原理来生成密钥序列。位寄存器的工作原理来生成密钥序列。位寄存器的工作原理来生成密钥序列。N N阶反馈移位寄存器模型如下:这是一个左阶反馈移位寄存器模型如下:这是一个左阶反馈移位寄存器模型如下:这是一个左阶反馈移位寄存器模型如下:这是一个左移一位寄存器,寄存器没运动一次,移一位寄存器,寄存器没运动一次,移一位寄存器,寄存器没运动一次,移一位寄存器,寄存器没运动一次,n n阶阶阶阶移位寄存器的内容就向移位寄存器的内容就向移位寄存器的内容就向移位寄存器的内容就向n-1n-1阶进一次,即阶进一次,即阶进一次,即阶进一次,即第第第第2 2阶的内容阶的内容阶的内容阶的内容S1S1传给第传给第传给第传给第1 1阶作为阶作为阶作为阶作为s0s0,依次类,依次类,依次类,依次类推,第推,第推,第推,第n n阶的内容传给第阶的内容传给第阶的内容传给第阶的内容传给第n-1n-1阶,最后阶,最后阶,最后阶,最后n n阶阶阶阶的内容由反馈函数的内容由反馈函数的内容由反馈函数的内容由反馈函数f(sf(s0 0,s,s1 1,s,s2 2,s,sn-1n-1)传送。传送。传送。传送。如果它是线性的,则此寄存器称为线性移如果它是线性的,则此寄存器称为线性移如果它是线性的,则此寄存器称为线性移如果它是线性的,则此寄存器称为线性移位寄存器位寄存器位寄存器位寄存器第43页,此课件共59页哦N阶反馈移位寄存器f(s0 0,s1 1,sn-1n-1)s0s1Sn-2Sn-1-输出第44页,此课件共59页哦n n图中图中图中图中s s0 0,s,s1 1,.,.组成左移移位寄存器,并称组成左移移位寄存器,并称组成左移移位寄存器,并称组成左移移位寄存器,并称每一时刻移位寄存器的取值的一个状态每一时刻移位寄存器的取值的一个状态每一时刻移位寄存器的取值的一个状态每一时刻移位寄存器的取值的一个状态n nf(sf(s0 0,s,s1 1.s.sn-1n-1)为反馈函数,如为线性的,为反馈函数,如为线性的,为反馈函数,如为线性的,为反馈函数,如为线性的,可写成可写成可写成可写成n nf(sf(s0 0,s,s1 1,s,sn-1n-1)=g)=g0 0s s0 0+g+g1 1s s1 1+g+gn-1n-1s sn-1n-1n n其中其中其中其中g g0,0,g g1 1,g,gn-1n-1为反馈系数为反馈系数为反馈系数为反馈系数n n在二进制中在二进制中在二进制中在二进制中+为为为为 ,反馈系数,反馈系数,反馈系数,反馈系数g gi iGF(2)GF(2)如果如果如果如果g gi i=0,=0,表示式中表示式中表示式中表示式中g gi is si i不存在,因此不存在,因此不存在,因此不存在,因此s si i不连接,同理不连接,同理不连接,同理不连接,同理g gi i=1,=1,表示表示表示表示s si i 连接,故连接,故连接,故连接,故g gi i的作的作的作的作用相当于一个开关用相当于一个开关用相当于一个开关用相当于一个开关,如图所示:如图所示:如图所示:如图所示:第45页,此课件共59页哦s0s1Sn-2Sn-1+-g1g2gn-1g0=1gn=1第46页,此课件共59页哦n n形式地:用形式地:用xi与与si相对应,则根相对应,则根据反馈函数得到一个关于据反馈函数得到一个关于x的多的多项式:项式:n ng(x)=gnxn+gn-1xn-1+g1x1+g0n n称称g(x)为线性移位寄存器的连接为线性移位寄存器的连接多项式多项式第47页,此课件共59页哦例题:n n一个上GF(2)的5阶移位寄存器,其反馈多项式为f(x)=1+x+x4,初始状态为s0=(10110),则其状态序列与输出序列是什么?第48页,此课件共59页哦由反馈多项式可以表示出连接多项式g(x)=1+x+x4+x5 ,由反馈多项式可知g0=g1=g4=1,则反馈可表示为f(x)=s0 s1 s4,如图:s0s1s2s3s4g1=1g0=1g4=1g5-=1第49页,此课件共59页哦状态状态 10110 01101 11010 10100 01001 10010输出输出 1 0 0 1 0 1状态状态 00101 01011 10110 01101输出输出 1 0 1 0该线性反馈寄存器的状态序列和输出序列的周期该线性反馈寄存器的状态序列和输出序列的周期为为8输出序列为输出序列为10010110第50页,此课件共59页哦n nN级线性移位寄存器最多有级线性移位寄存器最多有2n个个不同的状态,若其初始状态为不同的状态,若其初始状态为0,其后状态恒为,其后状态恒为0.若初始状态不若初始状态不为为0,其后状态也不为,其后状态也不为0,因此,因此n级线性反馈寄存器的状态周期小级线性反馈寄存器的状态周期小于或等于于或等于2n-1,其输出序列的周期其输出序列的周期小于或等于小于或等于2n-1第51页,此课件共59页哦n n只要选择合适的连接多项式便只要选择合适的连接多项式便可使线性移位寄存器的状态周可使线性移位寄存器的状态周期达到期达到2n-1,此时的输出序列为此时的输出序列为m序列序列n nM序列的优点序列的优点1.1.具有良好的随机性具有良好的随机性2.2.0和和1出现的次数接近相等,都出现的次数接近相等,都为为2n-1第52页,此课件共59页哦RC4n nRC4序列密码是美国序列密码是美国RSA数据安数据安全公司在全公司在1987年设计的一种序列年设计的一种序列密码,直到密码,直到1994年有人破获,在年有人破获,在1997年该公司公布了年该公司公布了RC4的算法。的算法。n n该算法密钥该算法密钥40为,在为,在Interner网网上上32小时可破获小时可破获第53页,此课件共59页哦RC4n n它是一种基于非线性数据表的交它是一种基于非线性数据表的交换序列密码,它以一个足够大的换序列密码,它以一个足够大的数据表为基础,对表进行非线性数据表为基础,对表进行非线性变换,产生非线性的密钥序列变换,产生非线性的密钥序列第54页,此课件共59页哦n nRC4RC4使用使用使用使用256256个字节的个字节的个字节的个字节的S S表和两个指针表和两个指针表和两个指针表和两个指针(I I和和和和J J)n nS S表的值为表的值为表的值为表的值为S S0 0,S,S1 1,S,S255255是是是是0 0,1.2551.255的一的一的一的一个排列个排列个排列个排列n nI I、J J的处置为的处置为的处置为的处置为0 0n n我们把我们把我们把我们把RC4RC4算法看成一个有限的状态自动机,算法看成一个有限的状态自动机,算法看成一个有限的状态自动机,算法看成一个有限的状态自动机,把把把把S