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