## Application: ElGamal encryption

ElGamal is another public key encryption idea. It is different from the RSA encryption scheme in that its security depends on the difficulty depends on the difficulty of the discrete log problem, as opposed to the factoring problem.

Anne's key

• Pick a large'' prime number and a generator of , . Publish them.

• Anne picks a random secret , and publishes .

• Anne's public key is . Anne's private key is .

ElGamal encryption

Ben sends message to Anne as follows:

• Ben obtains Anne's public key .

• Ben represents the message as an integer (by choosing sufficiently large, this is always possible; alternatively, the message may be broken up into smaller pieces, each piece belonging to the range ).

• Ben selects a random integer , .

• Ben computes and , .

• Ben sends the ciphertext'' to Anne.

Anne decrypts as follows:

• Anne uses her private key to compute and .

• Anne computes .

Example 1.8.15   Using the numerical position in the alphabet, A'' is the letter, which corresponds numerically to , B'' to , ..., Z'' to . A word corresponds to the associated string of numbers. Note, for example, ab'' is but ob'' is .

Pick , . Pick , so that . Anne's public key is . Anne's private key is . Suppose Ben is Anne's son and wants to send the message Hi Mom''. He converts this to and . Ben picks and computes , so . The encryption is and , so and are sent to Anne.

Anne computes . Then returns the original messages and . Since has an odd number of digits, the first digit must have been a 0 . Anne can see that must mean that the first letter comes from the , the second letter comes from a . These spell out hi''. For , the third letter must come from the , the fourth letter must come from the , and the last must be a . These spell out hi'' and mom''. Adding a space and proper capitalization, this is Hi Mom''!

More details are given in [MOV], §8.4.

Exercise 1.8.16 (a)   Let , . Pick , . Encrypt the messages and using ElGamal.

(a) Let , , . Decrypt the ElGamal ciphers and .

Exercise 1.8.17   Let , . Amelia chooses and sends to Ben. Ben picks and sends to Amelia. Compute the secret shared (Diffie-Hellman) key.

Exercise 1.8.18   Show that there is no satisfying . Why doesn't this contradict Definition 1.8.1?

Exercise 1.8.19   Find

(a) the order of mod ,

(b) the order of mod ,

(c) the order of mod ,

(d) the order of mod .

Exercise 1.8.20   Verify when and .

Exercise 1.8.21   Is a primitive root mod ? Find the discrete log, if it exists, of to the base , mod .(Ans: yes, )

Exercise 1.8.22   Is a primitive root mod ? Find the discrete log, if it exists, of to the base , mod . (Ans: yes, )

Exercise 1.8.23   Examine the first 100 digits in the decimal expansions of the following fractions, looking for any patterns. Try to predict the periods, then deduce them using the ideas from this section:

Exercise 1.8.24   Given as in Example 1.8.12, decrypt .

david joyner 2008-04-20