Mathematics for Computer Science

8.8. The RSA Algorithm 215

The RSA Cryptosystem

Beforehand The receiver creates a public key and a secret key as follows.

1. Generate two distinct primes,pandq. Since they can be used to
   generate the secret key, they must be kept hidden.


2. LetnDpq.


3. Select an integeresuch that gcd.e;.p1/.q1//D 1.
   Thepublic keyis the pair.e;n/. This should be distributed widely.


4. Computedsuch thatde1 .mod.p1/.q1//. This can be done
   using the Pulverizer.
   Thesecret keyis the pair.d;n/. This should be kept hidden!

Encoding Given a messagem, the sender first checks that gcd.m;n/D 1.

The sender then encrypts messagemto producemusing the public key:

mDrem.me;n/:

DecodingThe receiver decrypts messagemback to messagemusing the secret

key:

mDrem..m/d;n/: