Appendix C. Description of Public Key Algorithms

Table of Contents
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.