祖冲之序列密码算法(ZUC算法)

1祖冲之序列密码算法第1部分：算法描述1范围本部分描述了祖冲之序列密码算法，可用于指导祖冲之算法相关产品的研制、检测和使用。2术语和约定以下术语和约定适用于本部分。2.1比特bit二进制字符0和1称之为比特。2.2字节byte由8个比特组成的比特串称之为字节。2.3字word由2个以上（包含2个）比特组成的比特串称之为字。本部分主要使用31比特字和32比特字。2.4字表示wordrepresentation本部分字默认采用十进制表示。当字采用其它进制表示时，总是在字的表示之前或之后添加指示符。例如，前缀0x指示该字采用十六进制表示，后缀下角标2指示该字采用二进制表示。2.5高低位顺序bitordering本部分规定字的最高位总是位于字表示中的最左边，最低位总是位于字表示中的最右边。GM/T10004.2-201223符号和缩略语3.1运算符+算术加法运算mod整数取余运算⨁按比特位逐位异或运算⊞模232加法运算‖字符串连接符∙H取字的最高16比特∙L取字的最低16比特k32比特字左循环移k位k32比特字右移k位ab向量a赋值给向量b，即按分量逐分量赋值3.2符号下列符号适用于本部分：s0,s1,s2,…,s15线性反馈移位寄存器的16个31比特寄存器单元变量X0,X1,X2,X3比特重组输出的4个32比特字R1,R2非线性函数F的2个32比特记忆单元变量W非线性函数F输出的32比特字Z算法每拍输出的32比特密钥字k初始种子密钥iv初始向量D用于算法初始化的字符串常量3.3缩略语下列缩略语适用于本部分：ZUC祖冲之序列密码算法或祖冲之算法LFSR线性反馈移位寄存器BR比特重组F非线性函数4算法描述4.1算法整体结构祖冲之算法逻辑上分为上中下三层，见图1。上层是16级线性反馈移位寄存器（LFSR）；中层是比特重组（BR）；下层是非线性函数F。GM/T10004.2-20123图1祖冲之算法结构图4.2线性反馈移位寄存器LFSR4.2.1概述LFSR包括16个31比特寄存器单元变量s0,s1,…,s15。LFSR的运行模式有2种：初始化模式和工作模式。4.2.2初始化模式在初始化模式下，LFSR接收一个31比特字u。u是由非线性函数F的32比特输出W通过舍弃最低位比特得到，即u=W1。在初始化模式下，LFSR计算过程如下：LFSRWithInitialisationMode(u){(1)v=215s15+217s13+221s10+220s4+(1+28)s0mod(231-1)；(2)s16=(v+u)mod(231-1)；(3)如果s16=0，则置s16=231-1；(4)(s1,s2,…,s15,s16)(s0,s1,…,s14,s15)。}GM/T10004.2-201244.2.3工作模式在工作模式下，LFSR不接收任何输入。其计算过程如下：LFSRWithWorkMode(){(1)s16=215s15+217s13+221s10+220s4+(1+28)s0mod(231-1)；(2)如果s16=0，则置s16=231-1；(3)(s1,s2,…,s15,s16)(s0,s1,…,s14,s15)。}4.3比特重组BR比特重组从LFSR的寄存器单元中抽取128比特组成4个32比特字X0、X1、X2、X3。BR的具体计算过程如下：BitReconstruction(){(1)X0=s15H‖s14L；(2)X1=s11L‖s9H；(3)X2=s7L‖s5H；(4)X3=s2L‖s0H。}4.4非线性函数FF包含2个32比特记忆单元变量R1和R2。F的输入为3个32比特字X0、X1、X2，输出为一个32比特字W。F的计算过程如下：F(X0,X1,X2){(1)W=(X0R1)⊞R2；(2)W1=R1⊞X1；(3)W2=R2X2；(4)R1=S(L1(W1L‖W2H))；(5)R2=S(L2(W2L‖W1H))。}其中S为32比特的S盒变换，定义在附录A中给出；L1和L2为32比特线性变换，定义如下：L1(X)=X(X2)(X10)(X18)(X24)，L2(X)=X(X8)(X14)(X22)(X30)。4.5密钥装入密钥装入过程将128比特的初始密钥k和128比特的初始向量iv扩展为16个31比特字作为LFSR寄存器单元变量s0,s1,…,s15的初始状态。设k和iv分别为k0‖k1‖……‖k15和iv0‖iv1‖……‖iv15，GM/T10004.2-20125其中ki和ivi均为8比特字节，0≤i≤15。密钥装入过程如下：(1)D为240比特的常量，可按如下方式分成16个15比特的子串：D=d0‖d1‖……‖d15，其中：d0=1000100110101112，d1=0100110101111002，d2=1100010011010112，d3=0010011010111102，d4=1010111100010012，d5=0110101111000102，d6=1110001001101012，d7=0001001101011112，d8=1001101011110002，d9=0101111000100112，d10=1101011110001002，d11=0011010111100012，d12=1011110001001102，d13=0111100010011012，d14=1111000100110102，d15=1000111101011002。(2)对0≤i≤15，有si=ki‖di‖ivi。4.6算法运行4.6.1初始化阶段首先把128比特的初始密钥k和128比特的初始向量iv按照4.5节密钥装入方法装入到LFSR的寄存器单元变量s0,s1,…,s15中，作为LFSR的初态，并置32比特记忆单元变量R1和R2为全0。然后执行下述操作：重复执行下述过程32次：(1)BitReconstruction()；(2)W=F(X0,X1,X2)；(3)LFSRWithInitialisationMode(W1)。4.6.2工作阶段首先执行下列过程一次，并将F的输出W舍弃：(1)BitReconstruction()；(2)F(X0,X1,X2)；(3)LFSRWithWorkMode()。然后进入密钥输出阶段。在密钥输出阶段，每运行一个节拍，执行下列过程一次，并输出一个32比特的密钥字Z：(1)BitReconstruction()；(2)Z=F(X0,X1,X2)X3；(3)LFSRWithWorkMode()。GM/T10004.2-20126GM/T10004.2-20127附录A（规范性附录）S盒32比特S盒S由4个小的8х8的S盒并置而成，即S=(S0,S1,S2,S3)，其中S0=S2，S1=S3。S0和S1的定义分别见表1和表2。设S0(或S1)的8比特输入为x。将x视作两个16进制数的连接，即x=h||l，则表1(或表2)中第h行和第l列交叉的元素即为S0(或S1)的输出S0(x)(或S1(x))。设S盒S的32比特输入X和32比特输出Y分别为：X=x0‖x1‖x2‖x3，Y=y0‖y1‖y2‖y3，其中xi和yi均为8比特字节，i=0,1,2,3。则有yi=Si(xi),i=0,1,2,3。表1S0盒0123456789ABCDEF03E725B47CAE0003304D1549809B96DCB17B1BF932AF9D6AA5B82DFC1D0853039024D4E8499E4CED991DDB685488B296EAC3CDC1F81E734369C6B5BDFD396320D4384767DB2A7CFED57C5F32CBB142106559B5E3EF5E314F7F5AA40D8251495FBA581C64A16D517A892241F8CFFD8AE2E01D3AD73B4BDA46EBC9DE9A8F87D73A806F2FC88B1B437F70A2213287CCC3C89C7C39656907BF7EF00B2B975235417961A64C10FEABC2695888AB0A3FBC01894F2E1E5E95DBD0DC1166645CEC59427512F5749CAA23C0E86ABBE2A02E767E644A26CC2939FF1DF6FA36D250689E6271153DD640C4E20FE8E83776B25053F0C30EA70B7A1E8A965F8D271ADB81B3A0F4457A19DFEE783460表2S1盒0123456789ABCDEF055C263713BC847869F3CDA5B29AAFD7718CC5940CA61A1300E3A8167240F9F84224426689681D9453E1076C6A78B3943E133AB5562AC06DB3052266BFDC0BFA62484DD20110636C9C1CFF62752BB69F5D48757F844CD29C57A4BC4F9ADFFED68D7AEB62B53D85CA11417FB23D57D30677308097EEB7703F61B2198E4EE54B938F5DDBA98ADF1AE2ECB0DFCF42D466E1D97E8D1E994D37A5755E839EAB829DB91CE0CD4989A01B6BD5824A25F387899159050B895E4GM/T10004.2-20128BD091C7CEED0FB46FA0CCF0024A79C3DECA3EFEA51E66B18EC1B2C80F774E7FF21D5A6A541E41319235C433070ABA7E0E34E88B1987CF33D606C7BCAD31F32650428F64BE859B2F598AD7B025ACAF1203E2F2注：S0盒和S1盒数据均为十六进制表示。GM/T10004.2-20129（资料性附录）模231-1乘法和模231-1加法的实现B.1模231-1乘法两个31比特字模231-1乘法可以快速实现。特别地，当其中一个字具有较低的汉明重量时，可以通过31比特的循环移位运算和模231-1加法运算实现。例如，计算abmod(231-1)，其中b=2i+2j+2k。则abmod(231-1)=(a31i)+(a31j)+(a31k)mod(231-1)，其中31表示31比特左循环移位运算。B.2模231-1加法在32位处理平台上，两个31比特字a和b模231-1加法运算c=a+bmod(231-1)可以通过下面的两步计算实现：1)c=a+b；2)c=(c&0x7FFFFFFF)+(c31)。GM/T10004.2-201210附录C（资料性附录）算法计算实例C.1测试向量1（全0）输入:密钥k:00000000000000000000000000000000初始向量iv:00000000000000000000000000000000输出:z1:27bede74z2:018082da初始化：线性反馈移位寄存器初态:iS0+iS1+iS2+iS3+iS4+iS5+iS6+iS7+i00044d7000026bc0000626b0000135e00005789000035e200007135000009af008004d7800002f1300006bc400001af100005e2600003c4d0000789a000047ac00tX0X1X2X3R1R2WS150008f9a00f100005eaf00006b6b0000896782214162a3a55f008f9a004563cb1b18ac7ac00260000d7780000e25e00004d474a2e7e119e94bb