Embed Notice

@ondrej In a CTF I played in a long time ago, there was a high value challenge that involved recovering an RSA private key that had a bunch of random bytes erased.

I found a paper (oh, of course it's from Nadia Heninger) called "Reconstructing RSA Private Keys from Random Key Bits" and with some digging discovered that PoC code existed. With some prodding, I was able to solve the challenge.

One of the organizers was stunned that I solved it so quickly, and when I explained was even further stunned that any code existed - he just assumed the algorithm was only described in the paper.

This isn't my writeup, but describes the challenge and approximately what I did:

https://github.com/ctfs/write-ups-2014/blob/master/plaid-ctf-2014/rsa/README.md