id0-rsa.pubのメモ【Ps and Qs】

ctf crypto

Ps and Qs

以下問題文。

Here is an RSA public key and a message that's been encrypted with it.

-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAKzl5VggSXb/Jm2oqkPeRQwtpmGlLnJT
Nre4LKx3VUljtLzYWj4xoG+aHBouwJT7DyeibpasCH8Yderr4zIGTNUCAwEAAQ==
-----END PUBLIC KEY-----

message:
0xf5ed9da29d8d260f22657e091f34eb930bc42f26f1e023f863ba13bee39071d1ea988ca62b9ad59d4f234fa7d682e22ce3194bbe5b801df3bd976db06b944da


Luckily the recipient was using their random number generator incorrectly resulting in low entropy prime number generation. Here is another public key the recipient generated around the same time.

-----BEGIN PUBLIC KEY-----
MF0wDQYJKoZIhvcNAQEBBQADTAAwSQJCAPsrpwx56OTlKtGAWn24bo5HUg3xYtnz
nTj1X/8Hq7pLYNIVE57Yxoyr3zTOOBJufgTNzdKS0Rc5Ti4zZUkCkQvpAgMBAAE=
-----END PUBLIC KEY-----

Submit the secret message in lowercase hex. Some light reading material

大きな数の素因数分解は難しいが、2つの大きな数の最大公約数を求めることは容易であることを利用した問題。
2つのRSAの公開鍵に同じ素数が含まれていた場合、最大公約数を求めることで簡単にその素数がわかり、素因数分解をして秘密鍵を導出することができる。
割とCTFの問題として出題されるイメージがあり、公開鍵が2つあった場合は疑ってみると良いかもしれない。

公開鍵のパース

まず、opensslで表示した公開鍵の中身を計算に使えるようにパースする。

def parse_rsa_public_key(key):
    """Key is an RSA public-key, return the RSA modulus and exponent as ints."""
    out = subprocess.run("echo '%s' | openssl rsa -pubin -text -noout" % key, shell=True, stdout=subprocess.PIPE).stdout
    out = out.decode("utf-8")
    a = out.find("Modulus:") + len("Modulus:")
    b = out.find("Exponent")
    modulus = out[a:b]
    modulus = modulus.replace(' ', '').replace('\n', '').replace(':', '')
    N = int(modulus, 16)
    c = b + len("Exponent: ")
    d = out.find(" (0x")
    e = int(out[c:d])
    return N, e

あとはそれぞれの公開鍵をパースし、最大公約数を求め、秘密鍵を導出する。秘密鍵ができたら復号しておわり。

from math import gcd
from Crypto.Util.number import inverse
import subprocess

N1, e = parse_rsa_public_key(key1)
N2, e = parse_rsa_public_key(key2)
p = gcd(N1, N2)
q1 = N1 // p
q2 = N2 // p

phi = (p - 1) * (q1 - 1)
d = inverse(e, phi)

m = pow(message, d, N1)
solution = hex(m)[2:]
print(solution)

補足 : pycryptoは便利。

pip install pycrypto

参考