非线性序列

• 密钥流生成器可分解为驱动子系统和非线性组合子系统
  • 驱动子系统常用一个或多个线性反馈移位寄存器来实现
  • 非线性组合子系统用非线性组合函数F来实现
  • 为了使密钥流生成器输出的二元序列尽可能复杂，也应保证其周期尽可能大、线性复杂度和不可预测性尽可能高
    

    Geffe序列生成器

• Geffe序列生成器由3个LFSR组成，其中LFSR2作为控制生成器使用
• 当LFSR2输出1时，LFSR2与LFSR1相连接
• 当LFSR2输出0时，LFSR2与LFSR3相连接
  
  
  若设LFSRi的输出序列为$\{ {a_k}^{(i)}(i = 1, 2, 3) \}$，则输出序列$\{ b_k \}$可以表示为：
  $$b_k = {a_k}^{(1)}{a_k}^{(2)} + {a_k}^{(3)}\overline{ {a_k}^{(2)}} = {a_k}^{(1)}{a_k}^{(2)} + {a_k}^{(3)}{a_k}^{(2)} + {a_k}^{(3)}$$
  设LFSRi的特征多项式分别为$n_i$次本原多项式，且$n_i$两两互素，则Geffe序列的周期为：$\prod \limits_{i = 1}^3 (2^{n_i} - 1)$，线性复杂度：$(n_1 + n_3)n_2 + n_3$。
  Geffe序列的周期实现了极大化，且0与1之间的分布大体上是平衡的。

  J-K触发器

  J-K触发器如图所示，它的两个输入端分别用J和K表示，其输出$c_k$不仅依赖于输入，还依赖于前一个输出位$c_{k-1}$，即：
  $$c_k = \overline{(x_1 + x_2)}c_{k-1} + x_1$$。
  
  其中$x_1$和$x_2$分别是J和K端的输入。由此可得J-K触发器的真值表，如下表所示：
  | J | K | $c_k$|
  | --- | --- | --- |
  | 0 | 0 | $c_{k-1}$ |
  | 0 | 1 | 0 |
  | 1 | 0 | 1 |
  | 1 | 1 | $\overline{c_{k-1}}$ |

  利用J-K触发器的非线性序列生成器

  
  $$ \{ a_k \}: m级m序列 \\ \{ b_k \}: n级m序列 \\ c_k = \overline{(a_k + b_k)}c_{k - 1} + a_k = (a_k + b_k + 1)c_{k - 1} + a_k $$
  当m与n互素且$a_0 + b_0 = 1$时，序列$\{ c_k \}$的周期为$(2^m - 1)(2^n - 1)$。

  J-K触发器的缺陷

  由$c_k = (a_k + b_k + 1)c_{k - 1} + a_k$可得：
  $$ c_k = \left \{ \begin{array}{c} a_k, & c_{k - 1} = 0 \\ \overline{b_k}, & c_{k - 1} = 1 \end{array} \right . $$
• 如果知道$\{ c_k \}$中相邻位的值$c_{k - 1}$和$c_k$，就可以推断出$a_k$和$b_k$中的一个。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列$\{ a_k \}$和$\{ b_k \}$。
• 为了克服上述缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为Pless生成器。

  Pless生成器

  Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如图所示：
  

  钟控序列生成器

  钟控序列生成器模型

  钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图所示，一个最简单钟控序列生成器：
  
• 假设LFSR1和LFSR2分别输出序列$\{ a_k \}$和$\{ b_k \}$，其周期分别为$p_1$和$p_2$。
• 当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。
• 当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2。因此LFSR2重复输出前一位。

  钟控序列生成器周期

  假设LFSR1和LFSR2分别输出序列$\{ a_k \}$和$\{ b_k \}$，其周期分别为$p_1$和$p_2$。假设钟控序列$\{ c_k \}$的周期为$p$，可得如下关系：
  $$p = \frac{p_1p_2}{gcd(w_1, p_2)}, 其中w_1 = \sum^{p_1 - 1}_{i = 0}a_i$$
• $c_k$的一个周期至少是LFSR1和LFSR2同时回到初始状态的时刻
  • 显然当运行$p_1 \times p_2$个节拍后两个LFSR必然回到初态，因此周期至多是$p_1 \times p_2$
  • LFSR1运行一个周期，LFSR2运行$w_1 = dt$拍，$d = gcd(w_1, p_2)$
  • LFSR1运行$(p_2 / d)$个周期后，LFSR2刚好运行$dt \times p_2 / d = tp_2$拍，即t个周期，于是两个LFSR都回到初态，这时运行了$(p_2/d) \times p_1$个节拍
• 若$\{ a_k \}$和$\{ b_k \}$的极小特征多项式分别为$GF(2)$上的$m$和$n$次本原多项式$f_1(x)$和$f_2(x)$，且$m|n$。
  • 则$p_1 = 2^m - 1, p_2 = 2^n - 1$。
  • 而$w_1$为$\{ a_k \}$一个周期内1的个数，因此$w_1 = 2^{m - 1}$。
  • 故$gcd(w_1. p_2) = 1$，所以$p = p_1p_2 = (2^m - 1)(2^n - 1)$。

    钟控序列的线性复杂度

• 可推导出$\{ a_k \}$的线性复杂度为$n(2^m - 1)$，极小特征多项式为$f_2(x^{2^m - 1})$
  • 其对应的LFSR2的抽头每隔周期$p_1 = 2^m - 1$一个，这样，参与运算的每个抽头对应的状态的节奏相同，从而相当于对LFSR2序列进行每$2^m - 1$拍的抽样序列(不计由于LFSR1的0游程而产生的重复)，这个序列只是LFSR2的平移和按照LFSR1中的0游程进行迟延，而抽头应该与LFSR2的节奏一致，所以其极小多项式和线性复杂度如上

    A5流密码

    A5流密码算法的基本用法

    A5/1流密码算法的基本用法

• 用于蜂窝式移动电话系统语音和数字加密。
• A5/1算法用于用户的手机到基站之间的通信加密，通信内容到基站后先解密变成明文，然后再进行基站到基站之间、以及基站到用户手机之间的信息加密，完成通信内容在通信过程的加密保护
• 应用环节
  • 只需考察用户A到基站1之间通信内容的加解密，中间消息的传送由基站到基站之间的加密完成，而接收方用户B对消息的加解密与用户A到基站1之间的通信完全类似，只不过是用户B先解密消息。
• 基本密钥$K_{A1}$
  • 基本密钥$K_{A1}$：预置在SIM卡中，与基站1共享。
  • 生存期：一旦植入SIM卡将不再改变。
  • 用途：用来分配用户和基站之间的会话密钥
• 会话密钥k
  • 产生方式：在每次会话时，基站产生一个64比特的随机数k。
  • 分配方式：利用基本密钥$K_{A1}$，使用其它密码算法将k加密传给用户手机。
  • 生存期：仅用于一次通话时间。
• 明文处理
  • 按每帧228比特分为若干帧后逐帧加密，每帧处理方式相同。
• 加密方式
  • 加密：$E_k(M) = E_{k1}(M_1)E_{k2}(M_2)E_{k3}(M_3)···$
  • 一次通话使用一个会话密钥，对每帧使用不同的帧密钥
  • 帧会话密钥：帧序号，长度为22比特
  • 帧会话密钥共产生228比特密钥流，实现对本帧228比特通信数据的加解密
  • 明密结合方式：逐位异或
  • 一次通话量：至多$2^{22}$帧数据，约$0.89 \times 2^{30}$比特。

    A5/1序列密码算法中的线性反馈移位寄存器

    算法使用3个级数为19、22和23的本原移存器。
    
    注：A5/1算法中，LFSR的移位方式是左移方式。 各寄存器的编号从第0级编号
    到第n-1级。

    算法初始化

    初始化是利用一次通话的会话密钥k和帧序号设定三个移存器的起点，即初始状态。
• Step 1：将三个LFSR的初态都设置为全零向量；
• Step 2：(密钥参与) 三个LFSR都规则动作64次，每次动作1步。
  • 在第i步动作时，三个LFSR的反馈内容都首先与密钥的第i比特异或，并将异或结果作为LFSR反馈的内容

    帧序号参与

• Step 3：(帧序号参与) 三个LFSR都规则动作22次，每次动作1步。在第i步动作时，三个LFSR的反馈内容都首先与帧序号的第i比特异或，并将异或的结果作为LFSR反馈的内容；帧序号比特的序号是从最低位编到最高位。

帧序号参与方式：与密钥参与方式相同，不同的明文数据帧按顺序编号，每个编号为22比特。
记帧序号为：
$$ T_0 = t_{22}t_{21}...t_1 = 00...00 \\ T_1 = t_{22}t_{21}...t_1 = 00...01 \\ ...... $$
帧密钥参与的目的：对不同的帧设置不同的帧会话密钥，保证对每帧以不同的起点生成密钥流，尽可能避免密钥重用。

A5流密码算法的基本原理

密钥流生成与加解密

• A5算法中，采用钟控方式控制3个LFSR来产生密钥流。
• 钟控信号$x_1x_2x_3$的采取：$x_1$取自LFSR-1第9级； $x_2$取自LFSR-2第11级；$x_3$取自LFSR-3第11级 。
• 控制方式：采用多项式$g(x) = x_1x_2 + x_2x_3 + x_3x_1$来确定，取钟控信号和多项式值相同的进行移位，不同的就不动。

关于加密

• Step 4：三个LFSR以钟控方式连续动作100次，但不输出密钥流；
• Step 5：三个LFSR以钟控方式连续动作114次，在每次动作后，三个LFSR都将最高位寄存器中的值输出，这三个比特的异或就是当前时刻输出的1比特密钥。
  • 连续动作114步，共输出114比特密钥流，用于对用户手机到基站传送的114比特数据的加密
    $$加密方式：c_i = m_i \oplus d_i; i = 1, 2,..., 114$$

    关于解密

• Step 6：三个LFSR以钟控方式连续动作100次，但不输出密钥流；
• Step 7：三个LFSR以钟控方式连续动作114次，在每次动作后，三个LFSR都将最高级寄存器中的值输出，这三个比特的模2和就是当前时刻输出的1比特密钥流。
  • 连续动作114步，共输出114比特密钥流，这114比特用于对基站到用户手机传送的114比特数据的解密
    $$解密方式：m_i^{'} = c_i^{'} \oplus d_i; i = 115, 116,..., 228$$

    A5/1算法的弱点

• 移位寄存器太短容易遭受穷举攻击
  • A5/1算法把主密钥作为算法中三个寄存器的初始值，长度为64比特。如果利用已知明文攻击，只需要知道其中两个寄存器的初始值，就可以计算出另一个寄存器的初始值，这只需要$2^{40}$步就可以得出寄存器LFSR-1和LFSR-2的结构。
• 事实上，A5/1加密算法中存在严重的安全问题
  • 利用了GSM通信加密中的两个安全漏洞，可以通过离线迭代计算生成一个彩虹表，它包含有密钥和其相对应的输出密码。这个彩虹表的大小为984GB。得到了彩虹表之后，安全专家就可以在短短的九秒内确定用于加密通信数据的密钥

    密钥流生成器的基本原则

    设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则：

1. 长周期。
2. 高线性复杂度(用最少的移位寄存器来实现)。
3. 统计性能良好。
4. 足够的“混乱”。
5. 足够的“扩散”。
6. 抵抗不同形式的攻击。

   祖冲之序列密码算法（ZUC）

• ZUC 算法最初是面向4G LTE 空口加密设计的序列密码算法
• 2011年9月被3GPP LTE 采纳为国际加密标准（3GPP TS 33.401）
• 2012年3月，发布为国家密码行业标准GM/T0001-2012
• 2016年10月，发布为国家标准GB/T 33133-2016
• ZUC 算法目前主要用于通信领域
• ZUC算法是一个基于字设计的同步序列密码算法
  • 种子密钥SK和初始向量IV的长度均为128比特
  • 在SK和IV的控制下，每拍输出一个32比特字
• 标准起草人：冯登国、林东岱、冯秀涛、周春芳

  算法中的符号及含义

  数值表示

  文中整数如果不加特殊说明都为十进制，如果有前缀“0x”则表示十六进制，如
  果有下标“2”则表示二进制。
  例：整数$a$可以有以下不同数制表示形式：
  $$ \begin{aligned} a & = 1234567890 \hspace{1em} 十进制表示 \\ & = 0x499602D2 \hspace{1em} 十六进制表示 \\ & = 1001001100101100000001011010010_2 \hspace{1em} 二进制表示 \end{aligned} $$

  数据位序

  文中所有数据的最高位（或字节）在左边，最低位（或字节）在右边。如$a = 1001001100101100000001011010010_2$，$a$的最高位为其最左边一位1，$a$的最低位为其最右边一位0。

  运算符表示

  | 运算符 | 含义 |
  | --- | --- |
  | $+$ | 两个整数相加 |
  | $ab$ | 两个整数$a$和$b$相乘 |
  | $=$ | 赋值运算 |
  | $mod$ | 整数取模 |
  | $\oplus$ | 整数间逐比特异或（模2加） |
  | $\boxed{+}$ | 模$2^{32}$加 |
  | $a\|\|b$ | 串$a$和$b$级联 |
  | $a_H$ | 整数$a$的高（最左）16位 |
  | $a_L$ | 整数$a$的低（最右）16位 |
  | $a<<| $a>>1$ | $a$右移1位 |
  | $(a_1, a_2,..., a_n) \rightarrow (b_1, b_2,..., b_n)$ | $a_i$到$b_i$并行赋值 |

  ZUC算法结构

  

  线性反馈移位寄存器

  线性反馈移位寄存器（LFSR）由16个31比特寄存器单元$s_0, s_1,..., s_{15}$组成，每个单元在集合$\{ 1, 2, 3,...,2^{31} - 1 \}$中取值。
  线性反馈移位寄存器的特征多项式是有限域$GF(2^{31} - 1)$上的16次本原多项式:
  $$p(x) = x^{16} - 2^{15}x^{15} - 2^{17}x^{13} - 2^{21}x^{10} - 2^{20}x^{4} - (2^8 + 1)$$
  其输出为有限域$GF(2^{31} - 1)$上的m序列，具有良好的随机性。
  线性反馈移位寄存器的运行模式有两种：初始化模式和工作模式。

  初始化模式

  在初始化模式中，LFSR接收一个31比特字$u$，$u$是由非线性函数$F$的32比特输出$W$通过舍弃最低位比特得到，即$u = W>>1$。计算过程如下：
  LFSRWithInitialisationMode($u$)
  {
• $v = 2^{15}s_{15} + 2^{17}s_{13} + 2^{21}s_{10} + 2^{20}s_{4} + (1 + 2^8)s_0 \ mod(2^{31} - 1)$
• $s_{16} = (v + u)mod(2^{31} - 1)$
• 如果$s_{16} = 0$，则置$s_{16} = 2^{31} - 1$
• $(s_1, s_2,..., s_{16}) \rightarrow (s_0, s_1,..., s_{15})$

}

工作模式

在工作模式下，LFSR没有输入。计算过程如下：
LFSRWithWorkMode()
{

• $s_{16} = 2^{15}s_{15} + 2^{17}s_{13} + 2^{21}s_{10} + 2^{20}s_{4} + (1 + 2^8)s_0 \ mod(2^{31} - 1)$
• 如果$s_{16} = 0$，则置$s_{16} = 2^{31} - 1$
• $(s_1, s_2,..., s_{16}) \rightarrow (s_0, s_1,..., s_{15})$

}

比特重组

比特重组从LFSR的寄存器单元中抽取128比特组成4个32比特字$X_0, X_1, X_2, X_3$，其中前3个字将用于下层的非线性函数$F$，第4个字参与密钥流的计算。
具体计算过程如下：
BitReconstruction()
{

• $X_0 = s_{15H} || s_{14L}$；
• $X_1 = s_{11H} || s_{9L}$；
• $X_2 = s_{7H} || s_{5L}$；
• $X_3 = s_{2H} || s_{0L}$；

}

非线性函数$F$

非线性函数 有2个32比特长的存储单元$R_1$和$R_2$，其输入为来自上层比特重组的3个32比特字$X_0, X_1, X_2$，输出为一个32比特字$W$。因此，非线性函数$F$是一个把96比特压缩为32比特的一个非线性压缩函数。具体计算过程如下：
$F(X_0, X_1, X_2)$
{

• $W = (X_0 \oplus R_1) \boxed{+} R_2$
• $W_1 = R_1 \boxed{+} X_1$
• $W_2 = R_2 \boxed{+} X_2$
• $R_1 = S(L_1(W_{1L}||W_{2H}))$
• $R_2 = S(L_2(W_{2L}||W_{1H}))$

}

S盒

S盒：$32 \times 32$（即输入长和输出长都为32比特）的S盒由4个并置的$8 \times 8$的S盒构成，即
$$S = (S_0, S_1, S_2, S_3)$$
其中$S_2 = S_0, S_3 = S_1$,于是有：
$$S = (S_0, S_1, S_0, S_1)$$

线性变换

线性变换$L_1$和$L_2$：$L_1$和$L_2$为32比特线性变换，定义如下：
$$ R(t) = \left \{ \begin{array}{c} L_1(X) = X \oplus (X <<< 2) \oplus (X <<< 10) \oplus (X <<< 18) \oplus (X <<< 24) \\ L_2(X) = X \oplus (X <<< 8) \oplus (X <<< 14) \oplus (X <<< 22) \oplus (X <<< 30) \end{array} \right . $$
其中符号$a<<非线性函数$F$输出的$W$与比特重组（BR）输出的$X_3$异或，形成输出密钥序列$Z$。

密钥装载

密钥载入过程将128比特的初始密钥$k$和128比特的初始向量$IV$扩展为16个31比特长的整数，作为LFSR寄存器单元$s_0, s_1,..., s_{15}$的初始状态。
设$k$和$IV$分别为：
$$k = k_0 || k_1 || \cdots || k_{15}$$
和
$$IV = iv_0 || iv_1 || \cdots || iv_{15}$$
其中，$k_i$和$iv_i$均为8比特长字节，$0 \le i \le 15$。

密钥装载步骤

• 设D为240比特的常量，可按如下方式分成16个15比特的自创：
  $$D = d_0 || d_1 || \cdots || d_{15}$$
• 对$0 \le i \le 15$，取$s_i = k_i || d_i || iv_i$

  ZUC的运行

  算法运行有两个阶段：初始化阶段和工作阶段

  初始化阶段

  调用密钥装载过程，将128比特的初始密钥$k$和128比特的初始向量$IV$装入到LFSR的寄存器单元变量$s_0, s_1,..., s_{15}$中，作为LFSR的初态，并置非线性函数$F$中的32比特存储单元$R_1$和$R_2$全为0。
  然后重复执行以下过程32次：
• BitReconstruction()
• $W = F(X_0, X_1, X_2)$
• LFSRWithInitialisationMode($u$)

  工作阶段

  首先执行以下过程一次，并将$F$的输出$W$丢弃：
• BitReconstruction()
• $F(X_0, X_1, X_2)$
• LFSRWithWorkMode()

然后进入密钥输出阶段，其中每进行一次循环，执行以下过程一次，输出一个32比特的密钥字$Z$：

• BitReconstruction()
• $Z = F(X_0, X_1, X_2) \oplus X_3$
• LFSRWithWorkMode()

  基于祖冲之密码的机密性算法128-EEA3

  算法的输入与输出

  ZUC机密性算法输入参数表

算法工作流程

加解密算法流程如图所示：

初始化

初始化是指根据机密性密钥$CK$以及其他输入参数构造祖冲之算法的初始密钥$k$和初始向量$IV$。
把$CK$(128比特长)和$k$（128比特长）分别表示为16个字节：
$$ CK = CK[0] || CK[1] || CK[2] || \cdots || CK[15] \\ k = k[0] || k[1] || k[2] || \cdots || k[15] $$
令:
$$ k[i] = CK[i], i = 0, 1, 2,..., 15 $$
把计数器COUNT（32比特长）表示为4个字节：
$$COUNT = COUNT[0] || COUNT[1] || COUNT[2] || COUNT[3]$$
把IV（128比特长）表示为16个字节：
$$ IV = IV[0] || IV[1] || IV[2] || \cdots || IV[15], \\ \left \{ \begin{array}{l} IV[0] = COUNT[0], IV[1] = COUNT[1] \\ IV[2] = COUNT[2], IV[3] = COUNT[3] \\ IV[4] = BEARER || DIRECTION || 00_2 \\ IV[5] = IV[5] = IV[7] = 00000000_2 \\ IV[8] = IV[0], IV[9] = IV[1] \\ IV[10] = IV[2], IV[11] = IV[3] \\ IV[12] = IV[4], IV[13] = IV[5] \\ IV[14] = IV[6], IV[15] = IV[7] \\ \end{array} \right . $$

密钥流的产生

设消息长为LENGTH比特，由初始化算法得到的初始密钥$k$和初始向量$IV$，调用ZUC密码产生$L$个字（每个32比特长）的密钥，其中$L$为：
$$L = \left \lceil LENGTH / 32 \right \rceil $$
将生成的密钥流用比特串表示为$z[0], z[1],..., z[32 \times L - 1]$，其中$z[0]$为ZUC算法生成的第一个密钥字的最高位比特，$z[31]$为最低位比特，其他以此类推。

加解密

密钥流产生之后，数据的加解密就十分简单了。
设长度为 的输入消息的比特流为：
$$M = M[0] || M[1] || M[2] || \cdots || M[LENGTH - 1]$$
则输出的密文比特流为：
$$C = C[0] || C[1] || C[2] || \cdots || C[LENGTH - 1]$$
其中，$C[i] = M[i] \oplus z[i], i = 0, 1, 2,..., LENGTH - 1$。