Jun 10, 2025

3-RSA

Gabriel Yip

untagged

779 Words … ⏲ Reading Time: 3 Minutes, 32 Seconds

2025-06-10 15:47 +1000

3-RSA

I did nothing much in this except asking AI (Gemini 2.5 Pro) about this. Surprisingly the prompt works the first time! Since the AI probably explains it better than me, here is the LLM response:

The vulnerability in this code lies in the predictable way the prime numbers for the RSA moduli were generated. The primes a, b, c and x, y, z are not random; they form arithmetic progressions. This mathematical relationship allows an attacker to link the three public keys (n1, n2, n3) together, ultimately revealing all the secret prime factors.

The Vulnerability: Arithmetic Progressions

The script contains these two critical lines:
assert z - y == y - x and assert c - b == b - a

These assertions mean that a, b, c and x, y, z are sets of three primes in arithmetic progression. This implies:

  • \(b = \frac{a+c}{2}\)
  • \(y = \frac{x+z}{2}\)

This seemingly innocent constraint creates a fatal link between the three RSA moduli.

The Attack: A Mathematical Approach

The attack leverages this relationship to factor the moduli.

  1. Relating the Moduli: We can express the second public key, n2, in terms of the primes from the other two keys: \(n_2 = b \cdot y = (\frac{a+c}{2}) \cdot (\frac{x+z}{2})\) \(4n_2 = (a+c)(x+z) = ax + az + cx + cz\)

  2. Substituting Known Values: We know that \(n_1 = a \cdot x\) and \(n_3 = c \cdot z\). Substituting these into the equation gives: \(4n_2 = n_1 + az + cx + n_3\)

  3. Forming a Quadratic Equation: Let’s isolate the unknown terms. Let \(S = 4n_2 - n_1 - n_3\). \(S = az + cx\)

    We now have a system of equations involving two unknown products, az and cx:

    • Sum: \(az + cx = S\)
    • Product: \((az) \cdot (cx) = (ax) \cdot (cz) = n_1 \cdot n_3\)

    Any two numbers with a known sum and product are the roots of a simple quadratic equation: \(K^2 - (\text{sum of roots})K + (\text{product of roots}) = 0\) \(K^2 - S \cdot K + n_1n_3 = 0\)

  4. Solving for the Primes:

    • We can solve this quadratic equation for K using the quadratic formula. The two roots will be \(K_1 = a \cdot z\) and \(K_2 = c \cdot x\).
    • Once we have these products, we can find the individual prime factors using the greatest common divisor (GCD):
      • a = gcd(n1, K1) which is gcd(a*x, a*z)
      • c = gcd(n3, K2) which is gcd(c*z, c*x)
    • With a and c found, we can easily find the remaining primes (x, z, b, y).

  5. Decryption: After recovering all six prime factors, we can compute the totient (phi) for each modulus, calculate the private keys, and decrypt the three parts of the flag.

Solution Code

This Python script implements the attack described above to factor the public keys and retrieve the full flag.

import math

# Public values from the output
flag1 = 11492112663703232088998486179734356177771567146805158417960125003237116439231226258659875708797399817744931063299748318101064301294216136873298987081319490145937107048642337728535911253970741196295376922168448878976469589443846093196421830469617589107742470128537185244364757796970083415861786554196168517831966671244906283809132068677607882319793466679026787758887577990349442662100930139100336136175243045045966567615399099883892136366882468101432422494155346928263194773441199700185161047426593464784067654388038794015818789112382156282633137679906682839029587361557507124817043427634040108459655059076740987192384
flag2 = 4952509765068005943929023031843431114540597187092738714903126772067946141703989572784140897934401082697437162345382546363262539532326425498475165138862831578872326769058104757689642323436428400734549347987121729721999216972287610017181744621923580613784280528094319337115580468333962976664642382951713734996844557627097050558648598389254848040570771430319254911664805107658029100255583056718934305481684430771282023833079529280029156492348848881417157592538442094955548441597641873477997544274413802625533454240475278118401388524163774631458900120835168954124149376210125669487879076005224324402897828069400754462817
flag3 = 832635235843260963315954320975950760182343666597438109641505827662230808005904093467755157050220263396479252248813223128489531311261338768982946110126160600744765531264253128791579206197722640752945391966957504838191737045481547210603871589545608892344858449735051695103642275193727646751872742558944213474626362348978842738127628973051301523219151083407250098830278639049985019075872996575145110830076988689935892814129057961258041944950895126632409918730985389473336802153365766599338113009784032170567987292888755868361829266838451794862482137390672574209264849235381496657497250742436985162295780366726898361475

n1 = 17858189458331977176783205510145346242329075006164832737615260745307500777302923782391964669567649775085122681328872195823985225861546790981029181901697377617738017081303713219017671572361492390837847089196556031690974890809922884662678039254137587713002336455039498173306053994439163020453505352157698564958428447487550817456903730014043187074720704452312511793034780752764123414676884871563210725690386057007997022651617836076682803508719887751203436051121561828471343707387576953315756670760479266036148064337918362609447399308776983755240618746806694447782498244372434669071672049750668585915479351754044777991233
n-2 = 27988292511630408087628435379321614455905755155908526846245303815018831647470172411594854883620030615448110055118069234326939102090454077116649426727895959703121425978302565278958246699172962990698968383263856202038742080400833395699326649141862184813455501146105201914061652698539038504126091124829475746301242565988800180930109751956393420828946755373612363675944873639709271075863889618954766614476365612770800460612362627801799559523509061850369462031748981803274498119708059567622255620759508648716908850891237844987925855021202095512750624375024412242964800063919261993198259658255269969227717249296364394728701
n-3 = 38660180269440656477053314413313714739062655930125687065781703038150391320898743760212709373892830529605814753216140367569440889146085510051662809299856987103911894539082484910702016539429463270580447118064831756349229400710729340872901108067075023980052189953271797924249586371572823947426357923900405426018338108052104392652303276006930930451348478532135626424674508274264632509573012814884347342851455437267076470425745031250812060252385012112699148646763361357973846549910142450805741636272703367045063152051223051807503235461739514919589765417385756615237864412747917566329839115378785588573077455129039985274609
e = 65537

# 1. Calculate S = 4*n2 - n1 - n3
S = 4 * n2 - n1 - n3

# 2. Solve the quadratic equation K^2 - S*K + n1*n3 = 0
discriminant = S**2 - 4 * n1 * n3
sqrt_discriminant = math.isqrt(discriminant)

# The two roots are K1 and K2
K1 = (S + sqrt_discriminant) // 2
K2 = (S - sqrt_discriminant) // 2

# 3. Find the prime factors using GCD
# K1 and K2 are a*z and c*x. We test both possibilities.
a = math.gcd(n1, K1)
if a == 1: # If gcd is 1, we guessed the wrong K for n1
    a = math.gcd(n1, K2)
    c = math.gcd(n3, K1)
else:
    c = math.gcd(n3, K2)

x = n1 // a
z = n3 // c

# 4. Recover the remaining primes b and y
b = (a + c) // 2
y = (x + z) // 2

# Sanity check: ensure our calculated primes multiply to n2
assert n2 == b * y

# 5. Decrypt each part of the flag
def decrypt_part(ciphertext, p, q, e, n):
    """Decrypts an RSA message given the prime factors."""
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    plaintext_int = pow(ciphertext, d, n)
    # Convert the resulting integer to bytes
    byte_length = (plaintext_int.bit_length() + 7) // 8
    return plaintext_int.to_bytes(byte_length, 'big')

# Decrypt and get the byte representation of each flag part
part1_bytes = decrypt_part(flag1, a, x, e, n1)
part2_bytes = decrypt_part(flag2, b, y, e, n2)
part3_bytes = decrypt_part(flag3, c, z, e, n3)

# 6. Combine the parts and print the result
full_flag = part1_bytes + part2_bytes + part3_bytes
print("✅ The decrypted flag is:")
print(full_flag.decode())

See Also