triple-secure picoMini by redpwn Solution

Description

1. Step 1Understand the moduli structure
   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
   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!
   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
   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!
   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.

Alternate Solution

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.