RSA Cipher

RSA encryption is purely mathematical, any message must first be encoded by integers (any encoding works: ASCII, Unicode, or even A1Z26). For RSA encryption, the numbers $ n $ and $ e $ are called public keys.

The (numeric) message is decomposed into numbers (less than $ n $), for each number M the encrypted (numeric) message C is $$ C \equiv M^{e}{\pmod {n}} $$

Example: Encrypt the message R,S,A (encoded 82,83,65) with the public key $ n = 1022117 $ and $ e = 101 $ that is $ C = 828365^{101} \mod 1022117 = 436837 $, 436837 is the encrypted message.

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.

Example: $ p = 1009 $ and $ q = 1013 $ so $ n = pq = 1022117 $ and $ \phi(n) = 1020096 $. The numbers $ e = 101 $ and $ \phi(n) $ are prime between them and $ d = 767597 $.

The keys are renewed regularly to avoid any risk of disclosure of the private key.

Decryption requires knowing the private key $ d $ and the public key $ n $. For any (numeric) encrypted message C, the plain (numeric) message M is computed: $$ M \equiv C^{d}{\pmod {n}} $$

Example: Decrypt the message C=436837 with the public key $ n = 1022117 $ and the private key $ d = 767597 $, that is $ M = 436837^{767597} \mod 1022117 = 828365 $, 82,83,65 is the plain message (ie. the letters R,S,A)

The message is fully numeric and is normally accompanied by at least one key (also numeric). In practice the keys are displayed in hexadecimal, their length depends on the complexity of the RSA implemented (256 bits, 512, 1024 or 2048 are common)

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.

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

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