SECCON BeginnersCTF 2018 に参加したので wite-upを書いたけど解けなかった問題が多かったしコンテスト環境しばらく残していただけるそうなので、後追いでやってみる。（ほぼ大会中の話だったりする）

[Crypto] RSA is Power

問題

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

これだけ。

もうね、これ絶対解けると思ったのよね。
Nを素因数分解して、Eも与えられてるからRSA鍵が作れちゃって、CがCipherだからこれを復号してやれば・・・
ってウキウキで考えてたのよ。
下記、過去CTF問でやったばかりだったから、ここからコードも流用できちゃうからすぐできるじゃん？って。

kusuwada.hatenablog.com

#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse
from Crypto.Util.number import GCD
from Crypto.Util.number import long_to_bytes

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316


# Nを素因数分解する
# http://inaz2.hatenablog.com/entry/2016/01/09/032344
# Nが比較的小さいので、プログラムだけでできそう
def factorization(num):
  # TODO
  return 1

p = factorization(N)
q = N // p
d = inverse(E, (p-1)*(q-1))
key = RSA.construct(map(int, (N, E, d)))

print(long_to_bytes(key.decrypt(C)))

こんなプログラム組んで、よっしゃ、どのアルゴリズムで素因数分解にしようかしら。
なんて思ってましたの。
プログラム中にある通り、ももいろテクノロジーさんのブログからいくつかアルゴリズムを拝借して試してみたんだけど、
全然計算終わらない。

試し割り
Pollard-Rhoアルゴリズム + Miller-Rabin素数判定法
フェルマー法

このあたりを試してみた。

Nが比較的小さいので、プログラムだけでできそう

と信じて疑わなかった＆他の問題に挑戦していたので、いつか解けていると信じてちょっといいスペックのPC（しかしノート）でぶん回して一晩放置しました。

が、起きても計算は終わっておらず。ここで挑戦を終了しました。

同じくももいろテクノロジーさんのサイトで

というのが紹介されており、それぞれインストールして使用するタイプのライブラリのようで他の方のwrite-upでも使っていらっしゃる方いたので、
きっとこいつらに頼っていれば出来たに違いない。

しかし今回は、皆様のwrite-upを拝見している中で
https://factordb.com/
このサイトが紹介されていたのでこちらを使用。
オンラインで素因数分解してくれるサービス（！！！）
今回の問題の値を突っ込んでみると、2秒もせずに答えを表示してくれた。
・・・
えーーーーーっ！？
中でどういう計算になっているのか、どういう構成の計算機が動いているのか、はたまた巨大なマッピングテーブルを持っているのかわかりませんが、
こんなにすぐに終わるとは・・・。
今後もとっても役立ちそうなので、とりあえずブックマーク。

2018/6/7 追記
出題者のれっくすさんの記事を見て factordbでは一度解いたものをキャッシュしているのでは？ということで、コンテスト後半からはこのサービスですぐ答えが出るようになったっぽい。MsieveやYAFUなどのツールを使って解くことを想定していたとのこと。
どっちか入れて使ってみておこうかな・・・。2011年MacBookAirでも耐えられるのか・・・！？

で、解いてもらった p, q は 299681192390656691733849646142066664329 と 324144336644773773047359441106332937713 だったので、これを上記のプログラムに食わせて実行するとflagが得られた。

$ python rsa.py 
b'ctf4b{5imple_rs4_1s_3asy_f0r_u}'

好奇心の足跡

飽きっぽくすぐ他のことをしてしまうので、忘れないため・形にして頭に残すための備忘録。

SECCON BeginnersCTF 2018 復習 [Crypto] RSA is Power

[Crypto] RSA is Power