triple-secure picoMini by redpwn Solution

Description

1. Step 1

   Understand the moduli structure

   Observation

   I noticed the challenge description stated the message was encrypted three times with RSA and that the three moduli share prime factors, which immediately suggested that a GCD attack could factor all three moduli by exploiting the shared primes.

   Three RSA moduli were generated from only three primes p, q, r: n1 = p*q, n2 = p*r, n3 = q*r. Because each modulus shares a prime with another, GCD attacks instantly factor all three.

   Learn more

   RSA security relies entirely on the difficulty of factoring the modulus n = p * q into its two prime components. If n can be factored, the private key d = modinv(e, (p-1)*(q-1)) is immediately computable. The challenge here is that the key generation reused primes across multiple moduli - a catastrophic mistake.

   When n1 = p*q and n2 = p*r share the prime p, computing gcd(n1, n2) = p instantly reveals the shared factor. This is because GCD finds the largest number dividing both inputs, and the only shared prime divisor is p. Once p is known, q = n1/p and r = n2/p, completely factoring all three moduli in microseconds.

   This attack has been applied to real-world RSA keys: a 2012 study by Lenstra et al. ("Ron was wrong, Whit is right") scanned millions of public keys collected from HTTPS servers and found that 0.2% of keys shared prime factors with at least one other key, allowing all of them to be broken. This was caused by poor entropy in embedded devices during key generation at boot time.

2. Step 2

   Factor all three moduli using GCD

   Observation

   I noticed that n1, n2, and n3 were each products of exactly two of the three primes p, q, r, meaning every pair of moduli shared exactly one prime, which suggested running math.gcd on each pair to recover all three individual factors instantly.

   Compute GCD between pairs of moduli to recover the individual primes. Each GCD of two moduli returns their shared prime factor.

   python

   python3 -c "
   from math import gcd
   p = gcd(n1, n2)  # shared between n1 and n2
   q = gcd(n1, n3)  # shared between n1 and n3
   r = gcd(n2, n3)  # shared between n2 and n3
   print(p, q, r)
   "

   Copied!

   What didn't work first

   Tried: Run sympy.factorint(n1) directly on the 2048-bit RSA modulus to recover its prime factors.

   sympy.factorint uses trial division and Pollard rho, both of which are hopelessly slow against a well-chosen 1024-bit prime. The command will run for hours (or forever) without output. The GCD approach works not because the moduli are weak in isolation, but because they share a prime - exploiting the relationship between moduli, not the modulus itself.

   Tried: Assign the GCD results as p = gcd(n1, n2), q = gcd(n2, n3), r = gcd(n1, n3) without verifying which prime belongs to which modulus.

   The label (p, q, r) is arbitrary, but which factor pairs with which modulus matters for computing phi(n) = (factor_a - 1)*(factor_b - 1). If you compute phi(n1) = (gcd(n1,n2)-1)*(gcd(n2,n3)-1) you mix factors from n2 and n3 into n1's phi, so modinv(e, phi) will fail or produce a wrong d that decrypts to garbage. Always verify: assert gcd(n1,n2) * gcd(n1,n3) == n1 before using the factors.

   Learn more

   GCD (Greatest Common Divisor) is computed by the Euclidean algorithm, one of the oldest algorithms in mathematics (described by Euclid around 300 BC). The algorithm repeatedly replaces the larger number with the remainder of dividing the larger by the smaller, until one value reaches zero - the other is the GCD. For numbers with thousands of digits, this runs in microseconds.

   Python 3.9+ includes math.gcd() with arbitrary-precision integer support. For older Python versions, gmpy2.gcd() is faster. The result of gcd(n1, n2) is exactly the shared prime p because: n1 = p*q and n2 = p*r share exactly the prime p (assuming q ≠ r, which is virtually guaranteed for large random primes). All common divisors of n1 and n2 must divide gcd(n1, n2) = p, and since p is prime, there are no other common factors.

   Verifying the factorization: assert n1 % p == 0 and n1 // p == q confirms that p divides n1 cleanly and the cofactor is q. Checking p * q == n1 with large numbers confirms correctness before proceeding to decryption.

   GCD attack worked example (toy primes):
     p = 11, q = 13, r = 17
   
     n1 = p * q = 11 * 13 = 143
     n2 = p * r = 11 * 17 = 187
     n3 = q * r = 13 * 17 = 221
   
   To attacker, n1, n2, n3 look unrelated. But:
   
     gcd(143, 187):
       187 = 1*143 + 44
       143 = 3*44 + 11
        44 = 4*11 + 0       --> gcd = 11 = p
   
     gcd(143, 221):
       221 = 1*143 + 78
       143 = 1*78 + 65
        78 = 1*65 + 13
        65 = 5*13 + 0        --> gcd = 13 = q
   
     gcd(187, 221):
       221 = 1*187 + 34
       187 = 5*34 + 17
        34 = 2*17 + 0        --> gcd = 17 = r
   
   All three primes recovered in O(log n) Euclidean steps.
   
   For 1024-bit moduli, the same algorithm finds the shared
   factor in milliseconds (Python's math.gcd handles arbitrarily
   large ints). Real-world incidents: Lenstra et al. (2012)
   applied this to 6 million Internet HTTPS public keys and broke
   about 12,000 of them due to shared factors caused by weak
   embedded-device entropy at boot time.

3. Step 3

   Decrypt each RSA layer

   Observation

   I noticed that with all three prime factors recovered from the GCD step, I could compute phi(n) and then d = modinv(e, phi) for each modulus, and that because the ciphertext was wrapped in three layers, decryption had to run in reverse order (n3, n2, n1) to peel them off correctly.

   For each (n, e, c) triple, compute phi = (a-1)*(b-1) using the recovered prime factors, then d = modinv(e, phi), then m = pow(c, d, n). Apply this in reverse order through all three layers.

   python

   python3 -c "
   import gmpy2
   from math import gcd
   # Layer 1
   phi1 = (p-1)*(q-1)
   d1 = int(gmpy2.invert(e, phi1))
   m1 = pow(c, d1, n1)
   # Repeat for layers 2 and 3...
   print(bytes.fromhex(hex(final_m)[2:]))
   "

   Copied!

   Expected output

   picoCTF{1_gu3ss_tr1pl3_rs4_1snt_tr1pl3_s3cur3!!!!!!}

   What didn't work first

   Tried: Decrypt the layers in forward order: first n1, then n2, then n3 (the same order encryption was applied).

   Encryption was applied as c1 = m^e mod n1, then c2 = c1^e mod n2, then c3 = c2^e mod n3. Decrypting in forward order applies the n1 inverse first, but the ciphertext c3 was last wrapped with n3 - so the n1 decryption step produces a nonsensical intermediate rather than removing the outermost layer. Decryption must go n3 -> n2 -> n1 to undo each wrap in reverse.

   Tried: Use pow(e, -1, phi1) (Python 3.8+ built-in modular inverse) instead of gmpy2.invert to compute d.

   pow(e, -1, phi) raises ValueError if e and phi are not coprime. If you constructed phi1 with the wrong factor pair (mixing primes across moduli), phi1 is wrong and gcd(e, phi1) may not equal 1, causing a crash rather than a wrong-but-silent result. The fix is to ensure you compute phi(n1) = (p-1)*(q-1) where p and q are specifically the two primes whose product is n1, then confirm gcd(e, phi1) == 1 before inverting.

   Learn more

   RSA decryption computes m = c^d mod n where d = modinv(e, phi(n)) and phi(n) = (p-1)*(q-1). gmpy2.invert(e, phi) computes the modular inverse using the extended Euclidean algorithm - it finds d such that e*d ≡ 1 (mod phi). Python's built-in pow(c, d, n) uses fast modular exponentiation and handles arbitrarily large integers efficiently.

   With triple-layered encryption, the message was encrypted as: c1 = m^e mod n1, then c2 = c1^e mod n2, then c3 = c2^e mod n3. Decryption must reverse this in order: decrypt c3 using n3 to get c2, decrypt c2 using n2 to get c1, decrypt c1 using n1 to get m. Applying the layers in the wrong order produces garbage.

   bytes.fromhex(hex(m)[2:]) converts the large integer m back to bytes. hex(m) produces a hex string like '0x70696...'; [2:] strips the leading 0x; bytes.fromhex() converts the hex string to raw bytes. Alternatively, pwntools' long_to_bytes(m) handles this more cleanly and pads to the correct length.

Flag

When RSA moduli share a prime factor, GCD instantly breaks both keys - secure RSA key generation must produce entirely independent primes for every key pair.