RSA Cipher

RSA (named after its creators Ronald Rivest, Adi Shamir and Leonard Adleman) is an asymmetric cryptography algorithm based on modular arithmetic and the difficulty of factoring a large integer $ n $ which is the product of two large prime numbers. Using a public key and a private key, RSA can be used both for encryption and for digital signatures.

RSA encryption is based on a mathematical operation applied to an integer representing the message. In its simplified mathematical form, with the public key $ (n,e) $, the message $ M $ is encrypted as $$ C \equiv M^e \pmod n $$

In practice, this operation is not used alone to encrypt a message directly: a padding scheme, such as RSAES-OAEP, first transforms the message into a representation suitable for encryption.

If the integer representation of the message is greater than or equal to $ n $, it must be split into blocks whose values are less than $ n $. In practice, the maximum message size also depends on the padding scheme used.

RSA decryption requires the private key corresponding to the public key used for encryption. In its simplified mathematical form, the plaintext $ M $ is computed as: $$ M \equiv C^d \pmod n $$ with $ C $ the ciphertext and $ (n,d) $ the corresponding private parameters.

In practice, this raw number is not the ASCII message itself, because it is modified with a padding scheme that must be removed.

RSA needs a public key (consisting of 2 numbers $ (n, e) $) and a private key (only 1 number $ d $).

— Select 2 distinct prime numbers $ p $ and $ q $ (the larger they are and the stronger the encryption will be)

— Calculate $ n = p \times q $

— Calculate the indicator of Euler $ \phi(n) = (p-1)(q-1) $

— Select an integer $ e \in \mathbb{N} $, prime with $ \phi(n) $ such that $ e < \phi(n) $

— Calculate the modular inverse $ d \in \mathbb{N} $, ie. $ d \equiv e^{-1} \mod \phi(n) $ (via the extended Euclidean algorithm)

With these numbers, the pair $ (n, e) $ is called the public key and the number $ d $ is the private key.

A raw RSA message is generally represented by one or more integers, along with key parameters such as $ n $ and $ e $.

In real-world applications, however, RSA data can be represented in different forms: binary numbers, hexadecimal numbers, PEM files, ASN.1 structures or Base64-encoded data.

The size of RSA is generally expressed in bits and corresponds to the size of the modulus $ n $ (usually 1024, 2048 or 3072 bits)

RSA has notably been used in TLS/HTTPS for certificates and, in older versions of TLS, for key transport.

Method 1: Prime numbers factorization of $ n $ to find $ p $ and $ q $.

The RSA cipher is based on the assumption that it is not possible to quickly find the values $ p $ and $ q $, which is why the value $ n $ is public. To find the private key, a hacker must be able to perform the prime factorization of the number $ n $ to find its 2 factors $ p $ and $ q $. In practice, this decomposition is only possible for small values, i.e. a key $ n $ comprising less than 30 digits (for current algorithms and computers), between 30 and 100 digits, counting several minutes or hours, and beyond, calculation can take several years. With $ p $ and $ q $ the private key $ d $ can be calculated and the messages can be deciphered.

Method 2: Find the common factor to several public keys $ n $

Key generation is random but it is not unlikely that a factor $ p $ (or $ q $) could be used to calculate the values of 2 different public keys $ n $. By calculating the GCD of 2 keys, if the value found is different from 1, then the GCD is a first factor of $ n $ (therefore $ p $ or $ q $), by dividing $ n $ by the gcd is the second factor ($ p $ or $ q $).

Method 3: Chosen ciphertext attack

Given a published key ($ n $, $ e $) and a known encrypted message $ c \equiv m^e \pmod{n} $, it is possible to ask the correspondent to decrypt a chosen encrypted message $ c' $. Based on the property $ m_1^e m_2^e \equiv (m_1 m_2)^e \pmod{n} $, the decryption of a message $ c' \equiv c \times r^e \pmod{n} $ with $ r $ a chosen number (invertible modulo $ n $) will return the value $ m \times r \pmod{n} $. By calculating $ m \times r \times r^{-1} \pmod{n} $ (with $ r^{-1} $ the modular inverse) is found $ m $ the original message.

Method 4: Problem with short messages with small exponent $ e $

For a small exponent ($ e = 3 $) and a short message $ m $ (less than $ n^{1/e} $) then the encrypted message $ c = m^e $ is less than $ n $, so the calculation of the modulo has no effect and it is possible to find the message $ m $ by calculating $ c^{1/e} $ ($ e $-th root).

Method 5: Wiener's attack for private keys $ d $ too small

If the private key $ d $ is small compared to the message $ n $ and such that $ d < \frac{1}{3} n^{\frac{1}{4}} $ and that $ p $ and $ q $ are close $ q < p < 2q $, then by calculating approximations of $ n/e $ using continued fractions, it is possible to find the value of $ p $ and $ q $ and therefore the value of $ d $.

To find the private key, a hacker must be able to realize the prime factor decomposition of the number $ n $ to find its 2 factors $ p $ and $ q $. For small values (up to a million or a billion), it's quite fast with current algorithms and computers, but beyond that, when the numbers $ p $ and $ q $ have several hundred digits, the decomposition requires on average several hundreds or thousands of years of calculation. There are databases listing factorizations like here

With the numbers $ p $ and $ q $ the private key $ d $ can be computed and the messages can be decrypted.

The value $ e=65537 $ comes from a cost-effectiveness compromise.

A value of $ e $ that is too large increases the calculation times. A value of $ e $ that is too small increases the possibilities of attack.

$ 65357 $ is a Fermat number $ 65357 = 2^{2^4} + 1 $ which allows a simplification in the generation of prime numbers.

This value has become a standard, it is not recommended to change it in the context of secure exchanges.

The number found is an integer representing the decimal value of the plaintext content.

Generally, this number can be transcribed according to the character encoding used (such as ASCII or Unicode).

In a real-world RSA implementation, the decryption result may contain encoding or padding that must be processed before the original message is obtained.

An RSA certificate is a text file containing the data useful for a cryptographic exchange by RSA.

There are 2 types of certificate:

— the public certificate, which begins with -----BEGIN PUBLIC KEY----- and which contains the values of the public keys $ N $ and $ e $.

— the private certificate, which starts with -----BEGIN RSA PRIVATE KEY----- and which contains all the values: $ N $, $ e $, $ d $, $ q $ and $ p $. This file is usually kept safe and should never be disclosed.

An X.509 certificate differs from an RSA key: notably, it contains a public key and information about its owner, as well as a signature used to authenticate its content.

A sufficiently large and fault-tolerant quantum computer could efficiently factor large numbers using Shor's algorithm. This would compromise the security of RSA.

However, current quantum computers do not have the capabilities required to factor RSA moduli used in practice. This threat is motivating the development and gradual deployment of post-quantum cryptography.

Ronald Rivest, Adi Shamir and Leonard Adleman described the algorithm in 1977 and then patented it in 1983.