No Yangcheng Cup 2023, desafios de criptografia testaram habilidades em análise de algoritmos. Este artigo explora as soluções para dois problemas: Easy_3L, envolvendo LCG e uma variante NTRU, e danger_RSA, uma RSA modificada com geração de chaves não convencional.

Easy_3L

O desafio fornece o seguinte código Python, que utiliza um Gerador Congruencial Linear (LCG) para produzir uma sequência e depois aplica uma criptografia inspirada em NTRU:

from gmpy2 import *
from Crypto.Util.number import *
from secret import flag

msg = bytes_to_long(flag)

def get_key():
    prime_p = getPrime(1400)
    factor_f = getRandomNBitInteger(1024)
    while True:
        prime_q = getPrime(512)
        if gcd(factor_f, prime_q) != 1:
            continue
        else:
            break
    parameter_h = (invert(factor_f, prime_p) * prime_q) % prime_p
    return prime_p, parameter_h

def encrypt_lcg(message):
    coeff_a = getPrime(250)
    coeff_b = getRandomNBitInteger(240)
    mod_n = getPrime(512)
    seed = message
    sequence = [0] * 6
    sequence[0] = seed
    for idx in range(1, 6):
        sequence[idx] = (sequence[idx - 1] * coeff_a + coeff_b) % mod_n
    return sequence

def encrypt_ntru(val, prime_p, parameter_h):
    random_s = getRandomNBitInteger(512)
    ciphertext = (random_s * parameter_h + val) % prime_p
    return ciphertext

seq = encrypt_lcg(msg)
print("S1 =", seq[1])
print("S2 =", seq[2])
print("S4 =", seq[4])
print("S5 =", seq[5])

prime_p, parameter_h = get_key()
ct = encrypt_ntru(seq[3], prime_p, parameter_h)
print("p =", prime_p)
print("h =", parameter_h)
print("c =", ct)

Os valores conhecidos são S1, S2, S4, S5 e, da segunda etapa, p, h, c. O objetivo é recuperar a semente original (a mensagem flag). Primeiro, determina-se S3 usando os termos do LCG. Em seguida, para a parte NTRU, modela-se o problema como um sistema linear com parâmetros desconhecidos msg (que é S3) e s. A abordagem emprega redução de reticulado (lattice basis reduction). Constrói-se uma matriz M com base nas relações moudlares:

Matrix M = [[-p, 0, 0],
            [-h, 1, 0],
            [c, 0, 2^512]]

A aplicação do algoritmo LLL a M gera um vetor curto que contém msg. O código a seguir recupera msg:

from Crypto.Util.number import *

# Valores conhecidos do desafio
p_val = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
h_val = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
c_val = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287

# Construção da matriz
matrix_data = [[-p_val, 0, 0], [-h_val, 1, 0], [c_val, 0, 2^512]]
M = Matrix(ZZ, matrix_data)
short_vector = M.LLL()[0]
recovered_msg = short_vector[0]
print(f"Recuperado msg = {recovered_msg}")

Com msg (que é S3) obtido, os termos do LCG completos permitem resolver para a semente inicial. Usando as diferenças entre termos consecutivos, encontra-se o módulo n e os coeficientes a, b do LCG. O módulo n é recuperado via Máximo Divisor Comum (GCD) das combinações não-lineares das diferenças. Em seguida, a e b são calculados modularmente. Por fim, a semente (mensagem original) é derivada:

from Crypto.Util.number import GCD, isPrime, long_to_bytes
import gmpy2

# Valores dos termos do LCG
lcg_terms = [28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141,
             1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888,
             recovered_msg,  # S3 recuperado
             9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997,
             9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736]

# Calcular diferenças
diffs = []
for i in range(1, len(lcg_terms)):
    diffs.append(lcg_terms[i] - lcg_terms[i-1])

# Encontrar módulo n via GCD
modulus_n = 0
for i in range(1, len(diffs)-1):
    candidate = diffs[i+1] * diffs[i-1] - diffs[i]**2
    modulus_n = GCD(candidate, modulus_n)

# Refinar n (pode ser múltiplo de um primo)
for divisor in range(1, 100):
    if isPrime(modulus_n // divisor):
        modulus_n //= divisor
        break

# Calcular coeficientes a e b
a_coeff = (lcg_terms[3] - lcg_terms[2]) * gmpy2.invert(lcg_terms[2] - lcg_terms[1], modulus_n) % modulus_n
b_coeff = (lcg_terms[2] - a_coeff * lcg_terms[1]) % modulus_n
a_inv = gmpy2.invert(a_coeff, modulus_n)

# Recuperar semente inicial (mensagem original)
seed_msg = (lcg_terms[0] - b_coeff) * a_inv % modulus_n
print(long_to_bytes(seed_msg))

A saída revela a flag: DASCTF{NTRU_L0G_a6e_S1mpLe}.

danger_RSA

Este desafio implementa uma variante RSA com geração de chaves baseada em números da forma \( p = X^a + s \) e \( q = Y^a + t \), onde s e t são pequenos. O expoente público é \( e = s \cdot t \). O código forneicdo é:

from Crypto.Util.number import *

msg = bytes_to_long(flag)

def get_key(exp, bits):
    assert exp >= 2
    while True:
        base = getRandomInteger(bits // exp)
        small_param = getRandomRange(pow(2, exp**2 - exp + 4), pow(2, exp**2 - exp + 5))
        candidate = base**exp + small_param
        if isPrime(candidate):
            return (candidate, small_param)

p_val, s_val = get_key(exp=2, bits=1024)
q_val, t_val = get_key(exp=2, bits=1024)

N = p_val * q_val
e_val = s_val * t_val
cipher = pow(msg, e_val, N)
print("N =", N)
print("e =", e_val)
print("c =", cipher)

Valores conhecidos: N, e (com 34 bits), c. O expoente e é o produto de dois números pequenos s e t. Observando o comprimento de bits de e, infere-se que o expoente exp na geração de chaves é 4, pois \( 2^{exp^2 - exp + 5} \) define o limite superior para s e t. Com exp=4, \( 2^{4^2 - 4 + 5} = 2^{16+5} = 2^{21} \), e e tem 34 bits, o que é consistente com o produto de dois números de até 21 bits. A solução envolve fatorar e e testar combinações de fatores para s e t, de modo que \( p = X^4 + s \) e \( q = Y^4 + t \) sejam primos e \( N = p \cdot q \). O processo é iterativo, explorando divisores de e até encontrar o par correto que satisfaça a equação modular.