Better Algorithms for MSB-side RSA Reconstruction

Abstract : In this work, we extend research in the area of reconstruction of private RSA keys using few random bits made available through partial key exposure attacks such as the Cold Boot Attack. Our work discusses an approach to reconstruct private components of RSA from the most significant bit (MSB) side given only 26% of the secret bits. Our approach shows significant improvement over previous works on reconstruction from the MSB side. Our results closely match those of the Heninger and Shacham that gives reconstruction from the LSB side.