Researchers demonstrate RSA signature forgery without factoring keys

Researchers have demonstrated a classical-computing technique that can forge RSA digital signatures without first factoring the public key’s modulus, challenging the long-held assumption that defeating RSA requires solving the underlying factoring problem.

According to Ars Technica, the researchers completed an attack against a deprecated 1,024-bit RSA key in several months using an academic CPU cluster. Estimates for factoring a key of that size have typically involved computing resources available only to large technology companies or national intelligence agencies, potentially costing tens of millions of dollars for a single key.

Nadia Heninger, a University of California, San Diego professor and co-author of the research, said the forgery method is practical for 1,024-bit RSA. The researchers also found that it lowers the security offered by 2,048- and 4,096-bit keys.

The immediate risk is limited: 1,024-bit RSA has been deprecated, and widely used RSA implementations are reported to be safe from the demonstrated attack. However, the method reduces the computing resources needed to attack affected RSA signatures by orders of magnitude.

Cryptography expert Karsten Nohl said the result would represent a conceptual breakthrough if it withstands peer review, because it provides a route to producing valid signatures without recovering the private key.