第6讲-A5序列密码算法

1第6讲A5-1序列密码算法A5-1序列密码算法RC4序列密码算法A5算法是用于蜂窝式移动电话系统（GSM）加密的序列密码算法。2一、基本用法通信模式用户A用户B基站1基站2基站nA5-1算法用于用户的手机到基站之间的通信加密，通信内容到基站后先脱密变成明文，然后再进行基站到基站之间、以及基站到用户手机之间的信息加密，完成通信内容在通信过程的加密保护。A5-1序列密码算法31、应用环节只需考察用户A到基站1之间通信内容的加脱密，中间消息的传送由基站到基站之间的加密完成，而接收方用户B对消息的加脱密与用户A到基站1之间的通信完全类似，只不过是用户B先脱密消息。2、基本密钥KA1基本密钥KA1：预置在SIM卡中，与基站1共享。生存期：一旦植入SIM卡将不再改变。用途：用来分配用户和基站之间的会话密钥。A5-1序列密码算法43、会话密钥k产生方式：在每次会话时，基站产生一个64比特的随机数k。分配方式：利用基本密钥KA1，使用其它密码算将k加密传给用户手机。生存期：仅用于一次通话时间。A5-1序列密码算法54、明文处理按每帧228比特分为若干帧后逐帧加密，每帧处理方式相同。||||||||21iMMMM228||iM发送114比特接收114比特每帧处理方式加密后发送接收后脱密A5-1序列密码算法6)()()()(332211MEMEMEMEkkkk加密：一次通话使用一个会话密钥，对每帧使用不同的帧密钥。5、加密方式帧会话密钥：帧序号，长度为22比特。一次通话量：至多222帧数据，约0.89×230比特。帧会话密钥共产生228比特乱数，实现对本帧228比特通信数据的加脱密。明密结合方式：逐位模2加。A5-1序列密码算法7二、A5-1序列密码算法1、移存器描述算法使用3个级数为19、22和23的本原移存器。1)(141718191xxxxxfLFSR-11)(21222xxxfLFSR-21)(181922233xxxxxfLFSR-3注：A5-1算法中，LFSR的移位方式是左移方式。各寄存器的编号从第0级编号到第n-1级。A5-1序列密码算法8xn-1xn-2x1x0n级左移LFSR的结构框图c0=1c1c2cn-2cn-1cn=1移存器的左移和右移方式，除移位方式不同外，其工作原理完全相同。A5-1序列密码算法92、算法初始化初始化是利用一次通话的会话密钥k和帧序号设定三个移存器的起点，即初始状态。Step1：将三个LFSR的初态都设置为全零向量；Step2：(密钥参与)三个LFSR都规则动作64次，每次动作1步。在第i步动作时，三个LFSR的反馈内容都首先与密钥的第i比特模2加，并将模2加结果作为LFSR反馈的内容。A5-1序列密码算法10以移存器1为例的密钥参与过程：1)(141718191xxxxxf16364kkkk初始状态：)0,,0,0(),,,(017180xxxS动作1步后状态：),,0,0(),,,(1017181kxxxS),,,0,0(),,,(21017182kkxxxS动作2步后状态：动作14步后状态：),,,,,,0,0(),,,(1413210171814kkkkxxxS),,,,,,0,0(),,,(15114210171815kkkkkxxxS动作15步后状态：三个移存器各动作64步，完成密钥参与过程。A5-1序列密码算法11Step3：(帧序号参与)三个LFSR都规则动作22次，每次动作1步。在第i步动作时，三个LFSR的反馈内容都首先与帧序号的第i比特模2加，并将模2加的结果作为LFSR反馈的内容；帧序号比特的序号是从最低位编到最高位。帧序号参与方式：与密钥参与方式相同，不同的明文数据帧按顺序编号，每个编号为22比特。记帧序号为0000121220tttT0100121221tttT……帧密钥参与的目的：对不同的帧设置不同的帧会话密钥，保证对每帧以不同的起点生成乱数，尽可能避免密钥重用。A5-1序列密码算法123、乱数生成与加脱密A5算法中，LFSR的不规则动作采用钟控方式。(X1,X2,X2)000001010011100101110111LFSR-1动动动不动不动动动动LFSR-2动动不动动动不动动动LFSR-3动不动动动动动不动动钟控信号x1x2x3的采取：x1取自LFSR-1第9级；x2取自LFSR-2第11级；x3取自LFSR-3第11级。控制方式：择多原则。A5-1序列密码算法13Step4：三个LFSR以钟控方式连续动作100次，但不输出乱数；Step5：三个LFSR以钟控方式连续动作114次，在每次动作后，三个LFSR都将最高级寄存器中的值输出，这三个比特的模2和就是当前时刻输出的1比特乱数。连续动作114步，共输出114比特乱数，用于对用户手机到基站传送的114比特数据的加密；114,,2,1;idmciii加密方式：关于加密A5-1序列密码算法14Step6：三个LFSR以钟控方式连续动作100次，但不输出乱数；Step7：三个LFSR以钟控方式连续动作114次，在每次动作后，三个LFSR都将最高级寄存器中的值输出，这三个比特的模2和就是当前时刻输出的1比特乱数。连续动作114步，共输出114比特乱数，这114比特用于对基站到用户手机传送的114比特数据的脱密。关于脱密脱密方式：228,,116,115;idcmiiiA5-1序列密码算法154、A5-1算法的结构框图001走停走321321),,(xxxxxxf前馈函数A5-1序列密码算法16三、RC4算法设计者：RonRivest设计时间：1987年算法公开时间：1994密钥：支持可变的密钥长度RC4算法17S盒的初始化：线性填充：S0=0；S1＝1；S255＝255；然后用密钥重复填充另一个256字节的数组，不断重复密钥直到填充到整个数组，得到：K0,K1,…,K255对于i=0到255j:=(j+Si＋Ki)mod256交换Si和SjRC4算法18密钥生成算法8×8的S盒：S0，S1,…,S255，所有项是数字0-255的置换。两个指针（计数器）i、j的初值为0。i=(i+1)mod256j=(j+Si)mod256交换Si和Sjt=(Si+Sj)mod256K=St加密方式：m+K=c（以字节为单位，按位异或）RC4算法19四、序列密码的标准化进程（一）欧洲NESSIE工程简介欧洲于2000年1月1日启动了NESSIE工程，为期三年。总投资：264万欧元。主要目的：通过公开征集和评估提出一整套高效的密码标准。NESSIE（NewEuropeanSchemesforSignatures，Integrity，andEncryption）1、背景序列密码标准化进程202、征集算法的要求评选准则：长期安全，市场需要，效率以及灵活性。对序列密码算法安全性的最低要求：密钥长度至少256比特，内部记忆至少256比特3、评估准则（1）安全准则：攻击的难度至少要等同最一般的攻击。（2）实现准则：软硬件实现的效率不低于同类已有的算法。（3）其它准则：设计上的简单、清晰。（4）许可要求：选中的算法将被特许为免费使用。序列密码标准化进程214、NESSIE工程进程序列密码算法：第一阶段：2000年9月共提交了6个算法；第二阶段：2001年7月选出了3个算法；2003年2月评选结束，没有选定算法作为标准。序列密码标准化进程22（二）ECRYPT工程简介1、ECRYPT工程概述ECRYPT(EuropeanNetworkofExcellenceforCryptology)基金预算：560万欧元。主要目标：促进欧洲信息安全研究人员在密码学和数字水印研究上的交流，促进学术界和工业界的持久合作。ECRYPT工程2004年2月1日启动，2006年2月结束了第一阶段的评估，第二阶段在2006年7月到2007年9月进行，2008年1月完成评审活动。交流网站http：//。序列密码标准化进程232、eSTREAM简介类型1：适应软件快速执行；类型2：在有限资源下硬件能快速执行。类型1A：适应软件快速执行；自身带认证机制；类型2A：在有限资源下硬件能快速执行；带认证机制。（2）提交算法的类型（1）提交算法的要求输入：消息流；密钥；初始值(IV);辅助数据(AD)。输出：密文;认证码（AU）。序列密码标准化进程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的认证码；类型2A：80-bit的密钥，至少32或64bit的IV；至少32或64bit的认证码。序列密码标准化进程253、eSTREAM序列密码算法的征集2006年2月份，第一阶段的评估结束，组织者将算法分成三个档次。（1）FocusPhase2：是指在第二阶段的评选中，组织者希望公众给予特别关注，并鼓励密码分析者对其进行更多分析的一些算法；类型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；PolarBear；Rabbit；Yamb类型2（HW）：共19个算法Achterbahn；Decim；Edon80；F-FCSR；Hermes；LEX；Mickey；Mosquito；NLS；PolarBear；Pomaranch；Rabbit；Salsa20；Sfinks；TSC-3；VEST；WG；Yamb；Zk-Crypt（2）Phase2：是指进入第二阶段评选的其它算法；序列密码标准化进程27（3）Archived：是指将不会进入最后一个阶段评选的算法，是由于这些算法存在弱点或没有明显的优点。类型1（SW）：共9个算法F-FCSR；Fubuki；Frogbit；Hermes；MAG；Mir-1；Pomaranch；SSS；TRBDK3YAEA类型2（HW）：共3个算法MAG；SSS；TRBDKYAEA序列密码标准化进程282008年10月，最终评出了7个算法做为标准，基于软件实现的算法为：HC-128；Salsa20/12；Sosemanuk；Rabbit。基于硬件实现的算法为：Mickey-V2;Grain1.0;Trivium。