RSA CRT Attack 중국인 나머지 정리

CRT, 중국인 나머지 정리는 

1.  n1​,n2​,n3​과 c1,c2,c3의 값을 알아야 하고
2.  중국인 나머지를 사용하여 계산하면  새로운 값 M과 N을 얻을 수 있음
3. 세제곱근 계산:  M의 세제곱근을 구하면, 원래의 메세지를 복구
4. 바이트로 변환: 이 결과를 바이트로 변환하면 flag 값이 나오게 된다.

이때 중국인 나머지 정리는 

서로 소인 자연수 n1, n2, … , nk와 임의의 정수 a1, a2, … , ak가 있을 때, 임의의 i(1 ≤ i ≤ k)에 대해 
x ≡ ai (mod ni) 로 표현되는 변수 x의 연립 합동 방정식에 대해
이 방정식이 성립하는 값 x=a가 항상 존재하며
또한 그 값은 n1 n2 … nk의 나머지값 안에서 유일하게 존재한다. 
즉, 방정식의 해는 모두 x ≡ a (mod n1 n2 … nk)로 표현 가능하다.

 

https://flyingdcat4.tistory.com/entry/Chinese-Remainder-Theorem%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98-%EB%82%98%EB%A8%B8%EC%A7%80-%EC%A0%95%EB%A6%AC 블로그 참고

 

그래서 코드로 보자면 아래와 같이 나온다

from Crypto.Util.number import *
from sympy.ntheory.modular import crt  # 중국 나머지 정리 사용
import gmpy2 

e = 3  # 공개키가 3인 경우 (RSA의 일반적인 값)


n1 =
c1 = 
n2 = 
c2 = 
n3 = 
c3 = 

# 중국 나머지 정리를 사용하여 결합된 암호화된 값과 모듈러를 계산
# crt는 주어진 리스트의 나머지와 모듈러를 사용하여, 새로운 모듈러와 암호화된 값을 반환.
M, N = crt([c1, c2, c3], [n1, n2, n3])  # M은 결합된 암호화된 값, N은 결합된 모듈러스

# 세제곱근을 사용하여 암호화된 값을 해독
# gmpy2.iroot()는 M의 세제곱근을 반환 이는 e=3일 때, RSA 암호화의 복호화 방법임
m = gmpy2.iroot(M, 3)[0]  # 세제곱근의 첫 번째 반환 값은 정수 부분

plaintext = long_to_bytes(int(m))  # 정수를 바이트로 변환

print(plaintext.decode())  # 출력되는 문자열이 암호화된 원래 메시지