密码分析与身份基密码方案研究

### 密码分析与身份基密码方案研究 #### 1. LRainbow签名方案的密码分析 ##### 1.1 理论基础与问题提出 在LRainbow签名方案中，设$X : L^n → L^m$是具有来自固定子域$L_1 = F_{2^t}$系数的公共多项式，对于任意元素$z ∈ L^m$，定义微分$w′ + w$，其中$w′$是从$L^n$中任意选取的元素，$w$是$L^n_2$中的不定元素。计算公共多项式$X$在该微分处的值并令其等于$z$，最终表达式会包含$w′_iw′_j$、$w′_iw_j$、$w_iw_j$等项，$w′_i$的值已知，$w_i$的值未知。 由于$L ≃ L_2[x]/⟨b(x)⟩$，每个$L$中的元素都可以用变量$x$的多项式表达式描述。对等式两边应用此性质并比较$x$的幂次系数，可得到近似线性方程。此时自然会产生一个问题：给定消息$z = (z_1, …, z_m) ∈ L^m$和从$L^n$中任意选取的元素$w′$，能否找到一个小的自然数$d$，使得存在$w ∈ L^n_2 = F^n_{2^d} ⊂ L^n$，满足$X(w′ + w) = z$。 ##### 1.2 小的子域$L_2$的存在性 固定$w′ ∈ L^n$，定义新的多项式映射$X : L^n_2 → L^m$为$X(w) = X(w′ + w)$，假设$X$是从$L^n_2$到$L^m$的随机映射。可以证明，给定$X : L^n_2 → L^m$，$X^{-1}(z) ≠ ∅$的概率为$1 - e^{-2^{rm - dn}}$。 证明过程如下：固定$w′ ∈ L^n$，考虑函数$X : L^n_2 → L^m$，任意选取元素$z ∈ L^m$，估计不存在$w ∈ L^n_2$使得$X(w) = z$的概率。因为$|L^n_2| = 2^{dn}$且$|L^m| = 2^{rm}$，对于任意$w ∈ L^n_2$，$X(w) ≠ z$的概率为$1 - \frac{1}{2^{dn}}$。由于$X$的输出是随机且独立的，所需概率为$(1 - \frac{1}{2^{dn}})^{2^{rm}} = ((1 - \frac{1}{2^{dn}})^{2^{dn}})^{2^{rm - dn}} ≈ e^{-2^{rm - dn}}$。 ##### 1.3 寻找$w$和伪造签名的方法 已知存在小的子域$L_2$，使得$w ∈ L^n_2 ⊂ L^n$且$X(w′ + w) = z$。其中$L = F_{2^r} ≃ F_{2^d}[x]/⟨b(x)⟩ = L_2[x]/⟨b(x)⟩$，$b(x)$是次数为$l$（$l = r/d$）的不可约多项式。 设$w = (w_1, …, w_n) ∈ L^n_2$是不定点，$w′ = (w′_1, …, w′_n) ∈ L^n$是随机选取的固定点，定义$X(w) = X(w + w′)$，其第$k$个分量为： $X^{(k)}(w) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} \alpha_{i,j,k}(w_i + w′_i)(w_j + w′_j) + \sum_{i = 1}^{n} \beta_{i,k}(w_i + w′_i) + \gamma_k$ 展开可得： $X^{(k)}(w) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} \alpha_{i,j,k}(w′_iw_i + w′_jw_j + w′_iw′_j) + \sum_{i = 1}^{n} \beta_{i,k}(w_i + w′_i) + \sum_{i = 1}^{n} \alpha_{i,j,k}w_iw_j + \gamma_k$ 由于$\alpha_{i,j,k} ∈ L_1$，二次项$w_iw_j$的系数属于$L$的固定子域$L_1$，且$w′_i ∈ L$是任意选取的，线性项$w_i$的系数包含$x$的所有幂次直到$l - 1$。将$x$的不同幂次分组，可将$X(w)$重写为： $X(w) = \begin{pmatrix} X^{(1)}(w) = Q_1(w) + \sum_{i = 1}^{l - 1} L_{i,1}(w)x^i \\ X^{(2)}(w) = Q_2(w) + \sum_{i = 1}^{l - 1} L_{i,2}(w)x^i \\ \vdots \\ X^{(m)}(w) = Q_m(w) + \sum_{i = 1}^{l - 1} L_{i,m}(w)x^i \end{pmatrix}$ 伪造签名的步骤如下： 1. 对于给定的消息$z ∈ L^m$，将$z$表示为$x$的幂次形式，即$z = (z_1, …, z_m)$，其中$z_k = \sum_{i = 0}^{l - 1} z_{i,k}x^i$，每个$z_{i,k} ∈ L_2$。 2. 尝试求解线性方程组$\Delta = \{L_{i,k}(w) = z_{i,k} : 1 ≤ i ≤ l - 1, 1 ≤ k ≤ m\}$的解集$Sol$。由于$\Delta$是随机线性方程组，它很可能是满秩系统，其秩大概率为$(l - 1)m$（若$(l - 1)m ≥ n$则为$n$），解空间的维数为$\dim Sol = \max\{n - (l - 1)m, 0\}$。 3. 在解集$Sol$上求解$m$个二次多项式系统$B = \{Q_k(Sol) = z_{0,k} : 1 ≤ k ≤ m\}$。该系统$B$的解$w$满足$X(w) = z$，即$X(w + w′) = z$，从而得到所需的签名$w + w′$。 #### 2. 攻击的复杂度分析 攻击的主