Ever since my first post on breaking DSA, I’ve been meaning to write a clear description of how to recover a private key if you only have a fraction of the bits. For example, power analysis attacks may allow you to derive a few bits of the random k value on each measurement. It turns out you can combine multiple measurements to get a single k value and then recover the DSA private key. Of course, all this also applies to ECDSA.
Since I haven’t had time to put together a good summary article, here are some references for learning this on your own. The first paper in this area was Boneh and Venkatesan (1996). They described the basic Hidden Number Problem.
The next important paper was by Howgrave-Graham and Smart (1999) [1]. They used Babai’s algorithm[2] and LLL lattice reduction to solve for DSA private nonces. This was improved by Nguyen and Shparlinski (2000) [3] to solve for just the k values.
This attack applies any time the DSA nonce isn’t fully random and used only one time. It applies if a few of the bits are constant, if the RNG is biased towards certain values, or if you can recover part of the values by side channel attacks. These references should allow you to implement this attack yourself. It has been repeatedly used in private work, but I haven’t seen much public discussion about applying this to real-world systems.
[1] Howgrave-Grahm and Smart. “Lattice attacks on Digital Signature Schemes.” HP internal publication, 1999.
[2] Laszlo Babai. “On Lovász lattice reduction and the nearest lattice point problem.” Combinatorica 6. No online reference found.
[3] Nguyen and Shparlinski. “The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces.” Journal of Cryptology, volume 15, pp. 151-176, 2000.
Addendum: I found the following references to improve this list.
- Slides by Shparlinski on the HNP
- Nguyen on the hardness of the hidden subset sum problem (1999)
- DSA nonces can be forced into this form with a glitch attack (2004)
rdist 
I’m interested in any analysis you have on bitcasa and in particular their implementation of convergent encryption.
This is another reference you could add to your post. It talks about using redundant information in the RSA private key storage format to reconstruct the RSA private key given a small random fraction of the bits.
http://eprint.iacr.org/2008/510
That’s fine, but it’s totally unrelated. The Hidden Number Problem describes numbers of a particular form, which can be represented as integer lattice vectors.
The paper you reference talks about a common in-memory representation of RSA private keys. That’s an implementation detail, not an algorithmic property.