第二章流密码:21流密码的基本概念 k 9 213密钥流产生器 k ●同步流密码的关键是密钥流产生器( Key generator) 般可将其看成一个参数为k的有限状态自动机,由一个输出符号 集Z、一个状态集∑、两个函数和v以及一个初始状态O组成 状态转移函数q:q→+1,将当前状态变为一个新状态an1 输出函数q→,当前状态O变为输出符号集中的一个元素zo ●密钥流生成器设计的关键在于 找出适当的状态转移函数q和输出函数y,使得输出序列z满足密钥 流序列z应满足的几个条件,并且要求在设备上是节省的和容易实 现的。为了实现这一目标,必须采用非线性函数 历忠毛孑技*字 12/
2.1.3 密钥流产生器 同步流密码的关键是密钥流产生器(Key Generator) ⚫ 一般可将其看成一个参数为k的有限状态自动机，由一个输出符号 集Z、一个状态集∑、两个函数φ和ψ以及一个初始状态σ0组成 ⚫ 状态转移函数φ：σi→σi+1，将当前状态σi变为一个新状态σi+1 ⚫ 输出函数ψ: σi→zi，当前状态σi变为输出符号集中的一个元素zi。 密钥流生成器设计的关键在于 ⚫ 找出适当的状态转移函数φ和输出函数ψ，使得输出序列z满足密钥 流序列z应满足的几个条件，并且要求在设备上是节省的和容易实 现的。为了实现这一目标，必须采用非线性函数 12/ 第二章 流密码：2.1 流密码的基本概念 φ k σi ψ k k zi
第二章流密码:21流密码的基本概念 21.3密钥流产生器 ●由于具有非线性的φ的有限状态自动机理论很不完善,相 应的密钥流产生器的分析工作受到极大的限制。 ●相反地,当采用线性的q和非线性的v时,将能够进行深 入的分析并可以得到好的生成器。 为方便讨论,可将这类生成器分成驱动部分和非线性组合部分 驱动部分控制生成器的状态转移,并为非线性组合部分提供统计 性能好的序列; 非线性组合部分要利用这些序列组合出满足要求的密钥流序列 k 驱动子 非线性 系统 →组合子 系统 密钥流生成器的分解 历蟓毛孑拌技大字 13/
2.1.3 密钥流产生器 由于具有非线性的φ的有限状态自动机理论很不完善，相 应的密钥流产生器的分析工作受到极大的限制。 相反地，当采用线性的φ和非线性的ψ时，将能够进行深 入的分析并可以得到好的生成器。 ⚫ 为方便讨论，可将这类生成器分成驱动部分和非线性组合部分 ⚫ 驱动部分控制生成器的状态转移，并为非线性组合部分提供统计 性能好的序列； ⚫ 非线性组合部分要利用这些序列组合出满足要求的密钥流序列。 13/ 第二章 流密码：2.1 流密码的基本概念 k 驱动子 系统 非线性 组合子 系统 k zi 密钥流生成器的分解
第二章流密码:22线性反馈移位寄存器 221布尔函数简介 m元布尔函数f(x1xn)定义为f:F2"->F2 表示方法有三种:逻辑关系式,真值表,多元多项式 多元多项式:如fx1x2x3小=x2+x3+x4 异或x1x2x1+x2(在GF(2)上的“+”(模2加) 逻辑“与”x1x2→x2(GF(2)上的“乘法” 逻辑“或”xVx2→x12+x1+x2其真值表为:x1x2x1Vx2 非 1+x 000 幂 reXx.x=x t0 x=1;布尔函数的高次项只有如下形式 i 历忠毛孑技*字 14/
2.2.1 布尔函数简介 n元布尔函数f(x1 ,…,xn )定义为f：F2 n→F2 ⚫ 表示方法有三种：逻辑关系式，真值表，多元多项式 多元多项式：如f(x1 ,x2 ,x3 ,x4 )＝x1x2＋x3＋x4 ⚫ 异或 x1x2 →x1＋x2 (在GF(2)上的“＋”(模2加) ⚫ 逻辑“与”x1x2 →x1x2 (GF(2)上的“乘法”) ⚫ 逻辑“或”x1 x2 → x1x2+x1＋x2 其真值表为： ⚫ 非 → 1＋x ⚫ 幂 x t＝x·x…x=x t>0 ⚫ x 0=1;布尔函数的高次项只有如下形式 ⚫ xi1xi2…xik 14/ 第二章 流密码：2.2 线性反馈移位寄存器 x1 x2 x1 x2 0 0 0 0 1 1 1 0 1 1 1 1
第二章流密码:22线性反馈移位寄存器 221布尔函数筒介 ●布尔函数的重量W八:真值表中函数值列里”1”的个数 八x1x2)=x1Vx2=x1x2+x1+x2的重量W=3 ●布尔函数的次数 n)=a+∑ r=1(1≤1<i2<.<≤n 一个乘积项x,xx,的次数定义为r 最大次数定义为布尔函数的次数def(0,也称为代数次数 °de=1时,称为仿射函数:八x…)=a+x4+x2+…+x 若仿射函数的常数项a=0,则称为线性函数 deg(01时,称为非线性函数 历忠毛孑技*字 15/
2.2.1 布尔函数简介 布尔函数的重量W(f)：真值表中函数值列里”1”的个数 ⚫ f(x1 ,x2 )＝x1x2 = x1x2+x1＋x2的重量W(f)＝3 布尔函数的次数 ⚫ f(x1 ,…,xn )＝a0＋ 一个乘积项 的次数定义为r 最大次数定义为布尔函数的次数def(f)，也称为代数次数 def(f)＝1时，称为仿射函数：f(x1 ,…,xn )＝a0＋ ⚫ 若仿射函数的常数项a0＝0，则称为线性函数 def(f)>1时，称为非线性函数 15/ 第二章 流密码：2.2 线性反馈移位寄存器 = n r i i i n i i i i i i r r r a x x x 1 1 ... ... 1 2 1 2 1 2 ... r i i i x x ...x 1 2 r i i i x + x +...+ x 1 2
第二章流密码:22线性反馈移位寄存器 222线性反馈移位寄存器的结构与表示 ●移位寄存器(FSR)是序列密码产生密钥流的主要组成部分 ●GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函 数f(a1a2,…,am)组成,如图所示 输出序列 1 f(a1a2…,an) ●移位寄存器的状态 每一存储器称为移位寄存器的一级,具有0和1两个状态 在任一时刻,这些级的内容构成该反馈移位寄存器的状态,可用 GF(2)上的一个m维向量(a1,a2…,an)表示,其中a是第级存储器的 内容。共有2冲种可能的状态。 初始状态听由用户确定,属于密钥k的一部分 历忠毛孑技*字 16/
2.2.2 线性反馈移位寄存器的结构与表示 移位寄存器(FSR)是序列密码产生密钥流的主要组成部分 ⚫ GF(2)上一个n 级反馈移位寄存器由n 个二元存储器与一个反馈函 数f(a1 ,a2 ,…,an )组成，如图所示 移位寄存器的状态 ⚫ 每一存储器称为移位寄存器的一级，具有0和1两个状态 ⚫ 在任一时刻，这些级的内容构成该反馈移位寄存器的状态，可用 GF(2)上的一个n维向量(a1 ,a2 ,…,an )表示，其中ai是第i级存储器的 内容。共有2 n种可能的状态。 ⚫ 初始状态σ0由用户确定，属于密钥k的一部分 16/ 第二章 流密码：2.2 线性反馈移位寄存器 an an-1 ... a1 f(a1,a2,…,an) a2 输出序列