[CryptoHack] RSA Starter 5

풀이

---

공캐 키로 주어진 인자들을 가지고 암호화하였다.

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537

c = 77578995801157823671636298847186723593814843845525223303932

 

이 상황에서 c를 해독한다.

이전 문제에서 RSA의 원리를 공부하였고 여기서 비밀 키 d를 찾으면 된다.

그러기 위해 phi(N)을 구해야하고 이를 쉽게 하려면 N을 인수분해해야한다.

 

N은 생각보다 매우 작은 수이다. 이 정도로 작은 수는 쉽게 안수분해된다.

http://factordb.com/index.php?query=882564595536224140639625987659416029426239230804614613279163 

factordb.com

 

factordb라는 사이트에서 인수분해 한 값을 바로 확인할 수 있다.

 

p = 857504083339712752489993810777

q = 1029224947942998075080348647219

 

이다.

 

이를 이용해서 d를 구하고 암호문을 해독할 수 있다.

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537

c = 77578995801157823671636298847186723593814843845525223303932
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

print(pow(c, d, N))