Understanding RSA keys

RSA (Rivest, Shamir, Adleman) is a public key cryptographic system used to make communications secure. As in all public key system, there exists a public key, used to encrypt the messages, and a private key, used to decrypt those messages:

Both keys are just very large numbers. Of course, they must be mathematically linked someway so the encryption/decryption process works. The question is: how are they generated?

Public key

First, two large random prime numbers must be selected: p and q. Then, we get N by multiplying them:

N = p * q

Then, a public exponent e is selected so great common divisor between e and Euler's totient function of N equals 1:

gcd(e, euler_phi(N)) = 1

The tuple (N, e) is the public key (p and q must be secret). You share this so others can send encrypted messages to you. We will see later how encryption works.

Private key

To get the private key, we need to get the value of d by solving the modular equation below:

d = e^(-1) (mod euler_phi(N))

d is the modular inverse of e (public exponent) module euler_phi(N).

The tuple (N, d) is the private key. You will use this to decrypt messages sent to you and it must kept secret.

How to encrypt messages with the public key?

Given a plaintext message m and a public key (N, e), getting the ciphered text c is quite straightforward:

c = m^e (mod N)

How to decrypt messages with the private key?

Given a ciphered message c and a private key (N, d), getting the plaintext message m is quite straightforward:

m = c^d (mod N)

Example

I will omit the process of keys pair creation. In this case, for simplicity, I will use small numbers.

• Public key: (N = 77, e = 3)
• Private key: (N = 77, d = 43)

We want to encrypt the plaintext message m = 57 using the public key, so:

c = m^e (mod N)
c = 57^7 (mod 77)
c = 29

Now, to decrypt the ciphered message using the private key:

m = c^d (mod N)
m = 29^43 (mod 77)
m = 57

We have encrypted and decrypted the message and the result seems correct.

Conclusions

RSA system's security relies on the difficulty of getting the factors of N (p and q). If an attacker can guess p and q, he will obtain the private key and the process won't be secure anymore. When p and q are small numbers, it is easy to guess them from N. However, if they are large (say 2048 or 4096 bits, for example), it can take thousands of years to guess them using the most powerful computer.