## Challenge description

The challenge was called Revolutional Secure Angou. A zip file (revolutional-secure-angou-de97106aa248a41a40fdd001fc5f7b4b4f28a39eb6bcabf8401b108b7a8961c5) was given to us. Inside we could find three file: an

RSA public key publickey.pem (PEM formatted), the encrypted flag
flag.encrypted  and the Ruby script called generator.rb used to
generate both the public key and the ciphertext. Our goal is obvious: decrypt
the file flag.encrypted .

The source code of generator.rb  is quite simple:

As we can see line 6, q  is generated in a very peculiar way: it is set
to be the inverse of e  modulo p . Line 7 ensures that q  is prime
in order to avoid a trivial factorisation. The rest of the script just encrypts
the flag and write the publickey.

This challenge is just another RSA-based challenge where the vulnerability is
in the prime numbers generation.

## Solution

My approach when I need to face those RSA-based challenge is to write down the
informations that I have as equations. Here we know:

– The public modulus $$n = p.q$$;
– The public exponent $$e = 65537$$;

We don’t know the value of either $$p$$ or $$q$$ but we know that
$$q = e^{-1} \mod p$$, thus $$qe = 1\mod p$$. We can also express this
congruence as: $$\exists k, qe = kp + 1$$. Since $$q$$
is roughly the same size as $$p$$, then $$k$$ must be approximatly the same size as
$$e$$. Hence, even if we don’t know the exact value of $$k$$, it will be easy to
brute-force if we have a correct criterion to validate its value.

Since $$qe = kp + 1$$, then $$qep = ne = kp^2 + p$$. Thus, $$p$$ is a positive integer
root of the polynomial $$kX^2 + X – ne$$. As a first step, and because we don’t
know the value of all the coefficients of this polynomial, we use this property,
along with the standard method of resolution of a nd degree polynomial,
to find $k$ which is such that:

– $$\Delta = 1 + 4kne$$ is a perfect square;
– $$2k$$ is dividing $$\sqrt{\Delta} – 1$$.

Once such a $$k$$ is found, then we can compute
$$p = \frac{\sqrt{\Delta} – 1}{2k}$$. The modulus being factorised, we can
compute the associated private key and decrypt the flag.

Here is the Python script used to solve the challenge: