We show that an RSA private key with small public exponent can be eciently recovered given a 0.27 fraction of its bits at random. An important application of this work is to the \cold boot" attacks of Halderman et al. We make new observations ab