RSA 암호화 시스템에서 발생하는 몇 가지 흥미로운 취약점을 분석하고 이를 이용해 암호문을 해독하는 방법을 살펴보겠습니다. 특히, 소인수 $p$와 $q$가 매우 가까운 경우를 다루는 기법에 초점을 맞춥니다.
취약점 분석: $p$와 $q$의 근접성 RSA의 공개키는 모듈러스 $n$과 공개 지수 $e$로 구성됩니다. 여기서 $n = p \times q$이며, $p$와 $q$는 큰 소수입니다. 만약 $p$와 $q$가 소수열에서 서로 바로 이웃하는 관계라면, $n$의 제곱근 $\sqrt{n}$을 계산했을 때 그 결과값은 $p$와 $q$ 사이에 위치하게 됩니다. 이 값은 소수가 아니며, 이로부터 $p$와 $q$를 복구하는 것이 가능해집니다. 구체적인 공격 방법은 다음과 같습니다:
- $n$의 제곱근 $\lfloor \sqrt{n} \rfloor$을 계산합니다.
- 계산된 값에 가장 가까운 소수 $p'$를 찾습니다.
- $p'$가 $p$인지 확인합니다. 만약 $n$을 $p'$로 나누었을 때 나머지가 0이면, $q = n / p'$가 되어 $p$와 $q$를 모두 찾은 것입니다.
- 만약 $p'$가 $p$가 아니라면, $p'$의 다음 소수를 $q'$로 가정하여 $p'$와 $q'$를 찾습니다. 이 방법은 $p$와 $q$가 매우 가까울 때 효과적입니다. 하지만 이 방법만이 유일한 것은 아니며, $p$ 또는 $q$ 중 하나가 소수가 아니더라도 적용할 수 있는 다른 기법도 존재합니다.
RSA 암호화 과정 예시 (Python) 다음은 $p$와 $q$를 생성하고 RSA 암호화 키를 설정하는 과정입니다.
import gmpy2
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
# 공개 지수 설정
public_exponent = 65537
# 1024비트 소수 p 생성
prime_p = getPrime(1024)
# p의 다음 소수를 q로 설정
prime_q = gmpy2.next_prime(prime_p)
# 모듈러스 n 계산
modulus_n = prime_p * prime_q
# 메시지(flag)를 바이트로 변환하여 정수로 만듦
plaintext_message = bytes_to_long(b"flag{example_secret_message}")
# 메시지를 공개키 (public_exponent, modulus_n)로 암호화
ciphertext = pow(plaintext_message, public_exponent, modulus_n)
print(f"Modulus n: {modulus_n}")
print(f"Ciphertext c: {ciphertext}")
RSA 복호화 코드 예시 주어진 $n$과 암호문 $c$를 이용하여 비밀 메시지 $m$을 복호화하는 코드입니다. 이 코드에서는 $p$와 $q$가 서로 가깝다는 점을 이용합니다.
import gmpy2
from Crypto.Util.number import isPrime, long_to_bytes
# 주어진 모듈러스 n 값
n = 14649512071940761295526637299115559124785876291769759641385535810496168571356390875028933662157908527898907054595131961482960199302467356648190631379274697720401554559470504824985612622685394835695867966115901784024976569320394309553109935293587085148062564681314500481394907365147112082687540360098391086714184976743558033278590993154588786124775939766047431416725457741728688637126487364728587712375561695773966767394586311222451769970033239320178997793213284313210443479640426969378574483212255956628018029837363008023768111344140167747248153597634302708520935820581465887878375715293178199822355763254571306861917
# 주어진 암호문 c 값
c = 12027845013546239316392609172930965416584271242308913354667016233680471230190790405734811583067266163929286181494107261515098660000911579736414996680283956326170766501669935802000154155100686665545895817739485941641910099289990601294438262123368049333984283589964986184064905792613875257151557808151252971101910091243823103407818141675466520285172900274592414845571880035970983902425078647997819177759066019180722029670490597477951055687802318789372881560617674901053734286030365059070206136368543590547536318698381100062114654273208529717439733092703250435608159570238122076785000005010026224446523393666360709957236
# 공개 지수
public_exponent = 65537
# n의 제곱근을 계산하고 거기서부터 p를 찾기 시작
potential_p = gmpy2.iroot(n, 2)[0] - 10000
# potential_p가 소수가 될 때까지 증가시키며 확인
while not isPrime(potential_p):
potential_p += 1
# potential_p의 다음 홀수를 q로 설정하고 소수인지 확인
potential_q = potential_p + 2
while not isPrime(potential_q):
potential_q += 2
# p * q가 n이 될 때까지 반복 (p와 q가 연속된 소수 쌍이 아닐 경우 대비)
while potential_p * potential_q != n:
potential_p = potential_q
potential_q = potential_p + 2
while not isPrime(potential_q):
potential_q += 2
# 오일러 파이 함수 계산: phi(n) = (p-1)*(q-1)
euler_phi = (potential_q - 1) * (potential_p - 1)
# 개인 지수 d 계산: d * e ≡ 1 (mod phi(n))
private_exponent = gmpy2.invert(public_exponent, euler_phi)
# 암호문을 복호화하여 원래 메시지 m 복구
decrypted_message = gmpy2.powmod(c, private_exponent, n)
# 복구된 메시지를 바이트로 변환하여 출력
print(long_to_bytes(decrypted_message))
함수 설명
pow(m, e, n) 함수는 $m$의 $e$ 제곱을 $n$으로 나눈 나머지를 계산합니다. 즉, $m^e \pmod{n}$을 구합니다. 이는 RSA 암호화 및 복호화에서 핵심적인 연산입니다.
이러한 취약점을 이해하고 이를 활용하는 것은 CTF(Capture The Flag)와 같은 보안 관련 대회에서 RSA 암호 문제를 해결하는 데 중요한 기술입니다.