[Write-UP] CRYPTO/Buckeye CTF - Rivest-Shamir-Adleman

이번 블로그는 Buckeye CTF Write up 문제 풀이를 할 것이다.

변명을 하자면, 추석 연휴 겸사 생일이 겹치면서 끝나기 몇 시간 전에 들어가서 문제를 풀기 시작해서

Crypto 한 문제만 풀기도 했고 PWN 분야는 이미 나보다 잘하는 내 팀원이 풀어버렸다.  

우선 나는 Rivest-Shamir-Adleman 문제를 풀었다.

문제 설명에는 " Bing numbers make big security " 라는 문장이 쓰여져 있었다.

근데 제목에는   Rivest-Shamir-Adleman  = RSA를  뜻한다.

 

RSA?

RSA (Rivest–Shamir–Adleman) 암호화 알고리즘을 사용하여 메시지를 암호화 하는 공개키 암호화 시스템으로,

공개 키 (e, n)과 개인 키 (d, n) 쌍을 사용하여 메시지를 암호화 및 복호화 한다.

밑에는 문제 코드이다.

message = b"[REDACTED]"

m = int.from_bytes(message, "big")

p = 3782335750369249076873452958462875461053
q = 9038904185905897571450655864282572131579
e = 65537

n = p * q
et = (p - 1) * (q - 1)
d = pow(e, -1, et)

c = pow(m, e, n)

print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")


# OUTPUT:
# e = 65537
# n = 34188170446514129546929337540073894418598952490293570690399076531159358605892687
# c = 414434392594516328988574008345806048885100152020577370739169085961419826266692

암호화된 메시지를 해독하려면 개인 키 (d, n)를 사용하여 RSA 복호화 알고리즘을 적용해야 한다.

하지만, 위 코드에서는 개인 키 (d, n)과 c 포함한 복호화에 필요한 정보들을 다 줬기 때문에, 복호화 코드를 짤 수 있었다.

 

복호화 코드는 따로 올리지는 않겠다.

 

최종적으로 코드를 짜면 밑에와 같이 bctf { } 가 나온다. 

 

flag SUMBIT