第0回 RSAへのAttack ～RSAってなに～

どうも。duckです。
RSAへのAttackの記事を書くことにしました。

今回の流れ
・RSA暗号の仕組み
・Attackの成功条件
・Attackする場所

公開: $N,e,C$
秘密: $p,q,d$

暗号化
(0)暗号化したい平文mを準備する。
(1)素数 $p,q$ を用意する。( $N=pq$ とおく)
(2) ${\phi(N)}=(p-1)(q-1)$ と互いに素な自然数 $e$ を用意する。
(3) $ed \equiv 1 \pmod {\phi(N)}$ となるdを計算する。
(4) $C \equiv m^e \pmod N$ が暗号文となる。

復号
$C ^ d \bmod N$ を計算するとそれが平文となる。
つまり $m \equiv C ^ d \pmod N$

順に仕組みをみていく。
(0)平文 $ｍ$ の数字化
CTFではpythonのライブラリのCrypto.Util.numberの中の関数
bytes_to_longを用いられることが多い。

(1)素数 $p,q$ の生成
CTFではpythonのライブラリのCrypto.Util.numberの中の関数
getPrime(ビット数)関数が用いられることが多い。
もしくは、秘匿されたファイルから読みだされていることもある。

(2) $e$ の選択
一般的に $e=65537$ (素数)が選ばれることが多い。
$e$ は素数であるから ${\phi(N)}$ が $e$ の倍数でない限り ${\phi(N)}$ と $e$ は互いに素となる。

(3) $d$ の計算
拡張ユークリッドの互除法を用いる。
参考:CTFで使う数学前編 - CTFと共に生きる

(4)特になし。

復号できる理由
本質：オイラーの定理に基づく。
参考：CTFで使う数学後編 - CTFと共に生きる

$ed \equiv 1 \pmod {\phi(N)}$ より、ある整数 $k$ を用いて
$ed=k{\phi(N)}+1$ と書ける。

よって
$C ^d \equiv {(m ^e)}^d \equiv m ^{ed} \equiv m ^ {k{\phi(N)}+1} \equiv m \times {(m ^ k) }^ {\phi(N)} \pmod N$
オイラーの定理により ${(m ^ k) }^ {\phi(N)} \equiv 1 \pmod N$ だから
$C ^ d \equiv m \pmod N$

公開情報 $N,e,C$ のみから平文 $m$ を求めるのが目標である。
現実では適切なパラメータ設定が行われていると考えられるため、公開情報 $N,e,C$ のみから平文 $m$ を求めることはできない。
しかしCTFでは不適切なパラメータが設定されているので、そこをついて平文 $m$ の入手を目指すこととなる。

もう少し具体的に攻撃が成立する条件を見てみよう。

Attackの成功条件

(a) $d$ がわかる。
(b) ${\phi(N)}$ がわかる。
(c) $p$ または $q$ がわかる。
(d)なぜかいきなり $m$ がわかる。

理由
(a) $C ^ d \equiv m \pmod N$ から $m$ がわかる。
(b) ${\phi(N)}$ ,公開情報の $e$ から(3)を実行し $d$ が得られる。以下(a)と同様。
(c) ${\phi(N)}$ が計算できるため。以下(b)と同様。
(d)そりゃそうだろ。

これらのどれかをめざす。
Attackの成功条件がわかったところで、どこを見ればいいのかを教える。
具体的な攻撃手法については次回以降まとめていく。

Attackする場所

青文字は解くときに特に注意している部分である。
それ以外は最後に紹介する参考サイトのほうが見やすいのでそちらを見ることを推奨する。~~（じゃあなんで書いた）~~
(イ)素数 $p,q$ の生成
　－素数 $p,q$ が小さすぎる
　　具体的には $N$ のbit数が~300bit程度だと素因数分解が可能。(c)に帰着。
　　 $N$ のbit数は最低でも1024bit以上がふつう。
　－特殊な素数を使っている
　　フェルマー素数、メルセンヌ素数など有名な素数を使っている場合それを利用して素因数分解できる。(c)に帰着。
　　素数 $p,q$ が秘匿されたファイルから読みだされている場合は試す価値あり。
　－ $p,q$ の差 $p-q$ が小さすぎる
　　フェルマー法により素因数分解できる。(c)に帰着。
　　具体的には上位数十ビットが等しい場合などは試してみるといいだろう。
　－ $p,q$ の差 $p-q$ が大きすぎる、または $p,q$ のうち片方が極端に小さい
　　試し割法で素因数分解できる。(c)に帰着。
　　ふつうは $p,q$ のビット数は同じとするので、 $p,q$ のbit数が違うときは怪しいと思ったほうが良い。
　　素因数分解できない場合でもそこが突破口になりやすい。
(ロ) $e$ の選択
　－ $e$ が小さすぎる
　　中国剰余定理または実数上での $e$ 乗根を求めることで $m$ が直接求まる。(d)に帰着。
　　 $e=2,3$ ならまず間違いなくとける。
　－ $e$ が大きすぎる
　　Wieners attackにより $d$ が求まる。(a)に帰着。
　　具体的には[tex:N}と大差ないくらいの大きさだと怪しい。
　 $e \neq 65537$ のときは、注意すること。
(ハ)平文 $m$ の部分情報の漏洩
　 $m$ の一部分がわかる場合coppersmithの定理(CTFで使う数学後編 - CTFと共に生きる)により $m$ が直接求まる。
　ただし、一部分といっても大半がわからないと解けないことが多い。（ $m$ の半分以上がわかっているとか）(d)に帰着。

最初なのでお世話になっているサイトも紹介しておきます。

攻撃が成立するパラメータの不備がよくまとまっていて神
RSA暗号運用でやってはいけない n のこと #ssmjp
実際の攻撃方法を実装していて神
plain RSAに対する攻撃手法を実装してみる - ももいろテクノロジー

いつもありがとうございます！！！！

具体的な攻撃については次回からやっていきます。