암호화한 python코드를 보면 p=q인 것을 확인할 수 있다. 따라서 n=p*q=p^2이므로 p, q는 n의 제곱근이다.
sqrt()로 n의 제곱근을 구해주었다. 구한 값을 제곱하여 제대로 구해진 것이 맞나 확인해보니, 제곱근이 잘 구해졌음을 알 수 있었다.
e 모듈로 phi의 역을 구하는 과정으로 d값을 찾아준 후, c모듈로 phi의 d제곱을 해주어 m값을 구했다.
파이썬에서 pycrypto의 long_to_bytes함수를 이용하여 바이트로 바꿔주었는데, 값이 이상하게 나왔다.
phi를 p(p-1)로 바꿔서 다시
FLAG : flag{squarePrime_is_dangerous}
rememberSWINGCTF
문제의 파이썬 코드에서 p를 임의적으로 선택한 후, q값은 next_prime(p)로 정해주었기 때문에 p/q의 값은 1에 근사하게 되고, 따라서 해당 문제에서의 암호화는 Fermat Factorization Attack에 취약하다. 페르마 알고리즘으로 p, q값을 구해주고, 복호화를 해주자.
