西安电子科技大学：《现代密码学》课程教学资源（PPT课件讲稿）第三章 流密码（流密码的基本概念、线性反馈移位寄存器序列）

第三章流密码 流密码的基本概念 二、线性反馈移位寄存器序列 三、B-M综合算法 四、非线性序列 2021/2/21

2021/2/21 1 第三章 流密码 一、流密码的基本概念 二、线性反馈移位寄存器序列 三、B-M综合算法 四、非线性序列

流密码的基本概念 2021/2/21

2021/2/21 2 一、流密码的基本概念

流密码的分类 ■同步流密码SSC( Synchronous Stream Cipher) σ与明文消息无关,密钥流将独立于明文 ■特点: 对于明文而言,这类加密变换是无记忆的。但它是时变 的 只有保持两端精确同步才能正常工作。 对主动攻击时异常敏感而有利于检测 无差错传播( Error Propagation) 2021/2/21

2021/2/21 3 流密码的分类 ◼ 同步流密码SSC(Synchronous Stream Cipher)： i与明文消息无关，密钥流将独立于明文。 ◼ 特点： ◼ 对于明文而言，这类加密变换是无记忆的。但它是时变 的。 ◼ 只有保持两端精确同步才能正常工作。 ◼ 对主动攻击时异常敏感而有利于检测 ◼ 无差错传播(Error Propagation)

流密码的分类 自同步流密码SSSC( Self-Synchronous Stream Cipher) G依赖于(kG1,m),使密文G不仅与当前输入 m有关,而且由于k对o的关系而与以前的输入m n2…,m1有关。一般在有限的m级存储下将与m ,m-n有关。 优点:具有自同步能力,强化了其抗统计分析的能力 缺点:有m位长的差错传播 2021/2/21

2021/2/21 4 流密码的分类 ◼ 自同步流密码SSSC(Self-Synchronous Stream Cipher) i依赖于(kI ,i-1 ,mi )，使密文ci不仅与当前输入 mi有关，而且由于ki对i的关系而与以前的输入m1 , m2 ,…,mi-1有关。一般在有限的n级存储下将与mi- 1 ,…,mi-n有关。 ◼ 优点：具有自同步能力，强化了其抗统计分析的能力 ◼ 缺点：有n位长的差错传播

流密码的分类 n级移存器 n级移存器 k1 o 2021/2/21 5

2021/2/21 5 流密码的分类 n级移存器 n 级移存器 … … … … ki f f ki ki ki mi Eki(·) ci ci Dki(·) mi

序列的伪随机性 口周期 序列40,使对所有,kp=k成立的的最小整数P 长为串run)(k1,k+1…,k+1) 序列4的一个周期中,k11≠k=k1=.=k1≠k 钢:*串和为的S .ol.. 2021/2/21 6

2021/2/21 6 序列的伪随机性 ◼ 周期 序列{ki }i0，使 对所有i，ki+p=ki 成立的的最小整数p ◼ 长为l的串(run) (kt , kt+1…kt+l -1 ) 序列{ki }的一个周期中， kt-1kt =kt+1=…=kt+l -1 kt+l 例：长为l的1串和长为l的0串： .011  10,100  01 l l

序列的伪随机性 周期自相关函数 周期为的序列{40,其周期自相关函数 R()=(A-D),j=0,1,… 式中,A={0≤p:k=k+},D=0≤p:k≠k+丹 同相自相关函数 当为的倍数,即p耐为,R=1 异相自相关函数 当不是的倍数时 2021/2/21

2021/2/21 7 序列的伪随机性 ◼ 周期自相关函数 周期为p的序列{ki }i0，其周期自相关函数 R(j)=(A－D)/p ， j=0, 1, … 式中，A={0i<p|：ki=ki+j}，D={0i<p：kiki+j}。 ◼ 同相自相关函数 当j为p的倍数，即pj时为，R(j)=1； ◼ 异相自相关函数 当j不是p的倍数时

例2-2 二元序列11100101100101110010 周期p=7 同相自相关函数R()=1 异相自相关函数R()=-1/7 2021/2/21

2021/2/21 8 例2－2 二元序列111001011100101110010… 周期p=7 同相自相关函数R(j)=1 异相自相关函数R(j)=－1/7

Golomb随机性假设-PN序列 则莓锁个Vm个数等,为P2,若两奇 G2,长为的串占1/2,且“0″串和“1”串个数相等或 至多差 G3,R为双值,即所有异相自相关函数值相等。这与白 噪声的自相关函数(8函数相近,这种序列称为双值序 列( Two Value Sequence) PN序列可用于通信中同步序列、码分多址CDMA 导航中多基站码、雷达测距码等。但仅满足G1~G3特 底列虽与白噪声序列相似,但远还不能满足密码体 2021/2/21

2021/2/21 9 Golomb随机性假设－PN序列 G1．若p为偶，则0, 1出现个数相等，皆为p/2。若p为奇， 则0出现个数为(p1)/2。 G2．长为l的串占1/2 l ，且“0”串和“1”串个数相等或 至多差一个。 G3．R(j)为双值，即所有异相自相关函数值相等。这与白 噪声的自相关函数(函数)相近，这种序列又称为双值序 列(Two Value Sequence)。 PN序列可用于通信中同步序列、码分多址(CDMA)、 导航中多基站码、雷达测距码等。但仅满足G1～G3特 性的序列虽与白噪声序列相似，但远还不能满足密码体 制要求

满足密码体制的另外三个条件 1.周期/要足够大,如大于100 C2.序列{420产生易于高速生成; C3.当序列{k}20的任何部分暴露时,要分析整个序列,提 取产生它的电路结构信息,在计算上是不可行的,称此 为不可预测性( Unpredictability) C3决定了密码的强度,是流密码理论的核心。它包含 了流密码要研究的许多主要问题,如线性复杂度、相关 免疫性、不可预测性等等。 2021/2/21

2021/2/21 10 满足密码体制的另外三个条件 C1．周期p要足够大，如大于1050； C2．序列{ki }i0产生易于高速生成； C3．当序列{ki }i0的任何部分暴露时，要分析整个序列，提 取产生它的电路结构信息， 在计算上是不可行的，称此 为不可预测性(Unpredictability)。 C3决定了密码的强度，是流密码理论的核心。它包含 了流密码要研究的许多主要问题，如线性复杂度、相关 免疫性、不可预测性等等