# Appendix C. Description of Public Key Algorithms

How does RSA work?
How does El Gamal work?

# How does RSA work?

We show a high–level though working description of RSA. Then, we give an example with easy to work with numbers.

## Description

To initialise RSA, follow the steps

1. Pick two large primes, p and q.

2. Find N = p * q. N is the RSA modulus.

3. Let e be a number relatively prime to (p-1)*(q-1).

4. Find d, so that d*e = 1 mod (p-1)*(q-1) .

5. The set (e, N) is the public key. Make it known to every one.

The set (d, N) is the private key. Keep it private and safe.

To encrypt a message m,

1. Make sure m < N, otherwise chop m in suitably small pieces and perform RSA on each individual piece.

2. Compute c = m ^ e mod N

3. c is the encrypted message

To decrypt a ciphertext c,

1. Compute m = c ^ d mod N

2. m is the original message

To sign message m,

1. Compute s = m ^ d mod N

2. s is the digital signature. Send along with message m.

To verify signed message s,

1. Compute m = s ^ e mod N

2. Check if m from above calculation is the same with message sent.

TODO