密码学概论第2讲流密码

2.1流密码的基本概念2.2线性反馈移位寄存器2.3线性移位寄存器的一元多项式表示2.4m序列的伪随机性2.5m序列密码的破译2.6非线性序列第2章流密码2023/2/412.1流密码的基本概念流密码的基本思想y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。密钥流z=z0z1…，明文串x=x0x1x2…：2023/2/42E的选取二元加法流密码E可表示为yi=zixi。

2023/2/43流加密举例0110011111110010110101111001110100100001010110011111110010110101111001110100100001010110011111110100100010110101111011010111110100100001100111112023/2/442.1.3密钥流产生器状态转移函数φ:σi→σi+1输出函数ψ:σi→zi，目前最为流行和实用的密钥流产生器是线性反馈移位寄存器。密钥流由密钥流发生器f产生：zi=f(k,σi)，σi是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和σi产生的函数。2023/2/452.2线性反馈移位寄存器2023/2/46反馈移位寄存器状态：每一时刻的状态对应于GF(2)上的一个n维向量(a1,a2,…,an)，ai是第i级存储器的内容。共有2n种可能的状态。工作原理：当第i个移位时钟脉冲到来时，根据寄存器此时的状态计算f(a1,a2,…,an)，作为an+1,每一级存储器ai都将其内容向下一级ai-1传递，（计算、移位、反馈、输出）反馈函数f(a1,a2,…,an)：n元布尔函数，即n个变元a1,a2,…,an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算。2023/2/47线性反馈移位寄存器LFSR线性反馈移位寄存器LFSR（linearfeedbackshiftregister）:反馈函数f(a1,a2,…,an)是线性函数.f(a1,a2,…,an)=cna1cn-1a2…c1an其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，GF(2)上的n级线性反馈移位寄存器输出序列an+1线性反馈移位寄存器实现简单、速度快、理论成熟,是构造密钥流生成器的最重要的部件。2023/2/48例下图是一个5级线性反馈移位寄存器，其初始状态为（a5，a4，a3，a2，a1）=(1,1,0,0,1)输出序列为满足递推关系ak+5=ak+3+ak1001101001000010101110110001111100110…(a5,a4,a3,a2,a1)输出010111110011001011011000100100101100010011反馈函数f(a1,a2,a3,a4,a5)=a4+a1周期312023/2/49LFSR反馈函数f(a1,a2,a3,a4,a5)=C2a4+C5a1

定义LFSR特征多项式（连接多项式）P(x)=1+x2＋x5C5=1C2=12023/2/4102.3线性移位寄存器的特征多项式与序列周期n级线性移位寄存器的输出序列满足递推关系an+k=c1an+k-1c2an+k-2…cnak

用一个一元高次多项式表示P(x)=1+c1x+…＋cn-1xn-1＋cnxn称这个多项式为LFSR的特征多项式（连接多项式）2023/2/411序列周期序列周期使对所有k，ak+r=ak成立的的最小整数r多项式的周期使f(x)除尽xp-1的最小整数p的取值。序列的周期r与特征多项式的周期p密切相关。(r/p)特征多项式是n次既约多项式周期为p，则生成序列的周期为p。输出序列最大周期为2n-1。不可约多项式最大周期达到2n-1。序列为m序列的充要条件特征多项式为本原多项式。本原多项式m序列2023/2/4122023/2/413特征多项式x3+x+1多项式周期7输出序列ak+3=ak+ak+210100111010…10100111010…序列周期

7 x3+x2+1 7

ak+3=ak+ak+1 1011100

1011…

7特征多项式x3+x2+x+1多项式周期4输出序列

ak+3=ak+ak+1+ak+210101010…序列周期

2 x3+1 3

ak+3=ak

101101…

3初始1012023/2/414m序列的伪随机性随机性:如果密钥流是周期的，要完全做到随机性是困难的。游程:设{ai}=(a1a2a3…)为0、1序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。自相关函数:R(τ)=(1/T)∑k=1T(-1)ak(-1)ak+τ,序列向后平移τ位，0≤τ≤T-1定义中的和式表示序列{ai}与{ai+τ}在一个周期内对应位相同的位数与对应位不同的位数之差。当τ=0时，R(τ)=1；当τ≠0时，称R(τ)为异相自相关函数。10100111010R(1)=R(2)=….=-1/72023/2/415①在序列一个周期内，0与1出现个数相差至多为1;（0和1出现概率基本相同）②长为l的游程占1/2l，在等长的游程中，“0”游程和“1”游程个数相等或至多差一个。（0和1在各位置上出现概率基本相同）③异相自相关函数是常数,与白噪声的自相关函数(函数)相近（序列平移不能提供更多信息）PN序列可用于通信中同步序列、码分多址(CDMA)、导航中多基站码、雷达测距码等。PN序列虽与白噪声序列相似，但远还不能满足密码体制要求。Golomb随机性假设－PN序列m序列满足Golomb的三条伪随机假设。101001110102023/2/416满足密码体制的另外三个条件①周期p要足够大，如大于1050；②序列{ai}产生易于高速生成；③当序列{ai}的任何部分暴露时，要分析整个序列，在计算上是不可行的

条件③决定了密码的强度，是流密码理论的核心。它包含了流密码要研究的许多主要问题，如线性复杂度、相关免疫性、不可预测性等等。2023/2/4172.4m序列的伪随机性m序列否满足密码要求？n级m序列的周期为2n－1，n大，周期指数地加大，例如n=166时，p=1050(9.353610465×1049)。只要知道n次本原多项式，m序列极易生成。m序列极不安全，只要泄露2n位连续数字，就可完全确定出反馈多项式系数。定理m序列满足Golomb的三条伪随机假设。2023/2/418由于X可逆序列递推关系:限制了其在密码学中的应用2.5m序列密码破译n级LFSR2023/2/419若X可逆序列递推关系:令限制了其在密码学中的应用2023/2/420因为X是由S1,S2,…,Sn作为列向量，要证X可逆，只要证明这n个向量线性无关。设m是使S1,S2,…,Sm线性相关的最小整数，即存在不全为0的系数l1,l2,…,lm，其中不妨设l1=1，使得证明X是可逆的2023/2/421设序列{ai}满足线性递推关系：Sh+1=M·Sh密钥流的级数m-1=n

故m=n+1S1,S2,…,Sn线性无关，由此构成的X可逆2023/2/422攻击实例：设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可用密钥流的前10个比特建立如下方程已知明文攻击2023/2/4232023/2/424非线性移位寄存器序列f(a1,a2,a3)=a1a2+a3输出序列10111011....，周期为4.对线性移位寄存器序列进行非线性组合非线性移位寄存器研究困难，对线性移位寄存器研究充分。2.6非线性序列2023/2/425密钥流生成器驱动子系统一个或多个LFSR来实现非线性组合子系统用非线性组合函数F来实现生成序列评价周期极大化线性复杂度最短LFSR级数极小特征多项式：最短LFSR的特征多项式非线性组合2023/2/4262.6.2J-K触发器令c-1=0驱动序列{ak}和{bk}分别为m级和n级m序列m、n互素a0+b0=1{Ck}周期p=(2m-1)(2n-1)

2023/2/427例令m=2,n=3，两个驱动m序列分别为{ak}=0,1,1,0,1,1…和{bk}=1,0,0,1,0,1,1,…输出序列{ck}其周期为(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,如果知道{ck}中相邻位的值ck-1和ck，就可以推断出ak和bk中的一个，通过密码分析的方法得到序列{ak}和{bk}。为了克服上述缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案2023/2/4282.6.3Pless生成器2023/2/4292.6.4钟控序列生成器钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲.易于由硬件实现。当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位。当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2,LFSR2状态不改变。2023/2/430前提：LFSR1和LFSR2输出序列分别是{ak}和{bk}对应极小特征多项式分别为GF(2)上的m和n次本原多项式f1(x)和f2(x)，且m|n结论：序列{ck}周期p=(2m-1)(2n-1)线性复杂度为n(2m-1)极小特征多项式为相关结论2023/2/431例设LFSR1为3级m序列生成器，其特征多项式为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，则变化为:{ck}的周期为(23-1)2=49ak+3=ak+ak+2bk+3=bk+bk+1{ck}=1,1,1,0,0,0,0,0, 1,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,….2023/2/432序号状态输出0111110111200113100031000401004010040100{ck}=1,1,1,0,0,0,0,0,bk+3bk+1bkck{bk}=1,1,1,0,0,1,0，…。2023/2/433{ck}的周期（23-1）*（23-1）=49极小特征多项式为1+x14+x21线性复杂度为3·（23-1）=21线性等价生成器如下图f2(x)=1+x2+x3周期p=(2m-1)(2n-1)线性复杂度为n(2m-1)极小特征多项式2023/2/434有限状态自动机具有离散输入和输出的一种数学模型由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，而状态转移为sh。2023/2/435例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)12023/2/436同步流密码的密钥流产生器可看成一个有限状态自动机。由一个输出符号集Z、一个状态集∑、两个函数φ和ψ以及一个初始状态σ0组成。2023/2/437蓝牙是一种用于替代某些电子设备上使用电缆或连线的短距离无线连接技术。具有同样蓝牙接口的设备连接可以实现无线连接，有效连接距离达10米，一般的传输速度都有1M目前配置蓝牙接口的电子设备却不是很多；没有蓝牙接口的电脑可通过加装蓝牙适配器来实现无线连接，适配器一般都是USB接口，可以插在电脑上，使用方便。采用无线电波为载体，安全性差，信息传输需加密加密算法使用流密码.流密码的应用——蓝牙Bluetooth2023/2/438蓝牙流加密原理2023/2/4394个LFSR比特长度分别为25，31，33，39；长度之和是128bit特征多项式都是本原多项式设xti为LSFRi的第t个符号2023/2/440IEEE802.11是当今无线局域网WLAN通用的标准，IEEE802.11安全框架中包括站点接入认证方法、数据