Generalized Security Analysis of the Random Key Bits Leakage Attack

摘要

In CRYPTO 2009, Heninger and Shacham presented a new method of recovering RSA private keys bit by bit given a fraction of private data, and analyzed resistance of RSA against the attack. They obtained a system of relations between RSA private variables and cal culated the expected number of solution candidates. As they dealt with only RSA case, we consider the case that the system of equations is given in more general linear form. We show that the complexity of their at tack depends only on the number of variables, the number of ambiguous variables, and the degree of freedom. As concrete examples, we apply the attack to Paillier cryptosystem and Takagi's variant of RSA, and analyze their resistance against the attack. In Pailiier's case, its resistance is al most the same as the case when a fraction of three private RSA keys are leaked. In Takagi's case, we find that the asymmetricity in two factors of the modulus give some effects on the resistance against the attack.