[ImaginaryCTF 2023] - wasteful

뭐랄까,, 이 문제는 되게 간단한 것 같으면서도 사람을 짜증나게 했던 문제이다. 사실 혼자서는 풀지 못했어서 풀이를 봤는데, 뭔가 딱! 하고 떠올라서 푸는 문제가 아니라 되게 흐름대로 가니까 풀렸던 문제인 것 같다.. 약간 처음 접해보는 문제인 것 같다.

🖲️ Code Analysis

from Crypto.Util.number import *
from math import gcd


def keygen(sz):
    p = getPrime(sz // 2)
    q = getPrime(sz // 2)
    n = p * q
    phi = (p - 1) * (q - 1)
    e_fast = getPrime(sz // 2)
    # to make encryption more time consuming :P
    e_slow = e_fast + getPrime(sz // 3) * phi
    d = pow(e_fast, -1, phi)
    return (n, e_slow), (n, e_fast), (n, d)


def encrypt(pub, m):
    n, e = pub
    return pow(m, e, n)


def decrypt(priv, c):
    n, d = priv
    return pow(c, d, n)


pub, pub_fast, priv = keygen(2048)
m = bytes_to_long(open("flag.txt", "rb").read().strip())
c = encrypt(pub, m)
assert c == encrypt(pub_fast, m)
assert decrypt(priv, c) == m
print(f"{pub = }")
print(f"{c = }")

코드는 비교적으로 간단하다. (이 CTF의 대부분의 문제가 그렇다 ㅎㅎ)

 

keygen 함수를 통해서 2개의 e를 만들어내는데, 이 e 들로 암호화를 한 결과는 동일하다. 

$e_{slow} = e_{fast} + t * \phi(n)$ 이기 때문에 $m^{e_{slow}} = m^{e_{fast}} \times m^{t \times \phi(n)} = m^{e_{fast}} \; (mod \, n)$ 이 되어 결과 역시 동일하다. 

 

우리에게 주어진 정보는 $e_{slow}$, 그리고 $n$으로, 이 두 가지 정보만을 이용하여 n 을 인수분해 하는 것이 목표가 될 것이다. 

💡 Main Idea

이 문제를 봤을 때, 먼저 해야 할 일은 $t$를 알아내는 것이다. $n$이 2048 비트이기 떄문에, $\phi(n)$ 또한 2048 비트가 될 것이다. 따라서 주어진 식 $e_{slow} = e_{fast} + t \times \phi(n)$ 의 양 변을 모두 $n$ 으로 나누어보면 $e_{slow} \div n = e_{fast} \div n + t \times (\phi(n) \div n) \approx t$ 로 표현할 수 있을 것이다. 결국 $e_{slow}$ 의 값은 $t$보다 살짝 작은 값일 것이기 때문에 1씩 늘려 주면 원본의 $t$ 를 찾을 수 있을 것이다. 

(n, e_slow) = pub
# e_slow = e_fast + t * (p-1)(q-1)
t = next_prime(e_slow // n)
assert t.nbits() == 2048 // 3

(코드에서는 1씩 늘려주지 않고 그냥 next_prime 함수를 이용해서 구현하였다.)

 

자,, 그러면 이 $t$ 값을 이용해서 어떻게 $\phi(n)$ 의 정보를 가져올 수 있을까? 

만약 $e_{fast}$ 가 $t$ 보다 크기가 작았다면 단순히 $e_{slow}$ 를 $t$ 로 나눈 나머지를 구하는 것만으로도 충분했겠지만, $e_{fast}$의 비트 수는 1024 로 680 언저리인 $t$ 보다는 한참 크다.. 

 

하지만 ! 근사식을 조금 더 변형시켜보면 다음과 같이 바꿀 수 있게 된다. 

$$e_{slow} = e_{fast} + t \times \phi(n) = e_{fast} + t \times (n - p - q + 1)$$

$$t - e_{slow} = t \times (p + q - n) - e_{fast}$$

$$ t - e_{slow} \equiv t \times (p + q) - e_{fast} \; (mod \, n)$$

$$ (t - e_{slow}) \; (mod \, n) \div t \approx p + q $$

 

따라서, $t - e_{slow}$ 값을 n 으로 나눈 나머지를 $t$ 로 나눈 몫은 p + q 에 근사할 것이고, $(p+q)^2 - 4*n = (p-q)^2$ 라는 식을 적용해주면, 결국 $p$ 의 근사값 또한 구할 수 있을 것이다. 

 

이렇게 p 의 근사값을 구했다면, 바로 $Coppersmith Method$ 를 이용해서 sage 의 small roots 함수를 써줄 수 있다!!

📖 Exploit Code

from Crypto.Util.number import *
pub = (13922840822259331816327061476419085409003512519528232469661604921423111313933598569871108546042864180459201549111178812056125732062953204575105829153985440916358190133642640001059768522480269302460718708597523393249631888987925111597599833550446912844403320258488415701628616610291446078064678789122886626285576964983117608034972639529880315364530395658464093479171544352975507100901794069628879853771787404835325718642690170628943504486705897282590391844395048189949020318348859452241379637822658476872641393738097989171169214581791719140741349554748016829670973465416125341357284757048506380319235703137899963208097, 277280553454648256942834244379334472844168843473349557354045626945887508188843789771287658693103957086560979814144224475018152887866998026452048010146805033029525535857427508882228600591838528622357772029813779190474001956391284442790327418967008241712383374750163158501752035607501218757269377329115862935993211034408859090869371053922670217394364484435238584857739198196990517123089953446738914179515819217861804510588560805960014326909359351025582398395246863003472699126965102937701727970546875134667199496557865907051073237849103589853403297723219825816214258909806838856777367332603146213417602038287539276024671910161582026600672105045278321812944891449538504092047724097803562730455612681768718159973804451251572816656604960574129566605495957657313103014678987914865218770999608008584731005908772508291497450420251)
c = 3829822460565637897613746990073994763941184171034737019836828390881076647859928468862763977005814025279072259387758773244151849201650347661717265009919615554395232777636705330792559486048004076300537706604078026741727734943374711480077394341022197696120902084993991738576670236710557122356593411988288326114827264936321401579532665129353852827951354347055111972043781820183887400365339563091888343224947709711699474542183525971689156145628294192147447087789859929759168015997297169275809161690938900939934830602427271340102001253593076013316161869089892572516396348368906753304918487695981844135741146949836634949417

(n, e_slow) = pub
# e_slow = e_fast + t * (p-1)(q-1)
t = next_prime(e_slow // n)
assert t.nbits() == 2048 // 3

res1 = ((t - e_slow)%n) // t
res2 = int((res1^2 - 4 * n).sqrt())

near_p = (res1 + res2) // 2

F.<x> = PolynomialRing(Zmod(n))
f = x + near_p
k = (1024 - (2048 // 3) + 5)
X = 2^k
beta = 0.5

root = f.small_roots(X=X, beta=beta)

p = near_p + int(root[0])
assert n % p == 0
q = n // p

e_fast = e_slow - t * (p-1) * (q-1)
phi = (p-1) * (q-1)
d = inverse_mod(e_fast, phi)
flag = pow(c, d, n)

print(long_to_bytes(flag).decode())