crt-rsa 풀이

개요

오랜만에 간단한 크립토 문제를 하나 풀었다.

문제 상황

from Crypto.Util.number import *
from sympy import nextprime

flag = b'DH{?????????????????????????????????????????}'

q = getPrime(1024)
p = nextprime(q + 1)
N = p * q
while True:
    e = getPrime(256)
    if GCD(e, (p - 1) * (q - 1)) == 1:
        d = inverse(e, (p - 1) * (q - 1))
        break
    
dp = d % (p - 1)
dq = d % (q - 1)
qinv = inverse(q, p)

print(f'N = {N}')
print(f'dp = {dp}')
print(f'dq = {dq}')
print(f'qinv = {qinv}')
print(f'encrypted flag = {pow(bytes_to_long(flag), e, N)}')

N = 17948511...
dp = 98114400...
dq = 78494653...
qinv = 74362464...
encrypted flag = 26902795...

접근

RSA 문제로 보인다. 처음에는 qinv나 dp, dq같은 생소한 값을 함께 출력하는 부분에 착안해 합동식을 조합해 비밀키를 알아내고자 했다.

그러나 아무리 식을 조작해도 풀릴 기미조차 보이지 않았다.

다음으로 눈에 띄는 부분은 소수 p, q를 생성하는 부분인데, 결과적으로 p는 q보다 크면서 아주 비슷한 값이 될 것이라고 추측할 수 있다.

그러므로 sqrt(N) 근처에서 p나 q를 알아낼 수 있을 거라고 추측했다.

풀이

sqrt(N) 근처에서 브루트 포스를 수행한다. 될 지 안 될지는 알 수 없지만 믿져야 본전.

from math import isqrt

base = isqrt(N)
i = 1
while True:
    if(N%(q:=base-i)==0):
        print(f'q={q}\np={N//q}')
        break
    i+=2

sqrt(N) 이하의 가장 큰 정수 base를 구한 후 이보다 작은 홀수(연산 결과 base는 짝수였다)에 대해 N을 분해하는지 확인한다.

q=13397205...
p=13397205...

다행히 순식간에 구해졌다.

이후는 간단하다. d를 (p-1), (q-1)로 나눈 나머지가 주어지므로 중국인의 나머지 정리를 이용하면 d를 복원할 수 있다.

from sympy.ntheory.modular import crt
from Crypto.Util.number import long_to_bytes

crt_m_v = crt([(p-1),(q-1)],[dp,dq])
d = crt_m_v[0]
print(long_to_bytes(pow(c,d,N)))

플래그를 땄다.

다른 풀이

이상하게도 q_inv를 사용하지 않았는데, 원래 의도한 풀이가 따로 존재하는 것 같았다. 문제 제목인 crt-rsa를 검색해 봤다.

To decrypt chiperteks, using the private key (dP, dQ, qInv, p, q) The RSA-CRT decryption algorithm to restore chiperteks into plaintext is as follows:

1) Input chiperteks and Kprivate = (dP, dQ, qInv, p, q). 2) Calculate the value x1 = C^dP mod p. 3) Calculate the value x2 = C^dQ mod q. 4) Calculate h = qInv(x1 - x2) mod p. 5) The results of M = x2 + hq

이대로 계산해 보자.

x1 = pow(c,dp,p)
x2 = pow(c,dq,q)
h = qinv*(x1-x2) % p
M = x2 + h*q
print(long_to_bytes(M))
#b'DH{*******************}'

잘 되네. 신기하다.

정석적인 공격 방법

한편 p와 q를 복원하는 부분에서 내 맘대로 짜서 성공하긴 했지만, 실제로는 좀더 좋은 방법이 있는 것 같다.

이름하여 Fermat Factorazation. 페르마 소수랑 연관 있는 건가 싶은데 잘 모르겠군.

N=pq라면 일반적으로 p와 q는 홀수이고 일반성을 잃지 않고 p>q라 하면

a=(p+q)/2

b=(p-q)/2

이 모두 정수이고 N = a^2 - b^2가 된다.

따라서 N - a^2이 제곱수가 되게 하는 a를 찾는 것이 관건이다.

from sympy.ntheory.primetest import is_square
def fermatfactor(N):
     a = isqrt(N)
     while not is_square(a*a - N):
         a += 1
     b = isqrt(a*a - N)
     return (a-b, a+b)

잘 되긴 하는데 이게 처음 사용했던 방법보다 나은 게 맞는지 잘 모르겠다(?)

모듈러 연산이 없으니 그나마 낫다고 해야 할지…

여담

막상 풀고 나니 새로운 무언가라고 하기에는 좀 부족한 문제였다.

근데 왜 오래 걸렸지.