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) * (q - 1) 이기 때문에 phi(n) 도 자동적으로 구해진다. 구한 phi(n)과 e를 통해 d를 구하고 RSA decrypt를 진행하면 된다. 

다음은 Fermat Factorization Attack을 Python 코드로 구현한 함수이다. 

다음은 Fermat Factorization Attack으로 푼 Meepwn CTF quals 2018의 old_school 문제이다. 

페르마 알고리즘으로 구한 p, q값으로 p / q를 구했을 때 1과 인접한 값이 나오기 때문에 FFA에 취약한 것을 알 수 있다.