ISSN 
-
公钥密码学是现代化信息社会的一个重要工具。由于Shor的量子计算机攻击[1]，基于大数分解和离散对数等数论困难问题的传统公钥密码体制的安全性受到了威胁，如RSA和ElGamal等。因此，有必要寻找基于其他困难问题的公钥密码体制来替代RSA和ElGamal。
寻找可替代的公钥密码系统已有一些研究，多变量公钥密码体制也是其中一种。典型的多变量公钥加密体制的设计方法主要有小域-大域方法和三角形逐步迭代方法两种。
小域-大域方法是多变量公钥密码体制的公钥映射定义在小域上，而中心映射定义在小域的某个扩域上。比较典型的有MI体制[2]、HFE(隐藏域方程)体制[3]和Square体制[4]。原始的MI加密体制被文献[5]利用线性化方程的攻击方法破解了。HFE体制[3]自1996年提出之后，一直受到人们的关注，目前大量的研究集中在HFE抵抗解方程攻击的复杂度估计以及合适的安全参数选择。Square体制[4]其中心映射为奇特征有限域上的平方函数。原始的Square体制被文献[6]利用差分攻击破解。文献[7]提出了双层Square体制和Square+方案来抵挡差分攻击。但是，文献[8]对利用精炼的MinRank攻击方法破解了这两个体制。三角形逐步迭代方法指的是体制的中心映射可逐步迭代进行求逆，其中较为典型的有MFE[9]、TTM[10]等。原始的MFE体制在2007年被文献[11]利用二阶线性化方程方法破解，因而是不安全的。TTM体制多数满足线性化方程，也是不安全的[12]。目前，已有的多变量公钥加密体制的安全性均有待研究。
2014年，文献[13]提出了一种新多变量公钥密码体制，该体制结合了小域-大域方法和三角形逐步迭代方法，具有较高的加密和解密效率。虽然该体制满足线性化方程，但是合适的参数选择可以抵挡线性化方程攻击，并且能够抵挡秩攻击和差分攻击等。
通过理论分析和实验验证，本文结合线性化方程攻击方法和差分攻击方法给出了文献[13]方案的破解，可恢复合法密文相应的明文。首先利用线性化方程方法对文献[13]公钥进行消元获得与Square体制的等价方案，然后，利用差分攻击找到该等价方案的等价密钥，从而恢复合法密文相应的明文。在普通PC机上，利用Magma实现并验证了破解的全过程。当q = 31，n = 73，l = 2，t = 3时，给定公钥，在计算复杂度为238次域GF(31)上运算的预计算基础上，恢复明文的计算复杂度约为233次域GF(31)上运算；当q = 31，n = 103，l = 2，t = 3时，给定公钥，在计算复杂度为242次域GF(31)上运算的预计算基础上，恢复明文的计算复杂度约为235次域GF(31)上运算。
-
令$\mathbb{K}={{F}_{q}}$是一个q元域，n和m是两个正整数。L1和L2分别是${{\mathbb{K}}^{n}} $和${{\mathbb{K}}^{m}} $上的两个随机选取的仿射变换，$x=({{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}})$为明文变量，$y=({{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{m}})$为密文变量。令：
$$\begin{align} &P:x\in {{\mathbb{K}}^{n}}\xrightarrow{{{L}_{1}}}u={{M}_{1}}x+{{c}_{1}}\xrightarrow{F}v=F(u) \\ &\xrightarrow{{{L}_{2}}}y={{M}_{2}}v+{{c}_{2}}\in {{\mathbb{K}}^{m}} \\ \end{align}$$ 函数$P={{L}_{2}}\circ F\circ {{L}_{1}}$的表达式为多变量公钥密码体制的公钥，通常为一组多变量二次多项式。L1和L2为体制的私钥。
-
一阶线性化方程形式如下：
$$ \sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{m}{{{a}_{ij}}{{x}_{i}}{{y}_{j}}}}+\sum\limits_{i}^{n}{{{b}_{i}}{{x}_{i}}}+\sum\limits_{i}^{m}{{{c}_{i}}{{y}_{i}}+d=0} $$ 式中，$x=({{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}})$为明文变量；$y=({{y}_{1}}, {{y}_{1}}, \cdots, {{y}_{m}})$为密文变量。给定合法密文${y}'=({{{y}'}_{1}}, {{{y}'}_{2}}, \cdots, {{{y}'}_{m}})$，将其代入上述方程，这些方程将变为明文变量的一次多项式方程，所以称为线性化方程，方程的阶定义为密文变量在方程中的最高次数。
线性化方程最早是Patarin提出用来破解MI体制，2007年，文献[11]将该方法推广提出了高阶线性化方程方法，并用来破解MFE体制。
-
公钥多项式P在点a处的差分为：
$$D{{P}_{a}}(X)=P(X+a)-P(a)-P(X)+P(0)$$ 作为一个二元映射$D{{P}_{a}}$：$(X, a)\to D{{P}_{a}}(X)$是一个对称双线性映射。
利用公钥函数差分的双线性性，可对公钥函数的构造进行分析。在多数情况下，差分攻击明文空间的一个不变子空间用来恢复体制的私钥。
-
Square公钥加密体制的中心映射为：
$$Y={{X}^{2}}$$ Square体制在2009年被差分攻击破解[6]。
-
令$k={\rm GF}(q)$是一个特征为奇素数p的q阶有限域，$q\equiv 3\bmod 4$，K是域k的$\frac{n+l}{t}$次扩域，t、n和l为正整数，满足$t|(n+l)$，且$\frac{n+l}{t}$是奇数。定义映射$\phi :K\to {{k}^{\frac{n+l}{t}}}$为域K到域k上的k-线性同构映射，即取K在k上的一组基$\{{{\theta }_{1}}, {{\theta }_{2}}, \cdots, {{\theta }_{\tfrac{n+l}{t}}}\}$，使得：
$$ \phi ({{a}_{1}}{{\theta }_{1}}+{{a}_{2}}{{\theta }_{2}}+\cdots +{{a}_{\tfrac{n+l}{t}}}{{\theta }_{\tfrac{n+l}{t}}})=({{a}_{1}}, {{a}_{2}}, \cdots, {{a}_{\tfrac{n+l}{t}}}) $$ 将$ \phi :K\to {{k}^{\frac{n+l}{t}}}$推广为k-线性同构$ \varphi :{{K}^{t}}\to {{k}^{n+l}}$。
新的多变量公钥加密函数$ P:{{k}^{n}}\to {{k}^{n+l}}$，定义为：
$$ \begin{matrix} ({{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{n+l}})=P({{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}})= \\ T\circ \varphi \circ F\circ {{\varphi }^{-1}}\circ {{U}^{-1}}({{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}})= \\ ({{f}_{1}}, {{f}_{2}}, \cdots, {{f}_{n+l}}) \\ \end{matrix} $$ 式中，${{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{n+l}}$为密文变量；${{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}}$为明文变量；${{f}_{1}}, {{f}_{2}}, \cdots, {{f}_{n+l}}\in k[{{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}}]$，
1) $F:{{K}^{t}}\to {{K}^{t}}$是该体制的中心映射，定义为：
$$ ({{Y}_{1}}, {{Y}_{2}}, \cdots, {{Y}_{t}})=(X_{1}^{2}, {{X}_{1}}{{X}_{2}}, \cdots {{X}_{t-1}}{{X}_{t}}) $$ 2) ${{U}^{-}}:{{k}^{n}}\to {{k}^{n+l}}$，定义为将可逆仿射$ U:{{k}^{n+l}}\to {{k}^{n+l}}$作用在向量$(\overbrace{0, \cdots, 0}^{l}, {{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}})$上。
3) $T:{{k}^{n+l}}\to {{k}^{n+l}}$，为可逆仿射变换。
该多变量公钥加密体制的公钥为函数P的表达式，私钥为两个可逆仿射变换T和U。具体的加密、解密过程详见文献[13]。
为了抵挡现有攻击，文献[13]建议参数q = 31，n = 73，l = 2，t = 3；q = 31，n = 103，l = 2，t = 3。
-
文献[13]指出，该方案虽然满足一阶线性化方程，但是应用线性化方程攻击方法之后并不能得到破解该方案合法密文相应的明文。同时该方案还可抵挡低秩攻击和差分攻击。
经过理论分析和实验验证，本节提出将线性化方程和差分攻击相结合的方法能够恢复合法密文相应的明文。
给定公钥$ ({{y}_{1}}, {{y}_{2}}\cdots, {{y}_{n+l}})=({{f}_{1}}, {{f}_{2}}, \cdots, {{f}_{n+l}})$，攻击的目标是求出合法密文$ ({{{y}'}_{1}}, {{{y}'}_{2}}\cdots, {{{y}'}_{n+l}})$相应的明文$({{{x}'}_{1}}, {{{x}'}_{2}}\cdots, {{{x}'}_{n}}) $，即求解以下方程组：
$$\left\{ \begin{align} &{{{{y}'}}_{1}}={{f}_{1}}({{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}}) \\ &{{{{y}'}}_{2}}={{f}_{2}}({{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}}) \\ &\quad \quad \vdots \\ &{{{{y}'}}_{n+l}}={{f}_{n+l}}({{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}}) \\ \end{align} \right.$$ (1) -
设${{Y}_{1}}, {{Y}_{2}}, \cdots, {{Y}_{t}}$和${{X}_{1}}, {{X}_{2}}, \cdots, {{X}_{t}}$是体制的中心映射的变量，即：
$$ \left\{ \begin{align} &{{Y}_{1}}=X_{1}^{2} \\ &{{Y}_{2}}={{X}_{1}}{{X}_{2}} \\ &~~~~~~\vdots \\ &{{Y}_{t}}={{X}_{t-1}}{{X}_{t}} \end{align} \right. $$ 由$ {{Y}_{1}}=X_{1}^{2}$，${{Y}_{2}}={{X}_{1}}{{X}_{2}}$，可得：
$${{X}_{1}}{{Y}_{2}}={{X}_{1}}{{X}_{1}}{{X}_{2}}={{Y}_{1}}{{X}_{2}}$$ 由${{Y}_{2}}={{X}_{1}}{{X}_{2}}$，${{Y}_{3}}={{X}_{2}}{{X}_{3}}$，可得：
$${{X}_{1}}{{Y}_{3}}={{X}_{1}}{{X}_{2}}{{X}_{3}}={{Y}_{2}}{{X}_{3}}$$ 同理，依次由$ {{Y}_{i-1}}={{X}_{i-2}}{{X}_{i-1}}$，$ {{Y}_{i}}={{X}_{i-1}}{{X}_{i}}$，可得：${{X}_{i-2}}{{Y}_{i}}={{Y}_{i-1}}{{X}_{i}} $，即可得如下方程组：
$$ \left\{ \begin{align} &{{X}_{1}}{{Y}_{2}}={{Y}_{1}}{{X}_{2}} \\ &{{X}_{1}}{{Y}_{3}}={{Y}_{2}}{{X}_{3}} \\ &~~~~~~~~~~~\vdots \\ &{{X}_{t-2}}{{Y}_{t}}={{Y}_{t-1}}{{X}_{t}} \end{align} \right. $$ (2) 方程组(2)共包含t-1个方程，这些方程显然是线性无关的。
将$ ({{Y}_{1}}, {{Y}_{2}}, \cdots, {{Y}_{t}})={{\varphi }^{-1}}\circ {{T}^{-1}}({{y}_{1}}, \cdots, {{y}_{n+l}})$，$ ({{X}_{1}}, $ $ {{X}_{2}}, \cdots, $${{X}_{t}})= $${{\varphi }^{-1}}\circ {{({{U}^{-}})}^{-1}}(0, \cdots, 0, {{x}_{1}}, {{x}_{2}}, $$\cdots, {{x}_{n}}) $代入方程组(2)中，可以得到$\frac{n+l}{t}(t-1)$个如下形式的方程：
$$ \sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n+l}{{{a}_{ij}}{{x}_{i}}{{y}_{j}}}}+\sum\limits_{i=1}^{n}{{{b}_{i}}{{x}_{i}}}+\sum\limits_{j=1}^{n+l}{{{c}_{j}}{{y}_{j}}}+d=0 $$ (3) 式中，方程的系数${{a}_{ij}}, {{b}_{i}}, {{c}_{j}}, d\in k$。这类方程对于明文变量$ {{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}}$是线性的，对于密文变量${{y}_{1}}, $ ${{y}_{2}}, \cdots, {{y}_{n+l}}$是一次的，这些方程即为一阶线性化方程。
为了找到所有的线性化方程，需要计算足够多明密对，并将这些明密对代入式(3)得到以系数${{a}_{ij}}, {{b}_{i}}, {{c}_{j}}, d$为未知数的线性方程组。令D为这个线性方程组解空间的维数，$ \{(a_{ij}^{(m)}, b_{i}^{(m)}, c_{j}^{(m)}, {{d}^{(m)}})$，$ 1\le m\le D\}$为其解空间的一组基。即得到了D个线性无关的一阶线性化方程，记这组方程为：
$$ \sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n+l}{a_{ij}^{(m)}{{x}_{i}}{{y}_{j}}}}+\sum\limits_{i=1}^{n}{b_{i}^{(m)}{{x}_{i}}}+\sum\limits_{j=1}^{n+l}{c_{j}^{(m)}{{y}_{j}}}+{{d}^{(m)}}=0 $$ (4) 以上步骤仅依赖于公钥，与要破解的合法密文无关。因此对于给定公钥，该步骤可以预计算。
-
给定的合法密文${y}'=({{{y}'}_{1}}, {{y}_{2}}, \cdots, {{{y}'}_{n+l}})$，将其代入式(4)中，可得到明文变量的线性方程组：
$$ \sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n+l}{a_{ij}^{(m)}{{x}_{i}}{{{{y}'}}_{j}}}}+\sum\limits_{i=1}^{n}{b_{i}^{(m)}{{x}_{i}}}+\sum\limits_{j=1}^{n+l}{c_{j}^{(m)}{{{{y}'}}_{j}}}+{{d}^{(m)}}=0 $$ (5) 设该线性方程组的解空间为V′，维数为D′。解该方程组，可将D′个明文变量用其余h=n−D′个明文变量线性表出，记h个变量为${{w}_{1}}, {{w}_{2}}, \cdots, {{w}_{h}}$。将上述D′个表达式代入原公钥中，可得到$n+l$个新的二次多项式，记为${{\tilde{f}}_{1}}({{w}_{1}}, {{w}_{2}}, \cdots, {{w}_{h}}), $$\cdots, $${{\tilde{f}}_{n+l}}({{w}_{1}}, {{w}_{2}}, \cdots, $${{w}_{h}})$。
令${{Y}_{j}}^{\prime }\ (1\le j\le t)$表示相应于给定合法密文${y}'=({{{y}'}_{1}}, {{{y}'}_{2}}, \cdots, {{{y}'}_{n+l}}) $的${{Y}_{j}}\ (1\le j\le t)$值，即$({{{Y}'}_{1}}, {{{Y}'}_{2}}, \cdots, {{{Y}'}_{t}})={{\varphi }^{-1}}\circ {{T}^{-1}}({{{y}'}_{1}}, {{{y}'}_{2}}, \cdots, $ ${{{y}'}_{n+l}})$。因为已经找到所有的线性化方程张成的线性空间的一组基，所以每一个线性化方程都是这组基的一个线性组合。而且这些方程中的变量yj由yj'替代时同样成立，并应用于方程组(2)，可知由方程组：
$$ \left\{ \begin{align} &{{X}_{1}}{{{{Y}'}}_{2}}={{{{Y}'}}_{1}}{{X}_{2}} \\ &{{X}_{1}}{{{{Y}'}}_{3}}={{{{Y}'}}_{2}}{{X}_{3}} \\ &\vdots \\ &{{X}_{t-2}}{{{{Y}'}}_{t}}={{{{Y}'}}_{t-1}}{{X}_{t}} \\ \end{align} \right. $$ (6) 得到的明文变量的线性方程都是式(5)的线性组合，也就是方程组(6)在V'上成立。
整理方程组(6)，可得：
$$ \left\{ \begin{array}{l} {{X}_{2}}=\frac{{{{{Y}'}}_{2}}}{{{{{Y}'}}_{1}}}{{X}_{1}} \\ {{X}_{3}}=\frac{{{{{Y}'}}_{3}}}{{{{{Y}'}}_{2}}}{{X}_{1}} \\ ~~~~~~~~\vdots \\ {{X}_{t}}=\left\{ \begin{array}{l} \frac{{{{{Y}'}}_{t}}}{{{{{Y}'}}_{t-1}}}\frac{{{{{Y}'}}_{t-2}}}{{{{{Y}'}}_{t-3}}}\cdots \frac{{{{{Y}'}}_{2}}}{{{{{Y}'}}_{1}}}{{X}_{1}}~~~t~{\rm 为偶数} \\ \frac{{{{{Y}'}}_{t}}}{{{{{Y}'}}_{t-1}}}\frac{{{{{Y}'}}_{t-2}}}{{{{{Y}'}}_{t-3}}}\cdots \frac{{{{{Y}'}}_{3}}}{{{{{Y}'}}_{2}}}{{X}_{1}}~~~t~{\rm 为奇数} \\ \end{array} \right.\\ \end{array} \right. $$ (7) 将式(7)代入原公钥的中心映射式(2)中，可得：
$$ \left\{ \begin{align} &{{Y}_{1}}=X_{1}^{2} \\ &{{Y}_{2}}=\frac{{{{{Y}'}}_{3}}}{{{{{Y}'}}_{2}}}X_{1}^{2} \\ &\vdots \\ &{{Y}_{t}}={{C}_{t}}X_{1}^{2} \\ \end{align} \right. $$ (8) 当t是偶数时，${{C}_{t}}=\tfrac{{{{{Y}'}}_{t}}}{{{{{Y}'}}_{t-1}}}\tfrac{{{{{Y}'}}_{t-2}}}{{{{{Y}'}}_{t-3}}}\cdots \tfrac{{{{{Y}'}}_{2}}}{{{{{Y}'}}_{1}}} $；当t为奇数时，${{C}_{t}}=\tfrac{{{{{Y}'}}_{t}}}{{{{{Y}'}}_{t-1}}}\tfrac{{{{{Y}'}}_{t-2}}}{{{{{Y}'}}_{t-3}}}\cdots \tfrac{{{{{Y}'}}_{3}}}{{{{{Y}'}}_{2}}}$。
由式(8)的表达式可知，消元后的公钥中至多含有$\tfrac{n+l}{t}$个明文变量，而且消元后的公钥中心映射等价于Square公钥密码体制的中心映射$Y={{X}^{2}}$。
文献[6]中利用Square体制公钥的差分性质，成功地找到了该体制的私钥，从而破解了该体制。
为了方便起见，下面将消元后的公钥记为$\bar{P}=\bar{T}\circ \bar{F}\circ \bar{U}$，其中$\bar{T}$和$\bar{U}$为域k上的仿射变换，中心映射为$\bar{F}(X)={{X}^{2}}$。
不失一般性，将消元后的公钥函数写成：
$$ \bar{P}(X)=\hat{T}(\hat{U}{{(X)}^{2}})+\hat{T}(u\cdot \hat{U}(X))+v $$ (9) 式中，$\hat{U}$和$\hat{T}$分别是仿射变换$\bar{U}$和$\bar{T}$的线性部分。令$u=\frac{1}{2}\sigma $，$v=\tau +T({{\sigma }^{2}})$，其中σ和τ是仿射变换$\bar{U}$和$\bar{T}$中两个常数向量。由于$\hat{U}$和$\hat{T}$是线性的，所以式(9)中的第一项是域k上的二次项，第二项是域k上的一次项，最后一项为域k上的常数项。更进一步，这些齐次项分别可以由公钥中的二次项、一次项和常数项得到，即：
$${{\bar{P}}_{2}}(X)=\hat{T}(\hat{U}{{(X)}^{2}}), {{\bar{P}}_{1}}(X)=\hat{T}(u\cdot \hat{U}(X)), {{\bar{P}}_{0}}(X)=v$$ 函数P在点a处的差分是指$D{{P}_{a}}(X)=P(X+$ $a)-P(a)-P(X)+P(0)$。采用类似的符号，消元后的公钥函数的差分映射为：
$$ D\bar{P}(X, Y)=\hat{T}(2\cdot \hat{U}(X)\cdot \hat{U}(Y)) $$ 考虑映射$D{{\bar{P}}_{y}}:X\mapsto D\bar{P}(X, y)$。因为$\hat{U}$是满秩的，其维数为$\tfrac{n+l}{t}$，因此任意选择一组线性无关向量${{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{\tfrac{n+l}{t}}} $，都可使得$D{{\bar{P}}_{{{y}_{1}}}}, D{{\bar{P}}_{{{y}_{2}}}}, \cdots, D{{\bar{P}}_{{{y}_{\tfrac{n+l}{t}}}}}$成为整个向量空间${{\left\{ D{{{\bar{P}}}_{z}} \right\}}_{z\in K}}$的一组基。可以选择一组映射$\mathit{\Delta } =\left\{ {{{\bar{P}}}_{1}} \right\}\bigcup {{\left\{ D{{{\bar{P}}}_{{{y}_{i}}}} \right\}}_{i=1, 2, \cdots, \tfrac{n+l}{t}}}$，每个映射都满足$\hat{T}\circ {{\mathit{\Lambda }}_{\alpha }}\circ \hat{U}$形式，${{\mathit{\mathit{\Lambda }}}_{\alpha }}$表示有限域K中乘以α的数乘。这组映射可以表示为:
$$\mathit{\Delta } ={{\left\{ \hat{T}\circ {{\mathit{\Lambda }}_{{{\lambda }_{i}}}}\circ \hat{U} \right\}}_{i=1, 2, \cdots, \tfrac{n+l}{t}+1}}$$ 其中，$ (\tfrac{n+l}{t}+1)$个${{\lambda }_{1}}, {{\lambda }_{2}}, \cdots, {{\lambda }_{\tfrac{n+l}{t}+1}}$的值是一组未知的但线性无关的。实际的攻击中，攻击者并不需要知道求出${{\lambda }_{i}}$的值，而是需要寻找一个线性映射L满足：
$$L\circ {{D}_{1}}={{D}_{2}}$$ 式中，${{D}_{1}}=\hat{T}\circ {{\mathit{\Lambda }}_{{{\lambda }_{1}}}}\circ \hat{U}$；${{D}_{2}}=\hat{T}\circ {{\mathit{\Lambda }}_{{{\lambda }_{2}}}}\circ \hat{U}\in \mathit{\Delta }$。寻找映射L是这部分攻击中最耗时的部分，详见文献[6]。
在找到符合条件的线性映射$L=T\circ {{\mathit{\Lambda }}_{\lambda }}\circ {{T}^{-1}} $后，求解线性方程组$\tilde{T}\circ L=\mathit{\Lambda }{}_{\lambda }\circ \tilde{T}$找到$\hat{T}$的等价表示，记为${{T}_{0}}$。如果a是一个随机选择的元素，$\hat{U}$的等价表示U0可如下求出：
$$\begin{align} &\hat{U}(a)=\sqrt{T_{0}^{-1}({{{\bar{P}}}_{2}}(a))}, {{u}_{0}}=\frac{1}{\hat{U}(a)}T_{0}^{-1}({{{\bar{P}}}_{1}}(a)) \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{U}_{0}}=\frac{1}{{{u}_{0}}}T_{0}^{-1}\circ {{{\bar{P}}}_{1}} \\ \end{align}$$ 找到等价密钥后，对于给定的合法密文，很容易恢复其相应的明文。
-
给定新的多变量公钥密码体制的公钥和一个待破解的合法密文，进行如下步骤来恢复其相应的明文：
1) 找到所有的一阶线性化方程。
找到所有的线性化方程等价于找到所有一阶线性化方程的系数向量$ ({{a}_{ij}}, {{b}_{i}}, {{c}_{j}}, d)$所张成的线性空间的一组基。
式(3)的系数个数为$n(n+l)+2n+l+1$个。因此，可利用公钥随机生成略多于$n(n+l)+2n+l+1$个明文/密文对，代入式(3)，求解以线性化方程系数为未知数线性方程组，即可得到式(4)。若使用一般的高斯消元，该步骤的计算复杂度为$(n\times (n+l)+$ $2n+l+1{{)}^{3}}$次域k上的运算。
实验结果表明，当n = 73，l = 2，t = 3时，D = 50，该步骤的计算复杂度为238次域k上的运算；n = 103，l = 2，t = 3时，D = 70，该步骤的计算复杂度为242次域k上的运算。
2) 获取明文变量之间的线性关系。
将待破解的合法密文${y}'=({{{y}'}_{1}}, {{y}_{2}}, \cdots, {{{y}'}_{n+l}})$代入式(4)中，得到了关于明文变量的线性方程组。解该方程组，可将D′个明文变量用其余$h=n-{D}'$个明文变量线性表出。若使用一般的高斯消元，该步骤的计算复杂度为n3次域k上的运算。
实验结果表明，当n = 73，l = 2，t = 3时，D′ = 50，h = 25；n = 103，l = 2，t = 3时，D′ = 70，h = 35。
3) 得到等价的Square加密体制。
将步骤2)中获得的明文变量线性关系代入公钥多项式或式(1)中，可消去D′个明文变量，再对消元后的方程组进行高斯消元，可得到等价的Square加密体制，而消元后方程组左边为对应的合法密文。
实验结果表明，当n = 73，l = 2，t = 3时，等价的Square体制的明文变量和密文变量个数均为25；n = 103，l = 2，t = 3时，等价的Square体制的明文变量和密文变量个数均为35。
4) 利用Square公钥加密体制的破解方案求得h个明文变量的值。
该步骤最耗时的部分是求线性映射L，根据文献[6]，该部分的计算复杂度为$O({{\log }^{2}}(q){{h}^{6}})$。
实验结果表明，当q = 31，n = 73，l = 2，t = 3时，该步骤的计算复杂度约为233次域k上的运算；q = 31，n = 103，l = 2，t = 3时，该步骤的计算复杂度约为235次域k上的运算。
5) 将步骤4)求得的明文值，代入到步骤2)获得明文变量间的线性关系，可恢复出剩余的明文，从而恢复出完成的明文$({{{x}'}_{1}}, {{{x}'}_{2}}\cdots, {{{x}'}_{n}}) $。
实验结果表明，当q = 31，n = 73，l = 2，t = 3时，找到线性化方程的时间为531.557 s，而恢复明文所花费的时间仅为16.611 s；q = 31，n = 103，l = 2，t = 3时，找到线性化方程的时间为8 504.909 s，而恢复明文所花费的时间仅为52.947 s。
以上攻击过程均在普通计算机上使用Magma软件实现，计算机配置为Intel(R)Core(TM)i3-2 330 M CPU@2.20 GHz, 2.00 G RAM。
-
本文结合线性化方程方法和差分攻击方法破解了文献[13]提出的新的多变量公钥密码体制，并且通过计算机实验完整地实现了整个攻击过程。实验结果表明，攻击是有效的。
设计安全、高效的多变量公钥加密体制是目前多变量公钥密码研究的一个公开问题，需要考虑到所有的已有攻击方法，特别是要避免线性化方程的产生。
Cryptanalysis of a Multivariate Public Key Cryptosystem
-
摘要: 将"小域-大域"方法与三角形逐步迭代方法相结合，提出了一种新多变量公钥密码体制，并声称该体制能够抵抗秩攻击、线性化方程攻击和差分攻击。经过深入分析，发现该方案的中心映射满足大量一阶线性化方程。利用线性化方程可以将原体制转变为Square加密方案，然后利用差分攻击方案可恢复合法密文相应的明文。对于原体制的两种推荐参数，对于给定的公钥，恢复合法密文相应的明文复杂度分别约为233和235。上述攻击结果通过计算机实验得到了验证。Abstract: In 2014, Yuan et al. proposed a new multivariate public key cryptosystem by combining "small field-big field" and "stepwise triangular" methods. The authors claimed that their scheme can be secure against rank attack, linearization equation attack and differential attack. Through analysis, we found that there are a lot of linearization equations satisfied by this scheme. We can transform it to an equivalent square encryption scheme by linearization equation method and then recover corresponding plaintext for any given cipheretext by differential attack. As to two recommended parameters, for given public key, the complexities of recovering plaintext are 233 and 235, respectively. The results above are further confirmed by computer experiments.
-
[1] SHOR P, ONG B S, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Rev, 1999, 41(2):303-332. doi: 10.1137/S0036144598347011 [2] MATSUMOTO T, IMAI H. Public quadratic polynominal-tuples for efficient signature-verification and message-encryption[C]//EUROCRYPT'88: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques 1988. Heidelberg: Springer, 1988. http://dl.acm.org/citation.cfm?id=55593 [3] PATARIN J. Hidden fields equations (hfe) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms[C]//Eurocrypt'96: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques 1996. Heidelberg: Springer, 1996. [4] CLOUGH C, BAENA J, DING J, et al. Square, a new multivariate encryption scheme[C]//CT-RSA 2009: Cryptographers' Track at the RSA Conference 2009. Heidelberg: Springer, 2009. http://dl.acm.org/citation.cfm?id=1538002 [5] PATARIN J. Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88[C]//Eurocrypt'95: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques 1995. Heidelberg: Springer, 1995. [6] BILLET O, GILLES M R. Cryptanalysis of the square crypto systems[C]//ASIACRYPT 2009: Proceedings of Annual International Conference on the Theory and Applications of Cryptology and Information Security 2009. Heidelberg: Springer, 2009. [7] CLOUGH C, DING J. Secure variants of the square encryption scheme[C]//PQCrypto 2010: Proceedings of International Conference on Post-Quantum Cryptography 2010. Heidelberg: Springer, 2010. [8] THOMAE E, WOLF C. Roots of square: Cryptanalysis of double-layer square and square+[C]//PQCrypto 2011: Proceedings of International Conference on Post-Quantum Cryptography 2011. Heidelberg: Springer, 2011. [9] WANG L, YANG B, HU Y, et al. A "medium-field" multivarite public-key encryption scheme[C]//CT-RSA 2006: Cryptographers' Track at the RSA Conference 2006. Heidelberg: Springer, 2006. doi: 10.1007/11605805_9 [10] MOH T T. A fast public key system with signature and master key functions[J]. Comm in Algebra, 1999, 27:2207-2222. doi: 10.1080/00927879908826559 [11] DING J, HU L, NIE X, et al. High order linearization equation (HOLE) attack on multivariate public key cryptosystems[C]//PKC 2007: Proceedings of International Conference on the Theory and Practice of Public-Key Cryptography 2007. Heidelberg: Springer, 2007. doi: 10.1007%2F978-3-540-71677-8_16 [12] 刘梦娟, 聂旭云, 胡磊, 等.线性化方程方法破解TTM公钥加密体制[J].电子科技大学学报, 2010, 39(2):293-297. http://manu50.magtech.com.cn/dzkjdx/CN/abstract/abstract1095.shtml LIU Meng-juan, NIE Xu-yun, HU Lei, et al. Linearization equation attack on TTM public key cryptosystems[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(2):293-297. http://manu50.magtech.com.cn/dzkjdx/CN/abstract/abstract1095.shtml [13] YUAN F, SUN Y, JIANG J, et al. A multivariate public key cryptographic scheme[J]. Communications China, 2014, 11(12):120-124. doi: 10.1109/CC.2014.7019846 -
点击查看大图
计量
- 文章访问数: 6016
- HTML全文浏览量: 1824
- PDF下载量: 144
- 被引次数: 0
下载:
