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 $p$ and a generator $a$ of $(\mathbb{Z}/p\mathbb{Z})^\times$ , $2\leq a\leq p-2$ . Publish them.

• Anne picks a random secret $k$ , $2\leq k\leq p-2$ and publishes $a^k ({\rm mod} p)$ .

• Anne's public key is $(p,a,a^k ({\rm mod} p))$ . Anne's private key is $k$ .

ElGamal encryption

Ben sends message $m$ to Anne as follows:

• Ben obtains Anne's public key $(p,a,a^k ({\rm mod} p))$ .

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

• Ben selects a random integer $\ell$ , $1\leq \ell\leq p-2$ .

• Ben computes $d\equiv a^\ell ({\rm mod} p))$ and $e\equiv m\cdot (a^k)^\ell ({\rm mod} p))$ , $1\leq d,e\leq p-1$ .

• Ben sends the ``ciphertext'' $c=(d,e)$ to Anne.

Anne decrypts $m$ as follows:

• Anne uses her private key to compute $d^{p-1-k} ({\rm mod} p))$ and $d^{p-1-k}\equiv (a^{-k\ell} ({\rm mod} p))$ .

• Anne computes $m\equiv (d^{p-1-k})\cdot e ({\rm mod} p))$ .

Example 1.8.15   Using the numerical position in the alphabet, ``A'' is the $1^{st}$ letter, which corresponds numerically to $01$ , ``B'' to $02$ , ..., ``Z'' to $26$ . A word corresponds to the associated string of numbers. Note, for example, ``ab'' is $0102=102$ but ``ob'' is $1502$ .

Pick $p=150001$ , $a=7$ . Pick $k=113$ , so that $a^k=7^{113}\equiv 66436 ({\rm mod} p)$ . Anne's public key is $(150001,7,66436)$ . Anne's private key is $113$ . Suppose Ben is Anne's son and wants to send the message ``Hi Mom''. He converts this to $m=080913=809$ and $m=131513$ . Ben picks $\ell = 1000$ and computes $7^\ell \equiv 90429 ({\rm mod} 150001))$ , so $d=90429$ . The encryption is $809\cdot (7^{113})^{1000}\equiv 15061=e ({\rm mod} 150001))$ and $131513\cdot (7^{113})^{1000}\equiv 57422=e ({\rm mod} 150001))$ , so $c=(90429,15061)$ and $c=(90429,57422)$ are sent to Anne.

Anne computes $d^{p-1-k}=90427^{149887}\equiv 80802 ({\rm mod} 150001))$ . Then $m\equiv 80802\cdot e ({\rm mod} 150001))$ returns the original messages $m=809$ and $m=131513$ . Since $809$ has an odd number of digits, the first digit must have been a 0 . Anne can see that $809$ must mean that the first letter comes from the $8=08$ , the second letter comes from a $09$ . These spell out ``hi''. For $m=131513$ , the third letter must come from the $13$ , the fourth letter must come from the $15$ , and the last must be a $13$ . 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 $p=541$ , $a=2$ . Pick $k=113$ , $\ell = 101$ . Encrypt the messages $m=200$ and $m=201$ using ElGamal.

(a) Let $p=541$ , $a=2$ , $k = 101$ . Decrypt the ElGamal ciphers $c=(54,300)$ and $c=(54,301)$ .

Exercise 1.8.17   Let $p=541$ , $a=2$ . Amelia chooses $x=17$ and sends $a^x=2^{17} ({\rm mod} 541)$ to Ben. Ben picks $y=71$ and sends $a^y=2^{71} ({\rm mod} 541)$ to Amelia. Compute the secret shared (Diffie-Hellman) key.

Exercise 1.8.18   Show that there is no $k$ satisfying $2^k\equiv 1 ({\rm mod} 10)$ . Why doesn't this contradict Definition 1.8.1?

Exercise 1.8.19   Find

(a) the order of $2$ mod $3$ ,

(b) the order of $2$ mod $5$ ,

(c) the order of $7$ mod $10$ ,

(d) the order of $49$ mod $10$ .

Exercise 1.8.20   Verify $a^{\phi(n)}\equiv 1 ({\rm mod} n)$ when $a=3$ and $n=100$ .

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

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

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:

$$x = 5000/4999,$$

$$y = 1000000000000/998999999001,$$

$$z = 1 0000 9999 0001 00000000000/9999 9997 0000 0002 9999 9999.$$

Exercise 1.8.24   Given $p,q,e$ as in Example 1.8.12, decrypt $c=20$ .