RSA Fermat Factorization Attack

레드벨벳 아이린 최근에 사이버가디언즈 리그에서 RSA 문제들을 풀며 계속 공부하면서 많은 것을 알게 되어 정리한다. RSA 문제를 풀 때 N 값이 주어지면 사용할 수 있는 공격이다. RSA 알고리즘을 알고 있다면 알겠지만, N = p * q이다. 따라서 N의 값이 작다면 p와 q의 값을 쉽게 구할 수 있게 되고, 해당 RSA 암호화는 쉽게 공격당할 수 있다. 컴퓨터는 이에 대응하여 정말 복잡한 소수를 p와 q 값으로 사용한다. 따라서 간단한 Brute-forcing 으로는 RSA를 절대 못풀게 된다. 하지만, 만약 p / q가 1에 근사한 값이라면 Fermat Factorization Attack에 취약해진다. 따라서 페르마 알고리즘을 통해서 p, q 값을 구할 수 있게 되고 phi(n) = (p - 1..