第第4章章对称密钥密码体制对称密钥密码体制流密码流密码1流密码的特点流密码的特点 软件实现简单软件实现简单便于硬件实现便于硬件实现加解密处理速度快加解密处理速度快没有或只有有限的错误传播等特点没有或只有有限的错误传播等特点2流密码流密码一段待加密的消息明文被分成连续的符号一段待加密的消息明文被分成连续的符号，加密通过密钥流，加密通过密钥流以以的方式进行。的方式进行。其中其中是密钥流中的第是密钥流中的第i个元个元素素对消息明文中的第对消息明文中的第i个元素个元素进行加密所得进行加密所得的密文。的密文。3流密码的时变性流密码的时变性时变性：随时间而变化。时变性：随时间而变化。流密码内部状态随时间变化，通过加密器和解流密码内部状态随时间变化，通过加密器和解密器中的记忆元件得以保证；密器中的记忆元件得以保证；密钥流中的元素的产生由密钥流中的元素的产生由i时刻的流密码内部时刻的流密码内部状态（记作状态（记作）和种子密钥（记作）和种子密钥（记作k）决定）决定，即即；加密变换加密变换与解密变换与解密变换也和也和i时刻的流密时刻的流密码内部状态有关。码内部状态有关。4流密码分类流密码分类用状态转移函数用状态转移函数描述流密码加密器中存储器的状态描述流密码加密器中存储器的状态随时间变化的过程。随时间变化的过程。同步流密码同步流密码：如果某个流密码中的状态转移函数：如果某个流密码中的状态转移函数,不依赖被输入加密器存储器的明文；不依赖被输入加密器存储器的明文；自同步流密码自同步流密码：状态转移函数：状态转移函数与输入明文有关。与输入明文有关。5同步流密码同步流密码6同步流密码的表示同步流密码的表示同同步步流流密密码码为为一一个个六六元元组组（P,C,K,L,E,D）和和函函数数g,并并且满足以下条件：且满足以下条件：1P是由所有可能明文构成的有限集是由所有可能明文构成的有限集2C是由所有可能密文构成的有限集是由所有可能密文构成的有限集3K是由所有可能密钥构成的有限集是由所有可能密钥构成的有限集4L是一个称为密钥流字母表的有限集是一个称为密钥流字母表的有限集5g是是一一个个密密钥钥流流生生成成器器。g使使用用密密钥钥k作作为为输输入入，产产生无限的密钥流生无限的密钥流。6对对于于任任意意的的，都都有有一一个个加加密密规规则则和和相相应应的的解解密密规规则则 。并并且且对对每每一一个个明明文文和和是是满满足足 的函数的函数。7同步流密码的加密过程同步流密码的加密过程 其中，其中， 取决于密钥取决于密钥k的初始态，的初始态，f是下一是下一个态函数，个态函数，g是生成密钥流的函数。是生成密钥流的函数。8同步流密码的特点同步流密码的特点 同步要求同步要求在一个同步流密在一个同步流密码中，中，发送方和接送方和接收收方必方必须是同步的，用同是同步的，用同样的密的密钥且且该密密钥操作在同操作在同样的位置（的位置（态），才能保），才能保证正确地解密。正确地解密。 无错误传播无错误传播在在传输期期间，一个密文字符（或位）被改，一个密文字符（或位）被改变（不是（不是删除）只影响除）只影响该字符（或位）的恢复，字符（或位）的恢复，不会不会对后后续字符（或位）字符（或位）产生影响。生影响。 9同步流密码同步流密码两种基本工作方式：两种基本工作方式：输出输出-分组反馈模式（简称分组反馈模式（简称OFM）；）；计数模式。计数模式。10输出输出-分组反馈模式工作原理分组反馈模式工作原理11计数模式工作原理计数模式工作原理12自同步流密码的加密过程自同步流密码的加密过程其中，其中， 是非秘密是非秘密的初始态，的初始态，k是密钥，是密钥，g是生成密钥流的函数。是生成密钥流的函数。 13密码反馈模式工作原理密码反馈模式工作原理14密钥流生成器密钥流生成器两部分功能：两部分功能：驱动部分：负责控制存储器的状态并提供周期长、驱动部分：负责控制存储器的状态并提供周期长、统计特性好的序列供非线性组合部分使用；统计特性好的序列供非线性组合部分使用；非线性组合部分：对这些序列进行非线性组合，以非线性组合部分：对这些序列进行非线性组合，以便得到理想的密钥流便得到理想的密钥流。15反馈移位寄存器反馈移位寄存器两部分组成两部分组成：移位寄存器：移位寄存器是一个位序列（长度为移位寄存器：移位寄存器是一个位序列（长度为n的移位寄存器被称为的移位寄存器被称为n位移位寄存器），新的最左位移位寄存器），新的最左端的位由其余各位计算得到，通过所有各位右移一端的位由其余各位计算得到，通过所有各位右移一位输出的结果通常为最低有效位；位输出的结果通常为最低有效位；反馈函数。反馈函数。最简单的反馈移位寄存器最简单的反馈移位寄存器：线性反馈移位寄存器：线性反馈移位寄存器（LFSR）。）。16上上n级线性反馈移位寄存器的一般级线性反馈移位寄存器的一般结构结构17反馈函数反馈函数若若 ，则该，则该LFSRLFSR生成的序列为周期序列生成的序列为周期序列。 181.LFSR的联结多项式的联结多项式其中，其中， 表示未定元表示未定元。2.LFSR的特征多项式的特征多项式其中，其中，为为的互反多项式。的互反多项式。19LFSR的周期的周期对于对于上的半无限序列上的半无限序列，若，若存在正整数存在正整数T和非正整数和非正整数满足：对于所有的满足：对于所有的，均成立，均成立，则称该序列为终归周期序列，则称该序列为终归周期序列，称称T为该序列的一个周期，称所有可能周期中的为该序列的一个周期，称所有可能周期中的最小值为该序列的最小周期（记为最小值为该序列的最小周期（记为）。若）。若，则称该序列为周期序列。若，则称该序列为周期序列。若为为的最的最小终归周期，则称满足小终归周期，则称满足对所有对所有成成立的最小立的最小为预周期。为预周期。我们称我们称上周期为上周期为的的n级级LFSR序列序列a为为n级级最大最大LFSR序列（又称最长序列（又称最长LFSR序列），简称序列），简称m序列序列。20针对针对LFSR考虑的主要问题考虑的主要问题问题一：怎样利用级数尽可能小的问题一：怎样利用级数尽可能小的LFSR来生成周期长、来生成周期长、统计特性好的序列？统计特性好的序列？问题二：如何在已知一个序列的情况下，构造能够生问题二：如何在已知一个序列的情况下，构造能够生成该序列的级数尽可能小的成该序列的级数尽可能小的LFSR？21