I did not mean to say that private key was obtained from public key. By weak RNG, I meant the scenario of
reused R value, which might be the case for Bitstamp. Because, it is now known that multiple people are now scanning the blockchain for this vulnerability.
There is no indication for this on the blockchain. For the bitstamp incident, there has been no repeated R value on any of the compromised addresses. I'm pretty sure that this is not the problem here. Even if they used a weak RNG, it is more likely that the attacker hacked the computer storing the private keys than that he hacked the computer storing their private code, analysed their code for weaknesses, found a weak RNG and then broke it.
As for paper wallets. I always thought that you dispose a paper wallet once you use it to pay from it. Import the private key and then transfer some money to your hot wallet and the rest to a fresh paper wallet. This way you have no problems with weak signatures (as long as they are not so weak that you can break them faster than the transaction is confirmed). Using RFC6979 is still a good idea.
Preventing that the private key of your paper wallet was generated by a bad RNG is another important issue. And you need some trusted offline computer running a trusted program to generate the paper wallet. Even using the OS secure random number generator can be problematic: If you boot a well-known Linux image especially if you do this in a virtual machine it may not gather enough entropy (randomness), since the boot process is very deterministic. A hardware RNG (or just a physical coin or die that you throw often enough) may help here. Alternatively, let the system run for a while and gather more entropy from keystrokes and mouse movements before generating the keys.
The attack on the OS secure RNG is probably not practical as there is still a lot of randomness that an attacker needs to account for. However, it would be a bad idea to make a boot image that generates a paper wallet automatically on boot without any user interaction and any hardware rng device (I wouldn't be surprised if such an image already exists).
