Mathematics for Computer Science

Chapter 8 Number Theory280

The RSA Cryptosystem

AReceiverwho wants to be able to receive secret numerical messages creates a

private key, which they keep secret, and apublic key, which they make publicly

available. Anyone with the public key can then be aSenderwho can publicly

send secret messages to theReceiver—even if they have never communicated or

shared any information besides the public key.

Here is how they do it:

Beforehand TheReceivercreates a public key and a private key as follows.

1. Generate two distinct primes,pandq. These are used to generate the
   private key, and they must be kept hidden. (In current practice,pand
   qare chosen to be hundreds of digits long.)


2. LetnWWDpq.


3. Select an integere 2 Œ0::n/such that gcd.e;.p1/.q1//D 1.
   Thepublic keyis the pair.e;n/. This should be distributed widely.


4. Let theprivate key d 2 Œ0::n/be the inverse ofe in the ring
   Z.p1/.q1/. This private key can be found using the Pulverizer. The
   private keydshould be kept hidden!

Encoding To transmit a messagem 2 Œ0::n/toReceiver, aSenderuses the

public key to encryptminto a numerical message

bmWWDme.Zn/:

TheSendercan then publicly transmitbmto theReceiver.

DecodingTheReceiverdecrypts messagebmback to messagemusing the pri-

vate key:

mDbmd.Zn/: