Sistema Criptográfico Schmidt-Samoa

O esquema Schmidt-Samoa é um sistema criptográfico assimétrico cuja segurança reside na dificuldade de fatoração de inteiros, assemelhando-se ao RSA e ao Rabin. A chave pública é gerada na forma \( N = p^2 q \), e a chave privada é o inverso multiplicativo \( d = N^{-1} \pmod{\lambda(pq)} \), onde \( \lambda \) é a função de Carmichael. A criptografia é realizada através de \( c = m^N \pmod N \), enquanto a decifragem exige o cálculo de \( m = c^d \pmod{pq} \).

Para recuperar o produto \( pq \) necessário para a decifragem, podemos utilizar a propriedade de que \( 2^{d \cdot N} \equiv 2 \pmod{pq} \). Calculando o máximo divisor comum entre \( 2^{d \cdot N} - 2 \) e \( N \), obtemos diretamente o valor de \( pq \), permitindo a recuperação da mensagem original.

from gmpy2 import gcd, powmod
from Crypto.Util.number import long_to_bytes

modulus = 1768427447158131856514034889456397424027937796617829756303525705316152314769129050888899742667986532346611229157207778487065194513722005516611969754197481310330149721054855689646133721600838194741123290410384315980339516947257172981002480414254023253269098539962527834174781356657779988761754582343096332391763560921491414520707112852896782970123018263505426447126195645371941116395659369152654368118569516482251442513192892626222576419747048343942947570016045016127917578272819812760632788343321742583353340158009324794626006731057267603803701663256706597904789047060978427573361035171008822467120148227698893238773305320215769410594974360573727150122036666987718934166622785421464647946084162895084248352643721808444370307254417501852264572985908550839933862563001186477021313236113690793843893640190378131373214104044465633483953616402680853776480712599669132572907096151664916118185486737463253559093537311036517461749439
cipher = 1653396627113549535760516503668455111392369905404419847336187180051939350514408518095369852411718553340156505246372037811032919080426885042549723125598742783778413642221563616358386699697645814225855089454045984443096447166740882693228043505960011332616740785976743150624114653594631779427044055729185392854961786323215146318588164139423925400772680226861699990332420246447180631417523181196631188540323779487858453719444807515638025771586275969579201806909799448813112034867089866513864971414742370516244653259347267231436131850871346106316007958256749016599758599549180907260093080500469394473142003147643172770078092713912200110043214435078277125844112816260967490086038358669788006182833272351526796228536135638071670829206746835346784997437044707950580087067666459222916040902038574157577881880027391425763503693184264104932693985833980182986816664377018507487697769866530103927375926578569947076633923873193100147751463
priv_exp = 20650646933118544225095544552373007455928574480175801658168105227037950105642248948645762488881219576174131624593293487325329703919313156659700002234392400636474610143032745113473842675857323774566945229148664969659797779146488402588937762391470971617163496433008501858907585683428652637958844902909796849080799141999490231877378863244093900363251415972834146031490928923962271054053278056347181254936750536280638321211545167520935870220829786490686826062142415755063724639110568511969041175019898031990455911525941036727091961083201123910761290998968240338217895275414072475701909497518616112236380389851984377079

base_power = powmod(2, priv_exp * modulus, modulus)
pq_product = gcd(base_power - 2, modulus)

plaintext_int = powmod(cipher, priv_exp, pq_product)
print(long_to_bytes(plaintext_int))

Ataque de Smart em Curvas Elípticas Anômalas

Quando o número de pontos em uma curva elíptica sobre um corpo finito \( \mathbb{F}_p \) é exatamente igual a \( p \), a curva é classificada como anômala. Nesse cenário, o Problema do Logaritmo Discreto em Curvas Elípticas (ECDLP) pode ser resolvido em tempo polinomial utilizando o Ataque de Smart.

A técnica consiste em levantar a curva e seus pontos para o corpo p-ádico \( \mathbb{Q}_p \). Através do logaritmo do grupo formal, o problema é mapeado do grupo aditivo da curva para o grupo aditivo dos inteiros p-ádicos, onde o logaritmo discreto se torna uma simples divisão.

# SageMath
prime_field = 75206427479775622966537995406541077245842499523456803092204668034148875719001
coeff_a = 40399280641537685263236367744605671534251002649301968428998107181223348036480
coeff_b = 34830673418515139976377184302022321848201537906033092355749226925568830384464

curve_fp = EllipticCurve(GF(prime_field), [coeff_a, coeff_b])
point_P = curve_fp(63199291976729017585116731422181573663076311513240158412108878460234764025898, 11977959928854309700611217102917186587242105343137383979364679606977824228558)
point_Q = curve_fp(75017275378438543246214954287362349176908042127439117734318700769768512624429, 39521483276009738115474714281626894361123804837783117725653243818498259351984)

def p_adic_lift_and_solve(P, Q, p):
    E_qp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0, p) * p for t in P.curve().a_invariants()])
    
    P_lifted = [pt for pt in E_qp.lift_x(ZZ(P.xy()[0]), all=True) if GF(p)(pt.xy()[1]) == P.xy()[1]][0]
    Q_lifted = [pt for pt in E_qp.lift_x(ZZ(Q.xy()[0]), all=True) if GF(p)(pt.xy()[1]) == Q.xy()[1]][0]
    
    P_formal = p * P_lifted
    Q_formal = p * Q_lifted
    
    x_p, y_p = P_formal.xy()
    x_q, y_q = Q_formal.xy()
    
    log_P = -(x_p / y_p)
    log_Q = -(x_q / y_q)
    
    return ZZ(log_Q / log_P)

secret_scalar = p_adic_lift_and_solve(point_P, point_Q, prime_field)
print(secret_scalar)

Redução de Reticulados no NTRU Unidimensional

O criptossistema NTRU opera tradicionalmente em anéis de polinômios. No entanto, quando restrito a termos constantes, ele degenera para um problema de relação inteira simples. A chave pública é definida como \( h \equiv f^{-1} g \pmod q \), o que implica \( f h \equiv g \pmod q \), ou seja, \( f h - k q = g \).

Isso forma um reticulado bidimensional gerado pelos vetores \( (1, h) \) e \( (0, q) \). Como os componentes da chave privada \( f \) e \( g \) são inteiros pequenos, o vetor \( (f, g) \) representa um vetor curto neste reticulado. Algoritmos de redução, como o LLL (Lenstra-Lanstra-Lovász) ou a redução de Gauss, podem encontrá-lo eficientemente.

# SageMath
pub_key_h = 8916452722821418463248726825721257021744194286874706915832444631771596616116491775091473142798867278598586482678387668986764461265131119164500473719939894343163496325556340181429675937641495981353857724627081847304246987074303722642172988864138967404024201246050387152854001746763104417773214408906879366958729744259612777257542351501592019483745621824894790096639205771421560295175633152877667720038396154571697861326821483170835238092879747297506606983322890706220824261581533324824858599082611886026668788577757970984892292609271082176311433507931993672945925883985629311514143607457603297458439759594085898425992
modulus_q = 31985842636498685945330905726539498901443694955736332073639744466389039373143618920511122288844282849407290205804991634167816417468703459229138891348115191921395278336695684210437130681337971686008048054340499654721317721241239990701099685207253476642931586563363638141636011941268962999641130263828151538489139254625099330199557503153680089387538863574480134898211311252227463870838947777479309928195791241005127445821671684607237706849308372923372795573732000365072815112119533702614620325238183899266147682193892866330678076925199674554569018103164228278742151778832319406135513140669049734660019551179692615505961
cipher_e = 20041713613876382007969284056698149007154248857420752520496829246324512197188211029665990713599667984019715503486507126224558092176392282486689347953069815123212779090783909545244160318938357529307482025697769394114967028564546355310883670462197528011181768588878447856875173263800885048676190978206851268887445527785387532167370943745180538168965461612097037041570912365648125449804109299630958840398397721916860876687808474004391843869813396858468730877627733234832744328768443830669469345926766882446378765847334421595034470639171397587395341977453536859946410431252287203312913117023084978959318406160721042580688

basis_matrix = matrix(ZZ, [[1, pub_key_h], [0, modulus_q]])

reduced_basis = basis_matrix.LLL()
short_f, short_g = reduced_basis[0]

short_f, short_g = abs(short_f), abs(short_g)

intermediate_val = (short_f * cipher_e) % modulus_q % short_g
plaintext_int = (intermediate_val * inverse_mod(short_f, short_g)) % short_g

print(bytes.fromhex(hex(plaintext_int)[2:]))

Fatoração Pollard p-1 e Deciframento Rabin Iterativo

Neste cenário, os números primos são gerados de forma que \( p-1 \) seja \( B \)-suave (composto exclusivamente por fatores primos pequenos). Essa característica torna o módulo vulnerável ao algoritmo de fatoração p-1 de Pollard.

Adicionalmente, o expoente público é \( e = 196608 = 2^{16} \times 3 \). O processo de decifragem requer a fatoração de \( N \), seguida pela aplicação do algoritmo de deciframento de Rabin (raiz quadrada modular) 16 vezes consecutivas para eliminar o componente \( 2^{16} \), e finalmente o cálculo de uma raiz cúbica modular para o componente \( 3 \).

from Crypto.Util.number import long_to_bytes
import gmpy2

modulus_n = 3326716005321175474866311915397401254111950808705576293932345690533263108414883877530294339294274914837424580618375346509555627578734883357652996005817766370804842161603027636393776079113035745495508839749006773483720698066943577445977551268093247748313691392265332970992500440422951173889419377779135952537088733
cipher_c = 2709336316075650177079376244796188132561250459751152184677022745551914544884517324887652368450635995644019212878543745475885906864265559139379903049221765159852922264140740839538366147411533242116915892792672736321879694956051586399594206293685750573633107354109784921229088063124404073840557026747056910514218246

base = 2
exponent = 2
while True:
    base = pow(base, exponent, modulus_n)
    factor = gmpy2.gcd(base - 1, modulus_n)
    if 1 < factor < modulus_n:
        prime_p = factor
        prime_q = modulus_n // factor
        break
    exponent += 1

inv_p_q = gmpy2.invert(prime_p, prime_q)
inv_q_p = gmpy2.invert(prime_q, prime_p)

current_ciphers = [cipher_c]

for _ in range(16):
    next_ciphers = []
    for c_val in current_ciphers:
        root_p = pow(c_val, (prime_p + 1) // 4, prime_p)
        root_q = pow(c_val, (prime_q + 1) // 4, prime_q)
        
        val1 = (root_p * inv_q_p * prime_q + root_q * inv_p_q * prime_p) % modulus_n
        val2 = (root_p * inv_q_p * prime_q - root_q * inv_p_q * prime_p) % modulus_n
        
        for v in [val1, modulus_n - val1, val2, modulus_n - val2]:
            if v not in next_ciphers:
                next_ciphers.append(v)
    current_ciphers = next_ciphers

for final_c in current_ciphers:
    msg_int, is_exact = gmpy2.iroot(final_c, 3)
    if is_exact:
        print(long_to_bytes(msg_int))

Resolução de LWE (Learning With Errors) via Reticulados

O problema Learning With Errors (LWE) envolve a resolução de um sistema de equações lineares perturbado por um vetor de erro pequeno. O desafio fornece matrizes \( A, B, C \) e um vetor alvo \( b = xB + yA + zC + e \), onde \( e \) possui componentes de baixa magnitude.

Para extrair a mensagem, construímos um reticulado utilizando a técnica de embedding de Kannan. Ao anexar uma matriz identidade ponderada e o vetor alvo à base do reticulado, o algoritmo LLL é capaz de identificar o vetor mais curto, que corresponde diretamente aos coeficientes secretos ou ao vetor de erro, permitindo a reconstrução do texto plano.

import re
from sage.all import matrix, ZZ, vector, zero_vector, block_matrix

def parse_numbers(text_str):
    return [int(num) for num in re.findall(r"-?\d+", text_str)]

with open("enc.out", "r") as file:
    lines = file.readlines()

dim_n = 200
num_eq = 66

mat_B = matrix(ZZ, [parse_numbers(lines[i]) for i in range(num_eq)])
mat_A = matrix(ZZ, [parse_numbers(lines[i + num_eq]) for i in range(num_eq)])
mat_C = matrix(ZZ, [parse_numbers(lines[i + 2 * num_eq]) for i in range(num_eq)])
vec_b = vector(ZZ, parse_numbers(lines[-1]))

combined_mat = mat_A + mat_B + mat_C

identity_block = matrix.identity(ZZ, num_eq)
lattice_basis = block_matrix([[combined_mat, identity_block], [vec_b, zero_vector(ZZ, num_eq)]])

reduced_lattice = lattice_basis.LLL()
shortest_vec = reduced_lattice[0]

secret_coeffs = lattice_basis.solve_left(shortest_vec)

plaintext_chars = []
for coeff in secret_coeffs[:-1]:
    plaintext_chars.append(chr(abs(int(coeff))))

print("".join(plaintext_chars))