RSAisEasy

Explanation

1. Two RSA moduli are generated:

• n1 equals p times q
• n2 equals q times z
• The fatal flaw is that both moduli share the prime factor q.

1. Two ciphertexts are given:

• c1 equals flag1 to the power of e modulo n1
• c2 equals flag2 to the power of e modulo n2

1. Recovering n2:

• The script provides the value (n1 times E + n2), not n2 directly.
• However, since n1 is known, n2 can be recovered using modular arithmetic:
• n2 equals (n1 times E + n2) modulo n1

Exploit

The scheme is insecure because RSA moduli must be coprime. Here, n1 and n2 ​share a prime factor q.

Compute n2: n2 = (n1 * E + n2) mod n1

Factor the moduli using gcd: q = gcd(n1, n2) p = n1 / q z = n2 / q

Compute Euler’s totients: phi(n1) = (p - 1) * (q - 1) phi(n2) = (q - 1) * (z - 1)

Recover private keys: d1 = e to the power of -1 mod phi(n1) d2 = e to the power of -1 mod phi(n2)

Decrypt: m1 = c1 to the power of d1 mod n1 m2 = c2 to the power of d2 mod n2

Convert to bytes: Get both parts of the flag.

#!/usr/bin/env python3
import math

# --- given values ---
e = 0x10001
n1 = 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
c1 = 92506893588979548794790672542461288412902813248116064711808481112865246689691740816363092933206841082369015763989265012104504500670878633324061404374817814507356553697459987468562146726510492528932139036063681327547916073034377647100888763559498314765496171327071015998871821569774481702484239056959316014064
c2 = 46096854429474193473315622000700040188659289972305530955007054362815555622172000229584906225161285873027049199121215251038480738839915061587734141659589689176363962259066462128434796823277974789556411556028716349578708536050061871052948425521408788256153194537438422533790942307426802114531079426322801866673
n1E_plus_n2 = 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163
# --------------------

def invmod(a, m):
    return pow(a, -1, m)

def i2b(x):
    return x.to_bytes((x.bit_length()+7)//8, 'big')

# Recover n2 from (n1*E)+n2
n2 = n1E_plus_n2 % n1

# Shared-prime factorization
q = math.gcd(n1, n2)
p = n1 // q
z = n2 // q

phi1 = (p - 1) * (q - 1)
phi2 = (q - 1) * (z - 1)

d1 = invmod(e, phi1)
d2 = invmod(e, phi2)

m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)

pt1 = i2b(m1)
pt2 = i2b(m2)

print("flag1 bytes:", pt1)
print("flag2 bytes:", pt2)
try:
    print("flag1 text:", pt1.decode())
    print("flag2 text:", pt2.decode())
except:
    pass

python3 exploit.py                   
flag1 bytes: b'HTB{1_m1ght_h4v3_m3ss3d'
flag2 bytes: b'_uP_jU$t_4_l1ttle_b1t?}'
flag1 text: HTB{1_m1ght_h4v3_m3ss3d
flag2 text: _uP_jU$t_4_l1ttle_b1t?}