4.4带进位的反馈移位寄存器序列

密码学

第四章序列密码

第四节带进位的反馈移位寄存器序列

密码学

第四章序列密码

内在的线性结构是LFSR序列的致命弱点.上一节中介绍的组合生成器,前馈生成器以及钟控生成器的提出目的非常明确,都是为了破坏LFSR序列的线性结构以得到好的非线性序列.

密码学

第四章序列密码

近年来,几类好的非线性序列生成器逐渐受到国际学者的关注.由于非线性序列生成器可自然产生非线性结构好的序列,以它为基础构造伪随机序列比在LFSR基础上进行非线性改造相对要容易和安全.

密码学

第四章序列密码

带进位的反馈移位寄存器(Feedback with Carry Shift Register,简称FCSR)由两位美国学者Klapper A.和Goresky M.于1993年提出.其本质特征是利用整数的进位运算生成一类非线性序列.本节主要介绍FCSR序列的基本性质.应特别注意的是,在本节中的加法都指整数环Z中的加法.

密码学

2-adic数与有理分数导出序列

密码学

第四章序列密码

因为对任意非负整数 n,有唯一的 2-adic (或 2进制展开 n= n0+ n12+…+ nt2t,其中 ni∈{0, 1}, nt= 1, t= log2(n) ,且 1=∑ 2i,故整数环 Z是 2-adic整数i=0∞

环 Z2的子环. Z2中的零元素就是 0,单位元就是 1.

密码学

第四章序列密码

此外,由于 2-adic数α=∑ ai2i在 Z2中是(乘法)可i=0

∞

逆当且仅当 a0= 1.从而奇数在 Z2中可逆.所以,对奇数 q和任意整数 n,分数 n/q可自然视为 Z2中的元素,若记 n/q=∑ ai2i,则称序列(a0,a1,…)为有理数i=0∞

n/q的导出序列.

密码学

第四章序列密码

密码学

第四章序列密码

定理4.24若p和q互素, 0≤ p< q, q是奇数,则p/q导出序列的周期为 ordq(2).注4.7 ordq(2)表示2模q的乘法阶,即最小的正整数s使得同余式2s≡ 1 (mod q)成立.

密码学

基本概念和性质

密码学

第四章序列密码mn

an+r 1 an+r 2q1div 2 mod2

…

an+1qr 1

an

q2

……

qr

Σ

其中∑表示整数加法, mn是进位 (也称记忆 ), (mn; an+r 1, an+r 2,…, an)是 FCSR的一个状态.

密码学

第四章序列密码

具体实施过程如下:(1)设(m0; ar 1, ar 2,…, a0)是 FCSR的

初态, (2)若已产生(mn; an+r 1, an+r 2,…, an),计算整数和σn=∑ qkan+r k+ mn (n≥ 0);k=1 r

密码学

第四章序列密码

(3)右移一位,输出寄存器最右端的an; (4)令an+r=σn (mod 2),放入寄存器的最左端; (5)令mn+1= (σn an+r)/2= σn/2 .

密码学

第四章序列密码

密码学

第四章序列密码

密码学

第四章序列密码