第2章01--流密码(LFSR)

　　第2章01--流密码(LFSR)_数学_自然科学_专业资料。第2章 流密码(序列密码) 一、流密码的基本概念 二、线性反馈移位寄存器序列 三、线性移位寄存器的一元多项式表示 四、m序列的伪随机性 五、m序列密码的破译 1 加密 ci ? mi ?

　　第2章 流密码(序列密码) 一、流密码的基本概念 二、线性反馈移位寄存器序列 三、线性移位寄存器的一元多项式表示 四、m序列的伪随机性 五、m序列密码的破译 1 加密 ci ? mi ? ki mi ? ci ? ki 流密码的基本概念 ? 解密 流密码是将明文划分成字符(如单个字母)，或其编码 的基本单元(如0, 1数字)，字符分别与密钥流作用进 行加密，解密时以同步产生的同样的密钥流实现。 流密码强度完全依赖于密钥序列的随机性(Randomness) 和不可预测性(Unpredictability)。 ? ? ? 核心问题是密钥流生成器的设计。 保持收发两端密钥流的精确同步是实现可靠解密的关 键技术。 2 流密码的框图 kI 安 全 信 道 kI · · · KG · · · KG ki mi Eki(mi) ci · · · ci ki mi Eki(mi) 3 流密码的框图 ? ? 消息流：m=m1m2…mi，其中mi?M。 密文流： c=c1c2…ci…=Ek1(m1)Ek2(m2)… 密钥流：{ki}，i?0。 一个完全随机的非周期序列，可以实现一次一密体制。但 需要无限存储单元和复杂的输出逻辑函数f。?i是第i时刻 密钥流生成器的内部状态，以存储单元的存数矢量描述。 Eki(mi)…，ci?C。 ? ki ? f (k ,? i ) 4 流密码的分类(1) ? ? 同步流密码SSC(Synchronous Stream Cipher)： ?i与明文消息无关，密钥流将独立于明文。 特点： ? ? ? ? 对于明文而言，这类加密变换是无记忆的。但它是时变 的。 只有保持两端精确同步才能正常工作。 对主动攻击时异常敏感而有利于检测 无差错传播(Error Propagation) 5 流密码的分类(2) ? ? 自 同 步 流 密 码 SSSC(Self-Synchronous Stream Cipher) ? i 依赖于( kI,?i-1,mi)，使密文 ci 不仅与当前 输入mi有关，而且由于ki对?i的关系而与以前的输 入 m1, m2 ,…,mi-1 有关。一般在有限的 n 级存储下 将与mi-1,…,mi-n有关。 优点：具有自同步能力，强化了其抗统计分析的 能力 缺点：有n位长的差错传播。 密钥流与明文流不相互独立！ ? 6 同步流密码 ? ? 密钥流产生器 加密变换器 ? 主要问题：设计一个滚动的密钥产生器， 使k经其扩展成一个密钥流具有以下性质： 极大的周期、良好的统计特性、抗线性 分析、抗统计分析。 有限状态自动机FA 7 有限状态自动机FA (Finite state Automation) ? 具有离散输入和输出（输入集和输出集均有 限）的一种数学模型 ? ? ? ? 有限状态集S={sii=1,2,…,l} 有限输入字符集X={ Xii=1,2,…,m} 有限输出字符集Y={ Ykk=1,2,…,n} 转移函数 第j时刻输入Xj ? X ，输出Yj ? Y ? Yj＝f 1(sj ,Xj) ? Sj+1 ＝f 2(sj ,Xj) 第j时刻输入Xj ∈X ，状态变为Sj+1∈S 8 例 f1 s1 s2 s3 ? ? S={s1,s2,s3},X={x1, x2,x3},Y=(y1,y2,y3) 转移函数 x1 y1 y2 y3 x2 y3 y1 y2 X3 y2 y3 y1 f2 s1 s2 s3 x1 s2 s3 s1 x2 s1 s2 s3 X3 s3 s1 s2 9 FA的状态图表示 若输入为 x1x2x1x3x3x1 初始状态s1 状态序列：s1?s2?s2?s3?s2?s1?s2 输出序列： y1 10 y1 y2 y1 y3 y1 作为FA的密钥流产生器 ? ? 同步流密码的密钥流产生器可看为一 个参数为k的FA 输出集Z，状态集Σ，状态转移函数 φ和输出函数ψ，初态?0 k (Z , ?,?,? ,? 0 ) ? φ 设计的关键是φ和ψ 采用非线 ψ k zi 作为FA的密钥流产生器 (Z , ?,?,? ,? 0 ) ? ? 具有非线性的φ的FA理论很不完善，通 常采用线性状态转移函数φ以及非线性的 输出函数ψ 可将此类产生器分为驱动部分和非线性 组合部分。 ? ? 驱动部分控制状态转移 LFSR 非线性组合部分提供统计特性良好的序列 12 两种常见的密钥流产生器 LFSR LFSR LFSR 非线性组合函数 LFSR 非 线 性 组 合 函 数 zi zi 13 第四章 流密码 一、流密码的基本概念 二、线性反馈移位寄存器序列 三、线性移位寄存器的一元多项式表示 四、m序列的伪随机性 五、m序列密码的破译 14 线性反馈移位寄存器序列概念 移位寄存器是流密码产生密钥流的一个主要组成部分。 GF(2)上一个n级反馈移位寄存器由n个二元存储器与 一个反馈函数f(a1,a2,…,an)组成，如图所示。 每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反 馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种 可能的状态。每一时刻的状态可用n长序列表示: a1,a2,…,an 15 例： 3级反馈移位寄存器，其初始状态为 (a1,a2,a3)=(1,0,1)，输出可由表求出 状态 （a1,a2,a3) 非线性反馈移位寄存器 输出 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 0 16 如果移位寄存器的反馈函数f(a1,a2,…,an)是a1， a2，…，an的线性函数，则称之为线性反馈移位寄存器 LFSR（linear feedback shift register）。 此时f可写为 f (a1, a2 ,?, an ) ? cn a1 ? cn?1a2 ??c1an 其中常数ci=0或1，?是模2加法。 ? ci=0或1可用开关的断开和闭合来实现，如上图所示。 17 输出序列{at}满足 an+t=cnat?cn-1at+1?…?c1an+t-1 ? ?? 其中t为非负正整数。 线性反馈移位寄存器因其实现简单、速度快、有较为成 熟的理论等优点而成为构造密钥流生成器的最重要的部件 之一。 18 例，下图是一个5级线性反馈移位寄存器，其初始状态为 （a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为： 反馈函数： 输出序列为 f ? a4 ? a1 1100110… 周期：31 19 在线性反馈移位寄存器中总是假定c1,c2,…,cn中至 少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话， 在n个脉冲后状态必然是00…0，且这个状态必将一直 持续下去。 若只有一个系数不为0，设仅有cj不为0，实际上是 一种延迟装置。一般对于n级线性反馈移位寄存器，总 是假定c0=1。 20 f (a1, a2 ,?, an ) ? cn a1 ? cn?1a2 ??c1an 21 线性反馈移位寄存器输出序列的性质完全由其反馈函数 决定。 n ?n级线性反馈移位寄存器最多有2 个不同的状态。 ?若其初始状态为0，则其状态恒为0。若其初始状态非0， 则其后继状态不会为0。 n ?因此n级线性反馈移位寄存器的状态周期小于等于2 -1。 n ?其输出序列的周期与状态周期相等，也小于等于2 -1。 ?只要选择合适的反馈函数便可使序列的周期达到最大值 2n-1，周期达到最大值的序列称为m序列。 ? 第四章 流密码 一、流密码的基本概念 二、线性反馈移位寄存器序列 三、线性移位寄存器的一元多项式表示 四、m序列的伪随机性 五、m序列密码的破译 22 4.3 线性移位寄存器的一元多项式表示 设n级LFSR的输出序列满足递推关系 an+k=c1an+k-1 ? c2an+k-2 ? …? cnak P(x)=1+c1x+…＋cn-1xn-1＋cnxn 表示，称这个多项式为LFSR的特征多项式。 (*) 对任何k≥1成立。这种递推关系可用一个一元高次多项式 23 实例：（画出下列个移存器的逻辑框图，写出相应的线 性递推式，并讨论由它们所产生的序列） 1、不可约多项式 f ( x) ? x4 ? x3 ? x2 ? x ?1 2、可约多项式 f ( x) ? x4 ? x3 ? x ?1 ? ( x3 ?1)(x ?1) 3、本原多项式 4、环式移存器 f ( x) ? x 4 ? x ?1 f ( x) ? x 4 ?1 24 1、不可约多项式 f ( x) ? x4 ? x3 ? x2 ? x ?1 2、可约多项式 f ( x) ? x4 ? x3 ? x ?1 ? ( x3 ?1)(x ?1) 3、本原多项式 4、环式移存器 f ( x) ? x 4 ? x ?1 f ( x) ? x 4 ?1 答案： 1、该移存器产生三类周期相同（全为5）的序列及一个全 零序列。 2、该移存器产生五类周期分别为6、3、3、2、1的序列及 一个全零序列。 3、该移存器产生周期为15的m序列及一个全零序列。 25 本原多项式 ? 设p(x)是GF(2)上的多项式，使p(x)(xp-1)的最小 p称为p(x)的周期或者阶。 ? 仅能被非0常数或自身的常数倍除尽，但不能被其他 多项式除尽的多项式称为不可约多项式。 若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n 次本原多项式。 ? 以本原多项式为连接多项式产生的非零序列均是m序列。 26 若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式 例：本原多项式 f ( x) ? x 4 ? x ?1 因为，f(x)(x15-1)，但不存在比15小的常数m，使 f(x)(xm-1)，所以f(x)的阶是15。 因为，一次多项式x、x+1不能整除f(x)，所以任一个 三次多项式也不能整除f(x); 二次多项式x2+x+1不能整除f(x)； 所以f(x)是不可约多项式。 所以f(x)是本原多项式。 27 例：（32，7，5，3，2，1，0） x32 ? x 7 ? x5 ? x3 ? x 2 ? x ? 1 C语言代码？ 28 一些本原多项式: 29 30