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

난독화가 참 인상적인 문제였다.

해당 치환을 적용해주면

이렇게 코드를 볼 수 있는데

두번째 mode=1이 먼말인지 몰라서 구글링으로 보다가 

안타깝게도 라이트업을 보게 되버렸다 ㅜ.ㅜ

일단 첫번째 조건은 oldzombie 라는 쿠키가 없느냐를 검사하고 있다. 

우리는 else 이하가 필요하므로 있게 만들어야 한다.

두번째 조건은 URL 에서 mode = 1 이라는 파라미터가 있느냐 묻고 있는데

즉 join.php?mode=1 이렇게 하는 거였다.

아 이런거였다니 ( OTL )

그리고 진행해보면 admin이라는 계정은 이미 생성되있다고 나와있는데

난 라이트업을 봐버려서 우회방법을 알아버렸다 ;;

우회방법은 바로~~~

공백이다.

ㅇㅇㅇ..

;;

admin공백을 이용하여 우회하고

로그인 할때는 고냥 공백없이 넣어도 된다.

왜일까

아까 maxlength가 5였으니 5개까지만 들어가서 !~!