Rsa

RSA comes from the names of it's inventors: Rivest, Shamir and Adleman.

public and private key

It provides a public and a private key. The public key is provided to someone who wishes to communicate safely.

The idea is that a message encrypted with the public key can only be decrypted with the private key. So that is why it can be sent to anyone or even published, encrypt all you want, i am the only one who can decrypt it !

algorithm

This is based on two prime numbers : p and q If you know these numbers you can decrypt the message, they should be large and kept secret. But we will use small ones for this example:

P=61
Q=53

N=P*Q = 3233

This N is known as the modulus, you can see this for example in certificates (see below)

phi(N) = (p-1)(q-1) = 
phi(3233) = (61 - 1)(53 - 1) = 3120

Choose an exponent based on phi, it should be a prime, bigger than 1 and smaller than 3120, and not be a divisor of 3120 (so not 2, 3, 5, but 7 is ok) This is usually a small number, see below. We choose 17

exp=17

Calculate d such that exp * d % phi(N) = 1:

(17 * d) % 3120 = 1
d = 2753

The public key :

(n=3233, e=17) 
c(m) = m^17 % 3233

Where ^ is "to the power of"

The private key

(n=3233, d=2753) 
m(c) = c^2753 % 3233

To encrypt a letter 'm' (65) this would be :

c = 65 ^ 17 % 3233 = 2790

so 2790 is the encrypted 'm', only if you know d you can decrypt the message with :

m = 2790 ^ 2753 % 3233 = 65 

So the number n (3233) is also publicly available.

Note that you never need P and Q again.

For small numbers like these, you could just dissolve 3233 back into p and q, and so calculate d again. But it's just the difficulty to factor large numbers back into those two primes that ensures the safety of the algorithm.

As an example of how large see this RSA example, it's a public key so modules is n, and exponent = e.

RSA Public Key: (2048 bit)
     Modulus (2048 bit):
         00:bc:2c:51:72:ce:f5:f3:0d:61:74:cd:93:0d:63:
         0c:1f:eb:d5:58:ff:03:93:66:66:79:92:d9:5f:69:
         51:ba:dd:1c:39:22:95:a7:1b:77:e9:2f:b3:79:f3:
         b1:73:20:d8:8f:2c:0e:03:99:bb:45:18:2c:b8:56:
         90:bb:cd:b4:0b:6e:d6:f3:42:17:0d:67:26:8f:4f:
         83:22:a5:00:1c:8c:f3:1a:c1:86:be:1f:e2:f9:6a:
         ca:e0:5e:92:cb:69:0f:95:86:3c:cc:db:5a:b4:41:
         1a:d5:7b:09:ec:dc:21:50:d8:3c:ae:37:aa:ae:5e:
         61:39:ff:c8:68:3d:bd:37:60:1c:5b:ea:e1:ad:1d:
         3e:72:35:06:e1:fe:7c:53:05:b4:f0:1f:f1:75:2f:
         30:27:95:ca:5b:d6:7d:cd:41:56:93:70:07:1a:68:
         e5:05:3f:12:be:76:d9:e4:a2:3d:24:d4:43:38:22:
         74:7c:27:a8:ed:9c:8b:95:57:d4:e9:d5:be:d7:83:
         61:9b:6d:c8:49:3c:08:04:77:d2:a4:27:22:36:37:
         29:9f:3e:cf:81:fb:70:10:5c:af:4c:9d:0c:8c:10:
         6f:c1:d6:b8:75:19:f7:2a:61:6e:70:ab:5d:d3:bb:
         3b:10:11:41:4b:ee:ee:5a:4f:32:bc:fc:5a:93:d3:
         95:4d
     Exponent: 65537 (0x10001)

In a private key, the private exponent will also be a large number, you can show all components with this command :

openssl rsa -in ~/.ssh/id_rsa -text 

ssh

Note : though ssh uses this scheme for authentication, it does NOT for encryption!!. Whenever the opposite party is authenticated, they both establish an encryption key that is symmetric and that is then used to communicate. Nothing in the outside world ever sees anything of this key.