序列密码 3.5 典型序列密码算法

1、密码学第三章 序列密码3.5 典型序列密码算法第三章 序列密码 移位寄存器基础移位寄存器基础 m序列特性序列特性 序列密码编码技术序列密码编码技术 前馈函数的设计准则前馈函数的设计准则 典型序列密码算法典型序列密码算法 A5-1 序列密码算法序列密码算法 RC4算法算法 序列密码标准化进程序列密码标准化进程3.5 典型序列密码算法一一 A5-1序列密码算法用于蜂窝式移动电话系统语音和数字加密。用于蜂窝式移动电话系统语音和数字加密。 （一）基本用法（一）基本用法通信模式通信模式 用户用户A 用户用户B 基站基站1 1 基站基站2 2 基站基站n A5-1A5-1算法用于用户的手机到基站之间的通信

2、算法用于用户的手机到基站之间的通信加密，通信内容到基站后先脱密变成明文，然后加密，通信内容到基站后先脱密变成明文，然后再进行基站到基站之间、以及基站到用户手机之再进行基站到基站之间、以及基站到用户手机之间的信息加密，完成通信内容在通信过程的加密间的信息加密，完成通信内容在通信过程的加密保护。保护。 一一 A5-1序列密码算法1 1、应用环节、应用环节 只需考察用户只需考察用户A A到基站到基站1 1之间通信内容的加脱密，中之间通信内容的加脱密，中间消息的传送由基站到基站之间的加密完成，而接收方间消息的传送由基站到基站之间的加密完成，而接收方用户用户B B对消息的加脱密与用户对消息的加脱密与用户

3、A A到基站到基站1 1之间的通信完全之间的通信完全类似，只不过是用户类似，只不过是用户B B先脱密消息。先脱密消息。 2 2、基本密钥、基本密钥KA1基本密钥基本密钥K KA1A1：预置在：预置在SIMSIM卡中，与基站卡中，与基站1 1共享。共享。生存期：一旦植入生存期：一旦植入SIMSIM卡将不再改变。卡将不再改变。用途：用来分配用户和基站之间的会话密钥。用途：用来分配用户和基站之间的会话密钥。 一一 A5-1序列密码算法3 3、会话密钥、会话密钥k 产生方式：在每次会话时，基站产生一个产生方式：在每次会话时，基站产生一个6464比特比特的随机数的随机数k。 分配方式：利用基本密钥分配方

4、式：利用基本密钥KA1，使用其它密码算，使用其它密码算法法将将k加密传给用户手机。加密传给用户手机。 生存期：仅用于一次通话时间。生存期：仅用于一次通话时间。一一 A5-1序列密码算法4 4、明文处理、明文处理 按每帧按每帧228228比特分为若干帧后逐帧加密，每比特分为若干帧后逐帧加密，每帧处理方式相同。帧处理方式相同。 |21iMMMM 228|iM发送发送114114比特比特接收接收114114比特比特每帧处理方式每帧处理方式加密后发送加密后发送接收后脱密接收后脱密一一 A5-1序列密码算法)()()()(332211MEMEMEMEkkkk加密：加密： 一次通话使用一个会话密钥，对每帧

5、使用不同的一次通话使用一个会话密钥，对每帧使用不同的帧密钥。帧密钥。5 5、加密方式、加密方式帧会话密钥帧会话密钥：帧序号，长度为：帧序号，长度为2222比特。比特。一次通话量：一次通话量：至多至多2 22222帧数据，约帧数据，约0.890.892 23030比特比特 。 帧会话密钥共产生帧会话密钥共产生228228比特乱数，实现对本帧比特乱数，实现对本帧228228比特通信数据的加脱密。比特通信数据的加脱密。 明密结合方式：明密结合方式：逐位模逐位模2 2加。加。 一一 A5-1序列密码算法（二）（二）A5-1A5-1序列密码算法序列密码算法1 1、移存器描述、移存器描述算法使用算法使用3

6、 3个级数为个级数为1919、2222和和2323的本原移存器。的本原移存器。 1)(141718191xxxxxfLFSR-1 1)(131721222xxxxxfLFSR-2 1)(181922233xxxxxfLFSR-3 注注：A5-1A5-1算法中，算法中，LFSRLFSR的移位方式是的移位方式是左移左移方式。方式。 各寄存器的编号从第各寄存器的编号从第0 0级级编号到第编号到第n-1-1级级。一一 A5-1序列密码算法xn-1xn-2x1x0n级左移级左移LFSR的结构框图的结构框图c0=1c1 1c2 2cn-2-2cn-1-1cn=1 移存器的左移和右移方式，除移位方式不同移存

7、器的左移和右移方式，除移位方式不同外，其工作原理完全相同。外，其工作原理完全相同。一一 A5-1序列密码算法2 2、算法初始化、算法初始化 初始化是利用一次通话的会话密钥初始化是利用一次通话的会话密钥k和帧序号和帧序号设定三个移存器的起点，即初始状态。设定三个移存器的起点，即初始状态。Step 1：将三个：将三个LFSRLFSR的初态都设置为全零向量；的初态都设置为全零向量；Step 2：( (密钥参与密钥参与) ) 三个三个LFSRLFSR都规则动作都规则动作6464次，次，每次动作每次动作1 1步。步。 在第在第i步动作时，三个步动作时，三个LFSRLFSR的反馈内容都首先的反馈内容都首先

8、与密钥的第与密钥的第i比特模比特模2 2加，并将模加，并将模2 2加结果作为加结果作为LFSRLFSR反馈的内容。反馈的内容。一一 A5-1序列密码算法以移存器以移存器1 1为例的密钥参与过程：为例的密钥参与过程：1)(141718191xxxxxf16364kkkk初始状态：初始状态： )0 , 0 , 0(),(017180 xxxS动作动作1 1步后状态：步后状态： ), 0 , 0(),(1017181kxxxS), 0 , 0(),(21017182kkxxxS动作动作2 2步后状态：步后状态： 动作动作1414步后状态：步后状态： ), 0 , 0(),(1413210171814

9、kkkkxxxS), 0 , 0(),(15114210171815kkkkkxxxS动作动作1515步后状态：步后状态： 动作动作6464步完成密钥参与过程。步完成密钥参与过程。一一 A5-1序列密码算法Step 3：( (帧序号参与帧序号参与) ) 三个三个LFSRLFSR都规则动作都规则动作2222次，每次次，每次动作动作1 1步。在第步。在第i步动作时，三个步动作时，三个LFSRLFSR的反馈内容都首先的反馈内容都首先与帧序号的第与帧序号的第i比特模比特模2 2加，并将模加，并将模2 2加的结果作为加的结果作为LFSRLFSR反馈的内容；帧序号比特的序号是从最低位编到最高位。反馈的内容

10、；帧序号比特的序号是从最低位编到最高位。 帧序号参与方式：帧序号参与方式：与密钥参与方式相同，不同的与密钥参与方式相同，不同的明文数据帧按顺序编号，每个编号为明文数据帧按顺序编号，每个编号为2222比特。比特。 记帧序号为记帧序号为0000121220 tttT0100121221 tttT 帧密钥参与的目的帧密钥参与的目的：对不同的帧设置不同的帧会话：对不同的帧设置不同的帧会话密钥，保证对每帧以不同的起点生成乱数，尽可能避免密钥，保证对每帧以不同的起点生成乱数，尽可能避免密钥重用。密钥重用。一一 A5-1序列密码算法3 3、乱数生成与加脱密、乱数生成与加脱密A5算法中，算法中，LFSR的不规

11、则动作采用钟控方式。的不规则动作采用钟控方式。(X1,X2,X2) 000001010011100101110111LFSR-1动动动动动动不动不动 不动不动动动动动动动LFSR-2动动动动不动不动动动动动不动不动动动动动LFSR-3动动不动不动动动动动动动动动不动不动动动 钟控信号钟控信号x1 x2 x3的采取的采取：x1取自取自LFSR-1第第9级；级； x2取自取自LFSR-2第第11级；级； x3取自取自LFSR-3第第11级级 。控制方式控制方式：择多原则。：择多原则。一一 A5-1序列密码算法Step 4：三个：三个LFSRLFSR以钟控方式连续动作以钟控方式连续动作100100次

12、，但不输出次，但不输出乱数；乱数；Step 5：三个：三个LFSRLFSR以钟控方式连续动作以钟控方式连续动作114114次，在每次动次，在每次动作后，三个作后，三个LFSRLFSR都将最高级寄存器中的值输出，这三个都将最高级寄存器中的值输出，这三个比特的模比特的模2 2和就是当前时刻输出的和就是当前时刻输出的1 1比特乱数。比特乱数。 连续动作连续动作114114步，共输出步，共输出114114比特乱数，用于对用户比特乱数，用于对用户手机到基站传送的手机到基站传送的114114比特数据的加密；比特数据的加密； 114, 2 , 1;idmciii加密方式：加密方式： 关于加密关于加密一一 A

13、5-1序列密码算法Step 6：三个：三个LFSRLFSR以钟控方式连续动作以钟控方式连续动作100100次，但不输出次，但不输出乱数；乱数；Step 7：三个：三个LFSRLFSR以钟控方式连续动作以钟控方式连续动作114114次，在每次动次，在每次动作后，三个作后，三个LFSRLFSR都将最高级寄存器中的值输出，这三个都将最高级寄存器中的值输出，这三个比特的模比特的模2 2和就是当前时刻输出的和就是当前时刻输出的1 1比特乱数。比特乱数。 连续动作连续动作114114步，共输出步，共输出114114比特乱数，这比特乱数，这114114比特比特用于对基站到用户手机传送的用于对基站到用户手机传

14、送的114114比特数据的脱密。比特数据的脱密。 关于脱密关于脱密脱密方式：脱密方式： 228,116,115;idcmiii一一 A5-1序列密码算法4 4、A5-1A5-1算法的结构框图算法的结构框图0 0 0 0 1 1走走停停走走321321),(xxxxxxf前馈函数前馈函数一一 A5-1序列密码算法设计者：设计者：Ron Rivest设计时间：设计时间：1987年年算法公开时间：算法公开时间：1994 密钥：支持可变的密钥长度密钥：支持可变的密钥长度二二 RC4算法S盒的初始化：盒的初始化： 线性填充：线性填充：S0=0；S11；S255255； 密钥密钥key:40256个字节个

15、字节 用密钥重复填充另一个用密钥重复填充另一个256字节的数组，不字节的数组，不断重复密钥直到填充到整个数组，得到：断重复密钥直到填充到整个数组，得到：K0,K1,K255 对于对于i=0到到255j=(j+SiKi)mod256交换交换Si和和Sj 二二 RC4算法密钥生成算法密钥生成算法 88的的S盒：盒：S0，S1,S255，所有项是数字，所有项是数字0-255的的置换。两个指针（计数器）置换。两个指针（计数器）i、j的初值为的初值为0。 i=(i+1)mod256 j=(j+Si)mod256 交换交换Si和和Sj t=(Si+Sj)mod256 K=St加密方式加密方式：m+K=c（

16、以字节为单位，按位异或）（以字节为单位，按位异或）二二 RC4算法（一）欧洲（一）欧洲NESSIE工程简介工程简介欧洲于欧洲于2000年年1月月1日启动了日启动了NESSIE工程，为期三工程，为期三年。年。总投资总投资：264万欧元。万欧元。 主要目的主要目的：通过公开征集和评估提出一整套高效的：通过公开征集和评估提出一整套高效的密码标准密码标准 。 NESSIE （New European Schemes for Signatures，Integrity，and Encryption ） 1、背景、背景三三 序列密码标准化进程2、征集算法的要求、征集算法的要求评选准则：评选准则：长期安全，市

17、场需要，效率以及灵活性。长期安全，市场需要，效率以及灵活性。 对序列密码算法安全性的最低要求：密钥长度至少对序列密码算法安全性的最低要求：密钥长度至少256比特，内部记忆至少比特，内部记忆至少256比特比特 3、评估准则、评估准则（1）安全准则：攻击的难度至少要等同最一般的攻击）安全准则：攻击的难度至少要等同最一般的攻击 。（2）实现准则：软硬件实现的效率不低于同类已有的算法。）实现准则：软硬件实现的效率不低于同类已有的算法。（3）其它准则：设计上的简单、清晰。）其它准则：设计上的简单、清晰。（4）许可要求：选中的算法将被特许为免费使用。）许可要求：选中的算法将被特许为免费使用。三三 序列密码

18、标准化进程4、NESSIE工程进程工程进程2000年年1月月 NESSE工程第一阶段开始工程第一阶段开始2000年年9月月 算法提交截止，共提交算法提交截止，共提交39个算法个算法2001年年6月月 NESSIE进行第一次评估进行第一次评估2001年年7月月 NESSIE工程第二个阶段开始工程第二个阶段开始2001年年9月、月、10月月 分别召开两次分别召开两次NESSIE专题研讨会专题研讨会2002年年12月月 NESSIE计划最终评选计划最终评选2003年年2月月 公布公布17种推荐算法，种推荐算法，NESSIE工程结束工程结束 序列密码算法：第一阶段共选出了序列密码算法：第一阶段共选出了

19、6个算法，第二阶个算法，第二阶段选出了段选出了3个算法，最终没有选定算法作为标准。个算法，最终没有选定算法作为标准。三三 序列密码标准化进程（二）（二）ECRYPT工程简介工程简介 1、ECRYPT工程概述工程概述ECRYPT (European Network of Excellence for Cryptology) 基金预算基金预算：560万欧元。万欧元。 主要目标主要目标：促进欧洲信息安全研究人员在密码学和数字水：促进欧洲信息安全研究人员在密码学和数字水印研究上的交流，促进学术界和工业界的持久合作印研究上的交流，促进学术界和工业界的持久合作 。 ECRYPT工程工程2004年年2月月1

20、日启动，日启动，2006年年2月结束了月结束了第一阶段的评估，第二阶段在第一阶段的评估，第二阶段在2006年年7月到月到2007年年9月进月进行，行，2008年年1月完成评审活动。月完成评审活动。交流网站交流网站http：/www.ecrypt.eu. org/Stream。 三三 序列密码标准化进程2、eSTREAM简介简介类型类型 1：适应软件快速执行；：适应软件快速执行；类型类型 2：在有限资源下硬件能快速执行。：在有限资源下硬件能快速执行。类型类型 1A：适应软件快速执行；自身带认证机制；：适应软件快速执行；自身带认证机制；类型类型 2A：在有限资源下硬件能快速执行；带认证机制。：在有限资源下硬件能快速执行；带认证机制。（2）提交算法的类型）提交算法的类型（1）提交算法的要求）提交算法的要