ROCAと離散対数問題 - d0tfi1e’s blog

ROCA

原論文はhttps://acmccs.github.io/papers/p1631-nemecA.pdfです。

RSALibで生成された素数を利用したRSA暗号に関する脆弱性です。

RSALibで生成される素数の特徴

本記事では512bitの例を扱います。RSALibで生成される素数は次のような形をしています。

$p = kM + \mathrm{pow}(65537, a, M)$

$\mathrm{pow}(e, a, M)$ は $M$ を法とした $e$ の $a$ 乗を表します。ここで、 $M = P_{39}\#$ は素数を小さい順に39個かけ合わせた数です。

$p$ を決定するパラメータは37bitの $k$ および62bitの $a$ だけで、99bitの空間しかなく、512bitの素数全体の空間にくらべ非常に小さいです。

さて、この特徴をもつ素数から生成される公開鍵 $n = p \cdot q$ は次の特徴をもちます。

（特徴）合同式 $n \equiv 65537 ^ x (\mathrm{mod} M)$ が解 $x$ をもつ

$n \equiv 65537 ^ x (\mathrm{mod} M)$ を解く

本来離散対数問題を解くのはとてもむずかしいのですが、この場合は手元のPythonでも数秒もかからず解けてしまいます。

方針はシンプルで、まず $M = P_{39}\# = \prod p_i$ となる各 $p_i$ に対しもとの方程式を分解して

$n \equiv 65537^{x_i} (\mathrm{mod} p_i)$

の形の連立合同式にします。

それぞれの合同式は全探索することに簡単に解けます。 $p_i$ は非常に小さいですから、 $x_i$ を0から $p_i - 1$ まで動かしてみて、 $n$ と合同になるものを調べていきます。なお、そのような $x_i$ が見つからなかった場合、もとの方程式にも解がないことになりますので、その場合 $n$ はRSALibによって生成された素数からなる公開鍵ではありません。

$x_i$ が見つかったとします（ $a_i$ と置きましょう）。次に、65537の位数を調べます。つまり、 $65537^{q_i} \equiv 1 (\mathrm{mod} p_i)$ となるような最小の $q_i$ を探します。 $q_i$ は巡回群の性質より必ず存在し、合同式の解は $x_i = a_i + m \cdot q_i$ の形で一般化されます。

$q_i$ を探す作業もたかだか $p_i$ 回の探索で見つかるので十分高速です。

これらの合同式をそれぞれ解き、最後に中国剰余定理により連立合同式の解が一般に求められます。 $q_i$ が合成数のとき、中国剰余定理が使えないと思うかもしれませんが、 $q_i$ の各素因数について、 $x_i = a_i + m \cdot q_i$ の $q_i$ をそれぞれの素因数に置き換えた合同式が成り立つので、これらで代用すれば中国剰余定理が使えます。

$x = a + m \cdot q$

という形になったとします。しかしこの $x$ はすべてが

$n \equiv 65537 ^ x (\mathrm{mod} M)$

を満たすとは限りません。なぜなら $q$ が $M$ に比べて小さいからです。しかし、 $m \sim 1000$ ぐらいまでにはもとの合同式を満たす $x$ にヒットするので順番に $m$ を変えていくことでもとの方程式の解を簡単に調べることができます。

混乱しやすいポイント

連立合同式

$n \equiv 65537^{x_i} (\mathrm{mod} p_i)$

を解くとき、法 $p_i$ について中国剰余定理を使うと思いがちですが、 $x_i$ は法 $q_i$ に関して決まるので、ここに注意してください。また、 $q_i$ どうしは一般に互いに素とは限りませんから、中国剰余定理の結果得られる解 $x$ は $M = P_{39}\#$ よりずっと小さい法に関して決まります。

より大きな入力での離散対数問題

ROCAでは、それぞれの合同式を解く際に全探索でも十分高速ですが、全探索が難しくなってくると、Baby-step Giant-stepアルゴリズムや、Pohlig-Hellmanアルゴリズムが活躍するようになってきます。

参考文献

RSA鍵生成脆弱性ROCAの紹介