RSA에 대해 공부하기 전에 이 문제를 봤을 땐 시도할 엄두가 안나서 넘겼었는데

요번주에 RSA에 대해서 배운 후 다시 이 문제를 풀어보았다.

출제자의 의도는 hint = (d+q)^(d-q) 에서 xor 특징을 이용한 bit 관련 BF 공격이였다.

( 사실 이 공격방법은 아직 이해를 못하였다. )

하지만 출제자가 문제를 잘못내서 gint만 가지고도 문제를 풀 수 있었고

대부분의 라이트업이 그렇게 풀어져 있었다.

하지만 라이트업들이 뭔가 조금씩 부족한 부분이 있어서 애를 먹었는데

한번 내가 이해한 그대로 블로그에 자세히 기록해두겠다.

1. 문제 요약 

N = pq ( p,q is prime )

e that satisfy ((p-1)(q-1), e) = 1

d = e modular inverse at N

Public Key ( N, e ) 와 g = d(p-0xdeadbeef)를 알 때, enc_flag = flag^e mod N 를 복호화해라.

전형적인 RSA 문제이다. 

우리는 어떻게 N을 소인수 분해할까를 먼저 고민하는데 

0xdeadbeef를 c ( 상수 )라 두면

(p-c) 

우리는 여기서 페르마의 소정리를 활용할 생각을 해보아야 한다.

페르마의 소정리 : a^(p-1) mod p = 1

증명 : 생략

그리고 RSA 암호화, 복호화에 이용되는 성질인 M^ed mod N = M 에 대해서도 활용하여야 한다.

a^eg = a^ed(p-c)

a^eg ≡ a^(p-c) ( mod N )  ∵ a^ed mod N = a

a^eg * a^(c-1) ≡ a^(p-1) ( mod N )

a^(p-1) mod N = r ⇔ a^(p-1) = kN + r

a^(p-1) mod p = 1 ⇔ kN+r mod p = 1 ⇔ r mod p = 1 ⇔ r = kp + 1

⇔ a^(p-1) mod N = kp+1 

( cf. k는 그냥 상수라고 보고 의미없으니 그냥 넘기자 )

a^(p-1)mod N - 1 = kp

(a, N) = 1을 만족하고 그외 앞에 식의 조건들을 만족시키는 수들중 가장 작은 a = 2

2^(eg + (c - 1)) mod N - 1 = kp

(kp, N) = p (  ∵ if k = q, a^(p-1) mod N > N -> false )

그러면 p를 구할 수 있다.

p를 구하면 q = n/p 부터 시작해서 d까지 모두 구해낼 수 있다.

페이로드는 파이썬으로 짜보았다

RSABaby.py