[PlaidCTF 2019] R u SAd?

Description

Tears dripped from my face as I stood over the bathroom sink. Exposed again! The tears melted into thoughts, and an idea formed in my head. This will surely keep my secrets safe, once and for all. I crept back to my computer and began to type.

문제에서 RSA 파이썬 스크립트와 함께 암호화된 flag.enc파일과 공개키 key.sad.pub가 주어진다. key.sad.pub는 python의 pickle모듈을 통해 dump된 Key클래스 파일이다.

먼저 키 생성이 어떻게되는 것인지를 살펴보면 아래와 같습니다.

def genkey(bits):
	assert bits % 2 == 0
	while True:
		p = genprime(bits // 2)
		q = genprime(bits // 2)
		e = 65537
		d, _, g = egcd(e, (p-1) * (q-1))
		if g != 1: continue
		iQmP, iPmQ, _ = egcd(q, p)
		return Key(
			N=p*q, P=p, Q=q, E=e, D=d%((p-1)*(q-1)), DmP1=d%(p-1), DmQ1=d%(q-1),
			iQmP=iQmP%p, iPmQ=iPmQ%q, bits=bits,
		)

여기서 key.sad.pub은 N, iQmP, iPmQ, bits만이 남아있고, 나머지는 다 제거된 상태입니다.

iQmP, iPmQ, _ = egcd(q, p)

iQmP = a, iPmQ = b라고 나타내면 Bézout's identity에 의해서 a*q+b*p=1이 성립합니다.

$aq + bp = 1$

거기에 iQmP=iQmP%p, iPmQ=iPmQ%q으로 되기 때문에 이 iQmP = A, iPmQ = B라고 다시하면 아래와 같이 나타낼 수 있습니다.

$A = a + px \\ B = b + qy$

이제 여기서 A*q + B*p를 계산해봅시다.

$Aq + Bp = (a+px)q + (b+qy)p \\ = aq + bp + pq(x+y)$

여기서 aq+bp=1이고 n=pq이므로 다시 정리하면 아래와 같습니다.

$Aq+Bp = N(x+y)+1$

그런데 이때 우리는 A와 B가 p와 q에 의해 나머지연산된 것이라는 것을 압니다. 그러므로

$(0 < A < p,　0<B<q,　N=pq)$
이고 결국 아래와 같습니다.

$0 < Aq+Bp = N(x+y)+1 < 2N$

$Aq+Bp = N+1$

이제 양옆에 p를 곱하게되면 아래와 같이 정리됩니다.

$Apq+Bpp = pN+p \\ AN+Bp^2 = pN+p$

$Bp^2-p(N+1)+AN = 0$

이제 우리가 잘아는 근의 공식을 사용하면 p를 구할 수 있습니다.

$\frac{(N+1) \pm \sqrt{(N+1)^2-4BAN}}{2B}$

BAN = ((N+1)**2) - 4*B*A*N
BAN, _ = gmpy.root(D, 2)

T = ((N+1)-(BAN))//(2*B)
P = T
Q = N/P
print(N==P*Q)
print("p : " + str(P))
print("q : " + str(Q))

myria@ctf:~/CTF/PlaidCTF/rusad$ python get_pq.py
p : 31659077809885706699482361830477717572837081779677626435829903374921581240849180063108552019274021826092781287218568613206006085334956822705610578514426596962412655157776833178744403034727698399320215892200440936975683502329350531806920697009386909154114556681774784614085691096050135180228131842452179315216957730905902673882170120973148157907231188547167482558383495097819905373068326760590890291412820411304614611983343203819383860434964843931325658872603238498210722446318497674396725811567139923114789843056157733621133155720503541819498078610854651245426825738313809229403279974283490718799392611854934535622307
q : 25004672227855409995386175663336188685177638541286666056441830847618100808198668167307814236224429885295241140194633625051478252429462828073782848889819460674774292004752724556602147320684206242726073358822655212944688523823150236245522627662371134165404316388528738697090763677910441487876514668914442018764569771021916503649822836288868439220382922721194436569302106969570041514638164319835688101248578648742016186666021527781591528560611986692317045407081396778512783312692838307769559661780971287324753785154074832628454871505400166651610503632212720604214996108967812794633118832616768643612648168060802523582631

이제 주어진 rusad.py를 이용해 key파일을 만들어준 후, decrypt하면됩니다.

myria@ctf:~/CTF/PlaidCTF/rusad$ python3 rusad.py decrypt -i flag.enc -o flag -k attack.priv

PCTF{Rub_your_hands_palm_to_palm_vigorously_for_at_least_20_seconds_to_remove_any_private_information}