第二章流密码:22线性反馈移位寄存器 222线性反馈移位寄存器的结构与表示 ●状态转换规则 ●根据FSR的工作原理,当第移位时钟脉冲到来时 a1被移出,作为输出序列在第时刻的输出bit 其它每一级存储器都将其内容向下一级1传递 同时,根据时钟脉冲到来前寄存器的状态a1;a2,,an计 算出的anf(a1,a2,)移入最左边的寄存器 反馈函数(a1a2x…,an)是n元布尔函数 函数中的运算有逻辑与、逻辑或、逻辑补、或其它运算 最后的函数值为0或1。 输出序列 alan 可能是线性或非线性布尔函数 f 历忠毛孑技*字
2.2.2 线性反馈移位寄存器的结构与表示 状态转换规则 ⚫ 根据FSR的工作原理，当第i个移位时钟脉冲到来时 ⚫ a1被移出，作为输出序列在第i时刻的输出bit ⚫ 其它每一级存储器ai都将其内容向下一级ai-1传递 ⚫ 同时，根据时钟脉冲到来前寄存器的状态a1 ,a2 ,…,an计 算出的an =f(a1 ,a2 ,…,an )也移入最左边的寄存器 反馈函数f(a1 ,a2 ,…,an )是n元布尔函数 ⚫ 函数中的运算有逻辑与、逻辑或、逻辑补、或其它运算 ⚫ 最后的函数值为0或1。 ⚫ 可能是线性或非线性布尔函数 17/ 第二章 流密码：2.2 线性反馈移位寄存器 an an-1 ... a1 f(a1,a2,…,an) a2 输出序列
第二章流密码:22线性反馈移位寄存器 222线性反馈移位寄存器的结构与表示 ●例:下图是一个3级反馈移位寄存器,其初始状态为 (a1,a2,a3)=(1,0,1),输出可由表22求出 输出序列 03 a1 在一个一般n-FSR 的状态图中,至少 f(a1,a2, a3)=a1a2ea3 含有一个圈,且从 任意状态出发进动 该3级反馈移位寄存器的状态和输出如下若干拍后必定进入 状态(a32)输出 到的输出序列虽不 10 111 101 必是周期序列,但 去掉其前若千项后 即得到周期序列, 011 也就是说这样的序 列为终归周期序列 110 即输出序列为101110111011.,周期为4 历毛孑拌技大字 18
2.2.2 线性反馈移位寄存器的结构与表示 例：下图是一个3级反馈移位寄存器，其初始状态为 (a1 ,a2 ,a3 )=(1,0,1)，输出可由表2.2求出 18/ 第二章 流密码：2.2 线性反馈移位寄存器 a3 a2 a1 f(a1,a2,a3)＝a1a2a3 输出序列 该3级反馈移位寄存器的状态和输出如下 状态（a3 ,a2 ,a1 ) 输出 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 即输出序列为101110111011…，周期为4 在一个一般n-FSR 的状态图中，至少 含有一个圈，且从 任意状态出发进动 若干拍后必定进入 某一个圈！这时得 到的输出序列虽不 必是周期序列，但 去掉其前若干项后 即得到周期序列， 也就是说这样的序 列为终归周期序列
第二章流密码:22线性反馈移位寄存器 222线性反馈移位寄存器的结构与表示 ●线性反馈移位寄春器LFSR 如果反馈函数f(a1a2y,an)是a1,a2,…,n的线性函数线性布尔函数) 则称之为线性反馈移位寄存器( Linear feedback shift register., LFSR),此时间写为 f(a1,al2y…,un)= Cna,ec12④..C1n 二元情况下(GF(2),常数c=0或1,刚好可用开关的断开和闭合来 实现 根据反馈函数输出序列{a4}满足如下递推式 an= Crec11+,,AC1n+H1,其中伪非负正整数。 输出序列 Cr 毛拌技大字 19
2.2.2 线性反馈移位寄存器的结构与表示 线性反馈移位寄存器LFSR ⚫ 如果反馈函数f(a1 ,a2 ,…,an )是a1 ,a2 ,…,an的线性函数(线性布尔函数) ，则称之为线性反馈移位寄存器(Linear Feedback Shift Register, LFSR)，此时f可写为 f(a1 ,a2 ,…,an )=cna1cn-1a2…c1an ⚫ 二元情况下(GF(2))，常数ci=0或1，刚好可用开关的断开和闭合来 实现 根据反馈函数输出序列{at }满足如下递推式 ⚫ an+t = cnatcn-1at＋1…c1an＋t-1，其中t为非负正整数。 19/ 第二章 流密码：2.2 线性反馈移位寄存器 an an-1 ... a2 a1 输出序列 + c1 + c2 + cn-1 cn
第二章流密码:22线性反馈移位寄存器 222线性反馈移位寄存器的结构与表示 例23下图是一个5级线性反馈移位寄存器,其初始状态 为(a1,a2,a3ya4l3)=(1,0,0,1,1),可求出输出序列为 1001101001000010101110110001111100110 ●周期为31。 输出序列 4 ●线性反馈移位诗存器因其实现筒单、速度快、有较为成熟 的理论等优点面成为构造密钥流生成器的最重要的部件之 历忠毛孑技*字 20/
2.2.2 线性反馈移位寄存器的结构与表示 [例2-3]下图是一个5级线性反馈移位寄存器，其初始状态 为（a1 ,a2 ,a3 ,a4 ,a5）=(1,0,0,1,1)，可求出输出序列为 1001101001000010101110110001111100110… 周期为31。 线性反馈移位寄存器因其实现简单、速度快、有较为成熟 的理论等优点而成为构造密钥流生成器的最重要的部件之 一 20/ 第二章 流密码：2.2 线性反馈移位寄存器 a5 a4 a2 a1 输出序列 + a3
第二章流密码:22线性反馈移位寄存器 222线性反馈移位寄存器的结构与表示 ●LFSR的相关性质 ≥(1)反馈系数 所有系数都为0,即c=c2==Cn=0,由于没有反馈,n个时钟脉冲 后,状态变为全0,并一直下去 若12…中只有一个系数不为0,设仅有不为0,实际上是一种 延迟装置。 若从c开始cnc+1,…,cn都等于0,则是一种退化的LFSR, ccH"…cn对应的移位寄存器相当于延迟装置,因此,我们讨论的 LFSR总是假定cn=1 按照递推式,LFSR输出序列的性质由其反馈函数和初始状态决定 ,而其生成序列周期的性质主要由反馈函数决定 历忠毛孑技*字
2.2.2 线性反馈移位寄存器的结构与表示 LFSR的相关性质 (1) 反馈系数 ⚫ 所有系数都为0，即c1=c2=…=cn=0，由于没有反馈，n个时钟脉冲 后，状态变为全0，并一直下去 ⚫ 若c1 ,c2 ,…,cn中只有一个系数不为0，设仅有cj不为0，实际上是一种 延迟装置。 ⚫ 若从cj开始cj ,cj+1 ,…,cn都等于0，则是一种退化的LFSR， cj ,cj+1 ,…,cn对应的移位寄存器相当于延迟装置，因此，我们讨论的 LFSR总是假定cn=1 ⚫ 按照递推式，LFSR输出序列的性质由其反馈函数和初始状态决定 ，而其生成序列周期的性质主要由反馈函数决定 21/ 第二章 流密码：2.2 线性反馈移位寄存器