在多变量公钥密码中，Rainbow签名是油醋签名家族的一员，可以被看成多层的UOV签名。

在Rainbow的所有安全方案中，本文选取了一种常用的方案Rainbow(10, 10, 4, 3, 10)作为硬件实现方案。它的安全级别达到${2^{80}}$，在多项式时间内无法被数学分析攻击。Rainbow(10, 10, 4, 3, 10)由4层油醋结构组成。本文选定的Rainbow签名方案的参数如表 1所示。签名生成包括第一次仿射变换、中心映射变换和第二次仿射变换，如图 1所示。

图  1  Rainbow签名生成过程

假定消息的散列值是$y({y_0}, {y_1}, \cdots , {y_{26}})$，它的长度是27字节，其中${y_0}, {y_1}, \cdots , {y_{26}}$是${\text{GF}}({2^8})$的元素。而且，签名是$x({x_0}, {x_1}, \cdots , {x_{36}})$，它的长度是37字节，其中${x_0}, {x_1}, \cdots , {x_{36}}$是${\text{GF}}({2^8})$的元素。

为了对消息的散列值$y({y_0}, {y_1}, \cdots , {y_{26}})$签名，需要进行如下计算：

式中，$F$是一个中心映射变换；${L_1}$和${L_2}$是两个可逆的仿射变换。

首先计算可逆仿射${L_1}$的逆变换：

$\bar y({\bar y_0}, {\bar y_1}, \cdots , {\bar y_{26}})$是可逆仿射变换的结果，$\bar y$的长度是27字节。${L_1}$的逆变换$L_1^{ - 1}$的形式为：

式中，$\mathit{\boldsymbol{A}}$是规模为$27 \times 27$的矩阵；$\mathit{\boldsymbol{b}}$是维度为$27$的向量，$\mathit{\boldsymbol{A}}$和$\mathit{\boldsymbol{b}}$都被当作密钥来运算。

求解F的逆变换，$\bar x = {F^{ - 1}}({\bar y_0}, {\bar y_1}, \cdots , {\bar y_{26}})$，获得$\bar x({\bar x_0}, {\bar x_1}, \cdots , {\bar x_{26}})$的数值，$\bar x$的长度是27字节。

中心映射变换F由27个多变量多次多项式$({f_0}, {f_1}, \cdots , {f_{26}})$组成，它有如下形式：

将$\bar y({\bar y_0}, {\bar y_1}, \cdots , {\bar y_{26}})$代入中心映射的变换中，它变成如下形式：

中心映射F是4层的油醋结构，由27个多变量多次多项式组成，即$({f_0}, {f_1}, \cdots , {f_{26}})$被分成4层：

${f_i}|i = 0, 1, \cdots , 9$，共10个多项式；

${f_i}|i = 10, 11, 12, 13$，共4个多项式；

${f_i}|i = 14, 15, 16$，共3个多项式；

${f_i}|i = 17, 18, \cdots , 26$，共10个多项式。

F的27个多变量多次多项式$({f_0}, {f_1}, \cdots , {f_{26}})$的定义为：

式中，${V_i}$是醋变量；${O_i}$是油变量；${O_i}{V_j}$是油变量和醋变量的组合；${V_i}{V_j}$是醋变量和醋变量的组合；${\alpha _{ij}}$、${\beta _{ij}}$、${\gamma _i}$、${\delta _i}$和$\eta $是多变量多次多项式的系数，被当作私钥使用，$\eta $是常数。

多变量多次多项式包括5项，最高次数不超过二次，若将醋变量的数值代入多变量多次多项式，它将变换成关于油变量的一次多项式。通过4层的多项式系数求值和求解线性方程组，计算获得$\bar x({\bar x_0}, {\bar x_1}, \cdots , {\bar x_{36}})$。

最后，将$\bar x({\bar x_0}, {\bar x_1}, \cdots , {\bar x_{36}})$的37个元素代入${L_2}$的逆变换${L_2}^{ - 1}$，计算逆变换得$x({x_0}, {x_1}, {x_2}, \cdots , {x_{36}})$，$x = {L_2}^{ - 1}({\bar x_0}, {\bar x_1}, \cdots , {\bar x_{36}})$。$L_2^{ - 1}$的形式是$x = \mathit{\boldsymbol{C}}\bar x + \mathit{\boldsymbol{d}}$。这里，$\mathit{\boldsymbol{C}}$是一个规模为$37 \times 37$的矩阵，$\mathit{\boldsymbol{d}}$是一个维度为$37$的向量，$\mathit{\boldsymbol{C}}$和$\mathit{\boldsymbol{d}}$都被当作私钥来运算。所以$x({x_0}, {x_1}, {x_2}, \cdots , {x_{36}})$是$y({y_0}, {y_1}, \cdots , {y_{26}})$的签名。

为了攻击的普遍性，Rainbow签名实现基于原始方案，不采用优化手段。本文利用状态机的方式实现Rainbow签名设计，使用硬件描述语言Verilog作为编程语言，Xilinx公司开发的FPGA(field- programmable gate array)工具ISE(integrated software environment)9.1作为编程工具，实现平台选取的是Xilinx FPGA。在FPGA测试通过后，将Verilog代码加载至Synopsis Design Compiler，签名所需时间为102.8 ${\rm{\mu s}}$，等效门数约为15 490。

Rainbow签名的仿射变换由矩阵向量乘法和向量加法组成，中心映射变换由求解线性方程组和多项式系数求值组成。

下面是有限域加法、乘法、求逆和高斯消元运算的具体实现细节。

选择的有限域是${\text{GF}}({2^8})$，域的不可约多项式是$f(x) = {x^8} + {x^6} + {x^3} + {x^2} + 1$；有限域加法使用${\text{GF}}({2^8})$的加法运算；有限域乘法使用多项式基的一般乘法。假定$a(x)$和$b(x)$是${\text{GF}}({2^8})$的元素，那么$c(x) = $ $(a(x) \times b(x))\, \bmod \, f(x)$是两者的乘积，其中$f(x)$是${\text{GF}}({2^8})$的不可约多项式。计算多项式相乘的结果，即${s_0}, {s_1}, \cdots , {s_{14}}$：

模运算为：

$c(x)({c_7}, {c_6}, {c_5}, \cdots , {c_0})$是$a(x)$和$b(x)$的乘积，本文采用了基于费马小定理的求逆方法，假定$\beta $是${\text{GF}}({2^8})$的元素，求逆过程如下：

计算${\beta ^2}, {\beta ^4}, {\beta ^8}, {\beta ^{16}}, {\beta ^{32}}, {\beta ^{64}}$和${\beta ^{128}}$可以并行进行，${\beta ^{ - 1}}$是它们的乘积；需要求解$4$个线性方程组，这些方程组的系数矩阵的规模分别是$10 \times 10$、$4 \times 4$、$3 \times 3$和$10 \times 10$。本文采取有限域的高斯消元法作为求解线性方程组的方法：

在主元所在列选择一个非零元素作为主元；交换当前行与主元所在行的所有的元素，若当前行是主元所在行则不交换；对当前行所有的元素做归一操作；对当前行下面所有的元素做消元操作；结束本次迭代，重新选取下一列开始下一轮迭代；直到所有迭代完成，系数矩阵成为一个等效的上三角矩阵；接着使用回溯替代的方法对增广矩阵进行替代；完成回溯替代后，增广矩阵的最右一列(即常数项组成的向量)是线性方程组的解。

现有技术中，较少对Rainbow签名进行侧信道安全性分析，在一定程度上阻碍了Rainbow签名的广泛应用。针对Rainbow的侧信道分析可以分为对仿射变换${L_1}$、中心映射变换$F$、仿射变换${L_2}$的分析。

仿射变换${L_1}$：差分能量分析；中心映射变换$F$：故障分析结合差分能量分析；仿射变换${L_2}$：差分能量分析。图 2对Rainbow的分析方法基于差分能量分析和故障分析。

图  2  Rainbow分析过程

对于第一个仿射变换，采用差分能量分析。假定$y({y_0}, {y_1}, \cdots , {y_{m - 1}})$是待签名的消息，$\bar y({\bar y_0}, {\bar y_1}, \cdots , {\bar y_{m - 1}})$是仿射变换$\bar y{\rm{ = }}\mathit{\boldsymbol{A}}y + \mathit{\boldsymbol{b}}$的结果，$\mathit{\boldsymbol{A}}$是$m \times m$的矩阵，$\mathit{\boldsymbol{b}}$是长度为$m$的向量，$\mathit{\boldsymbol{A}}$和$\mathit{\boldsymbol{b}}$是密钥。以计算${a'_{ij}} = {a_{ij}} \times {y_i}$为例，${a_{ij}}$是$\mathit{\boldsymbol{A}}$第$i$行第$j$列的元素(密钥)，${y_i}$是$y$第$i$个元素(消息)，${a'_{ij}}$是有限域乘法结果，均是有限域${\text{GF}}({2^k})$的元素。建立基于汉明距离的多比特差分能量分析模型(以下简称汉明距离模型)，那么攻击${a_{ij}}$的思路如下：

输入$N$个不同的消息，获得$N$条功耗曲线。令 $D = {y_i},R = {{a'}_{ij}}{\rm{,}}E = {a_{ij}} $ ，开始猜测密钥，范围是${\text{GF}}({2^k})$所有的元素。因为$E$是密钥的猜测值(已知)，$D$是消息的一个元素(已知)，$R$可以通过$R = E \times D$计算获得。基于$D$和$R$之间的汉明距离$H(D \oplus R)$，把$N$条功耗曲线分成两组：

对于每个猜测值计算$\Delta {\text{ = }}\frac{{\sum\limits_{{T_0}} {{t_i}} }}{{|{T_0}|}} - \frac{{\sum\limits_{{T_1}} {{t_i}} }}{{|{T_1}|}}$，$|{T_0}|$和$|{T_1}|$分别是${T_0}$和${T_1}$中功耗曲线的数量。${\Delta _i}$是对应猜测值${E_i}$的曲线，用${\text{ma}}{{\text{x}}_i}$标记第$i$条曲线的最大值(绝对值)。如果$({\text{ma}}{{\text{x}}_0}, {\text{ma}}{{\text{x}}_1}, \cdots )$集合的最大值是${\text{ma}}{{\text{x}}_j}$，那么它对应的猜测值是密钥的正确值。矩阵$\mathit{\boldsymbol{A}}$其他的元素可以用相同的方法攻击获得。

向量$\mathit{\boldsymbol{b}}$的攻击方法也可以采用汉明距离模型，以计算${b'_i} = {y'_i} + {b_i}$为例，向量${\mathit{\boldsymbol{y'}}}$是$\mathit{\boldsymbol{y'}}{\rm{ = }}\mathit{\boldsymbol{A}}y$的运算结果，${y'_i}$是${\mathit{\boldsymbol{y'}}}$的第$i$个元素(可以计算得出)，${b_i}$是向量$\mathit{\boldsymbol{b}}$的第$i$个元素(密钥)，${b'_i}$是有限域加法结果。攻击${b_i}$的思路如下：

令 $D = {{y'}_i},R = {{b'}_i}{\rm{,}}E = {b_i} $ ，开始猜测密钥。因为$E$是密钥的猜测值(已知)，$D$是与消息相关的运算结果(已知)，$R$可以通过$R = E \times D$计算。对功耗曲线进行差分运算。对于密钥的每个猜测值${E_i}$，计算曲线${\Delta _i}$，用${\text{ma}}{{\text{x}}_i}$标记第$i$条曲线的最大值。如果$({\text{ma}}{{\text{x}}_0}, {\text{ma}}{{\text{x}}_1}, \cdots )$集合中的最大值是${\text{ma}}{{\text{x}}_j}$，则它对应的猜测值${E_j}$是密钥的正确值。向量$\mathit{\boldsymbol{b}}$其他的元素可以采用相同的方法攻击获得。

对于中心映射变换，建立基于故障分析的模型。假定${x_0}, {x_1}, \cdots , {x_{n - 1}}$是Rainbow在中心映射变换时需要随机生成的变量，使用强光或涡流，基于BSR(bit set or reset)方法引入故障，使这些变量固定成预设值${c_0}, {c_1}, \cdots , {c_{n - 1}}$，即${x_o} \to {c_0}, {x_1} \to {c_1}, \cdots , {x_{n - 1}} \to {c_{n - 1}}$。这样，签名在每次运行时，产生的随机变量是预设值。

中心映射变换$\bar x = {F^{ - 1}}({\bar y_0}, {\bar y_1}, \cdots , {\bar y_{m - 1}})$，$\bar y({\bar y_0}, {\bar y_1}, \cdots , {\bar y_{m - 1}})$是仿射变换$\bar y{\rm{ = }}\mathit{\boldsymbol{A}}y + \mathit{\boldsymbol{b}}$的结果。中心映射$F$是由多个多变量多项式组成的方程$\;\sum {{\alpha _{ij}}{V_j}{O_i}} + \sum {{\delta _i}{O_i}} + \sum {{\beta _{ij}}{V_i}{V_j}} + \sum {{\gamma _i}{V_i}} + \eta = {\bar y_k}$，将通过运算简化成关于$O$的一次多项式，$O$和$V$是两类变量，${\alpha _{ij}}$、${\beta _{ij}}$、${\gamma _i}$、${\delta _i}$和$\eta $是系数(密钥)。攻击思路如下：

对于密钥${\alpha _{ij}}$和运算${V'_j} = {\alpha _{ij}}{V_j}$，令 $D = {V_j},R = {V_j}^\prime {\rm{,}}E = {a_{ij}} $ ，通过故障攻击，将${V_j}$固定为预设值，再基于$H(D \oplus R)$采用汉明距离模型分析密钥；

对于密钥${\delta _i}$和运算${V''_j} = {\alpha _{ij}}{V_j} + {\delta _i}$，因为${V'_j} = {\alpha _{ij}}{V_j}$，令 $D = {V_j}^\prime ,R = {V_j}^{\prime \prime },E = {\delta _i}$ ，通过故障攻击，将${V_j}$固定为预设值，再基于$H(D \oplus R)$采用汉明距离模型分析密钥；

对于密钥${\beta _{ij}}$和运算${V'_i} = {\beta _{ij}}{V_i}$，令 $ D = {V_i},R = {V_i}^\prime ,E = {\beta _{ij}}$ ，通过故障攻击，将${V_i}$固定为预设值，再基于$H(D \oplus R)$采用汉明距离模型分析密钥；

对于密钥${\gamma _i}$和运算${V''_i} = {\gamma _i}{V_i}$，令 $D = {V_i},R = {V_i}^{\prime \prime },E = {\gamma _i} $ ，通过故障攻击，将${V_i}$固定为预设值，再基于$H(D \oplus R)$采用汉明距离模型分析密钥；

对于密钥$\eta $和运算${\bar y'_k} = \eta + {\bar y_k}$，令 $D = {{\bar y}_k}{\rm{, }}R = {{\bar y}_k}^\prime {\rm{, }}E = \eta $ ，通过输入不同的消息，计算${\bar y_k}$的值，再基于$H(D \oplus R)$采用汉明距离模型分析密钥。

根据上述分析，中心映射变换通过建立故障分析模型，固定随机变量，结合差分能量分析，攻击获得全部密钥。

对于第二个仿射变换，采用差分能量分析。${L_2}^{ - 1}({x_0}, {x_1}, \cdots , {x_{n - 1}}) = ({\bar x_0}, {\bar x_1}, \cdots , {\bar x_{n - 1}})$是第二个仿射变换，$\bar x({\bar x_0}, {\bar x_1}, \cdots , {\bar x_{n - 1}})$是中心映射变换结果，$x({x_0}, {x_1}, \cdots , {x_{n - 1}})$是签名。仿射变换${L_2}$的形式是$x = \mathit{\boldsymbol{C}}\bar x + \mathit{\boldsymbol{d}}$，$\mathit{\boldsymbol{C}}$是$n \times n$的矩阵，$\mathit{\boldsymbol{d}}$是长度为n的向量，$\mathit{\boldsymbol{C}}$和$\mathit{\boldsymbol{d}}$是密钥。

以计算${c'_{ij}} = {c_{ij}} \times {\bar x_i}$为例，${c_{ij}}$是$\mathit{\boldsymbol{C}}$第$i$行第$j$列的元素(密钥)，${\bar x_i}$是$\bar x$第$i$个元素(可以计算得)，${c'_{ij}}$是有限域乘法结果，均是有限域${\text{GF}}({2^k})$的元素。攻击${c_{ij}}$的思路如下：

令 $D{\rm{ = }}\bar x,{\rm{ }}R = {c_{ij}}^\prime {\rm{,}}E = {c_{ij}} $ ，开始猜测密钥。因为$E$是密钥的猜测值(已知)，$D$是已经计算完成的运算结果(已知)，$R$可以通过$R = E \times D$计算。对功耗曲线进行差分运算。对于密钥的每个猜测值${E_i}$，计算曲线${\Delta _i}$，用${\text{ma}}{{\text{x}}_i}$标记第$i$条曲线的最大值。如果$({\text{ma}}{{\text{x}}_0}, {\text{ma}}{{\text{x}}_1}, \cdots )$集合中的最大值是${\text{ma}}{{\text{x}}_j}$，则它对应的猜测值${E_j}$是密钥的正确值。矩阵$\mathit{\boldsymbol{C}}$其他的元素可以用相同的方法攻击获得。

向量$\mathit{\boldsymbol{d}}$的攻击方法也可以采用汉明距离模型，以计算${d'_i} = {x'_i} + {d_i}$为例，向量${\mathit{\boldsymbol{x'}}}$是$\mathit{\boldsymbol{x'}}{\rm{ = }}\mathit{\boldsymbol{C}}\bar x$的运算结果，${x'_i}$是${\mathit{\boldsymbol{x'}}}$的第$i$个元素(可以计算得出)，${d_i}$是向量$\mathit{\boldsymbol{d}}$的第$i$个元素(密钥)，${d'_i}$是有限域加法结果。攻击${d_i}$的思路如下：

令 $D{\rm{ = }}{x_i}^\prime ,{\rm{ }}R = {d_i}^\prime {\rm{,}}E = {d_i} $ ，开始猜测密钥。因为$E$是密钥的猜测值(已知)，$D$是与消息相关的运算结果(已知)，$R$可以通过$R = E \times D$计算。对功耗曲线进行差分运算。对于密钥的每个猜测值${E_i}$，计算曲线${\Delta _i}$，用${\text{ma}}{{\text{x}}_i}$标记第$i$条曲线的最大值。如果$({\text{ma}}{{\text{x}}_0}, {\text{ma}}{{\text{x}}_1}, \cdots )$集合中的最大值是${\text{ma}}{{\text{x}}_j}$，则它对应的猜测值${E_j}$是密钥的正确值。向量$\mathit{\boldsymbol{d}}$其他的元素可以采用相同的方法攻击获得。

至此，完成了所有密钥的分析。

1) 依据第2节描述的Rainbow签名算法，使用Verilog编程语言实现了签名电路，通过Xilinx的FPGA EDA工具ISE软件，下载至Xilinx FPGA开发板上验证签名过程。

2) 在FPGA测试通过后，将Verilog代码加载至安装在Redhat操作系统上的Synopsis Design Compiler编译环境，编译运行。

3) 将Synopsis Design Compiler生成的电路文件加载至ModelSim(Mentor的VHDL和Verilog混合评估器)仿真，PrimeTime(Synopsys的电路功耗评估工具)评估功耗。

通过输入2 000条消息，进行Rainbow签名，使用ModelSim仿真，通过PrimeTime进行功耗采集，获得2 000条功耗曲线。然后，基于侧信道攻击模型，采用计算机集群，建立分布式功耗分析平台并分析功耗。首先，构建4个集合：功耗曲线集合、密钥运算集合、密钥时间集合、密钥猜测值集合。再基于密钥时间集合将功耗曲线集合中的曲线分成多个时间段，每个时间段应包含尽可能少的密钥运算，每个时间段的曲线各自组成一个集合；基于密钥运算集合，为每个时间段曲线集合限定参与运算的密钥；为每个密钥在密钥猜测值集合内猜测一个的值，基于汉明距离模型分析功耗，若猜测值在最后计算的曲线对应位置出现尖峰，则将该值记录为该密钥的分析结果。

通过以上方法，使用分布式功耗分析平台分析获得Rainbow的所有密钥的分析结果，经过验证全部正确，证明本文的实验能够完全攻破Rainbow签名。实验流程如图 3所示。

图  3  实验过程

本文提出了一种基于差分能量分析和故障分析的侧信道分析算法，将Rainbow作为目标，实施侧信道攻击。故障分析用于固定Rainbow的中心映射变换的随机变量，结合差分能量分析可攻击Rainbow所有的密钥。实现了Rainbow签名电路，然后使用Synopsis Prime Time进行功耗采集，对采集的2 000条功耗曲线进行分析和计算，获取了所有的密钥。实验结果表明了需要对Rainbow进行侧信道攻击保护。在未来的工作中，将设计基于掩码或隐藏的方法对Rainbow进行保护。