祖冲之序列密码算法

信息安全研究第2卷第11期2016年11月Vol.2No.11Nov.2016祖冲之序列密码算法冯秀涛(中国科学院数学与系统科学研究院北京100190)([e-mail])TheZUCStreamCipherAlgorithmFengXiutao{.AcademyofMathematicsandSystemsScience9ChineseAcademyofSciences^Beijing100190)AbstractTheZUCalgorithmisawordorientedstreamcipher?whichoutputsa32bkeywordstreamunderthecontrolofa128bseedkeyanda128binitialvector.ZUCwasadoptedastheencryptionstandard(GrantTS35.221)by3GPPLTEinSeptember2011,i.e.,the4thmobilecommunicationencryptionstandard,andissuedasthenationalcipherindustrystandard(GrantGM/T0001—2012)inMarch2012andasthenationalstandard(GrantGB/T33133—2016)inOctober2016respectively.InthispapertheZUCalgorithmisrecalledsimply,andthentheideaofitsdesignandmainprogressonitssecurityanalysisaresurveyed.Keywords3GPPLTE；4Gmobilecommunication；confidentialityandintegrityalgorithm；streamcipher；ZUC摘要祖冲之算法，简称ZUC，是一个面向字设计的序列密码算法，其在128b种子密钥和128b初始向量控制下输出32b的密钥字流.祖冲之算法于2011年9月被3GPPLTE采纳为国际加密标准(标准号为TS35.221)，即第4代移动通信加密标准，2012年3月被发布为国家密码行业标准(标准号为GM/T0001—2012)，2016年10月被发布为国家标准（标准号为GB/T33133—2016).简单介绍了祖冲之算法，并总结了其设计思想和国内外对该算法安全性分析的主要进展.关键词3GPPLTE;4G移动通信;保密性和完整性算法;序列密码;祖冲之算法中图法分类号TP3093GPP(The3rdGenerationPartnerProject),即第三代合作伙伴计划，是由欧洲电信标准协会(ETSI)、日本无线工业及商贸委员会(ARIB)和电信技术委员会(TTC)、韩国电信技术协会(TTA)以及美国电信标准委员会TIA于1998年底发起成立的，是一个专门负责制定全球3G移动通信标准的计划.我国通信标准协会(CCSA)于1999年加人该计划.目前3GPP已经囊括了全球最主要的电信标准化协会以及电信运营商和设备提供商，是电信领域全球最具影响力的计划之一•2004年3GPP开始启动LTE(longtermevo­lution)，旨在确保3GPP未来在电信领域的持续竞争力.该计划于2010年底被指定为第4代移动通信标准，简称4G通信标准.LTE是第4代无线通信的主要技术之一，其中安全技术是LTE的关键技术，并预留了16个密码算法接口.2009年5月，收稿日期：2016-10-25基金项目：国家自然科学基金项目（61572491)»...我国推荐以祖冲之算法为核心的保密性算法128-EEA3和完整性算法128-EIA3在3GPP立项，申请成为3GPPLTE保密性和完整性算法标准.历经3GPPSAGE内部评估、定向学术机构外部评估以及公开评估3个阶段评估，于2011年9月以祖冲之算法为核心的保密性算法128-EEA3和完整性算法128-EIA3被3GPPSA全票通过，正式成为3GPPLTE保密性和完整性算法标准，与分别以AES和SNOW3G为算法核心的保密性算法和完整性算法共同占用LTE中的3个算法接口.期大、随机统计特性好等特点，且在二元域上是非线性的，可以提高抵抗二元域上密码分析的能力；过滤部分采用有限状态机设计，内部包含记忆单元，使用分组密码中扩散和混淆特性好的线性变换和S盒，可提供高的非线性性.祖冲之算法受益于其结构特点，现有分析结果表明其具有非常高的安全性.1算法简介祖冲之算法是一个基于字设计的同步序列密码算法，其种子密钥SK和初始向量JV的长度均为128b，在种子密钥SK和初始向量的控制下，每拍输出一个32b的密钥字.祖冲之算法采用过滤生成器结构设计，在线性驱动部分首次采用素域GF(231_1)上的m序列作为源序列，具有周本节简单介绍祖冲之算法，其详细信息请参考祖冲之算法标准规范[13].1.1算法结构祖冲之算法结构主要包含3层，如图1所示.上层为线性反馈移位寄存器LFSR，中间层为比特重组BR，下层为非线性函数mod23丨-1♦个个(b个(^)t；515卜14S13S12i511Ao卜958卜756卜55453；S2515〇|图1祖冲之算法结构图1.2LFSRLFSR由16个31b的字单元变量&(0«15)构成，定义在素域GF(231—1)®上，其特征多项式/(x)=x16-(215x15+217x13+221x10+220x4+(28+l))(1)为素域GF(231—1)上的本原多项式.设为LFSR生成的序列.则对任意〇,有：1)a16+t=215a15+t十217a13+s十221(21Q+(十220a4+t_l_(H_28)atmod(231_1);①在ZUC算法中有限域GF(231-1)的元素取值集合为{l，2，.,2a—1},而非通常意义下的{0,1,2，.,231—2}.网址|1029信息安全研究第2卷第11期2016年11月Vol.2No.11Nov.20162)如果ai6+t=〇,则2i6+t=231—1.1.3比特重组BR比特重组BR为中间过渡层，其从LFSR的寄存器单兀变量5。，$2，$5，$7，$9，$11，SU，$15中抽取128位组成4个32b的字X。，足，X2，X3，以供下层非线性函数F和密钥导出函数使用.BR的具体计算过程如下：1)-X〇~-Sl5Hlkl4L2)Xl—5iil||59h»3)X2=57lII-S5H4)X3—S2lIU〇Hf这里如和紅分别表示记忆单元变量&的高16位和低16位取值，0«15,||为字符串连接符.1.4非线性函数F非线性函数F包含2个32b记忆单元变量拓和沁，其输人为比特重组BR输出的3个32b的字X。，兄，X2，输出为一个32比特字W.F的计算过程如下：1)田私，2)%=私田兄，3)W2=R2®X2,4)J^SO^dllD)，5)j?2=sa2(m))，其中S为32b的S盒变换，定义在附录A中给出;Li和L2为32b的线性变换，定义如下：(X)=X©(X«2)㊉(X«10)㊉(X«18)㊉(X«24)，乙2(X)=X©(X«8)㊉(X«14)㊉(X«22)©(X30),这里“《”表示长度为32b的字的左循环移位运算.1.5密钥载入祖冲之算法种子密钥SK和初始向量IV长度均为128b.密钥载人过程首先将种子密钥SK和初始向量打入到LFSR的记忆单元变量s。，&，…，&中作为其初始状态.记为SK^SKoHSKill-llSK^和iy=iy〇II/Vili-il/Vis,这里SK;和均为8b的位串，0i15.于是有s^SKMWlVi,(2)这里忒(〇々15)为15b的常数，取值见附录B.其次，令非线性函数F的2个记忆单元变量i?i和i?2为〇.最后运行初始化迭代过程32次，完成密钥载图2祖冲之算法初始化过程1030|人过程，如图2所示.其中每次初始化迭代过程将依次执行比特重组、非线性函数F计算和LFSR状态更新3个子步骤.在LFSR状态更新过程中，非线性函数F的输出W需要向右移1位(即舍弃最末1位)参与到LFSR的反馈计算.1.6密钥流生成祖冲之算法在密钥载人之后，首先依次执行比特重组BR、非线性函数F计算和LFSR状态更新，完成1次迭代过程，在此过程中不输出任何密钥字，然后进人密钥字输出过程.在密钥字输出过程中，算法每迭代1次，输出一个32b的密钥字Z=W©X3,(3)其中W为非线性函数F的输出，X3为比特重组的输出.2设计原理祖冲之算法设计以髙安全性作为优先目标，同时兼顾高的软硬件实现性能，在整体结构上可以分为上中下3层，其中：上层为LFSR，采用素域GF(231_1)上的本原序列，主要提供周期大、统计特性好的源序列.由于素域GF(231—1)上的加法在二元域GF⑵上是非线性的，素域GF(231—1)上本原序列可视作二元域GF(2)上的非线性序列，其具有权位序列平移等价、大的线性复杂度和好的随机统计特性等特点(更多细节请参考3.1节），并在一定程度上提供好的抵抗现有的基于二元域的密码分析的能力，譬如二元域上的代数攻击、相关攻击和区分分析等.中层为比特重组BR，其主要功能是衔接上层LFSR和下层非线性函数F，将上层31b数据转化为32b数据以供下层非线性函数F使用.比特重组采用软件实现友好的移位操作和字符串连接操作，其主要目的是为了打破上层LFSR的线性代数结构，并在一定程度上提供抵抗素域GF(231_1)上的密码攻击的能力.下层为非线性函数F，其主要借鉴了分组密码的设计思想，采用具有最优差分/线性分支数的线性变换和密码学性质优良的S盒来提供好的扩散性和高的非线性性.此外，非线性函数F基于32b的字设计，采用异或、循环移位、模加、S盒等不同代数结构上的运算，彻底打破源序列在素域GF(231—1)上的线性代数结构，进一步提高算法抵抗素域GF(231—1)上的密码分析的能力.通过上述3层的有效结合，祖冲之算法能够抵抗各种已知序列密码分析方法.3.1LFSR令户=231—1.由LFSR定义，容易验证其特征多项式/(I)为GF(夕)上的本原多项式，故由/(x)生成的任意非0序列的周期均为—1〜2496.本节简单介绍与LFSR相关的部分密码学性质，其细节请参考文献[幻.设序列fl是GF〇)上由/〇c)生成的本原序列，其2-adic权位分解为aiao+aj+t^2.…+a30230，(4)其中a;(0i30)均为0，1序列，称之为第i权位序列.注意对任意整数i=+A2+:c222H----hx3〇23°e[〇,户），有2xmodx3〇+x〇2+xi22++X29230—X$CC311,(5)这里，《31表示长度为31b的字的循环移位操作.于是我们有以下性质.性质1.设序列a是GF(W上由/U)生成的本原序列，权位序列a,(0i30)如上定义.则所有权位序列&(0纟30)之间都是相互平移等价的，也就是说，X啊壬意可以通过a。平移得到.记素域GF(p)上由/(I)生成的所有序列a组成的集合为G(/(x)).如果对任意fl，&eG(/(x))，都有a=&当且仅当a〇=6。，这里a〇和分另!j表示a和6的第0权位序列，亦即最低权位序列，则称序列集合G(/(:c))是模2压缩保墒的.性质2[5].设/U)是GF〇)上的任意本原多项式序列.则由/(x)生成的序列集合G(/(i))是模2压缩保墒的•由性质1和性质2,可得到关于由/(x)生成的任意非〇序列a导出的权位序列的周期和线性复杂度性质：性质3[6].对任意非0序列aGGC/Oc))和整数0^30,设权位序列a,.如上定义.则有：3部件特性网址|1031信息安全研究第2卷第11期2016年11月Vol.2No.11Nov.20161)所有权位序列a,•的周期都相等，为夕16—1&2496;