triple-secure picoMini by redpwn Solution

Description

1. Step 1Understand the moduli structure

   Observation

   The message was encrypted three times with RSA, and the three moduli share prime factors. A GCD between them factors all three.

   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 2Factor all three moduli using GCD

   Observation

   Each modulus is the product of two of the same three primes, so every pair shares exactly one. A GCD on each pair recovers all three factors at once.

   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.

   factorint runs trial division and Pollard rho, neither of which touches a well-chosen 1024-bit prime; it runs for hours and returns nothing. The GCD works not because any modulus is weak on its own, but because they share a prime. The relationship between them is the vulnerability.

   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.

   What you call the primes is arbitrary; which pair belongs to which modulus is not, because the totient is the product of both factors minus one. Mix a factor from one modulus into another's totient and the inversion either fails or yields a wrong exponent that decrypts to garbage. Assert that the two factors multiply back to the modulus before using them.

   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 3Decrypt each RSA layer

   Observation

   With the three primes in hand, each modulus gives a totient and a private exponent. The ciphertext carries three layers, so peel them in reverse of how they went on.

   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 ran through the moduli in order, first to last. The ciphertext you hold was wrapped last by the third, so starting the decryption with the first produces a nonsensical intermediate instead of removing the outer layer. Work backwards through them.

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

   The modular inverse raises an error when the exponent and the totient are not coprime. Build the totient from the wrong factor pair and that is exactly what happens, which at least fails loudly rather than silently. Compute each totient from the two primes whose product is that modulus, and check coprimality 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.