SECCON CTF 2020 This is RSA writeup
こんにちは！Ken.Sです！
昨日まで開催されていたSECCON CTF 2020のwriteupを書いていこうと思います！
開催期間中には解法が一切分からず、チームメイトからヒント(ほぼ答え)を貰ってなんとかフラグを出せました…。実力じゃあないです(笑)
問題概要
問題名：This is RSA
分野：crypto (warmup)
得点：124pt (62 solves)
問題ファイル
- rsa.rb
- output.txt
解法
rsa.rbを見るとp,qをget_primeという関数で生成しており、その後はいつも通りの暗号化を行っています。このget_primeに何かあるのだろうとにらめっこしてたら時間切れ…。rubyの仕様調べたのに、結局何も分かりませんでした。
肝となるのはunpack1のところ。これ、一文字ずつASCIIコードに直してたんですね。つまりget_primeの流れとして
- 512bitsの乱数を生成する。
- 一桁ずつ上からASCIIコードに直す(16進数)。
- その16進数が素数だったらその値を返す。そうでないなら1. へ戻る。
という感じです。2. が伝わりにくそうなので仮に1234を1.で生成したとすると、
0x31323334という数字を作ります。(1->0x31, 2->0x32, 3->0x33, 4->0x44)
ASCII文字コードの数字は0x30~0x39なので、p,qを16進数に直すと偶数桁目に必ず3が出てきます。これが分かれば解けてたなぁ。
0x3*3*3*3*...3*3*3* × 0x3*3*3*3*...3*3*3* = N となります(* : 0~9)。*に0~9を当てはめていくbruteforceをします。全通り調べると10^64くらいになります(512bitsを16進数にすると128桁、その内不明なのは半分)。普通にbruteforceすることはできません。
ではここでかけ算の筆算を利用します。例えば、123456×987654の下二桁を求めてください。この際、必要な計算は掛けられる数掛ける数の下二桁だけ計算すればいいです。つまり、56×54の下二桁です。実際に計算してみると分かります。123456 × 987654 = 121931812224, 56 × 54 = 3024。下二桁は一致しました。では、下四桁を求めるにはどうしたらいいでしょうか。3456 × 7654の下四桁と同じです。この性質は筆算をしてみれば分かります。
p,qを求めるにはその積であるNと先の性質を利用します。pの下二桁とqの下二桁を掛けるとNの下二桁と一致します。これは16進数にしても同じ話です。p,qの下二桁は3*と分かっているので10×10通りで求められます。下二桁を求めたら下四桁を求めます。下二桁3m×3nが一致したとすると今度は3*3m × 3*3n = Nの下四桁を求めればいいのです。これを繰り返すと、128×10×10程度で求まります。注意すべき点としてはNを16進数に変換して行ってください。
p,qが求まったらあとはいつも通りに復号すればOKです。
solverや問題ファイルはこのgithubに載せてます。
最近、rubyで書かれた問題が多くなりました。前回出た時は特に気にしなくてよかったですが、今回は細かい点を突かれました。rubyの勉強もしないと…！
それでは！
See you next time!
