Bulletproof TLS Newsletter #60
New factoring and discrete log records, but RSA stays safe
31 December 2019
Author: Hanno Böck

This issue was distributed to 52,807 email subscribers.

Bulletproof TLS Newsletter is a free periodic newsletter bringing you commentary and news surrounding SSL/TLS and Internet PKI, designed to keep you informed about the latest developments in this space.

In this issue:

  1. New factoring and discrete log records, but RSA stays safe
  2. Short news

New factoring and discrete log records, but RSA stays safe

A team of researchers has announced a new record in factoring large numbers and calculating discrete logarithms. The researchers factored the RSA-240 number on hardware of the Grid’5000 project, a collaboration of French research institutes. At the same time, the researchers have calculated a discrete logarithm of the same size.

The hardness of factoring and of calculating discrete logarithms is relevant for the security of many public key algorithms, notably RSA (factoring) and Diffie-Hellman (discrete logarithms). The RSA numbers were published as a contest by RSA, Inc. in 1991. Although the contest officially ended in 2007, researchers are still trying to complete the challenges. RSA-240 is 795 bits long. The last RSA number with 768 bits was broken in 2009.

The new result was made possible not only due to faster hardware, but also because improvements made the algorithm faster. The CADO-NFS software that the researchers used is publicly available under a free license.

Although RSA relies on factoring, these results are unlikely to cause any harm for modern RSA implementations. Warnings about the use of short RSA keys have been around for a long time. In 2003, cryptographers Eran Tromer and Adi Shamir published a hypothetical design for a device called TWIRL that would be able to break 1,024-bit RSA keys. No such breakage has been demonstrated in public, but it is often assumed that 1,024-bit keys can be broken by a very powerful attacker.

Modern RSA implementations usually use a minimum key size of 2,048 bits. This is also the most common key size in the TLS ecosystem; smaller keys are not issued by certificate authorities because it is forbidden by the Baseline Requirements. These keys are unlikely ever to be broken on normal hardware. Only quantum computers are realistically a threat for RSA with the current key sizes.

Short news