개요
오랜만에 에너지 드링크를 마셨더니 잠이 안 오는 관계로 몇 달 전에 풀었던 간단한 문제를 풀이해보자.
한 번 맞췄던 문제라 다시 푸는 데는 별로 오래 걸리지 않았다. 당연한 거긴 한데…
문제 상황
from Crypto.Util.number import bytes_to_long, getPrime
from secret import flag
p = getPrime(1024)
q = getPrime(1024)
N = p * q
mpq = 0
for i in range(1024):
mpq |= (p if i & 1 else q) & (1 << i)
pt = bytes_to_long(flag.encode())
ct = pow(pt, 0x10001, N)
print('N:', '{:X}'.format(N))
print('mixed prime:', '{:X}'.format(mpq))
print('ct:', '{:X}'.format(ct))
N: 8F0559AB3395690795DCCC816CD804439F43CD...
mixed prime: E21537E91D94255F58D5E8C1F76560E61B0E4EE0E...
ct: 2D5A45809ECF39013441BD7E690EA1D05F44C90B6CAE247BF2...
관찰
주어지는 정보가 상당히 특이한데, 공개 정보, 암호문과 함께 mpq라는 값을 추가로 제공하고 있다. q와 p의 비트를 낮은 자리부터 번갈아 가며 쓰는 식이다.
N을 소인수분해하면 RSA는 뚫린다. 다른 말로는 p와 q 중 하나에 대한 정보가 모두 공개되면 게임 오버, 라는 거다.
이번 문제에서 이는 1,024개의 비트 정보에 해당하고, 만약 아무 단서도 없다면 2^1024회의 브루트 포스를 진행해야 할 것이다.
그러나 추가로 주어진 mpq는, 비록 섞여 있긴 하나, p와 q에 대한 1,024비트의 정보를 제공하고 있다.
정보량의 관점에서 보면 mpq만으로도 RSA를 뚫기에 충분하다는 말이다.
아이디어 및 구현
각 숫자의 least significant한 자리부터 생각해 보자.
q의 0번째 비트는 mpq에서 주어진다. 그러면 p의 0번째 비트를 알 수 있을까?
p[0] * q[0] = N[0]이므로 바로 특정된다.
이 상태에서 다시 생각해 보자.
p의 1번째 비트는 mpq에서 주어진다. 그러면 q의 1번째 비트를 알 수 있을까?
p와 q의 2번째 비트부터는 (p*q)[1]에 영향을 주지 못한다 는 점에 착안하여 등식을 쓰면
p[0~1] * q[0~1] = N[0~1]이고, 이 등식에서 q[1]을 제외한 모든 비트를 알고 있으므로 특정된다.
q의 2번째 비트는 mpq에서 주어진다. 그러면 p의 2번째 비트를 알 수 있을까?
p[0~2] * q[0~2] = N[0~2]이고, 이 등식에서 p[2]을 제외한 모든 비트를 알고 있으므로 또한 특정된다.
위의 과정을 반복하면 온전한 p와 q가 얻어진다.
16진수 데이터를 int로 변환한 후 비트 연산을 이용해 구현할 수 있다. 이진수를 다룰 때는 비트 연산이 아무래도 편하다.
N=int(N_hex, 16)
mpq=int(mpq_hex, 16)
p = mpq
q = mpq
for i in range(1024):
if N&(1<<i) != (p*q)&(1<<i):
if i&1:
q ^= 1<<i
else:
p ^= 1<<i
p와 q를 얻었으므로 평문을 구할 수 있다. RSA 복호화 과정을 직접 구현해도 되지만, 확장 유클리드 호제법 등을 이용해야 한다.
옛말에 바퀴를 다시 발명하지 말라고 하지 않던가. 아, 우리나라 속담은 아니었나? 아무튼. 그냥 온라인 디코더에 필요한 값만 넣어주면 복호화 후 아스키 인코딩까지 해주니 안 쓸 이유가 없다.
https://www.dcode.fr/rsa-cipher
이렇게 플래그를 얻었다.
여담
한동안 웹해킹만 하다 크립토 문제를 다시 보니, 문제가 너무너무 친절해 보인다. 해야 할 일이 무엇인지 알려주다니!? 반면에 웹해킹은…
그나저나 아직도 잠이 오질 않는다. 어떡하지 나…
그럼 다음에,
Gabriel-Dropout
at 16:42
