[Codegate2022] PrimeGenerator

R4v!dus 2022. 3. 7. 22:13

2022. 3. 7. 22:13

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의 풀이 코드로 본 문제 이해에 있어 많은 도움이 되었습니다.

추후 시간이 남는다면 풀이 코드에 대한 해설도 적어보도록 하겠습니다.

암호는 너무 어려운거 같습니다...

'Challenge > CTF' 카테고리의 다른 글

[dvCTF] CyberStreak v2.0 (0)	2022.03.14
[dvCTF] RSA (0)	2022.03.14
[CODEGATE2022] CAFE (0)	2022.03.05
[MHSCTF] Erlenmeyer Biscuits (Cuppa Joe 2) (0)	2022.02.23
[MHSCTF] Cuppa Joe (0)	2022.02.20

R4v!dus