Partial Exposure of the LSBs of the RSA Decryption Exponent

發表於 2026-02-06 更新於 2026-02-06 RSA partial-key-exposure LSB private-exponent Coppersmith LLL

當 RSA 使用 small public exponent $e$（例如 $e=3$）時，如果攻擊者已知 private exponent $d$ 的一段 LSBs (least significant bits)，即使只知道「四分之一」長度的低位 bits，也可能進一步恢復完整的 $d$，甚至 factor $N$。

把 $d$ 拆成「已知低位 + 未知高位」，利用 RSA 的關係式導出一個關於 $p \bmod 2^{n/4}$ 的同餘條件，將問題轉化為「已知 prime factor 的部分 bits」的情況；接著透過 Coppersmith/LLL 類的 lattice 技術嘗試 factor $N$，一旦成功得到 $p,q$，就能回推出完整的 $d$。

相關的 prime factor bits recovery 方法參考： Partial Exposure of the some bits of the RSA Prime Factors.

Setup

設 $N = p \cdot q$ 為 $n$-bit RSA modulus，且 $p \approx q$， public key 為 $(N,e)$，private exponent 為 $d$

已知 $d$ 的 $n/4$ 個 LSBs，記為 $d_0$，並寫成

\[d = d_0 + 2^{n/4}x_0\]

其中未知量 $x_0$ 滿足

\[0 \le x_0 \le 2^{3n/4}\]

已知存在整數存在整數 $k$ 且 $0 < k < e$ ，使得

\[ed - k (N - (p+q) + 1) = 1\]

Derive a congruence for $p \bmod 2^{n/4}$

先左右同乘 $p$

\[edp - kp (N - (p+q) + 1) = p\]

可將上式整理成

\[edp - kp (N - (p+q) + 1) = edp - kp (N - p - q + 1) = edp - kp (N - p + 1) + kpq =\]

由 $N=pq$，可得

\[edp - kp(N - p + 1) + kN = p\]

令

\[p_0 \equiv p \pmod{2^{n/4}}\]

並把 $d = d_0 + 2^{n/4}x_0$ 代回，上式在模 $2^{n/4}$ 下會消去含 $2^{n/4}x_0$ 的項，得到一個只含已知 $d_0$ 與未知 $p_0$ 的同餘：

\[\begin{equation}\label{eq:one} ed_0p_0 - kp_0(N - p_0 + 1) + kN - p_0 \equiv 0 \pmod{2^{n/4}} \end{equation}\]

重點：這個式子只在模 $2^{n/4}$ 下成立，且不再含未知的 $x_0$，因此可以用來枚舉/求解可能的 $p_0$。

Algorithm idea (recover $d$ via factoring $N$) 可以用下面的流程恢復完整的 $d$： Step 1: enumerate $k$ 由於 $0 < k < e$ 且 $e$ 很小，攻擊者可以枚舉每個可能的 $k$。 Step 2: solve Equation~(\ref{eq:one}) for $p_0$ 對固定的 $k$，在模 $2^{n/4}$ 下解： $$ ed_0p_0 - kp_0(N - p_0 + 1) + kN - p_0 \equiv 0 \pmod{2^{n/4}} $$ 每個 $k$ 會產生 $O(n/4)$ 個可能的 $p_0$。 Step 3: factor $N$ using partial bits of $p$ 一旦取得候選 $p_0 \equiv p \pmod{2^{n/4}}$，就把問題轉化成「已知 prime factor 的部分 bits」的情況：
  • 已知 $p$ 的 $n/4$ 個 LSBs
  • 使用 bivariate Coppersmith (heuristic) + LLL 尋找小根
  • 進而恢復 $p, q$，完成 factorization
若候選 $p_0$ 正確，這一步就能成功 factor 出 $N$。 Step 4: recover $d$ 當 $p, q$ 已知後，可直接算出： $$ \varphi(N) = (p-1)(q-1) $$ 再由 $$ ed \equiv 1 \pmod{\varphi(N)} $$ 恢復 $d$（例如計算 $e^{-1} \bmod \varphi(N)$）。
已知 $d$ 的 $n/4$ 個 LSBs（記為 $d_0$）時：
  1. 將 $d$ 表示為 $d = d_0 + 2^{n/4}x_0$。
  2. 由 RSA 關係式導出 Equation~(\ref{eq:one})，得到關於 $p_0 \equiv p \pmod{2^{n/4}}$ 的同餘條件。
  3. 枚舉小範圍的 $k$，對每個 $k$ 解出少量候選的 $p_0$。
  4. 對每個候選 $p_0$，將問題轉化為「已知 prime factor 的部分 bits」並使用 Coppersmith/LLL（lattice-based）方法嘗試 factor $N$。
  5. 一旦 factor 成功得到 $p, q$，即可回推出完整的 $d$。
  1. 這個攻擊利用了「$e$ 很小」使得 $k$ 可枚舉，以及「已知 $d$ 的低位」使得 Equation~(\ref{eq:one}) 在模 $2^{n/4}$ 下不含未知 $x_0$。
  2. 真正的關鍵在於 Step 3：一旦得到 $p_0 \equiv p \pmod{2^{n/4}}$，就能把問題化約成「已知 prime factor 的部分 bits」的情況，接著用 Coppersmith/LLL 這類 lattice-based 方法嘗試 factor $N$，若成功即可恢復 $p,q$ 並回推出完整的 $d$。

References

  • Nigel P. Smart, Cryptography: An Introduction (3rd ed.), Chapter 17. PDF
↑