CODEGATE 2022 암호학 문제입니다.
풀이에는 실패했으나 접근 방식은 맞았었기에 아쉬운 마음이 커서 작성하게 되었습니다.
암호학 방식은 RSA입니다.(Bold 쳐진 부분은 solver의 설명을 참조한 부분입니다.)
문제 분석
#!/usr/bin/python3
from Crypto.Util.number import *
import os
BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS
UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS
FLAG = b'codegate2022{this_is_a_sample_flag}'
def menu1():
while True:
lower = bytes_to_long(os.urandom(LOWER_BITS // 8))
p = UPPER | lower
if isPrime(p): return lower # p가 소수면 lower 반환
def menu2():
p = UPPER + menu1()
q = getPrime(512)
e = 65537
n = p * q
return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)
while True:
print("1. Generate 10 random primes (only lower bits)")
print("2. Encrypt a flag")
idx = int(input("> "))
if idx == 1:
print("How many? (Up to 10)")
num = int(input("> "))
for _ in range(min(10, num)):
print(menu1())
elif idx == 2:
n, c = menu2()
print(f"n : {n}")
print(f"c : {c}")
UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS
본 대회에서 제공된 문제 코드입니다.
문제 풀이를 위해 코드 분석부터 해보도록 하겠습니다.
크게 menu1과 menu2 두가지 부분으로 나뉩니다.
def menu1():
while True:
lower = bytes_to_long(os.urandom(LOWER_BITS // 8))
p = UPPER | lower
if isPrime(p): return lower
menu1 : p가 소수면 216 비트(25 바이트) lower 값을 반환합니다.
어떻게든 UPPER 값을 찾을 수 있다면 p의 상위 비트 중 절반 이상을 알 수 있으므로 Coppersmith 알고리즘을 사용하는 표준 RSA 공격을 통해 n을 인수분해할 수 있습니다.
이는 특정 소수에 대한 나머지 후보를 제거할 수 있습니다.
UPPER + lower가 소수가 되도록 충분한 수의 lower가 주어지면 각 소수 p<700에 대해 UPPER (mod p)에 대해 하나의 가능한 후보를 제외하고 모두 제거할 수 있습니다. 이는 소수 p<700에 대해 UPPER (mod p)를 복구할 수 있음을 의미합니다.
def menu2():
p = UPPER + menu1() # UPPER + lower
q = getPrime(512) # 512 비트 소수
e = 65537 # 65537 알려진 지수 공격
n = p * q # 공개키에 사용되는 (e, n) -> (65537, n)
return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)
menu2 : FLAG값을 포함하여 연산한 값에 FLAG가 포함되어 있습니다.
#!/usr/bin/python3
from Crypto.Util.number import *
import os
BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS
UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS # 37바이트, 206비트만큼 왼쪽으로 이동
FLAG = b'codegate2022{this_is_a_sample_flag}'
def menu1():
while True:
lower = bytes_to_long(os.urandom(LOWER_BITS // 8)) # 25바이트
p = UPPER | lower
if isPrime(p): return lower # p가 소수면 lower 반환
def menu2():
p = UPPER + menu1() # UPPER + lower
q = getPrime(512) # 512 비트 소수
e = 65537 # 65537 알려진 지수 공격
n = p * q # 공개키에 사용되는 (e, n) -> (65537, n)
return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)
# bytes_to_long(codegate2022{this_is_a_sample_flag} + 0x00 + random(91))만큼 랜덤 비트 생성^65537 % n
while True:
print("1. Generate 10 random primes (only lower bits)")
print("2. Encrypt a flag")
idx = int(input("> "))
if idx == 1:
print("How many? (Up to 10)")
num = int(input("> "))
for _ in range(min(10, num)):
print(menu1()) # lower값 획득
elif idx == 2:
n, c = menu2()
print(f"n : {n}") # n
print(f"c : {c}") # bytes_to_long(codegate2022{this_is_a_sample_flag} + 0x00 + random(91))만큼 랜덤 비트 생성^65537 % n
UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS # 37바이트, 206비트만큼 왼쪽으로 이동
최종적으로 분석한 내용은 위와 같습니다.
더보기
시도해본 방법
- 임의의 소수 q를 잡아내보려함 (어림도 없었습니다.)
- 충분한 정보를 수집하여 중국인의 나머지 정리를 적용 (실제로 해본적이 없었기에 대회 당시 생각은 했으나 많이 해매 결국 풀이에는 적용하지 못했습니다.)
더보기
생각 정리
암호화 C = M^e mod n
우리가 구하고자 하는 FLAG값은 M에 들어가 있습니다.
C나 e, n 값은 모두 주어집니다.
복호화 M = C^d mod n
d를 구하기 위해서는 n을 이루고 있는 소수 p, q를 알아야 합니다.
여기서 p는 upper+lower, q는 512바이트짜리 임의의 소수 (p-1)(q-1)을 통해서 phi라는 값을 구해야됩니다. invert(e, phi)를 통해서 d값을 구할수 있기 때문입니다.
문제 풀이
#!/usr/bin/sage
from Crypto.Util.number import *
from pwn import *
from sage.all import *
import math
r = remote("localhost", 9001)
BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS
primes = [ 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659]
remainders = [set([x for x in range(p)]) for p in primes]
def prod(L):
val = 1
for x in L:
val *= x
return val
def get_lower():
r.recvuntil(b"> ")
r.sendline(b"1")
r.recvuntil(b"> ")
r.sendline(b"10")
return [int(r.recvline()) for _ in range(10)]
def get_nc():
r.recvuntil(b"> ")
r.sendline(b"2")
r.recvuntil(b"n : ")
n = int(r.recvline())
r.recvuntil(b"c : ")
c = int(r.recvline())
return n, c
def rsa_high_bits_known(n, c, upper):
F.<x> = PolynomialRing(Zmod(n), implementation='NTL');
pol = x - upper
beta = 0.48 # we should have q >= N^beta
XX = 2 ** LOWER_BITS
epsilon = beta / 7
rt = pol.small_roots(XX, beta, epsilon)
q = int(gcd(rt[0] - upper, n))
p = int(n) // int(q)
assert(p*q == n and p > 1 and q > 1)
phi = (p-1)*(q-1)
e = 0x10001
d = int(pow(e, -1, phi))
plain = int(pow(c, d, n))
print(long_to_bytes(plain))
#### STEP 1. Recover UPPER using crt ####
print("[+] STEP 1. Recover UPPER using crt")
crt_a = [0]
crt_m = [2**LOWER_BITS]
cnt = 0
while prod(crt_m) < 2**BITS:
cnt += 1
if cnt % 10 == 0:
print(f"Gather {cnt*10} primes.. progress : {int(100 * (math.log2(prod(crt_m))-LOWER_BITS) / UPPER_BITS)}%")
lowers = get_lower()
for lower in lowers:
for i in range(len(primes)):
rem = lower % primes[i]
if rem in remainders[i]:
remainders[i].remove(rem)
if len(remainders[i]) == 1:
crt_a.append(primes[i] - remainders[i].pop())
crt_m.append(primes[i])
upper = crt(crt_a, crt_m)
print(f"[+]UPPER = {upper.hex()}")
#### STEP 2. Recover FLAG using RSA Factoring with high bits known attack ###
print("[+] STEP 2. Recover FLAG using RSA Factoring with high bits known attack")
n, c = get_nc()
rsa_high_bits_known(n, c, upper)
위 코드는 solver barkingdog의 풀이 코드로 본 문제 이해에 있어 많은 도움이 되었습니다.
추후 시간이 남는다면 풀이 코드에 대한 해설도 적어보도록 하겠습니다.
암호는 너무 어려운거 같습니다...
