RSAisEasy | T4QI-Blog

This challenge presents an RSA-based cryptography problem where two separate flags are encrypted using moduli that share a common prime factor $q$.

Challenge Overview

The script RSAisEasy.py performs the following operations:

Generates three 512-bit primes: $p$, $q$, and $z$.
Creates two RSA moduli: $n_1 = p \times q$ and $n_2 = q \times z$.
Encrypts flag1 using $n_1$ and flag2 using $n_2$ with the standard public exponent $e = 65537$.
Provides $n_1$, $c_1$, $c_2$, and a mixed value $y = (n_1 \times E) + n_2$, where $E$ is a random 69-byte integer.

Technical Analysis

The vulnerability lies in how $n_2$ is leaked. Since $y$ is defined as $(n_1 \times E) + n_2$, we can recover $n_2$ simply by taking the modulo of $y$ with $n_1$:

$$n_2 = y \pmod{n_1}$$

Once $n_2$ is known, we observe that $n_1$ and $n_2$ share the prime factor $q$. We can extract $q$ using the Greatest Common Divisor (GCD) algorithm:

$$q = \text{GCD}(n_1, n_2)$$

With $q$ recovered, we can easily find the remaining factors:

$p = \frac{n_1}{q}$
$z = \frac{n_2}{q}$

Decryption Process

The solution script follows these steps to recover both flags:

Extract $n_2$: n2 = y % n1
Factor the Moduli: Use GCD(n1, n2) to find the shared prime $q$, then divide to find $p$ and $z$.
Calculate Euler’s Totient:
- $\phi_1 = (p - 1)(q - 1)$
- $\phi_2 = (q - 1)(z - 1)$
Compute Private Keys: Find $d_1 = e^{-1} \pmod{\phi_1}$ and $d_2 = e^{-1} \pmod{\phi_2}$.
Decrypt:
- flag1 = $c_1^{d_1} \pmod{n_1}$
- flag2 = $c_2^{d_2} \pmod{n_2}$

PYTHON

from Crypto.Util.number import GCD, inverse, long_to_bytes


n1 = 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
c1 = 92506893588979548794790672542461288412902813248116064711808481112865246689691740816363092933206841082369015763989265012104504500670878633324061404374817814507356553697459987468562146726510492528932139036063681327547916073034377647100888763559498314765496171327071015998871821569774481702484239056959316014064
c2 = 46096854429474193473315622000700040188659289972305530955007054362815555622172000229584906225161285873027049199121215251038480738839915061587734141659589689176363962259066462128434796823277974789556411556028716349578708536050061871052948425521408788256153194537438422533790942307426802114531079426322801866673
y = 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163

e = 65537

n2 = y % n1

q = GCD(n1, n2)

p = n1 // q
z = n2 // q

assert n1 == p * q
assert n2 == q * z

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

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

print(long_to_bytes(pow(c1, d1, n1)), long_to_bytes(pow(c2, d2, n2)))