密码学概论第2讲流密码

1、2022-3-1912.1 流密码的基本概念流密码的基本概念2.2 线性反馈移位寄存器线性反馈移位寄存器2.3 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示2.4 m序列的伪随机性序列的伪随机性2.5 m序列密码的破译序列密码的破译2.6 非线性序列非线性序列 第2章 流密码2022-3-1922.1 流密码的基本概念流密码的基本思想流密码的基本思想y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)。密钥流密钥流z=z0z1，明文串明文串x=x0 x1x2：2022-3-193E E的选取的选取n二元加法流密码二元加法流密码nE可表示为可表示为yi=zi xi。 20

2、22-3-194流加密举例流加密举例0110011111110010110101111001110100100001010110011111110010110101111001110100100001010110011111110100100010110101111011010111110100100001100111112022-3-1952.1.3 密钥流产生器状态转移函数状态转移函数:ii+1输出函数输出函数:izi，目前最为流行和实用的密钥流产生器是线性反馈移位寄存器。目前最为流行和实用的密钥流产生器是线性反馈移位寄存器。密钥流由密钥流发生器密钥流由密钥流发生器f产生：产生：zi=f(

3、k,i)，i是加密器中的记忆元件（是加密器中的记忆元件（存储器存储器）在时刻）在时刻i的状态，的状态，f是由密钥是由密钥k和和i产生的函数。产生的函数。2022-3-1962.2线性反馈移位寄存器线性反馈移位寄存器2022-3-197反馈移位寄存器状态：状态：每一时刻的状态对应于每一时刻的状态对应于GF(2)上的一个上的一个n维向量维向量(a1,a2,an) ，ai是第是第i级存储器的内容。共有级存储器的内容。共有2n种可能的状态。种可能的状态。工作原理：工作原理：当第当第i个移位时钟脉冲到来时，根据寄存器此时的状态计算个移位时钟脉冲到来时，根据寄存器此时的状态计算f(a1,a2,an)，作为

4、作为an+1,每一级存储器每一级存储器ai都将其内容向下一级都将其内容向下一级ai-1传递，传递，（计算、移位、反馈、输出（计算、移位、反馈、输出 ）反馈函数反馈函数f(a1,a2,an)：n元布尔函数，即元布尔函数，即n个变元个变元a1,a2,an可以独立地取可以独立地取0和和1这两个可能的值，函数中的运算有逻辑与、这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算。逻辑或、逻辑补等运算。2022-3-198线性反馈移位寄存器线性反馈移位寄存器LFSR线性反馈移位寄存器线性反馈移位寄存器LFSR（linear feedback shift register）:反馈函数反馈函数f(a1

5、,a2,an)是线性函数是线性函数. f(a1,a2,an)=cna1cn-1a2c1an其中常数其中常数ci=0或或1，是模是模2加法。加法。ci=0或或1可用开关的断开和闭合来实现，可用开关的断开和闭合来实现，GF(2)上的上的n级线性反馈移位寄存器级线性反馈移位寄存器输出序列输出序列an+1线性反馈移位寄存器线性反馈移位寄存器实现简单、速度快、实现简单、速度快、理论成熟理论成熟, 是构造密是构造密钥流生成器的最重要钥流生成器的最重要的部件。的部件。例下图是一个例下图是一个5级线性反馈移位寄存器，其初始状态为级线性反馈移位寄存器，其初始状态为（a5，a4，a3， a2， a1 ）=(1,1

6、, 0,0,1)输出序列为满足递推关系输出序列为满足递推关系ak+5=ak+3+ ak1001101001000010101110110001111100110(a5,a4,a3,a2,a1)输出0 1 0 1 111 1 0 0 110 0 1 0 110 1 1 0 001 0 0 1 001 0 1 1 000 1 0 0 11反馈函数反馈函数f(a1,a2,a3,a4,a5)=a4 + a1周期31LFSR反馈函数反馈函数f(a1,a2,a3,a4,a5)=C2a4+ C5a1 定义定义LFSR特征多项式（连接多项式）特征多项式（连接多项式）P(x)=1+x2x5C5=1C2=1202

7、2-3-19112.3线性移位寄存器的特征多项式与序列周线性移位寄存器的特征多项式与序列周期期n级线性移位寄存器的输出序列满足级线性移位寄存器的输出序列满足递推关系递推关系an+k=c1an+k-1 c2an+k-2 cnak 用用一个一元高次多项式表示一个一元高次多项式表示P(x)=1+c1x+cn-1xn-1cnxn称这个多项式为称这个多项式为LFSR的的特征多项式特征多项式（连接多连接多项式项式）2022-3-1912序列周期序列周期n序列周期序列周期 使对所有使对所有k，ak+r=ak 成立的的最小整数成立的的最小整数rn多项式的周期多项式的周期使使f(x)除尽除尽xp-1的最小整数的

8、最小整数p的取值。的取值。n序列的周期序列的周期r与特征多项式的周期与特征多项式的周期p密切相关。密切相关。(r/p)n特征特征多项式是多项式是n次既约多项式周期为次既约多项式周期为p ，则生成序列的，则生成序列的周期为周期为p。n输出序列最大周期为输出序列最大周期为2n-1。n不可约多项式最大周期达到不可约多项式最大周期达到2n-1。序列为序列为m序列序列的充要条件特征多项式为的充要条件特征多项式为本原多项式。本原多项式。本原多项式本原多项式m序列序列a3a2a1+a3a2a1+a3a2a1+a3a2a1特征多项式特征多项式 x3+x+1多项式多项式周期周期 7输出序列输出序列 ak+3=a

9、k+ak+21 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 序列序列周期周期 7x3+x2+1 7ak+3=ak+ak+11 0 1 1 1 0 0 1 0 1 1 7特征多项式特征多项式 x3+x2+x+1多项式多项式周期周期 4输出序列输出序列 ak+3=ak+ak+1+ak+21 0 1 0 1 0 1 0 序列周期序列周期 2x3+13ak+3=ak 1 0 1 1 0 1 3初始初始1012022-3-1915m序列的伪随机性随机性随机性:如果密钥流是周期的，要完全做到随机性是困难的。如果密钥流是周期的，要完全做到随机性是困难的。游程游程:设设

10、ai=(a1a2a3)为为0、1序列，例如序列，例如00110111，其前两个数字是其前两个数字是00，称为，称为0的的2游程；接着是游程；接着是11，是，是1的的2游游程；再下来是程；再下来是0的的1游程和游程和1的的3游程。游程。自相关函数自相关函数:R()=(1/T)k=1T (-1)ak(-1)ak+, 序列向后平序列向后平移移位，位，0T-1定义中的和式表示序列定义中的和式表示序列ai与与ai+在一在一个周期内对应位相同的位数与对应位不同的位数之差。当个周期内对应位相同的位数与对应位不同的位数之差。当=0时，时，R()=1；当当0时，称时，称R()为异相自相关函数。为异相自相关函数。

11、1 0 1 0 0 1 1 1 0 1 0R(1)=R(2)=.=-1/72022-3-1916在序列一个周期内，在序列一个周期内，0与与1出现出现个数相差至多为个数相差至多为1 1; （0和和1出现概率基本相同）出现概率基本相同）长为长为l l的的游程游程占占1/21/2l l，在等长的游程中，在等长的游程中，“0 0”游游程程和和“1 1”游程游程个数相等或至多差一个。个数相等或至多差一个。（0 0和和1 1在各位置上出现概率基本相同）在各位置上出现概率基本相同）异相自相关函数是常数异相自相关函数是常数, ,与白噪声的自相关函数与白噪声的自相关函数( ( 函数函数) )相近相近（序列平移不

12、能提供更多信息）（序列平移不能提供更多信息）PNPN序列可用于通信中同步序列、码分多址序列可用于通信中同步序列、码分多址( (CDMA)CDMA)、导航中多基站码、雷达测距码等。导航中多基站码、雷达测距码等。PNPN序列虽与序列虽与白噪白噪声序列相似声序列相似，但远还不能满足密码体制要求。，但远还不能满足密码体制要求。Golomb随机性假设随机性假设PN序列序列m序列满足序列满足Golomb的三的三条伪随机假设条伪随机假设。 1 0 1 02022-3-1917满足密码体制的另外三个条件满足密码体制的另外三个条件周期周期p p要足够大，如大于要足够大，如大于10105050；序列序列 a ai

13、 i 产生易于高速生成；产生易于高速生成；当序列当序列 a ai i 的任何部分暴露时，要分析整个的任何部分暴露时，要分析整个序列，在计算上是不可行的序列，在计算上是不可行的 条件条件决定了密码的强度，是流密码理论的核心。它包决定了密码的强度，是流密码理论的核心。它包含了流密码要研究的许多主要问题，如线性复杂度、含了流密码要研究的许多主要问题，如线性复杂度、相关免疫性、不可预测性等等相关免疫性、不可预测性等等。2022-3-19182.4 m序列的伪随机性序列的伪随机性m序列否满足密码要求？序列否满足密码要求？nn级级m序列的周期为序列的周期为2n1，n大，周期指数地加大，大，周期指数地加大，

14、例如例如n=166时，时，p=1050(9.353610465 1049)。n只要知道只要知道n次本原多项式，次本原多项式，m序列极易生成。序列极易生成。m序列极不安全，只要泄露序列极不安全，只要泄露连续数字，就可完连续数字，就可完全确定出反馈多项式系数。全确定出反馈多项式系数。定理定理 m序列满足序列满足Golomb的三条伪随机假设的三条伪随机假设。2022-3-1919122311221112111nnnnnnnnnnnnaaaaaaaaacccaaacccX111122nnnnncccaaaX由于X可逆序列递推关系序列递推关系:限制了其在密码学中的应用限制了其在密码学中的应用2.5 m序

15、列密码破译序列密码破译n级级LFSR2022-3-1920122311221112111nnnnnnnnnnnnaaaaaaaaacccaaacccX12nXSSS111122nnnnncccaaaX1122h nh nh nnhac ac ac a 若X可逆序列递推关系序列递推关系:令令限制了其在密码学中的应用限制了其在密码学中的应用因为因为X是由是由S1,S2,Sn作为列向量，要证作为列向量，要证X可逆，可逆，只要证明这只要证明这n个向量线性无关。个向量线性无关。设设m是使是使S1,S2,Sm线性相关的最小整数，即线性相关的最小整数，即存在不全为存在不全为0的系数的系数l1,l2,lm，其

16、中不妨设其中不妨设l1=1，使得使得213210mmmmSl Sl Sl S11122111mmmmmjmjjSl SlSl SlS证明证明X是可逆的是可逆的设序列设序列ai满足线性递推关系：满足线性递推关系：12112110 1 000 0 10hhhhnnnh nh naaaaccccaa Sh+1=MSh122111221112211imimimmiimimmmmimiimSlSlSlSMlSMlSMlSlSlSlMSMS密钥流的级数密钥流的级数m-1=n 故故m=n+1S1,S2,Sn线性无关，由此构成的线性无关，由此构成的X可逆可逆攻击实例：攻击实例：设敌手得到密文串设敌手得到密文串

17、101101011110010和相应的明文和相应的明文串串011001111111001，因此可计算出相应的密钥流，因此可计算出相应的密钥流为为110100100001011。进一步假定敌手还知道密钥。进一步假定敌手还知道密钥流是使用流是使用5级线性反馈移位寄存器产生的，那么敌手可级线性反馈移位寄存器产生的，那么敌手可用密钥流的前用密钥流的前个比特建立如下方程个比特建立如下方程543211 1 0 1 01 0 1 0 00 1 0 0 00 1 0 0 11 0 0 1 00 0 1 0 0ccccc123452345667891054321345674567856789aaaaaaaaaa

18、aaaaacccccaaaaaaaaaaaaaaa11 1 0 1 00 1 0 0 11 0 1 0 01 0 0 1 00 1 0 0 10 0 0 0 11 0 0 1 00 1 0 1 10 0 1 0 01 0 1 1 0已知明文攻击已知明文攻击543210 1 0 0 11 0 0 1 00 1 0 0 00 0 0 0 10 1 0 1 11 0 1 1 0ccccc543211 0 0 1 0ccccc33255kkkkkaaacaca2022-3-1925n非线性移位寄存器序列nf(a1,a2,a3)=a1a2+a3n输出序列10111011.，周期为4.n对线性移位寄存器序

19、列进行非线性组合n非线性移位寄存器研究困难，n对线性移位寄存器研究充分。2.6 非线性序列2022-3-1926密钥流生成器密钥流生成器驱动子系统驱动子系统p一个或多个一个或多个LFSR来实现来实现非线性组合子系统非线性组合子系统p用非线性组合函数用非线性组合函数F来实现来实现生成序列评价生成序列评价周期极大化周期极大化线性复杂度线性复杂度p最短最短LFSR级数级数极小特征多项式：最短极小特征多项式：最短LFSR的特征多项式的特征多项式非线性组合2022-3-19272.6.2 J-K触发器111kkkkkkkkkcabcaabca001110122211012111cacabaacababa

20、aa令令c-1=0驱动序列驱动序列ak和和bk分别为分别为m级和级和n级级m序列序列m、n互素互素a0+b0=1Ck周期周期p = (2m-1)(2n-1) 2022-3-1928例例 令令m=2,n=3，两个驱动两个驱动m序列分别为序列分别为ak=0,1,1,0,1,1和和bk=1,0,0,1,0,1,1,输出序列输出序列ck111kkkkkkkkkcabcaabca其周期为其周期为(22-1)(23-1)=21。0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,11,0,1kkkkkaccbc如果知道如果知道ck中相邻位的值中相邻位的值ck-1和和ck，就

21、可以推就可以推断出断出ak和和bk中的一个，通过密码分析的方法得到中的一个，通过密码分析的方法得到序列序列ak和和bk。为了克服上述缺点，为了克服上述缺点，Pless提出了由多个提出了由多个J-K触发触发器序列驱动的多路复合序列方案器序列驱动的多路复合序列方案2022-3-19292.6.3 Pless生成器2022-3-19302.6.4 钟控序列生成器钟控序列最基本的模型是用一个钟控序列最基本的模型是用一个LFSR控制另外一个控制另外一个LFSR的移位时钟脉冲的移位时钟脉冲.易于由硬件实现。易于由硬件实现。当当LFSR1输出输出1时，移位时钟脉冲通过与门使时，移位时钟脉冲通过与门使LFSR

22、2进行一次移位。进行一次移位。当当LFSR1输出输出0时，移位时钟脉冲无法通过与门影响时，移位时钟脉冲无法通过与门影响LFSR2,LFSR2状态不改变。状态不改变。2022-3-1931前提：前提：LFSR1和和LFSR2输出序列分别是输出序列分别是ak和和bk 对应极小特征多项式分别为对应极小特征多项式分别为GF(2)上的上的m和和n次本原多项式次本原多项式f1(x)和和f2(x)，且且m|n结论：序列结论：序列ck周期周期p=(2m-1)(2n-1) 线性复杂度为线性复杂度为n(2m-1) 极小特征多项式为极小特征多项式为212mfx相关结论相关结论例设例设LFSR1为为3级级m序列生成器

23、，其特征多项式为序列生成器，其特征多项式为f1(x)=1+x+x3。设初态为设初态为(1,1,1)，输出序列为输出序列为ak=1,1,1,0,1,0,0,。又设又设LFSR2为为3级级m序列生成器，其特征多项式为序列生成器，其特征多项式为f2(x)=1+x2+x3且初态为且初态为(1,1,1)则则bk=1,1,1,0,0,1,0，。LFSR2状态向量为状态向量为k，则变化为则变化为:012334445600111234455560112220122333456600ck的周期为的周期为(23-1)2=49ak+3=ak+ak+2bk+3=bk+bk+1ck=1,1,1,0,0,0,0,0, 1

24、,0,1,1,1,1,1, 1,0,0,0,1,1,1, 0,1,1,1,1,1,1, 0,0,1,1,0,0,0,.序号序号状态状态输出输出011111011120011310003100040100401004010001233444ck=1,1,1,0,0,0,0,0,bk+3bk+1bkckbk=1,1,1,0,0,1,0，。2022-3-1934ck的周期（的周期（23-1）* （23-1）=49极小特征多项式为极小特征多项式为1+x14+x21线性复杂度为线性复杂度为3（23-1）=21线性等价生成器如下图线性等价生成器如下图212mfxf2(x)=1+x2+x3周期周期p=(2m

25、-1)(2n-1) 线性复杂度为线性复杂度为n(2m-1)极小特征多项式极小特征多项式2022-3-1935有限状态自动机有限状态自动机具有离散输入和输出的一种数学模型具有离散输入和输出的一种数学模型由由3部分组成：部分组成： 有限状态集有限状态集S=si|i=1,2,l。 有限输入字符集有限输入字符集A1=A(1)j|j=1,2,m和和有限输出字符集有限输出字符集A2=A(2)k|k=1,2,n。 输出函数输出函数A(2)k=f1(si,A(1)j)，转移函数转移函数sh=f2(si,A(1)j)即在状态为即在状态为si，输入为输入为A(1)j时，时，输出为输出为A(2)k，而状态转移为而状

26、态转移为sh。2022-3-1936例例S=s1,s2,s3，A1=A(1)1,A(1)2,A(1)3，A2=A(2)1,A(2)2,A(2)3，转移函数由表转移函数由表2.1给出。给出。输入序列为输入序列为A(1)1A(1)2A(1)1A(1)3A(1)3A(1)1，初始状态为初始状态为s1，则得到状态序列则得到状态序列s1s2s2s3s2s1s2输出字符序列输出字符序列A(2)1A(2)1A(2)2A(2)1A(2)3A(2)12022-3-1937同步流密码的同步流密码的密钥流产生器密钥流产生器可看成一个可看成一个有限状态自动机有限状态自动机。由一个输出符号集由一个输出符号集Z、一个状态

27、集一个状态集、两、两个函数个函数和和以及一个初始状态以及一个初始状态0组成。组成。2022-3-1938n蓝牙是一种用于替代某些电子设备上使用电缆或连线的蓝牙是一种用于替代某些电子设备上使用电缆或连线的短距离无线连接技术。短距离无线连接技术。n具有同样蓝牙接口的设备连接可以实现无线连接，有效具有同样蓝牙接口的设备连接可以实现无线连接，有效连接距离达连接距离达10米，一般的传输速度都有米，一般的传输速度都有1Mn目前配置蓝牙接口的电子设备却不是很多；没有蓝牙接目前配置蓝牙接口的电子设备却不是很多；没有蓝牙接口的电脑可通过加装蓝牙适配器来实现无线连接，适配口的电脑可通过加装蓝牙适配器来实现无线连接

28、，适配器一般都是器一般都是USB接口，可以插在电脑上，使用方便。接口，可以插在电脑上，使用方便。n采用无线电波为载体，安全性差，信息传输需加密采用无线电波为载体，安全性差，信息传输需加密n加密算法使用流密码加密算法使用流密码.流密码的应用流密码的应用蓝牙蓝牙Bluetooth2022-3-1939蓝牙流加密原理蓝牙流加密原理2022-3-19404个个LFSR比特长度分别为比特长度分别为25，31，33，39；长度之和是；长度之和是128bit特征多项式都是本原多项式特征多项式都是本原多项式设xti 为LSFRi的第t个符号2022-3-1941nIEEE 802.11是当今无线局域网WLAN通用的标准，IEEE 802.11安全框架中包括