id0-rsa.pubのメモ【Insufficient Key Size】

ctf crypto

Insufficient Key Size

以下問題文。

An incompetent systems administrator accidentally configured the company's encryption system to use very small keys. This RSA key modulus is only 119 bits.

-----BEGIN RSA PUBLIC KEY-----
MBYCD3AY9xf8ZmUVDBSIVPZMSQIDAQAB
-----END RSA PUBLIC KEY-----

Recover the decryption exponent (in lowercase hex).

とりあえず問題文の公開鍵の中身を確認してみる。公開鍵をpub.keyで保存して以下のコマンドを実行。

$ openssl rsa -RSAPublicKey_in -in pub.key -text
Public-Key: (119 bit)
Modulus:
    70:18:f7:17:fc:66:65:15:0c:14:88:54:f6:4c:49
Exponent: 65537 (0x10001)

ここでNとeがそれぞれわかる。また、Nが119bitで極端に短いことに気づく。（以前聞いた話だと512bitくらいまでならお手持ちのパソコンで簡単に素因数分解可能だったはず）
計算しやすいようにNをintに直して素因数分解する。（:を取り除いたものを10進数に直す）

$ python
>>> modulus = int("70:18:f7:17:fc:66:65:15:0c:14:88:54:f6:4c:49".replace(":", ""), 16)
>>> modulus
582043602765817436229812959722228809

素因数分解の方法については以下のようなものがある。
* 自分でプログラムを書く
* factordbにブチ込む
* WolframAlphaにブチ込む
今回はとりあえずfactordbにブチ込んで素因数分解をした。
素因数分解できたら秘密鍵を導出して終了。

from Crypto.Util.number import inverse

p = 662700133751480051
q = 878291059745115859
N = p * q
e = 65537

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(hex(d))