PlaidCTF 2014 RSA writeup

Our archaeologists recovered a dusty and corrupted old hard drive used by The Plague in his trips into the past. It contains a private key, but this has long since been lost to bitrot. Can you recover the full key from the little information we have recovered?

Here we have an RSA breaking challenge. We are given a public and a private key, but more than a half of the digits are removed:

Spoiler Inside SelectShow

We can easily guess names using another valid private key. So we have corrupted modulus, public/private exponents, prime1, prime2, exponent1, exponent2, coefficient:

        BIGNUM *n;              // public modulus
        BIGNUM *e;              // public exponent
        BIGNUM *d;              // private exponent
        BIGNUM *p;              // secret prime factor
        BIGNUM *q;              // secret prime factor
        BIGNUM *dmp1;           // d mod (p-1)
        BIGNUM *dmq1;           // d mod (q-1)
        BIGNUM *iqmp;           // q^-1 mod p
        // ...

My first idea was to brute force both primes digit by digit, starting from low bits. Indeed, we know modulus (from public key) and consider n = p*q (mod 16**t) – we can track valid pairs of (p mod 16**t, q mod 16**t). Unfortunately, known digits for p and q are not enough – number of valid pairs grows very quickly.

Therefore we have to consider other numbers from shredded private key too. It’s not obvious how to use information from e.g. d mod (p - 1) or e*d = 1 (mod phi(n)). The key is to rewrite equations without using mod operations:

This kind of equation can be taken mod 16**t so we can use information from shredded key about the private exponent d. Here we don’t know both d and k, but k is bounded by e (because d < phi(n)).

So if we know right k, we can use this equation to drop invalid (p mod 16**t, q mod 16**t) pairs from bruteforce (thus using digits from d). It happens that wrong candidates for k quickly collapse the search.

Even when using this equation, number of pairs grow fast (though at farther steps). Let's use modular private exponents in the same way:

Luckily, right candidates for k_q and k_p are also easy to find.

Summarizing, the method is:

  • given a candidate for (p mod 16**(t - 1)), generate all possible candidates for (p mod 16**t) (check against mask for prime1)
  • calculate q = n * invmod(p, 16**t) (and check against mask for prime2)
  • calculate d = invmod(e, 16**t) * (1 + k * (N - p - q + 1)) (and check against mask for private exponent)
  • calculate d_p = invmod(e, 16**t) * (1 + k_p * (p - 1)) (and check against mask for exponent1)
  • calculate d_q = invmod(e, 16**t) * (1 + k_q * (q - 1)) (and check against mask for exponent2)
  • if any of checks failed - check next candidate

Here's python code to solve the challenge. Most of the time is spent to get right k, k_p, k_q - wrong ones collapse fast but there are still lots of them to check.

$ time pypy solve.py
K = 4695
Kp = 15700
Kq = 5155
p = 12643740637395110652894262209502063899047520218436247735878188180335985789877601396069401620713231058940443043891453952791936466967524033214476598572706213
q = 12217494205780318874865198006759446969679921137474855298485716817925925911890415286181103665676748660959871257808447814451048738105000263500773868071134927
real	0m46.011s
user	0m45.715s
sys	0m0.048s

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>