문제 구조 분석

제공된 코드는 두 개의 RSA 암호화 시스템으로 구성됩니다. 첫 번째 시스템(소문자 변수)은 flag 암호화에, 두 번째 시스템(대문자 변수)은 첫 번째 시스템의 모듈러스 n을 암호화하는 데 사용됩니다. 두 번째 시스템에서는 P와 Q의 관계에 대한 힌트(gift)가 제공됩니다.

키 복구 공격

gift 값은 P XOR (Q >> 16)으로 정의됩니다. 이를 이용해 Q의 상위 16비트를 제외한 나머지 비트를 점진적으로 복구합니다. 각 비트 위치에서 가능한 4가지 조합(00, 01, 10, 11) 중에서 모듈러스 N을 만족하는 유효한 조합만 선택적으로 탐색합니다.

from Crypto.Util.number import *

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
encrypted_n = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943

def factorize_with_hint(bits, current_p, current_q):
    if len(bits) == 0:
        return
    if current_p * current_q > N:
        return
    if N % (current_p + 1) == 0:
        print(f"Found factor: {current_p + 1}")
        return
    
    remaining_length = len(bits)
    if (current_p + (1 << (remaining_length + 1))) * (current_q + (1 << (remaining_length + 17))) < N:
        return
        
    next_bit = bits[0]
    remaining_bits = bits[1:]
    
    if next_bit == '0':
        factorize_with_hint(remaining_bits, current_p, current_q)
        factorize_with_hint(remaining_bits, current_p + (1 << remaining_length), current_q + (1 << (remaining_length + 16)))
    else:
        factorize_with_hint(remaining_bits, current_p + (1 << remaining_length), current_q)
        factorize_with_hint(remaining_bits, current_p, current_q + (1 << (remaining_length + 16)))

binary_gift = bin(gift)[2:]
partial_p = int(binary_gift[:16] + '0'*(512-16), 2)
remaining_bits = binary_gift[17:]

initial_q = 1 << 511
initial_p = partial_p + (1 << (512-16-1))

factorize_with_hint(remaining_bits, initial_p, initial_q)

연관 메시지 공격

n을 복구한 후에는 두 암호문이 동일한 평문에 패딩 차이만 있는 특징을 이용합니다. Coppersmith의 방법을 적용하여 두 다항식의 최대공약수를 구함으로써 원본 평문을 복구합니다.

def coppersmith_attack(enc1, enc2, padding_diff, exponent, modulus):
    P.<x> = PolynomialRing(Zmod(modulus))
    poly1 = x^exponent - enc1
    poly2 = (x * 256 + padding_diff)^exponent - enc2
    
    while poly2:
        poly1, poly2 = poly2, poly1 % poly2
    return -poly1.monic()[0]

secret_enc = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
flag_enc = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

for length in range(5, 200):
    padding_value = bytes_to_long(b"dasctf{") * (2 ** (length * 8 + 8)) + bytes_to_long(b"}")
    result = coppersmith_attack(secret_enc, flag_enc, padding_value, 11, n)
    plaintext = long_to_bytes(int(result))
    if all(32 <= byte <= 126 for byte in plaintext):
        print(plaintext)
        break