RSA and El Gamal Public Key Encryption

Public Key Encryption (PKE):

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

It does not want to set up different keys for each customer, a lot of work.
It does not want to risk a customers secret key being stolen or otherwise compromized.

It will be notationally convenient below to abbreviate as $\QTR{Large}{e(s)}$ and as $\QTR{Large}{e(s)}$ and as $\QTR{Large}{d(c)}$ which is consistant with 1.

Methodology: The bank tells the world about $\QTR{Large}{e}$ and if a customer wants to communicate a message $\QTR{Large}{s}$ ,

the customer first computes $\QTR{Large}{e(s)}$ and then transmits $\QTR{Large}{e(s)}$ . The bank then "receives" the message by computing ).

Issues:

Knowing $\QTR{Large}{e\ }$ , it should be hard to determine $\QTR{Large}{d}$ .
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 $\QTR{Large}{A}$ and bank $\QTR{Large}{B}$ , as follows:

Assume bank $\QTR{Large}{A}$ has a PKE ( , ) and bank $\QTR{Large}{B\ }$ 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 $\QTR{Large}{A\ }$ wishes to send a secret message $\QTR{Large}{m}$ , using it computes and transmits it. To read the message bank $\QTR{Large}{B\ }$ computes

Again, bank $\QTR{Large}{A}$ knows $\QTR{Large}{e_{B}}$ but not $\QTR{Large}{d_{B}}$ and bank $\QTR{Large}{B}$ knows $\QTR{Large}{e_{A}}$ but not $\QTR{Large}{d_{A}}$ .

_________________________________________________________________________________

RSA ( Rivest-Shamir-Adleman) PKE:

Methodology: Our calculations are in $\QTR{Large}{Z\ \ }$ unless noted as .

Choose where $\QTR{Large}{p}$ $\QTR{Large}{\neq }$ $\QTR{Large}{q}$ are primes and

Choose $\QTR{Large}{c}$ such that , and let .

for some $\QTR{Large}{k}$ .

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

To allow anybody to securely transmit messages to you $\QTR{Large}{\ }$ : $\QTR{Large}{\ }$

Tell the world $\QTR{Large}{c\ }$ and $\QTR{Large}{n}$ . Assume somebody wants to send the message $\QTR{Large}{a\ \ }$ to you privately, tell them to compute

and transmit $\QTR{Large}{\ e.}$

To decode the message received:

Compute

To break the code:

Since people know $\QTR{Large}{c\ }$ and $\QTR{Large}{n}$ , they need to calculate $\QTR{Large}{d}$ , and to do that they need to calculate

In particular factor $\QTR{Large}{n}$ , 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 $\QTR{Large}{00}$ ):

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

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

Try it yourself:

Exercise(Due April 11 )

The Alphabet Encoding:

The Message:

CAB

Find an appropriate $\QTR{Large}{e}$ and $\QTR{Large}{\ d\ }$ then Encode Encipher Decipher the message.

________________________________________________________________________________

El Gamal PKE:

Definitions:

Given a prime, $\QTR{Large}{p}$ , 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 $\QTR{Large}{k}$ such that

Note

Methodology:

Given a primitive root, choose a private key $\QTR{Large}{k}$ .

To allow anybody to securely transmit messages to you $\QTR{Large}{\ }$ : $\QTR{Large}{\ }$

Tell the world and, . Assume somebody wants to send the message $\QTR{Large}{a\ \ }$ to you privately, tell them to select a private key $\QTR{Large}{l\ }$ compute