西华大学：《密码学 Cryptology》课程教学资源（PPT课件讲稿）第2章 序列密码

第二章序列密码 序列密码的基本概念 二、线性反馈移位寄存器 BM综合算法 四、非线性序列 2021/2/20

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

、序列密码的基本概念 萃大 2021/220

2021/2/20 2 一、序列密码的基本概念

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

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

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

2021/2/20 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级移存器 k k EkiO AkiO 2021/2/20

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

序列的伪随机性 周期 序列{40,使对所有,k+p=k成立的的最小整数卩 长为的串run)(k,k+1…k+1) 序列始的一个周期中,k1k=k1==k1≠kt 例:长为帕1串和长为的0串: Ol1·10 100∴01 2021/2/20 6

2021/2/20 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

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

2021/2/20 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 二元序列1101011001010 周期p=7 同相自相关函数R()=1 异相自相关函数R()=-1/。 2021/2/20

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

Golomb随机性假设PN序列 C1茹的个数(生进个数相等,鵲为m,若的奇 C至封点12,且“0”串和1串个数相等或 课后的省笑数8瑟籍签款系为福息 列( Two Value Sequence) PN序列可用于通信中同步序列、码分多址(CDMA 航中多基站码、雷达测距码等。但仅满足G1~G3特 底列虽与白噪声序列相似,但远述不能满足密码体 2021/2/20

2021/2/20 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特 性的序列虽与白噪声序列相似，但远还不能满足密码体 制要求

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

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