线性反馈移位寄存器

我国在zuc序列密码算法
ZUC（祖冲之）序列密码算法是我国自主研发的一种序列密码算法，该算法主要用于数据的机密性和完整性保护，是实现网络空间安全的基础算法和核心技术。

ZUC算法已成为国际标准ISO/IEC 29189：2017，标志着我国在密码算法领域取得了重要突破。

ZUC算法主要由LFSR（线性反馈移位寄存器）、BR（比特重组）和F （非线性函数）三部分组成。

输入为128位长的密钥和128位长的初始化向量，输出为(n, n)，其中n为节拍数（轮数）。

在ZUC算法的实现过程中，首先进行初始化阶段，然后进行多轮迭代，每轮迭代包括以下步骤：
1. 线性反馈移位寄存器（LFSR）操作：根据初始化向量和密钥进行LFSR操作，生成新的状态。

2. 比特重组（BR）操作：将LFSR生成的状态进行比特重组，得到新的数据。

3. 非线性函数（F）操作：将BR操作得到的新数据作为输入，经过非线性函数F处理，生成输出。

4. 输出：经过一定的轮数迭代后，ZUC算法输出一系列32位长的字串，用于加密和解密数据。

ZUC算法在我国商用密码体系中具有重要地位，广泛应用于移动通信、物联网、安全认证等领域。

其成为国际标准，不仅提升了我国在全球密码算法领域的地位，也为全球网络安全提供了更为可靠的技术保障。

lsfr表达式
LSFR（线性反馈移位寄存器，Linear Feedback Shift Register）是一种常用的序列发生器，它可以生成具有较长周期的伪随机序列。

LSFR的工作原理是利用移位寄存器和反馈线性组合的方式生成下一个状态的值。

LSFR的表达式可以表示为：
Y = XOR(X1, X2, X3, ..., Xn),
其中Y表示当前状态的值，X1、X2、X3等表示移位寄存器的位（也称为“阶数”），XOR表示异或运算。

LSFR的输入主要包括初始状态和反馈多项式。

初始状态是移位寄存器最初的值，反馈多项式则决定了计算下一个状态的方式。

反馈多项式一般以二进制表示，其中1表示对应位参与异或运算，0表示对应位不参与异或运算。

通过不断更新LSFR的状态，可以生成一个周期较长的伪随机序列。

这个序列在某些应用中具有随机性，并被广泛应用于密码学、通信等领域。

1. 3级线性反馈移位寄存器在 C 3 = 1时可有4种线性反馈函数，设其初始状态为(a i , a 2, a 3)=(1,0,1)，求各线性反馈函数的输出序列及周期。

解：此时线性反馈函数可表示为 f (a 1, a 2, a 3)= a C 2a 2 C 1 a 3 当 C 1 = 0, C 2= 0 时， f (ai, a 2, a 3)= :a 1 C 2a 2 C £3= a 1,输出序列为 101101 …， 周期=3 当 C 1 = 0, C 2= 1 时， f (ai,a 2, a 3)= :a 1 C 2a 2 C 1 a 3= a 1 a 2,输出序列为 0……，周期=7当 C 1= 1, C 2= 0 时，f (ai,a 2, a 3)= :a 1 C 2a 2 oa 3= a 1 a 3,输出序列为 1……，周期=7当 C 1= 1, C 2= 1 时， f (ai,a 2, a 3)= :a 1 C 2a 2 C 1 a 3= a 1 82 a 3,有输出序列为 1010 …， 周期=22. 设n 级线性反馈移位寄存器的特征多项式为 p (x )，初始状态为(a i ,a 2,…,a n-i , a n )=(00…01)，证明输出序列的周期等于 p (x )的阶证：设p (x )的阶为p ,由定理2-3，由r | p ，所以r p设A (x )为序列｛a 。

的生成函数，并设序列｛a ｝的周期为r ,则显然有A (x )p (x ) = (x )又 A (x ) = a+a 2x +…+ax +x (a 1+a 2x +…+a 「x )+( x ) (a+a 2x +…+ax )+ …r-1rr -1 r=a 1+a 2x +…+a r x /(1- x ) = a+a 2x +…+a 「x /( x -1)于是 A (x )=( a+a 2x +…+a r X r-1)/( x r -1) = (x )/ p (x )又(a 1, a 2,…,a n-1, a n )=(00 …01) 所以 p (x )( a n x +•• •+ a r x)=(x )(x -1) 即 p (x )x (a n +…+ a 「x )= (x )( x -1)由于x n-1不能整除x r -1，所以必有x n-1| (x )，而(x )的次数小于n ,所以必有 (x )= x n-1所以必有p (x ) | (x r -1)，由p (x )的阶的定义知，阶 p r综上所述：p = r #3. 设 n = 4, f ( a, a 2, a 3, a 4)=a 1 a 4 1a 2a 3，初始状态为(a, a 2, a 3, a 4)= (1,1,0,1),求此非线性反馈移位寄存器的输出序列及周期。

线性反馈与对偶移位寄存器的功能实现091234 谢锦仪一、实验目的：该实验为验证性实验。

通过本实验，使学生切实理解线性反馈移位寄存器与对偶移位寄存器的工作原理，学会编写和运用两种移位寄存器“进动一拍”的程序，培养和锻炼学生对于密码学中各种基本“构造”的编程实现能力。

二、实验内容及完成情况：1. 分别写出实现n-LFSR与 n-DSR（n为正整数）进动一拍的程序（旨在能“由寄存器的一个状态算出紧接着的下一个状态”），要求：寄存器状态的各分量自然地与相应数据存储区的各比特位一一对应，不允许仅1个状态分量就占据1个存储单元（字节、字或双字等）。

2. 基于上述程序完成以下工作：选定一个8次联接多项式，这时检验状态存储区自然形成的1字节二进制数是否与前出现者相同就可判定状态是否开始成圈（即进入周期性重复），据此编制i) 分别计算LFSR与DSR在一个给定初态（由外部响应给出）下输出序列ii) 求出LFSR或DSR之一状态图的程序。

三、实验要求：1．对较低次数的联接多项式，程序计算结果须与手工推算一致；2．抓图显示“输出序列”与“状态图”（附页），不能出现明显错误。

四、结果：1、LFSR2、DSR五、实验体会：这次实验有很大的难度，尤其是对其中移位的操作难倒了不少人。

并且看了老师给的程序后理解不是很深，看了很长时间后才有所了解，后来经过复习以前的课程对LFSR和DSR 有了更深层次的理解之后终于明白了程序改如何编写了。

总的来说，这次实验不但是我对LFSR和DSR两种古典密码有了很好的理解，而且也是我对C语言编程中的位运算也熟悉了不少，相信在以后的工作中会给我带来很大的便利。

六、思考题：为什么“检验状态存储区自然形成的二进制数是否与前出现者相同就可判定状态是否开始成圈（即进入周期性重复）”？答：因为每个状态都有唯一的前一拍状态，对应的所有的状态应该是一一连接的（不一定都在一条线上）。

所以如果出现了2个一样的状态，那么后续的对应状态一定相同。

线性反馈移位寄存器LFSRverilog实现⼀、什么是LFSR？线性反馈移位寄存器（linear feedback shift register, LFSR）是指，给定前⼀状态的输出，将该输出的线性函数再⽤作输⼊的移位寄存器。

异或运算是最常见的单⽐特线性函数：对寄存器的某些位进⾏异或操作后作为输⼊，再对寄存器中的各⽐特进⾏整体移位（百度百科定义）。

线性反馈移位寄存器反馈分为两种，⼀种是IE型的LFSR，即异或门内接的线性反馈移位寄存器：另⼀种是异或门外接的线性反馈移位寄存器，简称EE型LFSR：gi表⽰接不接⼊反馈，只能为0或1，为1即为接⼊，为0不接⼊。

关于线性反馈移位寄存器（LFSR）数学原理更加详细的介绍，可以参考下⾯这篇⽂章。

本⽂主要是介绍如果使⽤verilog来实现LFSR电路的编写。

需要注意的是，LFSR是伪随机的，这意味着它只是接近随机，并不是完全随机的。

这是因为其实从LFSR的任何状态，你都可以预测下⼀个状态。

有⼀些重要的移位寄存器属性需要注意：LFSR是伪随机的，从LFSR的任何状态，都可以预测下⼀个状态。

影响下⼀个状态的⽐特位叫做抽头。

当抽头使⽤XOR门时，全0状态不会出现，这是因为0与0异或将始终产⽣0，此时LFSR将停⽌运⾏。

当抽头使⽤XNOR门时，全1状态不会出现，这是因为1与1同或（异或⾮）将始终产⽣1，此时LFSR将停⽌运⾏。

任何LFSR的最⼤可能迭代次数 = 2^N-1，N为级数，也就是寄存器bit位的个数。

那么怎样的LFSR才能遍历2^N-1个状态，产⽣最⼤的迭代次数呢？也就是到底寄存器的哪些位去组合然后反馈到输⼊端，才能使该LFSR的所有2^N-1个状态都出现呢？这⾥官⽅给了⼀个表，我们可以根据这个表来确定LFSR的结构：需要注意的是LFSR的每⼀位的索引是从1开始，然后到N，⼀共2^N-1个状态（因为使⽤异或反馈时要除去全0状态，使⽤异或⾮反馈时要除去全1状态）。

【常⽤电路】线性反馈移位寄存器（LFSR）读华为技术⽂档《FIFO经验谈》看到的这个电路： FIFO的读写地址产⽣⽐较简单，当读使能有效时，在时钟作⽤下，读地址加1；当写使能有效时，写地址加1。

当FIFO深度较⼤时，同时FIFO的速度要求较⾼时，可以采⽤线性反馈移位计数器（LFSR）。

它的速度⾮常快，但是要牺牲⼀个地址。

针对同步的⼤FIFO，它们的读写地址完全可以使⽤线性反馈移位寄存器 LFSR 产⽣，⽽不是简单的加1操作，极⼤的提⾼了速度，如果对FIFO的利⽤率没有很⾼要求的时候，推荐使⽤该⽅法。

使⽤LFSR的优点是在XILINX的FPGA中布线，可以使⽤LUT直接完成。

1/************************************************************\2* *3* Generation of Read and Write address pointers. They use *4* LFSR counters, which are very fast. Because of the *5* nature of LFSR, one address is sacrificed. *6* *7\************************************************************/8wire read_linearfeedback, write_linearfeedback;910assign read_linearfeedback = ! (read_addr[8] ^ read_addr[4]);11assign write_linearfeedback = ! (write_addr[8] ^ write_addr[4]);1213always @(posedge clock or posedge fifo_gsr)14if (fifo_gsr) read_addr <= 9'h0;15else if (read_allow)16 read_addr <= { read_addr[7], read_addr[6], read_addr[5],17 read_addr[4], read_addr[3], read_addr[2],18 read_addr[1], read_addr[0], read_linearfeedback };1920always @(posedge clock or posedge fifo_gsr)21if (fifo_gsr) write_addr <= 9'h022else if (write_allow)23 write_addr <= { write_addr[7], write_addr[6], write_addr[5],24 write_addr[4], write_addr[3], write_addr[2],25 write_addr[1], write_addr[0], write_linearfeedback };。

m 序列一、m 序列的产生1、最长线性反馈移位寄存器序列m 序列是最长线性反馈移位寄存器序列的简称，它是由带线性反馈的移位寄存器产生的周期最长的序列。

可以看到图1A 的输出的周期为15，除去全0外，图1A 的输出是周期最长的的序列。

我们希望尽可能少的级数产生尽可能长的序列。

一般说来，一个n 级反馈移存器可能产生的最长周期为12-n 。

反馈电路如何连接才能输出序列最长？是本节要讨论的问题。

2、m序列的特征方程移存器的结构用特征方程表示：∑==+++=ni i i nn x c x c x c c x f 010...)(3、m 序列的递推方程∑=-=ni ik i k a c a 14、m 序列的母函数∑∞==++++=010......)(k k k nn x a x a x a a x G5、几个有用的定理用来构造m 序列定理一、)()()(x h x G x f =，其中)(x h 为次数低于)(x f 的次数的多项式。

定理二、一n 级线性反馈移位寄存器的相继状态具有周期性，周期为12-≤n p 。

定理三、若序列}{k a A =具有最长周期12-=n p ，则其特征多项式)(x f 应为既约多项式。

定理四、一个线性移位寄存器的特征多项式)(x f 若为既约的，则由其产生的序列}{k a A =的周期等于使)(x f 能整除的)1(+p x 最小正整数p 。

6、本原多项式若一个n 次多项式满足如下条件：（1）、)(x f 是既约的（2）、)(x f 可整除m x +1，12-=n m（3）、)(x f 除不尽1+q x ，m q <则称)(x f 为本原多项式。

由本原多项式产生的序列一定是m 序列。

二、m 序列的性质1、均衡性在m 序列的一个周期中，“0”“1”的数目基本相等。

“1”比“0”多一个。

2、游程分布游程：序列中取值相同的那些相继的元素合称为一个“游程”。

游程长度：游程中元素的个数。

第二章作业参考答案1．3级线性反馈移位寄存器在c3＝1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。

解：此时线性反馈函数可表示为f(a1,a2,a3)=a1⊕c2a2⊕c1a3当c1＝0，c2＝0时，f(a1,a2,a3)=a1⊕c2a2⊕c1a3＝a1，输出序列为101101…，周期＝3当c1＝0，c2＝1时，f(a1,a2,a3)=a1⊕c2a2⊕c1a3＝a1⊕a2，输出序列为10111001011100…，周期＝7当c1＝1，c2＝0时，f(a1,a2,a3)=a1⊕c2a2⊕c1a3＝a1⊕a3，输出序列为10100111010011…，周期＝7当c1＝1，c2＝1时，f(a1,a2,a3)=a1⊕c2a2⊕c1a3＝a1⊕a2⊕a3，有输出序列为1010…，周期＝22．设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2, …,a n-1,a n)=(00…01)，证明输出序列的周期等于p(x)的阶证：设p(x)的阶为p，由定理2-3，由r|p，所以r≤p设A(x)为序列{a i}的生成函数，并设序列{a i}的周期为r，则显然有A(x)p(x)＝φ(x)又A(x)＝a1+a2x+…+a r x r-1+x r(a1+a2x+…+a r x r-1)+(x r)2(a1+a2x+…+a r x r-1)+…＝a1+a2x+…+a r x r-1/(1-x r)＝a1+a2x+…+a r x r-1/(x r-1)于是A(x)=(a1+a2x+…+a r x r-1)/(x r-1)＝φ(x)/p(x)又(a1,a2, …,a n-1,a n)=(00…01)所以p(x)(a n x n-1+…+a r x r-1)=φ(x)(x r-1) 即p(x)x n-1(a n+…+a r x r-n)=φ(x)(x r-1)由于x n-1不能整除x r-1，所以必有x n-1|φ(x)，而φ(x)的次数小于n，所以必有φ(x)＝x n-1所以必有p(x)|(x r-1)，由p(x)的阶的定义知，阶p≤r综上所述：p＝r#3．设n＝4，f(a1,a2,a3,a4)=a1⊕a4⊕1⊕a2a3，初始状态为(a1,a2,a3,a4)＝(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。

线性反馈移位寄存器原理
线性反馈移位寄存器是一种在数字电路中常用的元件，它能够将输入数据按照一定的顺序进行移位，并以一定的方式反馈部分数据到输入端。

它由多个触发器组成，每个触发器都能存储一个比特的数据。

实现线性反馈移位寄存器基本的原理是运用触发器的工作原理。

触发器是一种能够存储数据并在时钟信号的作用下改变输出状态的元件。

常见的触发器有D触发器和JK触发器等。

线性反馈移位寄存器的输入数据依次通过每个触发器，并从最后一个触发器的输出端输出。

同时，一部分触发器的输出被反馈到输入端，与输入数据进行异或运算后作为下一个触发器的输入。

这样，每次时钟信号到来时，输入数据随着触发器的工作状态向前移位，并根据反馈数据的异或结果产生新的输入数据。

通过合理选择反馈数据的位置和数值，线性反馈移位寄存器可以实现不同的功能。

例如，当反馈数据位于最后一个触发器和倒数第二个触发器之间，并且为1时，可以实现一个带有反馈的移位寄存器；当反馈数据为1并且位于最后一个触发器时，可以实现一个循环移位寄存器。

线性反馈移位寄存器广泛应用于数字通信、数据编码、序列生成等领域。

它具有简单、可靠、高效的特点，在现代的数字系统中扮演着重要的角色。

第二章作业参考答案1．3级线性反馈移位寄存器在c3＝1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。

解：此时线性反馈函数可表示为f(a1,a2,a3)=a1?c2a2?c1a3当c1＝0，c2＝0时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1，输出序列为101101…，周期＝3当c1＝0，c2＝1时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1?a2，…，周期＝7当c1＝1，c2＝0时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1?a3，…，周期＝7当c1＝1，c2＝1时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1?a2?a3，有输出序列为1010…，周期＝22．设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2,…,a n-1,a n)=(00…01)，证明输出序列的周期等于p(x)的阶证：设p(x)的阶为p，由定理2-3，由r|p，所以r?p设A(x)为序列{a i}的生成函数，并设序列{a i}的周期为r，则显然有A(x)p(x)＝?(x)又A(x)＝a1+a2x+…+a r x r-1+x r(a1+a2x+…+a r x r-1)+(x r)2(a1+a2x+…+a r x r-1)+…＝a1+a2x+…+a r x r-1/(1-x r)＝a1+a2x+…+a r x r-1/(x r-1)于是A(x)=(a1+a2x+…+a r x r-1)/(x r-1)＝?(x)/p(x)又(a1,a2,…,a n-1,a n)=(00…01)所以p(x)(a n x n-1+…+a r x r-1)=?(x)(x r-1)即p(x)x n-1(a n+…+a r x r-n)=?(x)(x r-1)由于x n-1不能整除x r-1，所以必有x n-1|?(x)，而?(x)的次数小于n，所以必有?(x)＝x n-1所以必有p(x)|(x r-1)，由p(x)的阶的定义知，阶p?r综上所述：p＝r#3．设n＝4，f(a1,a2,a3,a4)=a1?a4?1?a2a3，初始状态为(a1,a2,a3,a4)＝(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。

作业参考答案年级线性反馈移位寄存器在c新编时可有种Document number【980KGB-6898YT-769T8CB-246UT-18GG08】第二章作业参考答案1．3级线性反馈移位寄存器在c3＝1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。

解：此时线性反馈函数可表示为f(a1,a2,a3)=a1?c2a2?c1a3当c1＝0，c2＝0时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1，输出序列为101101…，周期＝3当c1＝0，c2＝1时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1?a2，…，周期＝7当c1＝1，c2＝0时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1?a3，…，周期＝7当c1＝1，c2＝1时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1?a2?a3，有输出序列为1010…，周期＝22．设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2,…,a n-1,a n)=(00…01)，证明输出序列的周期等于p(x)的阶证：设p(x)的阶为p，由定理2-3，由r|p，所以r?p设A(x)为序列{a i}的生成函数，并设序列{a i}的周期为r，则显然有A(x)p(x)＝?(x)又A(x)＝a1+a2x+…+a r x r-1+x r(a1+a2x+…+a r x r-1)+(x r)2(a1+a2x+…+a r x r-1)+…＝a1+a2x+…+a r x r-1/(1-x r)＝a1+a2x+…+a r x r-1/(x r-1)于是A(x)=(a1+a2x+…+a r x r-1)/(x r-1)＝?(x)/p(x)又(a1,a2,…,a n-1,a n)=(00…01)所以p(x)(a n x n-1+…+a r x r-1)=?(x)(x r-1)即p(x)x n-1(a n+…+a r x r-n)=?(x)(x r-1)由于x n-1不能整除x r-1，所以必有x n-1|?(x)，而?(x)的次数小于n，所以必有?(x)＝x n-1所以必有p(x)|(x r-1)，由p(x)的阶的定义知，阶p?r综上所述：p＝r#3．设n＝4，f(a1,a2,a3,a4)=a1?a4?1?a2a3，初始状态为(a1,a2,a3,a4)＝(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。