RSAisEasy - HackTheBox

Description

The challenge provides two files:

1. RSAisEasy.py - The encryption script
2. output.txt - The encrypted output

RSAisEasy.py

#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, getPrime
from secrets import flag1, flag2
from os import urandom

flag1 = bytes_to_long(flag1)
flag2 = bytes_to_long(flag2)

p, q, z = [getPrime(512) for i in range(3)]

e = 0x10001

n1 = p * q
n2 = q * z

c1 = pow(flag1, e, n1)
c2 = pow(flag2, e, n2)

E = bytes_to_long(urandom(69))

print(f'n1: {n1}')
print(f'c1: {c1}')
print(f'c2: {c2}')
print(f'(n1 * E) + n2: {n1 * E + n2}')

output.txt

n1: 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
c1: 92506893588979548794790672542461288412902813248116064711808481112865246689691740816363092933206841082369015763989265012104504500670878633324061404374817814507356553697459987468562146726510492528932139036063681327547916073034377647100888763559498314765496171327071015998871821569774481702484239056959316014064
c2: 46096854429474193473315622000700040188659289972305530955007054362815555622172000229584906225161285873027049199121215251038480738839915061587734141659589689176363962259066462128434796823277974789556411556028716349578708536050061871052948425521408788256153194537438422533790942307426802114531079426322801866673
(n1 * E) + n2: 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163

Analysis

The vulnerability is that two RSA moduli n1 = p*q and n2 = q*z share a common prime factor q. This is a classic Common Prime Attack on RSA.

Key Observations:

1. Shared Prime Factor: Both moduli share the prime q

   • n1 = p * q
   • n2 = q * z

2. Hidden n2: We're given (n1 * E) + n2 instead of n2 directly

3. Extracting n2: Since n1 * E is divisible by n1, we can extract n2 using modulo:

   • n2 = (n1 * E + n2) mod n1

4. Finding q: Once we have both n1 and n2, we can find the shared prime:

   • q = gcd(n1, n2)

Solution

Attack Steps

1. Extract n2 from the given expression using modular arithmetic
2. Find common factor q using GCD
3. Factorize both moduli to get p and z
4. Compute private keys and decrypt both ciphertexts
5. Concatenate flags to get the full flag

solve.py

#!/usr/bin/env python3
from math import gcd
from Crypto.Util.number import long_to_bytes

# Given values
n1 = 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
c1 = 92506893588979548794790672542461288412902813248116064711808481112865246689691740816363092933206841082369015763989265012104504500670878633324061404374817814507356553697459987468562146726510492528932139036063681327547916073034377647100888763559498314765496171327071015998871821569774481702484239056959316014064
c2 = 46096854429474193473315622000700040188659289972305530955007054362815555622172000229584906225161285873027049199121215251038480738839915061587734141659589689176363962259066462128434796823277974789556411556028716349578708536050061871052948425521408788256153194537438422533790942307426802114531079426322801866673
n1_E_plus_n2 = 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163

e = 0x10001

# Step 1: Extract n2 using modular arithmetic
# n2 = (n1 * E + n2) mod n1
n2 = n1_E_plus_n2 % n1

# Step 2: Find common factor q = gcd(n1, n2)
q = gcd(n1, n2)

# Step 3: Find p and z
p = n1 // q
z = n2 // q

# Verify factorization
assert p * q == n1
assert q * z == n2

# Step 4: Compute private exponents
phi_n1 = (p - 1) * (q - 1)
phi_n2 = (q - 1) * (z - 1)

d1 = pow(e, -1, phi_n1)
d2 = pow(e, -1, phi_n2)

# Step 5: Decrypt flags
flag1 = pow(c1, d1, n1)
flag2 = pow(c2, d2, n2)

flag1_bytes = long_to_bytes(flag1)
flag2_bytes = long_to_bytes(flag2)

print(f"flag1: {flag1_bytes}")
print(f"flag2: {flag2_bytes}")
print(f"Full flag: {flag1_bytes.decode() + flag2_bytes.decode()}")

Output

flag1: b'HTB{1_m1ght_h4v3_m3ss3d'
flag2: b'_uP_jU$t_4_l1ttle_b1t?}'
Full flag: HTB{1_m1ght_h4v3_m3ss3d_uP_jU$t_4_l1ttle_b1t?}

References

• Common Prime Attack on RSA
• Batch GCD Attack