第6讲-A5序列密码算法ppt课件.ppt

1 A5-1 序列密码算法序列密码算法RC4序列密码序列密码算法算法 A5 A5算法是用于蜂窝式移动电话系统（算法是用于蜂窝式移动电话系统（GSMGSM）加密）加密的序列密码算法。的序列密码算法。2一、基本用法一、基本用法通信模式通信模式 用户用户A 用户用户B 基站基站1 1 基站基站2 2 基站基站n A5-1 A5-1算法用于用户的手机到基站之间的通信加密，算法用于用户的手机到基站之间的通信加密，通信内容到基站后先脱密变成明文，然后再进行基站通信内容到基站后先脱密变成明文，然后再进行基站到基站之间、以及基站到用户手机之间的信息加密，到基站之间、以及基站到用户手机之间的信息加密，完成通信内容在通信过程的加密保护。完成通信内容在通信过程的加密保护。 31 1、应用环节、应用环节 只需考察用户只需考察用户A A到基站到基站1 1之间通信内容的加脱密，中之间通信内容的加脱密，中间消息的传送由基站到基站之间的加密完成，而接收方间消息的传送由基站到基站之间的加密完成，而接收方用户用户B B对消息的加脱密与用户对消息的加脱密与用户A A到基站到基站1 1之间的通信完全之间的通信完全类似，只不过是用户类似，只不过是用户B B先脱密消息。先脱密消息。 2 2、基本密钥、基本密钥KA1基本密钥基本密钥K KA1A1：预置在：预置在SIMSIM卡中，与基站卡中，与基站1 1共享。共享。生存期：一旦植入生存期：一旦植入SIMSIM卡将不再改变。卡将不再改变。用途：用来分配用户和基站之间的会话密钥。用途：用来分配用户和基站之间的会话密钥。 43 3、会话密钥、会话密钥k 产生方式产生方式：在每次会话时，基站产生一个：在每次会话时，基站产生一个6464比特比特的随机数的随机数k。 分配方式分配方式：利用基本密钥：利用基本密钥KA1，使用其它密码算将，使用其它密码算将k加密传给用户手机。加密传给用户手机。 生存期生存期：仅用于一次通话时间。：仅用于一次通话时间。 54 4、明文处理、明文处理 按每帧按每帧228228比特分为若干帧后逐帧加密，每帧处比特分为若干帧后逐帧加密，每帧处理方式相同。理方式相同。 |21iMMMM 228|iM发送发送114114比特比特接收接收114114比特比特每帧处理方式每帧处理方式加密后发送加密后发送接收后脱密接收后脱密 6)()()()(332211MEMEMEMEkkkk加密：加密： 一次通话使用一个会话密钥，对每帧使用不同一次通话使用一个会话密钥，对每帧使用不同的帧密钥。的帧密钥。5 5、加密方式、加密方式帧会话密钥帧会话密钥：帧序号，长度为：帧序号，长度为2222比特。比特。一次通话量：一次通话量：至多至多2 22222帧数据，约帧数据，约0.890.892 23030比特比特 。 帧会话密钥共产生帧会话密钥共产生228228比特乱数，实现对本帧比特乱数，实现对本帧228228比特通信数据的加脱密。比特通信数据的加脱密。 明密结合方式：明密结合方式：逐位模逐位模2 2加。加。 7二、二、A5-1A5-1序列密码算法序列密码算法1 1、移存器描述、移存器描述算法使用算法使用3 3个级数为个级数为1919、2222和和2323的本原移存器。的本原移存器。 1)(141718191xxxxxfLFSR-1 1)(21222xxxfLFSR-2 1)(181922233xxxxxfLFSR-3 注注：A5-1A5-1算法中，算法中，LFSRLFSR的移位方式是的移位方式是左移左移方式。方式。 各寄存器的编号从第各寄存器的编号从第0 0级级编号到第编号到第n-1-1级级。 8xn-1xn-2x1x0n级左移级左移LFSR的结构框图的结构框图c0=1c1 1c2 2cn-2-2cn-1-1cn=1 移存器的左移和右移方式，除移位方式不同外，移存器的左移和右移方式，除移位方式不同外，其工作原理完全相同。其工作原理完全相同。 92 2、算法初始化、算法初始化 初始化是利用一次通话的会话密钥初始化是利用一次通话的会话密钥k和帧序号设定三和帧序号设定三个移存器的起点，即初始状态。个移存器的起点，即初始状态。Step 1：将三个：将三个LFSRLFSR的初态都设置为全零向量；的初态都设置为全零向量；Step 2：( (密钥参与密钥参与) ) 三个三个LFSRLFSR都规则动作都规则动作6464次，每次动次，每次动作作1 1步。步。 在第在第i步动作时，三个步动作时，三个LFSRLFSR的反馈内容都首先与密钥的反馈内容都首先与密钥的第的第i比特模比特模2 2加，并将模加，并将模2 2加结果作为加结果作为LFSRLFSR反馈的内容。反馈的内容。 10以移存器以移存器1 1为例的密钥参与过程：为例的密钥参与过程：1)(141718191xxxxxf16364kkkk初始状态：初始状态： )0 , 0 , 0(),(017180 xxxS动作动作1 1步后状态：步后状态： ), 0 , 0(),(1017181kxxxS), 0 , 0(),(21017182kkxxxS动作动作2 2步后状态：步后状态： 动作动作1414步后状态：步后状态： ), 0 , 0(),(1413210171814kkkkxxxS), 0 , 0(),(15114210171815kkkkkxxxS动作动作1515步后状态：步后状态： 三个移存器各动作三个移存器各动作6464步，完成密钥参与过程。步，完成密钥参与过程。 11Step 3：( (帧序号参与帧序号参与) ) 三个三个LFSRLFSR都规则动作都规则动作2222次，每次次，每次动作动作1 1步。在第步。在第i步动作时，三个步动作时，三个LFSRLFSR的反馈内容都首先与的反馈内容都首先与帧序号的第帧序号的第i比特模比特模2 2加，并将模加，并将模2 2加的结果作为加的结果作为LFSRLFSR反馈反馈的内容；帧序号比特的序号是从最低位编到最高位。的内容；帧序号比特的序号是从最低位编到最高位。 帧序号参与方式：帧序号参与方式：与密钥参与方式相同，不同的明与密钥参与方式相同，不同的明文数据帧按顺序编号，每个编号为文数据帧按顺序编号，每个编号为2222比特。比特。 记帧序号为记帧序号为0000121220tttT0100121221tttT 帧密钥参与的目的帧密钥参与的目的：对不同的帧设置不同的帧会：对不同的帧设置不同的帧会话密钥，保证对每帧以不同的起点生成乱数，尽可能话密钥，保证对每帧以不同的起点生成乱数，尽可能避免密钥重用。避免密钥重用。 123 3、乱数生成与加脱密、乱数生成与加脱密A5A5算法中，算法中，LFSRLFSR的不规则动作采用钟控方式。的不规则动作采用钟控方式。(X1,X2,X2)000001010011100101110111LFSR-1动动动动动动不动不动不动不动动动动动动动LFSR-2动动动动不动不动动动动动不动不动动动动动LFSR-3动动不动不动动动动动动动动动不动不动动动 钟控信号钟控信号x1 x2 x3的采取的采取：x1取自取自LFSR-1第第9级级 ； x2取自取自LFSR-2第第11级；级； x3取自取自LFSR-3第第11级级 。控制方式控制方式：择多原则。：择多原则。 13Step 4：三个：三个LFSRLFSR以钟控方式连续动作以钟控方式连续动作100100次，但不输出乱数；次，但不输出乱数；Step 5：三个：三个LFSRLFSR以钟控方式连续动作以钟控方式连续动作114114次，在每次动作后，次，在每次动作后，三个三个LFSRLFSR都将最高级寄存器中的值输出，这三个比特的模都将最高级寄存器中的值输出，这三个比特的模2 2和和就是当前时刻输出的就是当前时刻输出的1 1比特乱数。比特乱数。 连续动作连续动作114114步，共输出步，共输出114114比特乱数，用于对用户手比特乱数，用于对用户手机到基站传送的机到基站传送的114114比特数据的加密；比特数据的加密； 114, 2 , 1;idmciii加密方式：加密方式： 关于加密关于加密 14Step 6：三个：三个LFSRLFSR以钟控方式连续动作以钟控方式连续动作100100次，但不输出乱数；次，但不输出乱数；Step 7：三个：三个LFSRLFSR以钟控方式连续动作以钟控方式连续动作114114次，在每次动作后，次，在每次动作后，三个三个LFSRLFSR都将最高级寄存器中的值输出，这三个比特的模都将最高级寄存器中的值输出，这三个比特的模2 2和和就是当前时刻输出的就是当前时刻输出的1 1比特乱数。比特乱数。 连续动作连续动作114114步，共输出步，共输出114114比特乱数，这比特乱数，这114114比特用于比特用于对基站到用户手机传送的对基站到用户手机传送的114114比特数据的脱密。比特数据的脱密。 关于脱密关于脱密脱密方式：脱密方式： 228,116,115;idcmiii 154 4、A5-1A5-1算法的结构框图算法的结构框图0 0 0 0 1 1走走停停走走321321),(xxxxxxf前馈函数前馈函数 16三、三、RC4算法算法 设计者：设计者：Ron Rivest设计时间：设计时间：19871987年年算法公开时间：算法公开时间：19941994 密钥：支持可变的密钥长度密钥：支持可变的密钥长度RC4算法算法 17S S盒的初始化：盒的初始化： 线性填充：线性填充：S0=0；S11；S255255；然后用密钥；然后用密钥重复填充另一个重复填充另一个256字节的数组，不断重复密钥直到填字节的数组，不断重复密钥直到填充到整个数组，得到：充到整个数组，得到：K0,K1,K255 对于对于i=0到到255j:=(j+SiKi)mod256交换交换Si和和Sj RC4算法算法 18密钥生成算法密钥生成算法 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（以字节为单位，按位异或）（以字节为单位，按位异或）RC4算法算法 19四、序列密码的标准化进程四、序列密码的标准化进程（一）欧洲（一）欧洲NESSIENESSIE工程简介工程简介欧洲于欧洲于20002000年年1 1月月1 1日启动了日启动了NESSIENESSIE工程，为期三年。工程，为期三年。 总投资总投资：264264万欧元。万欧元。 主要目的主要目的：通过公开征集和评估提出一整套高效：通过公开征集和评估提出一整套高效的密码标准的密码标准 。 NESSIE （New European Schemes for Signatures，Integrity，and Encryption ） 1 1、背景、背景序列密码标准化进程序列密码标准化进程202 2、征集算法的要求、征集算法的要求 评选准则：评选准则：长期安全，市场需要，效率以及灵活性。长期安全，市场需要，效率以及灵活性。 对序列密码算法安全性的最低要求：密钥长度至少对序列密码算法安全性的最低要求：密钥长度至少256256比特，内部记忆至少比特，内部记忆至少256256比特比特 3 3、评估准则、评估准则（1 1）安全准则：攻击的难度至少要等同最一般的攻击。）安全准则：攻击的难度至少要等同最一般的攻击。（2 2）实现准则：软硬件实现的效率不低于同类已有的算法。）实现准则：软硬件实现的效率不低于同类已有的算法。（3 3）其它准则：设计上的简单、清晰。）其它准则：设计上的简单、清晰。（4 4）许可要求：选中的算法将被特许为免费使用。）许可要求：选中的算法将被特许为免费使用。序列密码标准化进程序列密码标准化进程214 4、NESSIE工程进程工程进程 序列密码序列密码算法：算法： 第一阶段：第一阶段：20002000年年9 9月共提交了月共提交了6 6个算法；个算法； 第二阶段：第二阶段：20012001年年7 7月选出了月选出了3 3个算法；个算法； 20032003年年2 2月评选结束，没有选定算法作为标准。月评选结束，没有选定算法作为标准。序列密码标准化进程序列密码标准化进程22（二）（二）ECRYPT工程简介工程简介 1 1、ECRYPT工程概述工程概述ECRYPT (European Network of Excellence for Cryptology) 基金预算基金预算：560560万欧元。万欧元。 主要目标主要目标：促进欧洲信息安全研究人员在密码学和数字水：促进欧洲信息安全研究人员在密码学和数字水印研究上的交流，促进学术界和工业界的持久合作印研究上的交流，促进学术界和工业界的持久合作 。 ECRYPTECRYPT工程工程20042004年年2 2月月1 1日启动，日启动，20062006年年2 2月结束了第月结束了第一阶段的评估，第二阶段在一阶段的评估，第二阶段在20062006年年7 7月到月到20072007年年9 9月进行，月进行，20082008年年1 1月完成评审活动。月完成评审活动。交流网站交流网站http：/www.ecrypt.eu. org/Stream。 序列密码标准化进程序列密码标准化进程232 2、eSTREAM简介简介类型类型 1 1：适应软件快速执行；：适应软件快速执行；类型类型 2 2：在有限资源下硬件能快速执行。：在有限资源下硬件能快速执行。类型类型 1A：适应软件快速执行；自身带认证机制；：适应软件快速执行；自身带认证机制；类型类型 2A：在有限资源下硬件能快速执行；带认证机制。：在有限资源下硬件能快速执行；带认证机制。（2）提交算法的类型）提交算法的类型（1）提交算法的要求）提交算法的要求输入：消息流；密钥；初始值输入：消息流；密钥；初始值(IV);(IV);辅助数据辅助数据(AD)(AD)。输出：密文输出：密文; ;认证码（认证码（AUAU）。）。序列密码标准化进程序列密码标准化进程24（3）提交算法的数据要求）提交算法的数据要求类型类型 1： 128-bit的密钥，至少的密钥，至少64或或128bit的的IV；类型类型 2：80-bit的密钥，至少的密钥，至少32或或64bit的的IV；类型类型 1A：128-bit的密钥，至少的密钥，至少64或或128bit的的IV；至少；至少32，64，96或或128-bit的认证码；的认证码；类型类型 2 A：80-bit的密钥，至少的密钥，至少32或或64bit的的IV；至少；至少32或或64bit的认证码。的认证码。序列密码标准化进程序列密码标准化进程253、eSTREAM序列密码算法的征集序列密码算法的征集 2006 2006年年2 2月份，第一阶段的评估结束，组织者将算月份，第一阶段的评估结束，组织者将算法分成三个档次。法分成三个档次。 （1 1）Focus Phase 2：是指在第二阶段的评选中，组织者是指在第二阶段的评选中，组织者希望公众给予特别关注，并鼓励密码分析者对其进行更希望公众给予特别关注，并鼓励密码分析者对其进行更多分析的一些算法；多分析的一些算法； 类型类型1（SW）：共）：共7个算法；个算法；Dragon-128；HC-256； LEX；Phelix；Py；Salsa20；Sosemanuk。类型类型2（HW）：共）：共4个算法个算法 Grain；Mickey-128；Phelix；Trivium 序列密码标准化进程序列密码标准化进程26类型类型1（SW）：共：共7个算法个算法 ABC；CryptMT；Dicing；NLS；Polar Bear； Rabbit；Yamb 类型类型2（HW）：共：共19个算法个算法 Achterbahn；Decim；Edon80；F-FCSR；Hermes； LEX ； Mickey；Mosquito ；NLS；Polar Bear； Pomaranch； Rabbit；Salsa20；Sfinks；TSC-3； VEST ；WG；Yamb； Zk-Crypt（2 2）Phase 2Phase 2：是指进入第二阶段评选的其它算法；是指进入第二阶段评选的其它算法；序列密码标准化进程序列密码标准化进程27（3 3）ArchivedArchived：是指将不会进入最后一个阶段评选的算法，是指将不会进入最后一个阶段评选的算法，是由于这些算法存在弱点或没有明显的优点。是由于这些算法存在弱点或没有明显的优点。类型类型1 1（SWSW）：共）：共9 9个算法个算法 F-FCSR F-FCSR；FubukiFubuki；FrogbitFrogbit；HermesHermes；MAGMAG； Mir-1 Mir-1；PomaranchPomaranch；SSSSSS；TRBDK3 YAEATRBDK3 YAEA类型类型2 2（HWHW）：共）：共3 3个算法个算法 MAG MAG ；SSSSSS；TRBDK YAEATRBDK YAEA序列密码标准化进程序列密码标准化进程28 2008年年10月，最终评出了月，最终评出了7个算法做为标准，个算法做为标准，基于基于软件软件实现的算法为：实现的算法为： HC-128；Salsa20/12；Sosemanuk； Rabbit。基于基于硬件硬件实现的算法为：实现的算法为： Mickey-V2;Grain1.0; Trivium。