RSA暗号をMsieveで解読する

Last updated at 2024-08-22Posted at 2024-08-22

はじめに

CTFという競技があります。平たく言うと、セキュリティに関する問題が与えられ、様々な手法を駆使して隠されたフラッグを見つけるというものです。

その問題カテゴリに「Crypt」というものがあります。これは主に暗号を解読するという問題です。その中でもRSA暗号は一番簡単な問題としてよく出題されます。

RSA暗号は公開鍵暗号の一つで、公開鍵と秘密鍵のペアを生成し、公開鍵で暗号化、秘密鍵で復号するという仕組みです。秘密鍵の推定は非常に困難なので、これによって、セキュアな情報のやり取りを行うことができます。

以下の記事などに詳しい解説があります。

RSA暗号は$N$の桁数が多く、素因数分解が現実的な時間ではできないということを安全性の根拠としています。しかし、CTFの問題になっている以上、秘密鍵の推定が可能になっています。具体的には、以下のような手順を取ります。

今回は1の手順にフォーカスして解説していきます。

例えば、$N$が$39$だとしましょう。この時、$N$は$3$と$13$の積であることがわかります。このように、$N$が小さい場合は素因数分解が簡単にできます。このとき$\phi$は

$\phi = (3-1)(13-1) = 24$

となります。

では、$N$がより多くの素数の積で、かつ桁数が多いとどうなるでしょうか。$N=120363689$を考えます。おそらくすぐには素因数分解できないと思います。

その場合、$1 \leqq i \leqq \sqrt N$を満たす$i$で$N$を順次割っていく、という考え方で素因数分解を行うという手があります。桁数が大したことなければいいんですが、桁数が大きいとなかなか時間がかかります。計算量は$O(\sqrt N)$です。

しかし、Msieveというツールを使うことで、$N$の桁数が大きい場合でも素因数分解を行うことができます。

今回はWindows環境を想定して解説します。

このソフトでは「楕円曲線法」で素因数分解を行うとされています。楕円曲線は公開鍵暗号アルゴリズムによく使われている手法ですが、今回は詳しい説明は省略します。

まず、Msieveをこちらからダウンロードします。

ダウンロード後、zipファイルを解凍し、解凍したディレクトリのパスを環境変数に通しておきます。

次に、コマンドプロンプトを開き、以下のコマンドを実行します。

msieve153 -qve (正の整数)

msieveの後に来る数字はバージョンを表しています。解凍したディレクトリを漁っていくとexeファイルがあるので、そのファイルの名前をコマンド名として用いることとなります。

オプションはそれぞれ以下のような意味を持ちます。

例えば、$N=120363689$を素因数分解する場合、以下のようになります。

msieve153 -qve 120363689

結果は以下の通りです。

120363689
p2: 17
p2: 19
p2: 53
p2: 79
p2: 89

これによって$120363689$が、$17 \times 19 \times 53 \times 79 \times 89$という形で素因数分解されました。

では、もっと桁数の多い$N$を素因数分解してみましょう。実際にあるCTF問題で出題された$N$を素因数分解してみます。

msieve153 -qev 317903423385943473062528814030345176720578295695512495346444822768171649361480819163749494400347

結果は以下の通りです。

p2: 9953162929836910171
p2: 11771834931016130837
p2: 12109985960354612149
p2: 13079524394617385153
p2: 17129880600534041513

流石にこの桁数になってくると結構時間がかかりますが、愚直に素因数分解を行うよりは早いです。

Msieveを使うことで、桁数の大きい$N$を素因数分解することができました。通常使われているRSA暗号の桁数は$2048$ビットくらいで、これを素因数分解することはたとえMsieveでも現実的ではありません。

しかし、CTFの問題においては、素因数分解が可能な桁数であることが多いので、このようなツールを使って現実的な時間で解読することができます。CTFの問題でRSA暗号が出てきたら、使用してみると良いと思います。