第15讲—序列密码1

1、序序 列列 密密 码码主要内容主要内容 序列密码概述序列密码概述 布尔函数布尔函数 线性反馈移位寄存器线性反馈移位寄存器序列密码概述序列密码概述 序列密码的起源序列密码的起源 序列密码的加解密思想序列密码的加解密思想 序列密码的基本原理序列密码的基本原理序列密码的基本原理序列密码的基本原理 序列密码的加密变换和解密变换都非常简单，序列密码的加密变换和解密变换都非常简单，易于实现。序列密码的安全性主要倚赖于密钥序易于实现。序列密码的安全性主要倚赖于密钥序列。列。 由少量的随机密钥由少量的随机密钥,通过移位寄存器以及非线通过移位寄存器以及非线性变换等多层编码环节，产生变化量大、复杂度性变换等多层编

2、码环节，产生变化量大、复杂度高、随机性好的伪随机乱数，利用简单的密码法高、随机性好的伪随机乱数，利用简单的密码法把它与明文数据串进行结合，从而实现对明文数把它与明文数据串进行结合，从而实现对明文数据的加密。据的加密。 预备知识：布预备知识：布 尔尔 函函 数数一般地，我们把n n元布尔函数元布尔函数定义为如下映射：记为 ，其中22:FFfn)(xf1, 0,)(,),(22221FFxfFxxxxnn 布尔函数是研究数字逻辑电路的重要数学工具，在序列密码、分组密码和公钥密码中，布尔函数都有重要的应用。特别在序列密码中，布尔函数是重要的数学工具之一。1 1、真值表、真值表 例如),()(21xx

3、fxfxf(x)001101010110 小项表示实际上是布尔代数表达方式，即逻辑表达方式，此方法常用于布尔函数的设计实现。2 2、小项表示、小项表示上例的小项表示为1212( )f xx xx x3 3、多项式表示、多项式表示因为 ，将小项表示中的逻辑非的形式换掉即得多项式表示。xx112( )f xxx5.1 线性反馈移位寄存器一、线性反馈移位寄存器简介一、线性反馈移位寄存器简介（一）基本概念（一）基本概念 定义：移位寄存器是用来产生序列密码中的密钥序列的一定义：移位寄存器是用来产生序列密码中的密钥序列的一种重要工具。种重要工具。 一个一个q q元域元域GF(q)GF(q)上的上的n n阶

4、反馈移位寄存器由阶反馈移位寄存器由n n个寄存器和一个寄存器和一个反馈函数构成（如下图所示）个反馈函数构成（如下图所示）. .反馈函数反馈函数 是一个从是一个从 到到GF(q)GF(q)的函数，这里的函数，这里 表示表示q q元域元域GF(q)GF(q)上上的的n n维向量空间维向量空间. .反馈函数反馈函数 的自变量取值为的自变量取值为相应寄存器中的内容，反馈移位寄存器一般简称为移位寄存器相应寄存器中的内容，反馈移位寄存器一般简称为移位寄存器. . 若反馈函数是线性函数，则称该移位寄存器为线性移位寄若反馈函数是线性函数，则称该移位寄存器为线性移位寄存器，否则称为非线性移位寄存器。存器，否则称

5、为非线性移位寄存器。),(121nnxxxxfnqGF)(nqGF)(),(121nnxxxxf图图1、线性反馈移位寄存器、线性反馈移位寄存器nx1nx2x1x),(121nnxxxxf输出输出说明：上图中标有说明：上图中标有 的小方框表示第的小方框表示第i级寄存器，最右端的寄存器为第级寄存器，最右端的寄存器为第1级寄存级寄存器，最左端的寄存器为第器，最左端的寄存器为第n级寄存器级寄存器. ix（二）、工作原理（二）、工作原理假设在j时刻其内部状态为：),(21rjjjaaa在j+1时刻其内部状态变为：),(11rjjjaaa其中：),(21rjjjjaaafa此时的输出为j时刻的最高级：rj

6、a当一个时钟脉冲来到时，第当一个时钟脉冲来到时，第i级寄存器的内容传送给第级寄存器的内容传送给第i-1级，第级，第1级寄存器的内容为反馈移位寄存器的输出，反级寄存器的内容为反馈移位寄存器的输出，反馈函数馈函数 的值传送给第的值传送给第n级寄存器级寄存器.),(121nnxxxxf312第7时刻 0 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产生序列为：10011101（三）、表示方法（三）、表示方法1 1、线性递推式表示、线性递推式表示一个r级线性移位寄存器的线性递推式表示为：)(2211r

7、nacacacarnrnnn)4(432naaaannnnan-1an-2an-3an-4an2 2、一元多项式表示、一元多项式表示x1x2x3x41)(234xxxxfnnnnxcxcxcxxxf121121),(设一个设一个GF(q)GF(q)上的上的n n阶线性移位寄存器的反馈函数为阶线性移位寄存器的反馈函数为其中其中 . .称一元多项式称一元多项式为该线性移位寄存器的联系多项式为该线性移位寄存器的联系多项式. .niqGFci1),(nnxcxcxcxg2211)(（四）、序列和周期（四）、序列和周期一般地，一个移存器序列表示为：iaaaaa210 对于序列 ，若存在整数p使得对任意正

8、整数k有 成立，称满足该式的最小正整数p为序列的周期序列的周期。iaaaaa210pkkaa r级线性反馈移存器的最长周期: ，能达到最长周期的线性移存器序列称为m序列序列。12 r 在密码学中，我们希望参与变换的序列周期越长越好，因在密码学中，我们希望参与变换的序列周期越长越好，因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列，即列，即m序列。序列。（五）、实例（五）、实例（画出下列个移存器的逻辑框图，写出相（画出下列个移存器的逻辑框图，写出相应的线性递推式，并讨论由它们所产生的序列）应的线性递推式，并讨论由它们所产生的序列）1、不可约多项式2、可约多项式3、本原多项式1)(234