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:

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Post Navigation