一个常数时间双并行Montgomery算法的简单说明

考虑使用 P+Q ←\leftarrow xADD(P, Q, P-Q) 和 [2]P ←\leftarrow xDBL(P) 实现 [m]P + [n]Q 的常数时间双并行计算。

我们可以将 mm 和 nn 分解成二进制形式：

[m]P+[n]Q=[∑i=0k−1b0,i2i]P+[∑i=0k−1b1,i2i]Q[m]P + [n]Q = \left[ \sum\limits_{i=0}^{k-1} b_{0,i} 2^i \right] P + \left[ \sum\limits_{i=0}^{k-1} b_{1,i} 2^i \right] Q

根据二分法的经典思路，我们可以写出递归式：

R0(i)=2R0(i+1)+b0,iP+b1,iQR_0^{(i)} = 2 R_0^{(i+1)} + b_{0,i} P + b_{1,i} Q

其中，初始状态 R0(k)=OR_0^{(k)} = \mathcal{O}，R0(i)=[∑j=ik−1b0,j2j−i]P+[∑j=ik−1b1,j2j−i]QR_0^{(i)} = \left[\sum\limits_{j=i}^{k-1} b_{0, j} 2^{j-i} \right] P + \left[ \sum\limits_{j=i}^{k-1} b_{1, j} 2^{j-i} \right] Q。

不过值得注意的是：这种基础算法不仅容易受到侧信道攻击（执行时间取决于比特位是 0 还是 1），而且无法使用高效的蒙哥马利 xADD，因为 xADD 要求在计算 A+BA+B 时，必须已知 A−BA-B 的值。

这时我们将偏差记成一个预存的常量 D(i)=b0,iP+b1,iQD^{(i)} = b_{0,i} P + b_{1,i} Q，这样就有：

R0(i)=2R0(i+1)+D(i)←xADD(R0(i+1),R0(i+1)+D(i),D(i))R_0^{(i)} = 2 R_0^{(i+1)} + D^{(i)} \leftarrow \texttt{xADD}(R_0^{(i+1)}, R_0^{(i+1)} + D^{(i)}, D^{(i)})

记 R∗(i)=R0(i)+D(i)R_*^{(i)} = R_0^{(i)} + D^{(i)}。

所有 R∗(i)R_*^{(i)} 可能的值就恰好构成了一个差分矩形：

+P +P +Q +Q +(P+Q)
$R_0^{(i)}$
$R_0^{(i)} + P$
$R_0^{(i)} + Q$
$R_0^{(i)} + P + Q$

但是问题来了：我们需要预先计算出 D(i)D^{(i)} 的值，而 D(i)D^{(i)} 的值又依赖于 b0,ib_{0,i} 和 b1,ib_{1,i} 的值，这是变化的。不过我们注意到，他们的变化范围是有限的，于是我们可以利用打表的方式，即预先计算出 D(i)D^{(i)} 的所有可能取值。

PP 和 QQ 的值我们总是清楚的，D(i)D^{(i)} 的值也只有 4 种可能：{0,P,Q,P+Q}\{0, P, Q, P+Q\}。且根据 xADD\texttt{xADD} 的方法，当我们知道 {P,Q,P+Q,P−Q}\{P, Q, P+Q, P-Q\} 中任意三个点的值时，我们总能构造出第四个值。

如果我们允许用四个寄存器来存储上述差分矩形的基点，那么算法会变得十分清楚。

设：

{R0(i)=R0(i)R1(i)=R0(i)+PR2(i)=R0(i)+QR3(i)=R0(i)+P+Q\begin{cases} R_0^{(i)} = R_0^{(i)} \\ R_1^{(i)} = R_0^{(i)} + P \\ R_2^{(i)} = R_0^{(i)} + Q \\ R_3^{(i)} = R_0^{(i)} + P + Q \end{cases}

与此同时，将上述构造出来的四个点打包成一个整体的状态：

S(i)=(R0(i)R1(i)R2(i)R3(i))S^{(i)} = \begin{pmatrix} R_0^{(i)} \\ R_1^{(i)} \\ R_2^{(i)} \\ R_3^{(i)} \end{pmatrix}

根据递归式，我们可以得到如下运算表格：

b0,ib_{0, i} b1,ib_{1, i} R0(i−1)R_0^{(i-1)} R1(i−1)R_1^{(i-1)} R2(i−1)R_2^{(i-1)} R3(i−1)R_3^{(i-1)}
0 0 2R0(i)2 R_0^{(i)} R0(i)+R1(i)R_0^{(i)} + R_1^{(i)} R0(i)+R2(i)R_0^{(i)} + R_2^{(i)} R0(i)+R3(i)R_0^{(i)} + R_3^{(i)}
1 0 R1(i)+R0(i)R_1^{(i)} + R_0^{(i)} 2R1(i)2R_1^{(i)} R1(i)+R2(i)R_1^{(i)} + R_2^{(i)} R1(i)+R3(i)R_1^{(i)} + R_3^{(i)}
0 1 R2(i)+R0(i)R_2^{(i)} + R_0^{(i)} R2(i)+R1(i)R_2^{(i)} + R_1^{(i)} 2R2(i)2R_2^{(i)} R2(i)+R3(i)R_2^{(i)} + R_3^{(i)}
1 1 R3(i)+R0(i)R_3^{(i)} + R_0^{(i)} R3(i)+R1(i)R_3^{(i)} + R_1^{(i)} R3(i)+R2(i)R_3^{(i)} + R_2^{(i)} 2R3(i)2R_3^{(i)}

下面用函数式的方式重述算法。

注意到上述表格告诉我们，每一行都会恰好有一个 xDBL 和 三个 xADD，为了尽量做到常数时间，我们固定主要运算函数：

f(T0,T1,T2,T3,D1,D2,D3)={T0←xDBL(T0)T1←xADD(T0,T1,D1)T2←xADD(T0,T2,D2)T3←xADD(T0,T3,D3)=(2T0,T0+T1,T0+T2,T0+T3,∗)\begin{aligned} f(T_0, T_1, T_2, T_3, D_1, D_2, D_3) &= \begin{cases} T_0 \leftarrow \texttt{xDBL}(T_0)\\ T_1 \leftarrow \texttt{xADD}(T_0, T_1, D_1)\\ T_2 \leftarrow \texttt{xADD}(T_0, T_2, D_2)\\ T_3 \leftarrow \texttt{xADD}(T_0, T_3, D_3)\\ \end{cases}\\ &= (2T_0, T_0 + T_1, T_0 + T_2, T_0 + T_3, *) \end{aligned}

为了完整描述算法过程，我们定义置换函数：

{π0=idπ1:(R0,R1,R2,R3,∗)↦(R1,R0,R2,R3,∗)π2:(R0,R1,R2,R3,∗)↦(R2,R1,R0,R3,∗)π3:(R0,R1,R2,R3,∗)↦(R3,R1,R2,R0,∗)\begin{cases} \pi_0 = \text{id}\\ \pi_1: (R_0, R_1, R_2, R_3, *) \mapsto (R_1, R_0, R_2, R_3, *)\\ \pi_2: (R_0, R_1, R_2, R_3, *) \mapsto (R_2, R_1, R_0, R_3, *)\\ \pi_3: (R_0, R_1, R_2, R_3, *) \mapsto (R_3, R_1, R_2, R_0, *)\\ \end{cases}

不难发现上述置换事实上均为对换，即具有对合性。

设初始状态（未开始迭代的状态）为 S(k)=(O,P,Q,P+Q)tS^{(k)} = (\mathcal{O}, P, Q, P + Q)^{t}，标量位组合索引序列为 βi=b0,i+2b1,i\beta_i = b_{0, i} + 2b_{1, i}。下面考虑将 S(k)→S(0)S^{(k)}\rightarrow S^{(0)} 进行全路径展开。

根据单步状态转移方程：

S(i)=πβi(f(πβi(S(i+1)),Δβi))S^{(i)} = \pi_{\beta_i} \left( f\left( \pi_{\beta_i}\left(S^{(i+1)}\right), \Delta_{\beta_i} \right) \right)

其中，Δβi=(D1,D2,D3)\Delta_{\beta_i} = (D_1, D_2, D_3) 是传给 xADD 的差值常量组。因为 Montgomery 曲线上的 xADD 仅依赖于差值的仿射 x 坐标（即 x(A−B)=x(B−A)x(A-B) = x(B-A)，符号免疫），我们可以通过预计算得出所有可能的 Δβ\Delta_\beta。

具体来说，Δβ\Delta_\beta 恰好是点集 {0,P,Q,P+Q}\{0, P, Q, P+Q\} 在经过 πβ\pi_\beta 置换后，第 1、2、3 项与第 0 项的差值：

  • β=0\beta=0：Δ0=(P,Q,P+Q)\Delta_0 = (P, Q, P+Q)
  • β=1\beta=1：Δ1=(P,P−Q,Q)\Delta_1 = (P, P-Q, Q)
  • β=2\beta=2：Δ2=(P−Q,Q,P)\Delta_2 = (P-Q, Q, P)
  • β=3\beta=3：Δ3=(Q,P,P+Q)\Delta_3 = (Q, P, P+Q)

这意味着我们还需要四个寄存器预存储预计算的四个差点： PP，QQ，P+QP+Q，P−QP - Q。

将全过程从 S(k)S^{(k)} 向 S(0)S^{(0)} 逐层嵌套展开：

S(k−1)=πβk−1∘f∘πβk−1(S(k))S(k−2)=πβk−2∘f∘πβk−2∘πβk−1∘f∘πβk−1(S(k))⋮S(0)=πβ0∘f∘πβ0∘πβ1∘f∘πβ1∘⋯∘πβk−2∘πβk−1∘f∘πβk−1(S(k))\begin{aligned} S^{(k-1)} &= \pi_{\beta_{k-1}} \circ f \circ \pi_{\beta_{k-1}} \left( S^{(k)} \right) \\ S^{(k-2)} &= \pi_{\beta_{k-2}} \circ f \circ \pi_{\beta_{k-2}} \circ \pi_{\beta_{k-1}} \circ f \circ \pi_{\beta_{k-1}} \left( S^{(k)} \right) \\ &\vdots \\ S^{(0)} &= \pi_{\beta_{0}} \circ f \circ \pi_{\beta_{0}} \circ \pi_{\beta_{1}} \circ f \circ \pi_{\beta_{1}} \circ \dots \circ \pi_{\beta_{k-2}} \circ \pi_{\beta_{k-1}} \circ f \circ \pi_{\beta_{k-1}} \left( S^{(k)} \right) \end{aligned}

仔细观察 S(0)S^{(0)} 的表达式，发现除了最外层和最内层的置换，中间所有的置换全部两两相邻，形成了 πβi∘πβi+1\pi_{\beta_i} \circ \pi_{\beta_{i+1}} 的形式。

之前定义的 π\pi 函数（例如 π1\pi_1 仅仅对换了 R0R_0 和 R1R_1，而保持 R2,R3R_2, R_3 不变）在数学上是一个局部对换，它们不满足封闭性。
比如 π1∘π2\pi_1 \circ \pi_2 会产生一个三阶循环轮换（(0,1,2,3)↦(1,2,0,3)(0,1,2,3) \mapsto (1,2,0,3)），它既不是对合的，也无法用单一的 πx\pi_x 来表示。如果沿用这个定义，我们举步维艰，接下来我们必须将 π\pi 置换升级为全局异或置换

将基点状态 SS 的四个位置索引看作两位二进制数 x∈{00,01,10,11}2x \in \{00, 01, 10, 11\}_2。重新定义置换群 Π={π0,π1,π2,π3}\Pi = \{\pi_0, \pi_1, \pi_2, \pi_3\}，使其作用在状态 SS 上的规则为索引的按位异或：

πj(Rx)=Rx⊕j\pi_j(R_x) = R_{x \oplus j}

展开来看，四个置换的完整映射为：

{π0:(R0,R1,R2,R3)↦(R0,R1,R2,R3)π1:(R0,R1,R2,R3)↦(R1,R0,R3,R2)(不仅换 0,1，还换 2,3)π2:(R0,R1,R2,R3)↦(R2,R3,R0,R1)π3:(R0,R1,R2,R3)↦(R3,R2,R1,R0)\begin{cases} \pi_0: (R_0, R_1, R_2, R_3) \mapsto (R_0, R_1, R_2, R_3) \\ \pi_1: (R_0, R_1, R_2, R_3) \mapsto (R_1, R_0, R_3, R_2) \quad \text{(不仅换 0,1，还换 2,3)} \\ \pi_2: (R_0, R_1, R_2, R_3) \mapsto (R_2, R_3, R_0, R_1) \\ \pi_3: (R_0, R_1, R_2, R_3) \mapsto (R_3, R_2, R_1, R_0) \end{cases}

即使 π1\pi_1 同时交换了 R2R_2 和 R3R_3，经过固定的 ff 函数计算后，再用 π1\pi_1 换回来，结果依然完美符合上述运算表格（因为 ff 中的加法操作是关于 T0T_0 的，且差值 Δ\Delta 也经过了对应的预排列）。值得一提的是，升级为异或置换后，群 Π\Pi 同构于 Klein 四元群 V4V_4，满足复合律：

πa∘πb=πa⊕b\pi_a \circ \pi_b = \pi_{a \oplus b}

定义索引序列 β\beta 的布尔差分导数序列 rr：

ri=∂β∂i≡βi⊕βi+1i∈{0,1,…,k−2}r_i = \frac{\partial \beta}{\partial i} \equiv \beta_i \oplus \beta_{i+1} \quad i \in \{0, 1, \dots, k-2\}

注：为了形式统一，我们可以假定一个虚拟的初始前置状态 βk=0\beta_k = 0，使得 rk−1=βk−1⊕0=βk−1r_{k-1} = \beta_{k-1} \oplus 0 = \beta_{k-1}。

利用 Klein 四元群的复合律 πa∘πb=πa⊕b\pi_a \circ \pi_b = \pi_{a \oplus b}，我们将所有相邻的置换合并：

πβi∘πβi+1=πβi⊕βi+1=πri\pi_{\beta_i} \circ \pi_{\beta_{i+1}} = \pi_{\beta_i \oplus \beta_{i+1}} = \pi_{r_i}

将 rir_i 代入展开式中，就有：

S(0)=πβ0∘f∘πr0∘f∘πr1∘f∘⋯∘πrk−2∘f∘πrk−1(S(k))S^{(0)} = \pi_{\beta_0} \circ f \circ \pi_{r_0} \circ f \circ \pi_{r_1} \circ f \circ \dots \circ \pi_{r_{k-2}} \circ f \circ \pi_{r_{k-1}} \left( S^{(k)} \right)

这样构造出来的常数时间算法，实际上是再执行这样一条流水线：

状态装载→πdk−1计算f→πdk−2计算f⋯→πd0计算f→πβ0还原目标结果\textbf{状态装载} \xrightarrow{\pi_{d_{k-1}}} \textbf{计算} f \xrightarrow{\pi_{d_{k-2}}} \textbf{计算} f \cdots \xrightarrow{\pi_{d_0}} \textbf{计算} f \xrightarrow{\pi_{\beta_0}} \textbf{还原目标结果}

这样的方法只关注当前步和上一步的状态差异，将置换次数减半，同时差分导数只会最多泄露标量位之间的相对消息，具有天然的抗测信道攻击的能力。

最后写出伪代码如下所示：

\begin{algorithm}
\caption{Constant-Time 2-D Montgomery Ladder (4 Registers, Baby)}
\begin{algorithmic}
\Require $k$-bit scalars $m = \sum b_{0,i}2^i, n = \sum b_{1,i}2^i$, Base points $P, Q, P+Q, P-Q$
\Ensure Return point $R = [m]P + [n]Q$

\State \Comment{Phase 1: Precompute Difference Table $\Delta$}
\State $\Delta_0 \gets (P, Q, P+Q)$
\State $\Delta_1 \gets (P, P-Q, Q)$
\State $\Delta_2 \gets (P-Q, Q, P)$
\State $\Delta_3 \gets (Q, P, P+Q)$

\State \Comment{Phase 2: Initialization}
\State $(R_0, R_1, R_2, R_3) \gets (\mathcal{O}, P, Q, P+Q)$
\State $\beta_{prev} \gets 0$

\State \Comment{Phase 3: Main Evaluation Loop}
\For{$i = k-1$ \textbf{downto} $0$}
\State $\beta_i \gets b_{0,i} + 2 \cdot b_{1,i}$
\State $r_i \gets \beta_i \oplus \beta_{prev}$ \Comment{Boolean differential derivative}

\State \Comment{Apply $\pi_{r_i}$ using orthogonal Constant-Time Swaps (CSWAP)}
\State $v_0 \gets r_i \text{ AND } 1$
\State $v_1 \gets (r_i \text{ AND } 2) \gg 1$
\State $\texttt{CSWAP}(v_0, R_0, R_1)$
\State $\texttt{CSWAP}(v_0, R_2, R_3)$
\State $\texttt{CSWAP}(v_1, R_0, R_2)$
\State $\texttt{CSWAP}(v_1, R_1, R_3)$

\State \Comment{Execute fixed function $f$}
\State $T_0 \gets \texttt{xDBL}(R_0)$
\State $T_1 \gets \texttt{xADD}(R_0, R_1, \Delta_{\beta_i}[0])$
\State $T_2 \gets \texttt{xADD}(R_0, R_2, \Delta_{\beta_i}[1])$
\State $T_3 \gets \texttt{xADD}(R_0, R_3, \Delta_{\beta_i}[2])$

\State $(R_0, R_1, R_2, R_3) \gets (T_0, T_1, T_2, T_3)$
\State $\beta_{prev} \gets \beta_i$
\EndFor

\State \Comment{Phase 4: Final Restore Permutation $\pi_{\beta_0}$}\State $v_0 \gets \beta_{prev} \text{ AND } 1$
\State $v_1 \gets (\beta_{prev} \text{ AND } 2) \gg 1$
\State $\texttt{CSWAP}(v_0, R_0, R_1)$
\State $\texttt{CSWAP}(v_0, R_2, R_3)$
\State $\texttt{CSWAP}(v_1, R_0, R_2)$
\State $\texttt{CSWAP}(v_1, R_1, R_3)$
\State \Return $R_0$
\end{algorithmic}
\end{algorithm}

可以看到，上述伪代码中所构造出的差分表所体现的对存储空间的需求略显臃肿，这是因为上文中列出的 Δβ\Delta_\beta 差分表，其实依然是基于旧的“局部对换”法则得出的结果。如果我们严格按照全局异或置换 πj(Rx)=Rx⊕j\pi_j(R_x) = R_{x \oplus j} 来重新推导，稍后我们就会发现，几乎不需要复杂的动态加载。

在每一步迭代中，ff 函数执行的核心操作是：

Tx←xADD(T0,Tx,Dx)for x∈{1,2,3}T_x \leftarrow \texttt{xADD}(T_0, T_x, D_x) \quad \text{for } x \in \{1, 2, 3\}

由于状态 SS 经过了 πβ\pi_\beta 的置换，我们有 Tx=Sβ⊕xT_x = S_{\beta \oplus x} 和 T0=SβT_0 = S_\beta。因此，ff 函数所需要的差值必然是：

Dx=Tx−T0=Sβ⊕x−SβD_x = T_x - T_0 = S_{\beta \oplus x} - S_\beta

我们将四个基点用二进制索引 y=y1y0∈{00,01,10,11}2y = y_1 y_0 \in \{00, 01, 10, 11\}_2 统一表示：

Sy=y0P+y1QS_y = y_0 P + y_1 Q

代入差值公式：

Dx=((β⊕x)0P+(β⊕x)1Q)−(β0P+β1Q)D_x = ((\beta \oplus x)_0 P + (\beta \oplus x)_1 Q) - (\beta_0 P + \beta_1 Q)

Dx=((β0⊕x0)−β0)P+((β1⊕x1)−β1)QD_x = ((\beta_0 \oplus x_0) - \beta_0) P + ((\beta_1 \oplus x_1) - \beta_1) Q

利用布尔代数的一个小技巧 (b⊕a)−b=(−1)ba(b \oplus a) - b = (-1)^b a，上式可以直接化简为：

Dx=(−1)β0x0P+(−1)β1x1QD_x = (-1)^{\beta_0} x_0 P + (-1)^{\beta_1} x_1 Q

由于 Montgomery 曲线上的 xADD\texttt{xADD} 具有符号免疫性（仅依赖仿射 xx 坐标，即 A−B≡B−AA-B \equiv B-A），我们在传入差点时可以取绝对值。

下面分别来看 x=1,2,3x=1, 2, 3 时的 DxD_x：

  • 对于 T1T_1 (x=1  ⟹  x0=1,x1=0x=1 \implies x_0=1, x_1=0)：D1=(−1)β0P≡PD_1 = (-1)^{\beta_0} P \equiv P （永远是 PP，与 β\beta 无关）
  • 对于 T2T_2 (x=2  ⟹  x0=0,x1=1x=2 \implies x_0=0, x_1=1)：D2=(−1)β1Q≡QD_2 = (-1)^{\beta_1} Q \equiv Q （永远是 QQ，与 β\beta 无关）
  • 对于 T3T_3 (x=3  ⟹  x0=1,x1=1x=3 \implies x_0=1, x_1=1)：D3=(−1)β0P+(−1)β1QD_3 = (-1)^{\beta_0} P + (-1)^{\beta_1} Q
    • 如果 β0=β1\beta_0 = \beta_1（即 β∈{0,3}\beta \in \{0, 3\}），D3=±(P+Q)≡P+QD_3 = \pm(P+Q) \equiv P+Q。
    • 如果 β0≠β1\beta_0 \neq \beta_1（即 β∈{1,2}\beta \in \{1, 2\}），D3=±(P−Q)≡P−QD_3 = \pm(P-Q) \equiv P-Q。

综上所述：在全局异或置换下，真正的差分表 Δβ\Delta_\beta 应该是：

  • Δ0=(P,Q,P+Q)\Delta_0 = (P, Q, P+Q)
  • Δ1=(P,Q,P−Q)\Delta_1 = (P, Q, P-Q)
  • Δ2=(P,Q,P−Q)\Delta_2 = (P, Q, P-Q)
  • Δ3=(P,Q,P+Q)\Delta_3 = (P, Q, P+Q)

通过上述推导可以发现，我们只需要让 D1D_1 和 D2D_2 是绝对的静态常量 PP 和 QQ，然后动态传递 T3T_3 的差值（在 P+QP+Q 和 P−QP-Q 之间横跳）。下面用 F1,F2F_1, F_2 分别存储 P+QP+Q 和 P−QP-Q。

定义状态变量 ci=b0,i⊕b1,ic_i = b_{0,i} \oplus b_{1,i}，于是不难讨论得到：

  • 当 ci=0c_i = 0 时，我们需要 T3T_3 的差值为 P+QP+Q；
  • 当 ci=1c_i = 1 时，我们需要 T3T_3 的差值为 P−QP-Q。

据此，给出优化后的伪代码如下：

\begin{algorithm}
\caption{Optimized Constant-Time 2-D Montgomery Ladder (4 Registers, Dynamic Diff)}
\begin{algorithmic}
\Require $k$-bit scalars $m = \sum b_{0,i}2^i, n = \sum b_{1,i}2^i$, Base points $P, Q, P+Q, P-Q$
\Ensure Return point $R = [m]P + [n]Q$

\State \Comment{Phase 1: Dynamic Difference Initialization}
\State $D_1 \gets P$
\State $D_2 \gets Q$
\State $F_1 \gets P+Q$
\State $F_2 \gets P-Q$
\State $c_{prev} \gets 0$ \Comment{Tracks the XOR state of scalar bits}

\State \Comment{Phase 2: Point Initialization}
\State $(R_0, R_1, R_2, R_3) \gets (\mathcal{O}, P, Q, P+Q)$
\State $\beta_{prev} \gets 0$

\State \Comment{Phase 3: Main Evaluation Loop}
\For{$i = k-1$ \textbf{downto} $0$}
    \State $\beta_i \gets b_{0,i} + 2 \cdot b_{1,i}$
    \State $r_i \gets \beta_i \oplus \beta_{prev}$ \Comment{Boolean differential derivative}

    \State \Comment{Apply $\pi_{r_i}$ using orthogonal Constant-Time Swaps}
    \State $v_0 \gets r_i \text{ AND } 1$
    \State $v_1 \gets (r_i \text{ AND } 2) \gg 1$
    \State $\texttt{CSWAP}(v_0, R_0, R_1)$
    \State $\texttt{CSWAP}(v_0, R_2, R_3)$
    \State $\texttt{CSWAP}(v_1, R_0, R_2)$
    \State $\texttt{CSWAP}(v_1, R_1, R_3)$

    \State \Comment{Dynamic Difference Loading for $T_3$}
    \State $c_i \gets b_{0,i} \oplus b_{1,i}$
    \State $swap\_diff \gets c_i \oplus c_{prev}$
    \State $\texttt{CSWAP}(swap\_diff, F_1, F_2)$

    \State \Comment{Execute fixed function $f$}
    \State $T_0 \gets \texttt{xDBL}(R_0)$
    \State $T_1 \gets \texttt{xADD}(R_0, R_1, D_1)$
    \State $T_2 \gets \texttt{xADD}(R_0, R_2, D_2)$
    \State $T_3 \gets \texttt{xADD}(R_0, R_3, F_1)$

    \State $(R_0, R_1, R_2, R_3) \gets (T_0, T_1, T_2, T_3)$
    \State $\beta_{prev} \gets \beta_i$
    \State $c_{prev} \gets c_i$
\EndFor

\State \Comment{Phase 4: Final Restore Permutation $\pi_{\beta_0}$}
\State $v_0 \gets \beta_{prev} \text{ AND } 1$
\State $v_1 \gets (\beta_{prev} \text{ AND } 2) \gg 1$
\State $\texttt{CSWAP}(v_0, R_0, R_1)$
\State $\texttt{CSWAP}(v_0, R_2, R_3)$
\State $\texttt{CSWAP}(v_1, R_0, R_2)$
\State $\texttt{CSWAP}(v_1, R_1, R_3)$
\State \Return $R_0$
\end{algorithmic}
\end{algorithm}

那么问题来了，我们是否可以考虑用三个寄存器存储基点（R0(i)R_0^{(i)}，R1(i)R_1^{(i)}，R2(i)R_2^{(i)}）达到目的呢？

设：

{R1(i)=R0(i)+D(i)R2(i)=R0(i)+F(i)\begin{cases} R_1^{(i)} = R_0^{(i)} + D^{(i)} \\ R_2^{(i)} = R_0^{(i)} + F^{(i)} \end{cases}

与此同时，将上述构造出来的三个点打包成一个整体的状态：

S(i)=(R0(i)R1(i)R2(i))S^{(i)} = \begin{pmatrix} R_0^{(i)} \\ R_1^{(i)} \\ R_2^{(i)} \end{pmatrix}

这时的 S(i)S^{(i)} 在同构意义上就恰好有三种取法：

D(i)D^{(i)} F(i)F^{(i)} R0(i)R_0^{(i)} R1(i)R_1^{(i)} R2(i)R_2^{(i)}
PP QQ R0(i)R_0^{(i)} R0(i)+PR_0^{(i)} + P R0(i)+QR_0^{(i)} + Q
PP P+QP + Q R0(i)R_0^{(i)} R0(i)+PR_0^{(i)} + P R0(i)+P+QR_0^{(i)} + P + Q
QQ P+QP + Q R0(i)R_0^{(i)} R0(i)+QR_0^{(i)} + Q R0(i)+P+QR_0^{(i)} + P + Q

体现在差分矩形上即下图所示：

$R_0^{(i)}$
$R_1^{(i)}$
$R_2^{(i)}$
(a) $D^{(i)} = P, F^{(i)} = Q$
$R_0^{(i)}$
$R_1^{(i)}$
$R_2^{(i)}$
(b) $D^{(i)} = P, F^{(i)} = P + Q$
$R_0^{(i)}$
$R_1^{(i)}$
$R_2^{(i)}$
(c) $D^{(i)} = Q, F^{(i)} = P + Q$

基于当下的这个状态，我们继续往后推导。接下来我们需要关注的就是两件事：

  • 在上述三种情况下，我对下一状态能够使用 xDBL 和 xADD 组合出多少结果；
  • 对于下一个状态我们需要的是哪些结果

我们需要对照这两件事是否兼容。

  • 第一种情况：D(i)=P,F(i)=QD^{(i)} = P, F^{(i)} = Q，下一个状态 S(i−1)S^{(i-1)} 的四种计算情况为：
b0,ib_{0, i} b1,ib_{1, i} R0(i−1)R_0^{(i-1)} R1(i−1)R_1^{(i-1)} R2(i−1)R_2^{(i-1)}
0 0 2R0(i)2 R_0^{(i)} R0(i)+R1(i)R_0^{(i)} + R_1^{(i)} R0(i)+R2(i)R_0^{(i)} + R_2^{(i)}
1 0 R0(i)+R1(i)R_0^{(i)} + R_1^{(i)} 2R1(i)2R_1^{(i)} R1(i)+R2(i)R_1^{(i)} + R_2^{(i)}
0 1 R0(i)+R2(i)R_0^{(i)} + R_2^{(i)} R1(i)+R2(i)R_1^{(i)} + R_2^{(i)} 2R2(i)2R_2^{(i)}
1 1 R1(i)+R2(i)R_1^{(i)} + R_2^{(i)} 2R1(i)+Q2R_1^{(i)} + Q 2R2(i)+P2R_2^{(i)} + P
$R_0^{(i)}$
$R_1^{(i)}$
$R_2^{(i)}$
$D^{(i)} = P, F^{(i)} = Q$
→
$2R_0^{(i)}$
$R_0^{(i)}+R_1^{(i)}$
$2R_1^{(i)}$
$R_0^{(i)}+R_2^{(i)}$
$R_1^{(i)}+R_2^{(i)}$
$2R_1^{(i)}+Q$
$2R_2^{(i)}$
$2R_2^{(i)}+P$
$2R_2^{(i)}+2P$

其中 b0,i=1b_{0, i} = 1，b1,i=1b_{1, i} = 1 情况下，我们无法直接通过已有的变量得到 2R1(i)+Q2R_1^{(i)} + Q 和 2R2(i)+P2R_2^{(i)} + P。

  • 第二种情况：D(i)=P,F(i)=P+QD^{(i)} = P, F^{(i)} = P + Q，下一个状态 S(i−1)S^{(i-1)} 的四种计算情况为：
b0,ib_{0, i} b1,ib_{1, i} R0(i−1)R_0^{(i-1)} R1(i−1)R_1^{(i-1)} R2(i−1)R_2^{(i-1)}
0 0 2R0(i)2 R_0^{(i)} R0(i)+R1(i)R_0^{(i)} + R_1^{(i)} R0(i)+R2(i)R_0^{(i)} + R_2^{(i)}
1 0 R0(i)+R1(i)R_0^{(i)} + R_1^{(i)} 2R1(i)2R_1^{(i)} R1(i)+R2(i)R_1^{(i)} + R_2^{(i)}
0 1 R0(i)+R2(i)+PR_0^{(i)} + R_2^{(i)} + P R0(i)+R2(i)R_0^{(i)} + R_2^{(i)} R0(i)+R2(i)+QR_0^{(i)} + R_2^{(i)} + Q
1 1 R0(i)+R2(i)R_0^{(i)} + R_2^{(i)} R1(i)+R2(i)R_1^{(i)} + R_2^{(i)} 2R2(i)2R_2^{(i)}
$R_0^{(i)}$
$R_1^{(i)}$
$R_2^{(i)}$
$D^{(i)} = P, F^{(i)} = P + Q$
→
$2R_0^{(i)}$
$R_0^{(i)}+R_1^{(i)}$
$2R_1^{(i)}$
$2R_0^{(i)}+Q$
$R_0^{(i)}+R_2^{(i)}$
$R_1^{(i)}+R_2^{(i)}$
$2R_0^{(i)}+2Q$
$R_1^{(i)}+R_2^{(i)}+Q$
$2R_2^{(i)}$

其中 b0,i=0b_{0, i} = 0，b1,i=1b_{1, i} = 1 情况下，我们无法直接通过已有的变量得到 R1(i)+R2(i)+QR_1^{(i)} + R_2^{(i)} + Q 和 2R0(i)+Q2R_0^{(i)} + Q。

  • 第三种情况：D(i)=Q,F(i)=P+QD^{(i)} = Q, F^{(i)} = P + Q，下一个状态 S(i−1)S^{(i-1)} 的四种计算情况为：
b0,ib_{0, i} b1,ib_{1, i} R0(i−1)R_0^{(i-1)} R1(i−1)R_1^{(i-1)} R2(i−1)R_2^{(i-1)}
0 0 2R0(i)2 R_0^{(i)} R0(i)+R1(i)R_0^{(i)} + R_1^{(i)} R0(i)+R2(i)R_0^{(i)} + R_2^{(i)}
1 0 2R0(i)+P2R_0^{(i)} + P R0(i)+R2(i)R_0^{(i)} + R_2^{(i)} R1(i)+R2(i)+PR_1^{(i)} + R_2^{(i)} + P
0 1 R0(i)+R2(i)R_0^{(i)} + R_2^{(i)} 2R1(i)2R_1^{(i)} R1(i)+R2(i)R_1^{(i)} + R_2^{(i)}
1 1 R0(i)+R2(i)R_0^{(i)} + R_2^{(i)} R1(i)+R2(i)R_1^{(i)} + R_2^{(i)} 2R2(i)2R_2^{(i)}
$R_0^{(i)}$
$R_1^{(i)}$
$R_2^{(i)}$
$D^{(i)} = Q, F^{(i)} = P + Q$
→
$2R_0^{(i)}$
$2R_0^{(i)}+P$
$2R_0^{(i)}+2P$
$R_0^{(i)} + R_1^{(i)}$
$R_0^{(i)}+R_2^{(i)}$
$R_1^{(i)}+R_2^{(i)}+P$
$2R_1^{(i)}$
$R_1^{(i)}+R_2^{(i)}$
$2R_2^{(i)}$

其中 b0,i=1b_{0, i} = 1，b1,i=0b_{1, i} = 0 情况下，我们无法直接通过已有的变量得到 R1(i)+R2(i)+PR_1^{(i)} + R_2^{(i)} + P 和 2R0(i)+P2R_0^{(i)} + P。

我们发现，不幸的是，在上述三种情况下，我们总有一种输入比特的组合 (b0,i,b1,i)(b_{0, i}, b_{1, i})，使得我们无法通过已有的变量通过 xDBL 和 xADD 得到对应的下一个状态。

这时，我们又该怎么办？

如果可以把 D(i)=PD^{(i)} = P，F(i)=P+QF^{(i)} = P + Q 和 D(i)=QD^{(i)} = Q，F(i)=P+QF^{(i)} = P + Q 这两种情况拼在一起，那么是不是就可以通过 xDBL 和 xADD 得到所有的下一个状态了？

LadderBiscalar Algo Monitor

🖱️ Scroll to Zoom | Drag to Pan
$m$: $n$:
Trace Log
 2026-03-10  

下一篇