祖冲之序列密码算法第1部分:算法描述1范围本部分描述了祖冲之序列密码算法,可用于指导祖冲之算法相关产品的研制、检测和使用。
2术语和约定以下术语和约定适用于本部分。
2.1比特bit二进制字符0和1称之为比特。
2.2字节byte由8个比特组成的比特串称之为字节。
2.3字word由2个以上(包含2个)比特组成的比特串称之为字。
本部分主要使用31比特字和32比特字。
2.4字表示word representation本部分字默认采用十进制表示。
当字采用其它进制表示时,总是在字的表示之前或之后添加指示符。
例如,前缀0x指示该字采用十六进制表示,后缀下角标2指示该字采用二进制表示。
2.5高低位顺序bit ordering本部分规定字的最高位总是位于字表示中的最左边,最低位总是位于字表示中的最右边。
3符号和缩略语3.1运算符+ 算术加法运算mod 整数取余运算⨁按比特位逐位异或运算⊞模232加法运算‖字符串连接符∙H取字的最高16比特∙L取字的最低16比特<<<k 32比特字左循环移k位>>k 32比特字右移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。
图 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=W >> 1。
在初始化模式下,LFSR计算过程如下:LFSRWithInitialisationMode(u){(1)v = 215s15 +217 s13 + 221s10 + 220s4 + (1 + 28)s0 mod (231-1);(2)s16=(v+u) mod (231-1);(3)如果s16=0,则置s16=231-1;(4)(s1, s2, …, s15, s16) (s0, s1, …, s14, s15)。
}4.2.3 工作模式在工作模式下,LFSR不接收任何输入。
其计算过程如下:LFSRWithWorkMode(){(1)s16 = 215 s15 +217s13 + 221 s10 + 220s4 + (1 + 28)s0 mod (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⊕ (X <<< 2) ⊕ (X <<< 10) ⊕ (X <<< 18) ⊕ (X <<< 24),L2(X) = X⊕ (X <<< 8) ⊕ (X <<< 14) ⊕ (X <<< 22) ⊕ (X <<< 30)。
4.5密钥装入密钥装入过程将128比特的初始密钥k和128比特的初始向量iv扩展为16个31比特字作为LFSR 寄存器单元变量s0, s1, …, s15的初始状态。
设k和iv分别为k0‖k1‖……‖k15和iv0‖iv 1‖……‖iv 15,其中k i和iv i均为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,有s i = k i‖d i‖iv i。
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 (W >> 1)。
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()。
附录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,其中x i和y i均为8比特字节,i = 0, 1, 2, 3。
则有y i = S i(x i), i = 0, 1, 2, 3。
表1 S0盒表2 S1盒01(资料性附录)模231-1乘法和模231-1加法的实现B.1 模231-1乘法两个31比特字模231-1乘法可以快速实现。
特别地,当其中一个字具有较低的汉明重量时,可以通过31比特的循环移位运算和模231-1加法运算实现。
例如,计算ab mod(231-1),其中b=2i+2j+2k。
则ab mod(231-1) = (a <<<31i) + (a <<<31j) +(a <<<31k) mod(231-1),其中<<<31表示31比特左循环移位运算。
B.2 模231-1加法在32位处理平台上,两个31比特字a和b模231-1加法运算c =a + b mod(231-1)可以通过下面的两步计算实现:1)c = a + b;2)c = (c & 0x7FFFFFFF) + (c >> 31)。
附录C(资料性附录)算法计算实例C.1 测试向量1(全0)输入:密钥k: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00初始向量iv: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 输出:z1: 27bede74z2: 018082da初始化:有限状态机内部状态:R1 = 14cfd44cR2 = 8c6de800密钥流:C.2 测试向量2(全1)输入:密钥k: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff初始向量iv: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff 输出:z1: 0657cfa0z2: 7096398b初始化:线性反馈移位寄存器初态:R1 = b8017bd5R2 = 9ce2de5c密钥流:C.3 测试向量3(随机)输入:密钥k: 3d 4c 4b e9 6a 82 fd ae b5 8f 64 1d b1 7b 45 5b初始向量iv: 84 31 9a a8 de 69 15 ca 1f 6b da 6b fb d8 c7 66输出:z1: 14f1c272z2: 3279c419初始化:线性反馈移位寄存器初态:R1 = 860a7dfaR2 = bf0e0ffc密钥流:————————————参考文献[1]ETSI/SAGE TS 35.221. Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 &128-EIA3. Document 1: 128-EEA3 and 128-EIA3 Specification.[2]ETSI/SAGE TS 35.222. Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 &128-EIA3. Document 2: ZUC Specification.[3]ETSI/SAGE TS 35.223. Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 &128-EIA3. Document 3: Implementor's Test Data.[4]ETSI/SAGE TR 35.924. Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 &128-EIA3. Document 4: Design and Evaluation Report.祖冲之序列密码算法第2部分:基于祖冲之算法的机密性算法1 范围本部分描述了基于祖冲之算法的机密性算法。