In this challenge we get an RSA public key, an encrypted flag and a Ruby script.

If we analyse the Ruby script, we can see a modified RSA algorithm for the key generation. It uses the public exponent \(e = 65537\) and generate a random \(1024\) bits prime \(p\).

Then, and the vulnerability is here, the script generate the \(q\) as the inverse of \(e~mod~p\) and loop, until \(q\) is not prime. If we look the equations, we have :

$$eq \equiv 1~(mod~p)$$

So there exists an integer \(k\) such as $$eq = 1 + kp$$.

If we multiply both sides with \(p\), we get :

$$eqp = p + kp^{2}$$

$$\iff en = p + kp^{2}$$

$$\iff kp^{2} + p - en = 0$$

As you can see, it's a quadratic equation with two unknowns (the \(p\) and the \(k\)). For the \(k\), if we look at the equation \(eq = 1 + kp\), we know that \(q < p\) because \(q\) it's an inverse modulo \(p\). It implies \(k < e\).

Now, we can just iterates over all possibles \(k\) and try to solve the quadratic equation with only the \(p\) unknown. We can stop when \(p|n\) and \(p\) is not a trivial factor.

I used gmpy2 to calculate an integer square root and solve the equation. The script to recover \(p\) and \(q\) can be found here : sploit.

Once the \(n\) is factorised, I used this C program to generate the private key at PEM format, and finally used openssl to decrypt the flag :

$ openssl rsautl -inkey private.pem -decrypt < flag.encrypted