International Association
for Cryptologic Research

We discuss how to recover RSA secret keys from noisy analog data

obtained through physical attacks such as cold boot and side channel

attacks. Many studies have focused on recovering correct secret keys

from noisy binary data. Obtaining noisy binary keys typically involves

first observing the analog data and then obtaining the binary data

through quantization process that discards much information pertaining

to the correct keys. In this paper, we propose two algorithms for

recovering correct secret keys from noisy analog data, which are

generalized variants of Paterson et al.\'s algorithm. Our algorithms

fully exploit the analog information. More precisely, consider observed

data which follows the Gaussian distribution

with mean $(-1)^b$ and variance $\\sigma^2$ for a secret key bit $b$.

We propose a polynomial time algorithm based on

the maximum likelihood approach and show that it can recover secret keys

if $\\sigma < 1.767$. The first algorithm works only if the noise

distribution is explicitly known. The second algorithm does not need to

know the explicit form of the noise distribution. We implement the first

algorithm and verify its effectiveness.