Provided by: Charles University
Date Added: Jun 2009
The paper describes a new attack on RSA-CRT employing Montgomery exponentiation. Given the amount of so-called final subtractions during the exponentiation of a known message (not chosen, just known), it creates an instance of the well known Hidden Number Problem (HNP,). Solving the problem reveals the factorization of RSA modulus, i.e. breaks the scheme. The main advantage of the approach compared to other attacks is the lack of the chosen plaintext condition. The existing attacks, for instance, cannot harm so-called Active Authentication (AA) mechanism of the recently deployed electronic passports.