picoCTF2022 Sum-O-Primes 日本語Writeup

問題概要

RSA暗号では、公開鍵として
$$ n = p \times q $$
が与えられる。
しかしこの問題では
$$ x = p + q $$
も与えられた上で、RSA暗号で暗号化された暗号文cを復号することが求められた。

解法

RSA暗号はpとqが分かれば解読できるので、これを求める。
$$ x = p + q $$
だが、この両辺を2乗して
$$ x^2 = (p+q)^2 $$
$$ x^2 = p^2 + 2pq + q^2 $$
両辺から4pqを引き
$$ x^2 - 4pq = p^2 - 2pq + q^2 $$
$$ x^2 - 4pq = (p-q)^2 $$
また、n = pqより
$$ x^2 - 4n = (p-q)^2 $$
p > qとすると、両辺の正の平方根をとって
$$ p - q = \sqrt{x^2 - 4n} $$
この時点で、xとnは判明しているため、p-qの値は判明した。
また、p+qの値も判明しているため(=x)、この連立方程式を解けばよい。
これを解けば、
$$ p = \frac{x + \sqrt{x^2-4n}}{2} $$
となり、qは
$$ q = \frac{n}{p} $$
によって求められる。

あとはRSA暗号を解けばよい。
$$ \phi(n) = (p - 1) \times (q - 1) $$
$$ d = e^{-1} \mod \phi(n) $$
$$ m = c^d \mod n $$
これで平文mが求まったので、あとはこれを文字にすればよい。

問題を解くスクリプト(Python)

from Crypto.Util.number import *
import gmpy2

x = gmpy2.mpz(0x1b1fb4b96231fe1b723d008d0e7776169ee5d4a8e3573c12c37721cee5de1d882f040d1e3f543d36a574984ad95c1e79e02de14fa136b4be7f4468cbd62773f6a4fd06effc2b845ca07424100466bdfeee652d78b25a4273ba4e950e1a8ebfe256a2f8541fe2207c41f39c2363e23064bc56bed5cf563b8dba873da3c1320256e)
n = gmpy2.mpz(0xb6b2353316c7b0a6c0ecae3bd7d2191eee519551f4ed86054e6380663668e595f6f43f867caa8feda217905643d73453f3797f6096c989fd099852239e5d73c753f909d8efd172d211a4ed4a966dbcbf56b9cbadd416de0a3472a253571b4e4f1bab847a407a27eb37449488f63aedb9f5ec72d9e331ab6154fe45c8cb4e2005d124d1ac8ecd588cd2280e215b078d8ea9da438bbcb1b155a339b91f39e3d17bab112436cdbb6d104fdeb0dce1ac41a1fe8fda0490ef3124794e0383565c299df24ad8a915669469c0b0dc604ed359afb3636d5f633362d8ef9fce7a42f64d5f1f4e50911a15459f97c1b11ee44af4e8bb636895cf75da105a8d1564160ba091)
c = gmpy2.mpz(0x49e426aba3431d9bb73bfc5dd18115dcea3c78a9915e9cf65e060560015c951327f20fe5dd74bfecd9a00659d4f740e42f707e47d8f6b331d8ad1021de41e15f133cbe7c782f22168149df57a6c37095ba6877765a67d8478434a7a5eabb26097404ad464fa0388cacb97a26aaf3b83b6eb0fa73e16bc1de49b33ee64920118f8483feff3634541df97dadad88302392095059cbe56e7148453f16464da8be2b6ca4a6fc0052210f697975fd3c4f3f94bfa3bb2422124a6f0e9685f0440ed020294b6788d7ea3c002d86d86faced8e37b36673ea2b5c72726c66d1834d2dcafdf40220c41dfb3d1f07c5c0d236ce7af86b937476c5aabe33cae8d535713627de)
e = 0x10001


p_minus_q = int(gmpy2.isqrt(pow(x, 2) - 4 * n))

p = (x + p_minus_q) // 2
q = p - p_minus_q

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)

print(long_to_bytes(m).decode())

使用ライブラリ

• gmpy2(平方根を正確に計算したいとき役立った)
• pycryptodome

参考文献

問題自体の参考文献というわけではないが、数式を記述するために以下のサイトを参照した。
https://qiita.com/tomtsutom0122/items/e0ab6b6ccbd369db1aa2 (2022/3/30アクセス)