# RSA and El Gamal Public Key Encryption

### Public Key Encryption (PKE):

Setting: A bank wants to communicate with its customers over the internet.

1. It does not want to set up different keys for each customer, a lot of work.

2. It does not want to risk a customers secret key being stolen or otherwise compromized.

It will be notationally convenient below to abbreviate as and as and as which is consistant with 1.

Methodology: The bank tells the world about and if a customer wants to communicate a message ,

the customer first computes and then transmits . The bank then "receives" the message by computing ).

Issues:

1. Knowing , it should be hard to determine .

2. The message should still contain some private information, maybe an account number, so that a customer's account is not compromised.

Digital Signatures:

PKE can be used for two way secret communication, between bank and bank , as follows:

• Assume bank has a PKE ( , ) and bank has a PKE ( , ).

• Assume the Messages are the same for both PKEs , moreover assume for both.

• Finally assume,

Note that this would be true for 2 RSA schemes (see below).

Methodology: bank wishes to send a secret message , using it computes and transmits it. To read the message bank computes

Again, bank knows but not and bank knows but not .

### _________________________________________________________________________________

Methodology: Our calculations are in unless noted as .

Choose where are primes and

Choose such that , and let .

for some .

The key observation is that if for then by the Fermat--Euler Theorem:

To allow anybody to securely transmit messages to you:

Tell the world and . Assume somebody wants to send the message to you privately, tell them to compute

and transmit

Compute

To break the code:

Since people know and , they need to calculate , and to do that they need to calculate

In particular factor , which can be difficult.

Some additional Notes. from a course I taught a few years back.

An original example from Rivest, Shamir, Adleman(1978):

The Alphabet Encoding:

The Message:

ITS ALL GREEK TO ME

The Message encoded in blocks of 2(with padding the last ):

- - - - - -- - - - - -

Note: Encoding in blocks of 2 and then enciphering the block is a bit idiosyncratic. I chose to reproduce the original example.

What makes this work is that the biggest, thus encoded message (ZZ) ,considered as a number

Of course, the price paid is that the deciphered message may have an extra blank at the end.

- - - - - - - - - - - - - - - - - -

IT :Enciphered

The Message Enciphered :

IT :Deciphered

Exercise(Due April 11 )

The Alphabet Encoding:

The Message:

CAB

Find an appropriate and then Encode Encipher Decipher the message.

### El Gamal PKE:

Definitions:

Given a prime, , we are looking at , the multiplicative group of non-zero elements in .

• We say is primitive root if for .

An an example is but not

• Given a primitive root , for any define the discrete logarithm of written , to be the least positive integer such that

Note

Methodology:

Given a primitive root, choose a private key .

To allow anybody to securely transmit messages to you:

Tell the world and, . Assume somebody wants to send the message to you privately, tell them to select a private key compute

and , and transmit both values.

Compute

To break the code:

Plan A: You know and, just compute .

Plan B: You know and, just compute and since you know compute then compute

In both cases you need to be able to compute the discrete logarithm of a number. Again this is hard computationally.

### ______________________________________________________________________________________________________

This image is from Cryptography: Theory And Practice By Douglas Robert Stinson,

an excellent book for those who wish to pursue this subject further.