[드림핵] chinese what? - RSA CRT 암호학 문제 풀이

RSA와 중국인의 나머지 정리(CRT)

 

RSA(Rivest-Shamir-Adleman)는 공개키 암호화 알고리즘 중 하나로, 안전한 통신을 위해 사용됩니다. RSA에서는 두 개의 큰 소수 ( p )와 ( q )를 선택하여 이들의 곱으로 ( N )을 생성합니다. 즉, ( N = p \times q )입니다. 이 ( N )은 공개키로 사용되며, 암호화에 필요합니다.

 

공개키와 개인키를 생성하기 위해 오일러의 피 함수 ( \phi(N) = (p-1)(q-1) )을 계산하고, 이를 이용하여 공개키 ( e )와 개인키 ( d )를 계산합니다. 여기서 ( e )는 ( \phi(N) )과 서로소인 임의의 정수이며, ( d )는 ( e )에 대한 모듈러 역수로서 ( e \times d \equiv 1 \pmod{\phi(N)} )을 만족해야 합니다.

 

중국인의 나머지 정리(CRT, Chinese Remainder Theorem)는 여러 모듈러 연립 방정식을 풀 때 사용되는 수학적 원리입니다. 이는 한 개의 정수를 여러 소수로 나누어 나머지를 취한 뒤, 이를 이용하여 해당 정수를 복원하는 방법을 제공합니다.

CRT를 사용하는 상황은 주로 RSA와 같은 공개키 암호화에서 발생합니다. RSA에서는 여러 소수의 곱인 ( N )을 사용하여 암호문을 생성합니다. 이때, CRT를 사용하면 ( N )이 매우 큰 경우에도 각 소수에 대한 연산만 수행하여 효율적으로 암호문을 해독할 수 있습니다.

 

이 문제에서 CRT를 사용하는 이유는 세 개의 소수로 생성된 ( N )에 대한 암호문이 주어졌기 때문입니다. 각 소수에 대한 모듈러 연립 방정식을 풀기 위해 CRT를 사용하면 플래그를 쉽게 복원할 수 있습니다.

 

---

 

prob.py

 

from Crypto.Util.number import bytes_to_long, getPrime

flag = bytes_to_long(b'DH{???????????????????????????????????????????????????????}')

p1 = getPrime(420)
p2 = getPrime(420)
p3 = getPrime(420)

print(f'p1 = {p1}')
print(f'p2 = {p2}')
print(f'p3 = {p3}')
print(f'c1 = {flag % p1}')
print(f'c2 = {flag % p2}')
print(f'c3 = {flag % p3}')

 

 

prob.py는 세 개의 랜덤한 소수 ( p_1 ), ( p_2 ), ( p_3 )를 생성하고, 각 소수로부터 생성된 모듈러 값에 플래그를 대입하여 암호문을 생성합니다.

 

 

이 문제에서 주어진 페이로드는 첫 번째 코드 블록에서 암호화된 플래그입니다.

 

---

 

exploit.py

 

from Crypto.Util.number import long_to_bytes

# output.txt 파일에서 소수와 암호문 읽어오기
with open('output.txt', 'r') as f:
    lines = f.readlines()
    p1 = int(lines[0].split('=')[1].strip())
    p2 = int(lines[1].split('=')[1].strip())
    p3 = int(lines[2].split('=')[1].strip())
    c1 = int(lines[3].split('=')[1].strip())
    c2 = int(lines[4].split('=')[1].strip())
    c3 = int(lines[5].split('=')[1].strip())

# 중국인의 나머지 정리를 사용하여 각 소수에 대한 암호문의 값을 복원
N = p1 * p2 * p3
N1 = N // p1
N2 = N // p2
N3 = N // p3

# 각 소수에 대한 모듈러 역원 계산
s1 = pow(N1, -1, p1)
s2 = pow(N2, -1, p2)
s3 = pow(N3, -1, p3)

# 중국인의 나머지 정리를 통해 플래그 복원
m = (c1 * N1 * s1 + c2 * N2 * s2 + c3 * N3 * s3) % N

# 복원된 플래그 출력
flag = long_to_bytes(m)
print(flag.decode())

 

 

• 주어진 소수들 ( p_1, p_2, p_3 )을 이용하여 ( N = p_1 \times p_2 \times p_3 )을 계산합니다.
• 각 소수에 대한 ( N )의 모듈러 역원을 계산합니다. 즉, ( N_1 = N / p_1, N_2 = N / p_2, N_3 = N / p_3 )을 계산하고, 이들에 대한 모듈러 역원 ( s_1, s_2, s_3 )을 구합니다.
• 중국인의 나머지 정리를 이용하여 플래그를 복원합니다. 즉, ( m = (c_1 \times N_1 \times s_1 + c_2 \times N_2 \times s_2 + c_3 \times N_3 \times s_3) \mod N )을 계산합니다.
• 복원된 ( m )을 바이트로 변환하여 원래의 플래그를 얻습니다.

 

 

플래그가 잘 출력되었습니다 ^^

 

 

---