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:
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 |
1 ping
[…] 这道题目给出了一个4096位的RSA公钥，标准e，同时给出了部分私钥，参考国外类似题目wp，我们编写脚本完成解密 […]