Awareness Services

New Technology Accelerates Factorization Enormously – Threat to RSA Encryption?

New Technology Accelerates Factorization Enormously – Threat to RSA Encryption?

The RSA encryption requires two different keys so that messages can be signed or encrypted. The two keys, private and public, consist of the RSA20148, a 2048bit long number and the RSA module.

To generate these keys you need two prime numbers and exactly these provide an attack vector, because a new technology allows a factorization to happen much faster.

The RSA Encryption

Do you work with e-mails on a daily basis? If so, you are dealing with RSA encryption on a daily basis. Let’s take a closer look at this encryption and try to understand the attack vector, which is getting more dangerous with a new technology.

Private and Public Key

In order to sign or encrypt messages with RSA encryption, we need the private and public keys. Both keys consist of the so-called RSA module, which is the same for both keys, and the encryption or decryption exponent. The public key is not secret. This means that it can be found publicly e.g. on a key server. It is only important that a public key is assigned to exactly one person, otherwise other people could sign messages with your name.

The private key, on the other hand, should remain secret. Anyone who knows the private key can decrypt and read the ciphertext. In addition, a signature is only unique if the private key does not fall into the hands of others. The exact process of creating the keys is time-consuming. However, our summary is sufficient for an overview.

An Overview of RSA Encryption

As transmitter the formula: c = m^e mod(N) is used. This means that each character of my message m, factorizes with the encryption component of the receiver. The encryption component is in the public key, so anyone can encrypt a message for the recipient. After the character has been factorized, it is shared with the also public N, the RSA module, modulo. The result of this calculation is the c, the so-called cipher.

Example: We want to encrypt character 6. The public key of the recipient is (N=143, e=23).

               128 = 6^23 mod(143)

The message we send to our recipient is 128, this number represents the cipher to the above message with the public key (143, 23).

Decrypting the RSA encryption

As recipient we receive the message 128. This message was encrypted with our public key so that we can decrypt it with our private key (N=143, d=47).

6 = 128^47 mod(143)

As a result we get the character 6 and have encrypted and decrypted a message. If nobody but me knows the private key, the ciphertext can only be decrypted with considerable effort.

An essential component – time

In reality, important documents are encrypted with as large a key as possible so that the attacker cannot guess the key via a brute force attack. RSA encryption, in which a key consists of a 2048-bit number, is frequently used. In decimal space, the highest number corresponds to a 617-digit number.

Since we increase the power of our key during encryption and decryption, there is a large computing load. Up to now, quantum computers have used the so-called qubits. A qubit is a system within a quantum computer that can only assume two states. Decomposing (factorizing) a 2048bit number into its individual prime numbers is practically impossible because the computing load could not yet be processed.

But with a new technology, the number of qubits necessary for such a decomposition has decreased from about 1 billion to only 2 million. This means that fewer resources in the form of qubits are needed to perform factorization. Accordingly, the duration also decreases, because there are now more resources available. The current duration is about 8h to factorize a 2048bit long number.

Importance for IT security

The RSA module consists of the multiplication of two prime numbers. This module is public because it is part of the public key. Both the decryption and encryption exponents depend on the two prime numbers, so strangers should have no information about the two prime numbers selected.

Now that it only takes 8h to factorize a 2048bit long number, the attacker gets a list of possible prime numbers you might have used and can start a brute force attack.

The German Federal Network Agency recommends a 2000bit long number when using RSA encryption until 2022. However, a key length of 3000bit will be required in future so that the security risks of prime number decomposition are minimized.

Photo of author

Jan Hörnemann

Ich bin Jan Hörnemann, TeleTrust Information Security Professional (T.I.S.P.) und seit 2016 leidenschaftlich in der Welt der Informationssicherheit unterwegs. Mein Master of Science in Internet-Sicherheit hat mir ein fundiertes Verständnis für verschiedene Aspekte dieser Branche vermittelt, das ich in meiner laufenden Promotion kontinuierlich ausbaue. In der AWARE7 bin ich Chief Operating Officer und Prokurist, gleichzeitig koordiniere ich die Abteilungen "Informationssicherheit" und "Offensive Services" und sorge dafür, dass alle Projekte reibungslos ablaufen.