【安全课件】第13讲—序列密码

1、1序序 列列 密密 码码量子密码研究室量子密码研究室2005年年3月月28日日2主要内容主要内容 序列密码概述序列密码概述 布尔函数布尔函数 线性反馈移存器线性反馈移存器3序列密码概述序列密码概述 序列密码的起源序列密码的起源 序列密码的加解密思想序列密码的加解密思想 序列密码的基本原理序列密码的基本原理4序列密码的基本原理序列密码的基本原理 由少量的随机密钥,通过移位寄存器以及非线性变换等多层编码环节，产生变化量大、复杂度高、随机性好的伪随机乱数，利用简单的密码法把它与明文数据串进行结合，从而实现对明文数据的加密。5预备知识：布预备知识：布 尔尔 函函 数数一般地，我们把n n元布尔函数元布

2、尔函数定义为如下映射：记为 ，其中22:FFfn)(xf1, 0,)(,),(22221FFxfFxxxxnn 布尔函数是研究数字逻辑电路的重要数学工具，在序列密码、分组密码和公钥密码中，布尔函数都有重要的应用。特别在序列密码中，布尔函数是重要的数学工具之一。61 1、真值表、真值表 例如),()(21xxfxfxf(x)0011010101107 小项表示实际上是布尔代数表达方式，即逻辑表达方式，此方法常用于布尔函数的设计实现。2 2、小项表示、小项表示上例的小项表示为1212( )f xx xx x3 3、多项式表示、多项式表示因为 ，将小项表示中的逻辑非的形式换掉即得多项式表示。xx11

3、2( )f xxx85.1 线性反馈移存器一、线性反馈移存器简介一、线性反馈移存器简介（一）基本概念（一）基本概念 定义：反馈移存器的反馈逻辑电路可用一布尔函数来表示，若对应的布尔函数是线性函数，则称该反馈移存器为线性反馈移存器，否则称为非线性反馈移存器。91342123图图1、线性反馈移位寄存器、线性反馈移位寄存器图图2、非线性反馈移位寄存器、非线性反馈移位寄存器10（二）、工作原理（二）、工作原理假设在j时刻其内部状态为：),(21rjjjaaa在j+1时刻其内部状态变为：),(11rjjjaaa其中：),(21rjjjjaaafa此时的输出为j时刻的最高级：rja11132第7时刻 0

4、0 1第0时刻 0 0 1第1时刻 1 0 0第2时刻 1 1 0第3时刻 1 1 1第4时刻 0 1 1第5时刻 1 0 1第6时刻 0 1 0产生序列为：1001110和一个全零序列。12（三）、表示方法（三）、表示方法1 1、线性递推式表示、线性递推式表示一个r级线性移存器的线性递推式表示为：)(2211rnacacacarnrnnn)4(432naaaannnnan-1an-2an-3an-4an132 2、反馈多项式表示、反馈多项式表示x1x2x3x4一个r级线性移存器的反馈多项式表示为：1)(111xcxcxcxfrrrr1)(234xxxxf14（四）、序列和周期（四）、序列和周

5、期一般地，一个移存器序列表示为：iaaaaa210 对于序列 ，若存在整数p使得对任意正整数k有 成立，称满足该式的最小正整数p为序列的周期序列的周期。iaaaaa210pkkaa r级线性反馈移存器的最长周期: ，能达到最长周期的线性移存器序列称为m序列序列。12 r 在密码学中，我们希望参与变换的序列周期越长越好，因在密码学中，我们希望参与变换的序列周期越长越好，因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列，即列，即m序列。序列。15（五）、实例（五）、实例（画出下列个移存器的逻辑框图，写出相（画出下列个移存器的逻辑框图，写出

6、相应的线性递推式，并讨论由它们所产生的序列）应的线性递推式，并讨论由它们所产生的序列）1、不可约多项式2、可约多项式3、本原多项式4、环式移存器1)(234xxxxxf) 1)(1(1)(334xxxxxxf1)(4xxxf1)(4 xxf答案：1、该移存器产生三类周期相同（全为5）的序列及一个全零序列。2、该移存器产生五类周期分别为6、3、3、2、1的序列及一个全零序列。3、该移存器产生周期为15的m序列及一个全零序列。16（六）、反馈多项式的含义（六）、反馈多项式的含义一个r级线性移存器的线性递推式表示为：)(2211rnacacacarnrnnn引进迟延算子D：IDaaDaDaikkikk01,递推式可改写为：02210nrrnnnaDcaDcDacIac将上式中的D用符号x代替，引入多项式：1)(111xcxcxcxfrrrr从而有：)( , 0)(rnaDfn那么对于序列a，0)(aDf即：0)(2210nrraDcDcDcc10c17集合1： ； 是以 为反馈多项式的移存器产生的所有可能序列的集合。0)(|)(aDfafG)(xf集合2： ；是所有能产生序列的多项式的集合。0)(| )()(aDfxfaA对于该集合有以下性质：（1）若 ，则)()(),(aAxgxf)(),()()(gfaAxgxf（2）若 ，则)(),()(xFxgaAxf)()()(a