SECCON 2017 online CTF の問題がGitHubで公開されたので、これを後追いでやってみた記事になります。
後追い記事の一覧はこちら
SECCON 2017 online CTF を後追いでみっちりやってみよう！

問題

Ps and Qs
Decrypt it.

psqs1-0dd2921c9fbdb738e51639801f64164dd144d0771011a1dc3d55da6fbcb0fa02.zip (pass:****)

psqs1-*** は添付ファイルへのリンク。

200点問題のCrypto。
競技中は解けそうで解けず、結構時間を使ってしまった。

事前調査

添付ファイルを解凍すると、以下のファイルが出現。

$ file *
cipher:   data
pub1.pub: ASCII text
pub2.pub: ASCII text

公開鍵暗号系の問題のようです。
公開鍵が二つと暗号化ファイルが一つ。これをdecryptするのがミッション。
pubファイルをみた感じRSA暗号の公開鍵のよう。

まずググってみる。Ps and Qsだと、以下のようなサイトが引っかかってなかなかこれというのが出てこない。

なんか英語の慣用句らしい。関係あるんだかないんだか。困ったので検索ワードを変えてみる。
Ps and Qs RSA

おお、っぽいぽい。
最後の日本語の論文から引用。

2012 年に Heninger らと Lenstra らが, それぞれ独立に公開鍵証明書に含まれている多くの公開鍵に脆弱性があることを報告した. 具体的には, RSA の公開鍵の素因数が多数の公開鍵において共有されており, 最大公約数を計算することによって, 素因数分解ができてしまうといったものであった.

ほうほう！
ということはきっと、この二つの鍵について最大公約数を計算することが比較的短時間ででき、(よくわかっていないが、ホニャホニャすることで) 秘密鍵を推定できるということかな？

RSA暗号方式について、使うことはあれど中身の仕組みを深く考えたことがなかったので調べてみる(素因数分解を活用、くらいの知識しかなかった)。下記サイトでちょっとお勉強。

意外にシンプルで小さい数字を例に考えるとわかりやすい。以降、「RSA暗号の仕組みと安全性」の記事を元に考える。　
数学的な説明がメインだったので実際に鍵を作ったりするのは別の知識が必要そうだが、今回はこの知識＋RSA暗号を扱うなにがしかのライブラリの力を借りて解いてみる。

解法

とにかくPythonでRSA暗号を扱うためのライブラリを探してみる。

Crypto::PublicKey::RSA

これがよく使われているよう。
このモジュールを使って、二つの鍵から最大公約数とやらを割り出し、秘密鍵を生成したい。

与えられた二つの公開鍵をimportKeyすると、_RSAobj型のオブジェクトが得られる。
このオブジェクトは以下のデータを持つ

n, the modulus.
e, the public exponent.

上記記事のk1がeにあたる。

何が必要なのかを確認するため、秘密鍵を生成する関数を調査。
construct関数でどうやらRSA keyセットが生成される。
これにより生成されたRSA keyオブジェクトをexportKeyすると、privateKeyを書き出すことができる。
で肝心のconstructをするには、下記のパラメータが必須。

RSA modulus (n).
Public exponent (e).
Private exponent (d). Only required if the key is private.

この中のnとeについては、与えられた公開鍵で使われているもの（今回はpub1.pubのほう）を使用するとして、dを求める必要がある。
上記記事のk2がこのdにあたる。
このdの求め方は、

k1*k2 ≡ 1 mod (p−1)(q−1) なる k2 を取ってくる

※数式が表記できないので、引用ですがわかるように書き直しました。とあるので、すなわち読み替えると
e*d ≡ 1 mod (p-1)(q-1) なる d を計算する、ということ。
なんか難しそうだなぁと思ってググる。

この辺りを参考にすると、dを求めるにはinverse関数を使うと一発らしいということがわかった。モジュラ逆数、のinverseか。

ということで、コードが書けそう。

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

pub1 = RSA.importKey(open("pub1.pub").read())
pub2 = RSA.importKey(open("pub2.pub").read())

N = pub1.n
E = pub1.e
q = GCD(pub1.n, pub2.n)
p = N // q
d = inverse(E, (p-1)*(q-1))

key = RSA.construct(map(int, (N, E, d)))
open("prikey", "bw").write(key.exportKey())

※pを求める時にp = N / qと書いたら、OverflowError: integer division result too large for a floatで怒られた。
python3では/演算子はfloatで返却してくるそうで、大きな数になるとキャパオーバーになってしまうそうだ。明示的に切り捨てのintで返してくれるように指定するには、//演算子を使うらしい。これだとより大きな桁まで計算可能。
参考:How to manage division of huge numbers in Python?

privateKeyができたので、復号してみる。普段やらないのでいちいちググる。。。

$ openssl rsautl -decrypt -inkey prikey -in cipher

flagが出てきました！

感想

今回少々強引に「欲しいもの」を求めるために必要なところだけつまみ食いでググってつないだが、ちゃんと理解するにはオイラーの定理やフェルマーの小定理とかが出てくるらしい。
調べているうちに、この最大公約数を用いたRSA暗号に関する問題は過去のCTFでも登場しているようなので、有名どころだったのかもしれない。
競技中にわちゃわちゃ調べて、既存のスクリプトを使って〜とか考えていたが、実際にコードを書いてみるとすごくシンプルにできて感動。次に出会ったらその時こそは解きたい。

好奇心の足跡

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

Ps and Qs (Crypt, 200)

問題

事前調査

解法

感想