RSA encryption

The RSA cryptosystem is one of the first public-key cryptosystems. The encryption key is public, while the decryption key is secret. The RSA encryption security is based on the practical difficulty of "the factoring problem". It is constructed using two large prime numbers and only by knowing them can the decryption key be calculated. It is named after the inventors, Ron Rivest, Adi Shamir and Leonard Adleman.

Key generation

The key for the RSA encryption is generated in the following steps:

  • Choose two random big prime numbers, p and q.
  • Multiply the prime numbers to get the modulus: n = pq.
  • Choose an exponent, e, such that the greatest common divisor between e and (p-1)(q-1) is 1. A common value for e is 3. There is no need to chose any larger integer.
  • Calculate the modular multiplicative inverse, d. This means solving the equation de ≡ 1 (mod (p-1)(q-1)).

If you only have n and e, without access to the prime numbers, p and q, it will be extremely difficult (practically impossible) to calculate d. Therefore, there is no need to keep n and e secret.

Encryption

Encryption is done using the public key (e and n). This means that anyone can encrypt. If m is the message, calculate:

c ≡ m e (mod n)

This calculation is called modular exponentiation and can be done pretty fast, especially if e is not too large.

Decryption

Decryption is done using the private key (d and n). This means that only the holder of the private key can decrypt. If c is the encrypted message, calculate:

m ≡ c d (mod n)

Example

Key generation

Choose the prime numbers p = 62273 and q = 56767 (for demo purposes, small prime numbers are chosen, while in a real-world case MUCH bigger prime numbers would have been chosen).

Calculate n = pq = 62273 x 56767. Therefore n = 3535051391.

Calculate (p-1)(q-1) = 62272 x 56766 = 3534932352. Choose and exponent e which has no common divisor with (p-1)(q-1). We cannot choose e = 3, because 3534932352 is divisibly by 3. However, we can choose e = 5.

Calculate the modular multiplicative inverse. It can easily be done using this modular multiplicative inverse tool. The result is d = 1413972941.

Encryption example

Let's encrypt the number 1234567890. We get:

c ≡ 12345678905 (mod 3535051391).

This can easily be calculated using this modular exponentiation tool. The result is 855907849.

Note: To encrypt text, you will first have to convert the text that you want to encrypt to a number (or series of numbers) between 0 and n-1 (3535051390). The text could for instance be converted to ASCII codes, and then divided into blocks of 3 bytes each, which would represent 24-bit integers. You then fill up the remaining bits with a padding, and then each block will be a number between 0 and n-1.

Decryption example

Using the numbers from the previous examples, we get:

m ≡ 8559078491413972941 (mod 3535051391)

Again, this can easily be calculated using this modular exponentiation tool. The result is 1234567890, which is the number we encrypted.

See also: Code-Breaking overview | Aes | Des | Rc4