Public-Key Encryption - Everyday Cryptography - page 163

Generating the modulus . Let p = 47 and q = 59. Thus:

n = pq = 47 × 59 = 2773 .

Generating e . Select e = 17, which is a valid choice since there is no number that

divides into 17 and ( p − 1)( q − 1) = 46 × 58 = 2668, except for 1.

Forming the public key . The pair of numbers ( n 17) form the public

key and can be made available to anyone whom we wish to be able to send us
encrypted messages.
Generating the private key . Input p

, e ) = (2773 ,

= 47, q = 59 and e = 17 to the Extended

Euclidean Algorithm. The output will be d = 157. We can check that this result

is correct by computing:

de = 17 × 157 = 2669 = 1mod 2668 .

The private key is d = 157, which is a value that only we know.

5.2.2 Encryption and decryption using RSA

Once an RSA key pair has been set up, the hard work is done. Encryption and
decryption are relatively simple processes to understand.

RSA ENCRYPTION
Suppose that we wish to send some plaintext to someone whose public key is
( n e ).

The first point to note is that RSA does not directly operate on strings of bits,
but rather on numbers modulo n . Thus our first task is to represent the plaintext
as a series of numbers less than n . We will not discuss exactly how to do this here,
but it is not any more difficult than the process of converting an English plaintext
into a string of bits that can be processed by a block cipher such as AES. So long
as everyone using RSA agrees to the same 'rules' for performing this conversion,
everything will work.
We thus assume that every plaintext is a number less than n . Note that these
numbers must be less than n . If we allow a plaintext to be greater than n then
we will not be able to represent it uniquely since we will not be able to tell
the difference between, for example, the plaintext 5 and the plaintext n + 5,
since both of these would be considered by RSA to be equal to 5 (because
n

,

5mod n ).
Suppose that we now want to encrypt the first plaintext P , which is a number
modulo n . The encryption process to obtain the ciphertext C is very simple:

+ 5 =

P e mod n C = .

In other words, the ciphertext C is equal to the plaintext P multiplied by itself
e times and then reduced modulo n . This means that C is also a number less
than n .