[picoCTF 2022] Sum-O-Primes

1. Investigation

Hint#1 : I love squares :)

 

문제를 살펴보니 RSA 에 대한 믿음이 막강해서 소수들의 곱 뿐만 아니라 합도 제공해주겠다고 합니다.

힌트#1 에서는 제곱을 사랑한다네요. (?)

---

2. Solution

문제에서 주어진 파일들을 확인해보겠습니다.

 

>> gen.py

#!/usr/bin/python

from binascii import hexlify
from gmpy2 import mpz_urandomb, next_prime, random_state
import math
import os
import sys

if sys.version_info < (3, 9):
    import gmpy2
    math.gcd = gmpy2.gcd
    math.lcm = gmpy2.lcm

FLAG  = open('flag.txt').read().strip()
FLAG  = int(hexlify(FLAG.encode()), 16)
SEED  = int(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)

def get_prime(bits):
    return next_prime(mpz_urandomb(STATE, bits) | (1 << (bits - 1)))

p = get_prime(1024)
q = get_prime(1024)

x = p + q
n = p * q

e = 65537

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = pow(FLAG, e, n)

print(f'x = {x:x}')
print(f'n = {n:x}')
print(f'c = {c:x}')

별 다를게 없는 RSA 알고리즘인데 특이한 부분이 하나 있었습니다.

 

x = p + q ← 바로 이 부분인데 Public Modulus 인 n 값을 만들어내는데 사용한 소수 p, q 의 합을 알 수 있게 코드가 짜여져 있었습니다. (기억해둘 것)

 

>> output.txt

x = 1b1fb4b96231fe1b723d008d0e7776169ee5d4a8e3573c12c37721cee5de1d882f040d1e3f543d36a574984ad95c1e79e02de14fa136b4be7f4468cbd62773f6a4fd06effc2b845ca07424100466bdfeee652d78b25a4273ba4e950e1a8ebfe256a2f8541fe2207c41f39c2363e23064bc56bed5cf563b8dba873da3c1320256e
n = b6b2353316c7b0a6c0ecae3bd7d2191eee519551f4ed86054e6380663668e595f6f43f867caa8feda217905643d73453f3797f6096c989fd099852239e5d73c753f909d8efd172d211a4ed4a966dbcbf56b9cbadd416de0a3472a253571b4e4f1bab847a407a27eb37449488f63aedb9f5ec72d9e331ab6154fe45c8cb4e2005d124d1ac8ecd588cd2280e215b078d8ea9da438bbcb1b155a339b91f39e3d17bab112436cdbb6d104fdeb0dce1ac41a1fe8fda0490ef3124794e0383565c299df24ad8a915669469c0b0dc604ed359afb3636d5f633362d8ef9fce7a42f64d5f1f4e50911a15459f97c1b11ee44af4e8bb636895cf75da105a8d1564160ba091
c = 49e426aba3431d9bb73bfc5dd18115dcea3c78a9915e9cf65e060560015c951327f20fe5dd74bfecd9a00659d4f740e42f707e47d8f6b331d8ad1021de41e15f133cbe7c782f22168149df57a6c37095ba6877765a67d8478434a7a5eabb26097404ad464fa0388cacb97a26aaf3b83b6eb0fa73e16bc1de49b33ee64920118f8483feff3634541df97dadad88302392095059cbe56e7148453f16464da8be2b6ca4a6fc0052210f697975fd3c4f3f94bfa3bb2422124a6f0e9685f0440ed020294b6788d7ea3c002d86d86faced8e37b36673ea2b5c72726c66d1834d2dcafdf40220c41dfb3d1f07c5c0d236ce7af86b937476c5aabe33cae8d535713627de

output 으로는 소수 p, q 의 합인 x, Public Modulus 인 n, 암호문 c 를 제공해주고 있습니다.

 

그래서?

소수 p, q 의 합인 x 를 가지고 무엇을 할 수 있을까요?

 

Public Modulus 인 n 을 이미 알고 있다는 전제 하에 x 와 n 만을 이용하여 소수 p, q 의 값을 정확히 알아낼 수 있습니다.

 

어떻게?

잠시 중학생 때 배웠던 수학을 떠올려봅시다.

 

근이 α, β 인 이차방정식을 어떻게 만들 수 있을까요?

 

바로 다음과 같습니다:

 

위 식을 풀면 아래와 같은 이차방정식이 만들어집니다:

 

여기서 우리가 만약 α, β 을 모른다고 하더라도 α + β 와 αβ 를 알고 있다면 근의 공식을 이용하여 α, β 의 값을 알아낼 수 있게 됩니다.

 

이번에는 근이 p, q 인 이차방정식을 만들어 봅시다:

 

위 식을 풀면 아래와 같은 이차방정식이 만들어집니다:

 

pq 는 곧 n = pq 이기 때문에 아래와 같이 정리 가능합니다:

 

이제 어떻게 문제를 풀어야할지 감이 잡히시나요?

 

(저는 SageMath 를 사용하여 컴퓨터가 알아서 근을 구하도록 했습니다.)

 

>> Sum-O-Primes-sol.py

'''
# Implemented in SageMath
# If we know p + q in rsa, we can find solution of f(x) = (x - p)(x - q) = 0.
# Since, (x - p)(x - q) = x^2 - (p + q)*x + N.

A = 0x1b1fb4b96231fe1b723d008d0e7776169ee5d4a8e3573c12c37721cee5de1d882f040d1e3f543d36a574984ad95c1e79e02de14fa136b4be7f4468cbd62773f6a4fd06effc2b845ca07424100466bdfeee652d78b25a4273ba4e950e1a8ebfe256a2f8541fe2207c41f39c2363e23064bc56bed5cf563b8dba873da3c1320256e
n = 0xb6b2353316c7b0a6c0ecae3bd7d2191eee519551f4ed86054e6380663668e595f6f43f867caa8feda217905643d73453f3797f6096c989fd099852239e5d73c753f909d8efd172d211a4ed4a966dbcbf56b9cbadd416de0a3472a253571b4e4f1bab847a407a27eb37449488f63aedb9f5ec72d9e331ab6154fe45c8cb4e2005d124d1ac8ecd588cd2280e215b078d8ea9da438bbcb1b155a339b91f39e3d17bab112436cdbb6d104fdeb0dce1ac41a1fe8fda0490ef3124794e0383565c299df24ad8a915669469c0b0dc604ed359afb3636d5f633362d8ef9fce7a42f64d5f1f4e50911a15459f97c1b11ee44af4e8bb636895cf75da105a8d1564160ba091

x = var('x')

f = x^2 - A*x + n
#print(f)

p, q = solve(f == 0, x)
print(p)
print(q)
'''

import math

p = 164835494260217071382678895425735808406535017400082400754856273491643724646229724348288020393864609224570393479618139327815990256813074846497080513682510420950489208065538161863662253258975974440161544649768192767706751015138346355681900542579387552792425991641079585300654515662754392928884112544177614392079
q = 139916764614806908246583886373837970228055394443550294549913446222854757003217893373251434985194109542680018702462195178704367740846416201876205869576073127196630784795011094736997433428438852280354101375245935432927445002098437154710187833752657703151726757660055064708074016708725761243033132884002591578719
n = p * q
e = 65537

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = 0x49e426aba3431d9bb73bfc5dd18115dcea3c78a9915e9cf65e060560015c951327f20fe5dd74bfecd9a00659d4f740e42f707e47d8f6b331d8ad1021de41e15f133cbe7c782f22168149df57a6c37095ba6877765a67d8478434a7a5eabb26097404ad464fa0388cacb97a26aaf3b83b6eb0fa73e16bc1de49b33ee64920118f8483feff3634541df97dadad88302392095059cbe56e7148453f16464da8be2b6ca4a6fc0052210f697975fd3c4f3f94bfa3bb2422124a6f0e9685f0440ed020294b6788d7ea3c002d86d86faced8e37b36673ea2b5c72726c66d1834d2dcafdf40220c41dfb3d1f07c5c0d236ce7af86b937476c5aabe33cae8d535713627de

flag = pow(c, d, n)
flag = bytes.fromhex(format(flag, 'x'))
print(flag)
# b'picoCTF{12****ab}'

 

🚩 FLAG : picoCTF{12****ab}

---

P.S.

사실 위 방법보다 더 쉬운 방법 또한 존재합니다.

 

RSA 에서 개인키를 구할 때 오일러 피함수를 이용하여 구하는데, 이 때 오일러 피함수는 아래와 같습니다:

 

이를 풀면 아래와 같습니다:

 

공개키(n, e) 값과 (p + q) 을 알고 있다는 전제 하에 우리는 위와 같이 오일러 피함수 값을 알아낼 수 있기 때문에 개인키 d 를 구해 암호문을 복호화할 수 있습니다:

---

REF#1 : https://crypto.stackexchange.com/questions/87308/relation-between-factors-and-their-sum-on-rsa