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:

 r    e   y: (         
 o  lu :
      :d :f : d:b1:4 :5d: 2: 6:  : 2:  :8 :  :  :
      :c :0 : 1: c: 7:  :  :  :  : f:  :  :2c:6 :
      : 2:  : 3:  : f:  :d :  :  :  :a : 7:  : e:
     b:7 :  :  :5 : 0:2 :  :  : 0:  :9 :  :2 :  :
    e :7 :  :30:d :0 :  :  :  :  :  :  :  :  :  :
    e :  :  :  :  :  :  :  : 3:95:f : c:  :6 :  :
     8:  :b9:dd:  :  :  :  :5 :8e: 0:41: 3:  :  :
     0:3 :e :09: 0:  :1 :5 :6 :  :0 :0 : 3:  : 5:
     4:  :  :  :  :  :  :  : b
     c xpon n :   53  (0  0  1 
   v te xp   n :
     f:  :  : a: a:9 :e :  : 1: 2:  :  :e :  :1 :
    3 : 1:  :  :  : a:  :2 :  :  :  :  :  :  :  :
    9 : a:  :  :  :  :  : 5:c1: 0:b : 3: 2:0 :b0:
      :c : f:  :f :  :d2:  :  : d:  :1 :  :3 :  :
      :  :  :0 : 3:  :  : 5:c :  :3 :6 :  :a4:  :
    4 :  :  :8f:  :  :  :  : a:  : c:5f: 7: 6:  :
     1:  : b:  : 5:  :84:0 :b : f: 3:  :  : 4: 6:
      :  : 5:1 :  :d :  : f:  : c:  :  : 5:  :  :
      :e :f4:b :4 :8e:  :  
 r    :
    00:  :6 : 1:1 :  :b :0 : 2:c : b:2 :  : a:1 :
    c :  : 0:  :28:0 :  :cd:  : 8:  :  :20: c:  :
      : 5:  :9 : c:3 :  :  : a:b :c :3 :  :  :  :
     f:  :  : f: 1: 1:b :  : c:f : a:  :a :  :  :
     a:38:  :6 :  
  i   :
      :e :  :d :2 :6 : 7:  :33:  :46:  : 4:  :  :
      :5 :  : 4:6 :  : 6:  : e:d :  :  : 9: e:1 :
      :  :  :  :  :0 :  :  :  :c : 5:  :  :a :0 :
    6 :  :  :8 :e9:f : f:7 :5 : e:1 :  :  : 1:9 :
     4:d :e9: 6:  
 x  n   1:
     9:d : 5:  :c :67:  : 9:  :  :  : d:  :  : 3:
     f:6 : 0:c :  :6 :ad:  :2 :d :d :  :  :0 :7 :
      :5 : 6:  : 5:1 :f : d:  : 2:  :  : 2: 3:  :
    9 :  :  :  :  :67: 3:  :4 : 7:c0: 4:b :c :f :
      :3 :b : 1
 x on  t :
    1 : 9:47:8 :  :  :  : 3:  :  :  :6 :  :  :0 :
    e :e :8 :  :  :  :  : 1:c :74:  :  :d : 9:3 :
    5 : e:  : 2:  :7 : 2:c :  :  :  :  :5 :  : 8:
      :  :c :  : 1:  :a :  : 9: 5:  : 3:  : e:c :
      :  : 6:  
c e    i  t:
      :a :d :84:f :  : c:43:  :  :  : 6:  :  :  :
      : b:  :c :9 :  :  :  :  :  : 4:23:8b:  :6 :
    2 : 2:  :  : 7:5b:  :  :  :7 :  :  :  :  :  :
    f1:7 :1 :  :f : a:  : 5:  :  :  : 5:  : c: 1:
      :48: b: 6:

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

struct
        {
        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
        // ...
        };
 RSA

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:

$$e d = 1 + k \phi(n)$$

$$\phi(n) = (p – 1) (q – 1) = n – p – q + 1$$

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:

$$e d_p = 1 + k_p (p – 1)$$

$$e d_q = 1 + k_q (q – 1)$$

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
pwned
p = 12643740637395110652894262209502063899047520218436247735878188180335985789877601396069401620713231058940443043891453952791936466967524033214476598572706213
q = 12217494205780318874865198006759446969679921137474855298485716817925925911890415286181103665676748660959871257808447814451048738105000263500773868071134927
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDb+r2xSV0ydudia4R5bp/CD6E8F0TxDIw/PjwsYEDC5/MT36PR
/hDRrld8/qt0UqpTEC7ve+AJnAIlYOV6XDDVCUBkLRsJfdIQmuAvLc/4GYzVo5X8
rEJmEHhIud1jw4fSU45QQVNDBCAz6gnAhBVeZSsPBiNA1dRxekAqnYBqawIDAQAB
AoGAD8JTypqd4ZqhEuzu7aAeM9HY1Cw6lSY3+ePkfa1bllr1kAvqeYXBALSDsgGw
mMG/T/oN0rxGHYoeoTzi07Q9DzP71RXFBT5p56SYTCa7j6THXXyqMLxfd+YFgVsr
ehXMhAi97yMeMoTmoQ91GN/cqW9n/MflJdm0aOv0skSOA0kCQQDxaVEeZr4GIsKr
LsFaF8DHoMcoCK7NuijH9SDsrSNlspzMNTHbGrzAPmk5aF/iFK/RQbqfbP06c6X6
6Fo482mlAkEA6UXeImHntzMXRh7EhZlxXyvkYwhm+Z7aWKFJrhAtGpHE+Qlof1bO
Zdf6qw9knY6K6fwvflNeHVqnYZe01+mmzwJAOdUVDcdnNmkVYZTt1Ptjv28QxtJt
rfMu2dgrbwd7N122mmUT8H1TQmqxIoOSlMKH7AVnA9JER8B0vsry8jm90QJAEllH
jsbKtjNTmlVjOesG6uiF73BCwVHIdP5C0Gk/Uv6yUrB1wsZuN76UXg446NfEf4Ex
rysZlQ+DaP7I387mKwJBAKXQhPcX/EP6kOMGR8eGc8sVy5tg55GQVpQjixZlIlLs
QrdbuK0Ad4szHWCm8XkRafba9EW966JFipzRfkg7Vjw=
-----END RSA PRIVATE KEY-----
 
real	0m46.011s
user	0m45.715s
sys	0m0.048s