BabyRSA: 공통 모듈러스 공격(Common Modulus Attack)

BabyRSA 문제는 동일한 모듈러스 $n$을 사용하고 서로 다른 공개키 $e_1, e_2$로 암호화된 두 개의 암호문 $c_1, c_2$가 주어졌을 때, 메시지 $m$을 복구하는 문제입니다. $gcd(e_1, e_2) = 1$인 경우 확장 유클리드 알고리즘을 사용하여 $s_1 e_1 + s_2 e_2 = 1$을 만족하는 $s_1, s_2$를 구할 수 있으며, 이를 통해 $m$을 추출할 수 있습니다.

from Crypto.Util.number import long_to_bytes
import gmpy2

def solve_common_modulus():
    e1 = 3247473589
    e2 = 3698409173
    n = 5497857005549635433932229... (중략)
    c1 = 2956587880741578166703935... (중략)
    c2 = 2194543570173591382385633... (중략)

    # 확장 유클리드 알고리즘 적용
    g, s1, s2 = gmpy2.gcdext(e1, e2)
    
    # s1 또는 s2가 음수일 경우 모듈러 역원을 계산하여 처리
    if s1 < 0:
        m1 = gmpy2.invert(c1, n)
        s1 = -s1
    else:
        m1 = c1
        
    if s2 < 0:
        m2 = gmpy2.invert(c2, n)
        s2 = -s2
    else:
        m2 = c2

    # 메시지 복구: m = (c1^s1 * c2^s2) % n
    res = (gmpy2.powmod(m1, s1, n) * gmpy2.powmod(m2, s2, n)) % n
    print(long_to_bytes(res))

solve_common_modulus()
# 결과: flag{baby_r3a_sierting_2023}

EasyRSA: 공개키 및 개인키 파싱

이 문제는 RSA 공개키와 개인키가 PEM 형식으로 제공되었습니다. 개인키 $d$가 이미 노출되어 있으므로, 단순히 암호문을 복호화 공식 $m = c^d \pmod n$에 대입하면 됩니다.

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes
import base64

def decrypt_easy_rsa():
    private_pem = """-----BEGIN RSA PRIVATE KEY-----
MIICWwIBAAKBgQCjkl/AEfPwrKmrD3wu1S+Wic4nPFvShSNfdtEh4RIZnFne8qeQ5fVH14MyxyCGSRMXew9QsCMQDBwDR1eqhf+xRHncBDB7rAcWwFrI10FBhXhDJs6PklFW20Zw0sP42cAjaKH0H7pFTu/uQgc1eUvzeVg05PvG78H6wwwPQB3VuQIDAQABAoGADZ61jFeyWTr3UcATVg74TG+jE89J0gi1/k/1b/2+tRU4woCwBTewqc+/I+5Cvgu9pDnh95UDBmYLuxYorZFEzgrSa3rZ5y7OFQZl9nXapt2LttBXoQaWf3jtyslsGmfNi/VuNgKaiiVwINhVG8NeIFzzAB3AqNDitHlKDalkKZECQQDN1lZKV8bximZNDVL9CajmdE6f3DobYgGNvOXsOS4Qkzx+/3LvAbqSiiiel5V08pBIG18DRIpxBRN57z8fbJxlAkEAy28zeeMeb3ZFL7/iyosQ8RWrz3/BxlUtREh9GSplRa7EJtjm852IQCk98lg2HR++tuugmdtVAS0lxd/UVDXMxQJAFaVwtai9dzFCyN+Z1pppdLLOgek7Ax4vY6R12X255mxVdFWQ1Kmt4TM+Sk9OnFnV6n9WYpWWqYQLJEuQq9FUMQJAe6Vt+yJhCEwxRxFw7bxSosWSNL8o7rwslDke1+HdxdmwXRAuZ1mTS7QFc7vLwC3gQ9u5NGqMIvfm4nrl2f0NJQJAJrOQDrZX/KpYAnFmW8IGXxkcJrtdB2Xi9VN1WdC9r4QGz28X5ScH0o9mcYVxaDxzNU7A9DPiRL28fAltiGdJLg==
-----END RSA PRIVATE KEY-----"""
    
    key = RSA.importKey(private_pem)
    encrypted_msg = "QhS9n7TkavmU8E4CFa872ZzqIq/NG/agtCkxQBzB0/E1PDZRv6otOYxBLsxwd/7h0fPkYYMCpPt4nXqYBGQ/n8/F3q3spV94+IFs7+CjyybUvAQg8MXLgSTzVt+ua0Ub0/et5/7Q1xAcgzT3/jWHwjklEAykdpSYMAqv5PQrhT4="
    
    c = int.from_bytes(base64.b64decode(encrypted_msg), 'big')
    m = pow(c, key.d, key.n)
    
    print(long_to_bytes(m).decode())

decrypt_easy_rsa()
# 결과: flag{c2915ff0a0ca8ffd50af20cd27682ff2}

ezPython: 다중 인코딩 역산

입력된 플래그가 카이사르 암호, 문자열 반전, Atbash 암호, Base64(20회), Base100 순서로 인코딩되어 있습니다. 이를 역순으로 풀어내면 원본 플래그를 얻을 수 있습니다. Base100의 경우 이모지 형태로 표현되므로 공백을 제거한 후 디코딩해야 합니다.

from qsnctf import *
import base64

def reverse_encoding():
    data = "👍👤🐧👮..." # 주어진 이모지 데이터
    # 1. Base100 디코딩
    current = base100_decode(data.replace(" ", ""))
    
    # 2. Base64 20회 반복 디코딩
    for _ in range(20):
        current = base64.b64decode(current).decode()
    
    # 3. Atbash 암호 해제
    current = atbash_cipher(current)
    
    # 4. 문자열 반전 21회 수행
    for _ in range(21):
        current = current[::-1]
        
    # 5. 카이사르 암호 해제 (오프셋 8)
    final_flag = caesar_decrypt(current, 8)
    print(final_flag)

# reverse_encoding() 호출 시 flag 획득 가능
# 결과: flag{dea8a56c1dcf73ae7fa75c52af41bb70}

N and n: 확장 위너 공격 및 연분수 공격

이 문제는 플래그가 두 부분으로 나뉘어 있으며, 각각 서로 다른 암호화 방식이 적용되었습니다.

Part 1: 공개키 $e_1, e_2$가 $\phi(N)$에 비해 매우 큰 경우입니다. 격자 기반의 LLL 알고리즘을 사용하여 $\phi(N)$을 도출하고 $d$를 계산합니다.

# SageMath Script
N = 30344300732...
e1 = 67828306822...
e2 = 21032143363...
C = 29989464921...

m_bound = N^(0.5)
alpha = 729 / 2048
m2_bound = N^(1 + alpha)

# LLL 격자 구성
lat = diagonal_matrix(ZZ, [N, m_bound, m2_bound, 1])
base_mat = matrix(ZZ, [[1, -N, 0, N^2], [0, e1, -e1, -e1*N], [0, 0, e2, -e2*N], [0, 0, 0, e1*e2]]) * lat
reduced_lat = base_mat.LLL()
vector_x = reduced_lat[0] * base_mat^-1

phi_val = int(vector_x[1] / vector_x[0] * e1)
priv_d = inverse_mod(65537, phi_val)
m1 = pow(C, priv_d, N)
print(bytes.fromhex(hex(m1)[2:]))

Part 2: $e$가 $(p^2-1)(q^2-1)$에 대한 역원으로 정의된 경우입니다. 연분수 전개(Continued Fraction Expansion)를 통한 위너 공격의 변형을 사용하여 $d$를 찾습니다.

# SageMath Script
n = 85956565536...
e = 29974200486...
c = 12669560272...

# 연분수 공격 시도
target_val = e / (n^2 - 2.25*n + 1)
fractions = (target_val).continued_fraction()

for i in range(len(fractions)):
    d_cand = fractions.denominator(i)
    if d_cand.bit_length() == 2048:
        recovered_m2 = pow(c, d_cand, n)
        print(bytes.fromhex(hex(recovered_m2)[2:]))
        break