seccon 2017 ps and qs

セキュリティ

2017/12/11

seccon 2017 ps and qs

Shota Oikawa

この記事は1年以上前に書かれたもので、内容が古い可能性がありますのでご注意ください。

先週の土日に開催されていた SECCON 2017 に参加してきました。その中で出題された、ps and qs という RSA暗号を用いた問題を取り上げようと思います。この問題の flag は一緒に参加チームメンバーが capture してくれました。

PS and QS

この問題は、暗号文のバイナリ data と、2つの公開鍵が渡されました。ps and qs で検索をかけると Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices がヒットします。この問題は、インターネット上で使用されている多くの RSA 暗号の公開鍵の素数が共有されている脆弱性を模した問題でした。

渡された公開鍵の初めと終わりが以下のようになっていたので、openSSL によって作成された公開鍵であることがわかります。これをツールを使用して dump すると、(N, e) が抽出できます。

"-----BEGIN PUBLIC KEY-----"
"-----END PUBLIC KEY-----"

渡された 2つの公開鍵 (N1, e1), (N2, e2) のうち、合成数である N1 と N2 の最大公約数を求めればよいわけです。合成数というのは、複数の素数を掛け合わせて生成された数のことです。この ps and qs の神託に基づき、N1 と N2 の最大公約数 (gcd) を計算すると、計算結果として素数が取得できるので、それをもとにもう一つの素数も計算します。

最後に、求まった素数を用いて秘密鍵を生成し、暗号を復号化すると flag がゲットできます。