The most popular public key cryptosystem to date has been RSA, whose security primarily relies on the unfeasibility of factoring the modulus, which is a product of two large primes, and on the secrecy of certain RSA parameters. In 2009, the cold-boot attack by Halderman et al presented an important cryptanalytic model where a portion of the secret parameters may be exposed. In this direction, Heninger and Shacham (Crypto 2009) introduced the problem of reconstructing RSA private keys when few random bits from each are known. Later, Henecka, May and Meurer (Crypto 2010) introduced the problem of error-correction in the RSA private keys when all the bits are known with some probability of error. Their approach attempted error-correction from the least significant side of the parameters. In this paper we provide a novel technique for error-correction that works from the most significant side of the parameters. Representative experimental results are provided to substantiate our claim. © 2013 Springer-Verlag.