# MAT 112 Integers and Modern Applications for the Uninitiated

## Section16.3ElGamal crypto system

The ElGamal encryption system is a public key encryption algorithm by Taher Elgamal [3] in 1985 that is based on the Diffie-Hellman key exchange. We give an introduction to the ElGamal Encryption System and an example in the video in Figure 16.20.
We assume that the message $$m$$ that Alice encrypts and sends to Bob is an integer. In Chapter 12 we saw how a message can be encoded into integers. We describe the three components of ElGamal encryption, namely key generation, encryption, and decryption.
Bob: Key Generation
To generate his private key and his public key Bob does the following.
1. Bob chooses a prime $$p$$ and and a generator $$g\in\Z_p^\otimes\text{.}$$
2. Bob chooses a random $$b\in\N\text{.}$$
3. Bob computes $$B=\gexp{g}{b}{\otimes}$$ in $$(\Z_p^\otimes,\otimes)\text{.}$$
4. Bob publishes his public key $$p\text{,}$$ $$g\text{,}$$ $$B$$ in the key directory.
Alice: Encryption
To encrypt a message $$m\in\Z_p^\otimes$$ Alice does the following.
1. Alice gets Bob’s public key $$p\text{,}$$ $$g\text{,}$$ $$B$$ from the key directory.
2. Alice chooses a random $$a\in\N\text{.}$$
3. Alice computes the shared secret $$s=\gexp{B}{a}{\otimes}\text{.}$$
4. Alice computes $$A=\gexp{g}{a}{\otimes}\text{.}$$
5. Alice encrypts $$m$$ by computing $$X=m\otimes s\text{.}$$
6. Alice sends $$(A,X)$$ to Bob.
Bob: Decryption
The information available to Bob to decrypt a message are his private key $$b$$ and his public key consisting of the prime $$p\text{,}$$ the generator $$g\text{,}$$ and $$B=g^b\text{.}$$ To decrypt a message $$(A,X)$$ Bob does the following.
1. Bob receives $$(A,X)$$ from Alice.
2. Bob computes the shared secret $$s=\gexp{A}{b}{\otimes}\text{.}$$
3. Bob computes the inverse $$s^{-1\otimes}$$ of $$s$$ in $$(\Z_p^\otimes,\otimes)\text{.}$$
4. Bob decrypts the message by computing $$M=X\otimes s^{-1\otimes}\text{.}$$
We now show that the message $$M$$ received by Bob is equal to Alice’s plain text message $$m\text{.}$$ We have
\begin{equation*} M=X\otimes s^{-1\otimes}=(m\otimes s)\otimes s^{-1\otimes}=m\otimes(s\otimes s^{-1\otimes})=m\otimes 1=m\text{.} \end{equation*}
Investigate the dependencies of the steps in the ElGamal crypto system in the interactive Example 16.22.

### Example16.22.ElGamal interactive.

In Checkpoint 16.23 Fill in the blanks to complete the description of key generation, encryption, and decryption following the ElGamal protocol.

### Checkpoint16.23.ElGamal protocol.

When using the ElGamal cryptosystem Bob and Alice do the following.
Bob: Key generation
To generate his public key Bob chooses a prime number $$p$$ and a generator $$g$$ in the group $$(\lbrace1,2,3,...,p-1\rbrace ,*)$$ where $$a*b = (a \cdot b) \bmod p\text{.}$$
In the dropdown menus we write $$g\hat{\;}c$$ for $$g^{c*}\text{.}$$
Bob chooses an element b in $$\lbrace 1,2,3,...,p-1\rbrace$$ and computes B :=
• select
• g*a
• g*b
• g^a
• g^b
• g^p
• A^b
• B^a
• m*s
• X*t
.
Bob publishes his public key
• select
• (a,X)
• (A,X)
• (B,X)
• (g,b,B)
• (p,g,b)
• (p,g,B)
• (p,b,B)
.
Alice: Encryption
Alice wants to send the secret message m to Bob.
Alice obtains Bob’s public key
• select
• (a,X)
• (A,X)
• (B,X)
• (g,b,B)
• (p,g,b)
• (p,g,B)
• (p,b,B)
from the public key directory.
Alices chooses a in $$\lbrace1,2,3,...,p-1\rbrace$$ and computes A :=
• select
• g*a
• g*b
• g^a
• g^b
• g^p
• A^b
• B^a
• m*s
• X*t
.
Alice computes the shared secret s :=
• select
• g*a
• g*b
• g^a
• g^b
• g^p
• A^b
• B^a
• m*s
• X*t
.
To encrypt m in $$\lbrace 1,2,3,...,p-1\rbrace$$ Alice computes X :=
• select
• g*a
• g*b
• g^a
• g^b
• g^p
• A^b
• B^a
• m*s
• X*t
Alice sends
• select
• (a,X)
• (A,X)
• (A,m)
• (B,X)
• (s,m)
• (s,X)
to Bob.
Bob: Decryption
• select
• (a,X)
• (A,X)
• (A,m)
• (B,X)
• (s,m)
• (s,X)
from Alice
Bob computes the shared secret
• select
• g*a
• g*b
• g^a
• g^b
• g^p
• A^b
• B^a
• m*s
• X*t
.
Bob computes the inverse t of s in the group $$(\lbrace 1,2,3,...,p-1\rbrace,*)\text{.}$$
Bob obtains the message m by computing
• select
• g*a
• g*b
• g^a
• g^b
• g^p
• A^b
• B^a
• m*s
• X*t
.
We work through a small example.

### Example16.24.ElGamal with small numbers.

We follow the steps above to generate a private and a public key, encrypt a message, and decrypt a message.
Bob: Key Generation
First Bob chooses the group, the generator, and his private key and computes and publishes his public key.
1. Bob chooses the prime $$p=29$$ and $$g=2\text{.}$$
2. Bob chooses $$b=5$$ as his private key,
3. Bob computes $$B=\gexp{2}{5}{\otimes}=(2^5)\fmod 29=32\fmod 29=3\text{.}$$
4. Bob publishes his public key $$p=29\text{,}$$ $$g=2\text{,}$$ $$B=3$$ in the public key directory.
Alice: Encryption
Alice wants to send the secret message $$m=6$$ to Bob.
1. Alice obtains $$p=29\text{,}$$ $$g=2\text{,}$$ $$B=3$$ from the public key directory.
2. Alice chooses her secret $$a=4\text{.}$$
3. Alice computes the shared secret $$s=\gexp{B}{a}{\otimes}$$ $$=\gexp{3}{4}{\otimes}=$$ $$(3^4)\fmod 29$$ $$=81\fmod 29=23\text{.}$$
4. Alice computes $$A=g^a=2^4=16\text{.}$$
5. Alice encrypts the message $$m=6$$ as $$X=m\otimes s$$ $$=6\otimes 23$$ $$=138\fmod 29=22\text{.}$$
6. Alice sends $$(A,X)=(16,22)$$ to Bob.
Bob: Decryption
Bob uses $$A$$ and his private key $$b$$ to decrypt the message
1. Bob computes the shared secret
$$s=\gexp{A}{b}{\otimes}$$ $$=\gexp{16}{5}{\otimes}$$ $$=\gexp{16}{4}{\otimes}\otimes 16$$ $$=\gexp{\left(\gexp{16}{2}{\otimes}\right)}{2}{\otimes}$$ $$= \gexp{24}{2}{\otimes}\otimes 16$$ $$=25\otimes 16=$$ $$400\fmod 29=23.$$
2. Bob finds the inverse $$s^{-1\otimes}=24$$ of $$s=23$$ in $$(\Z_{29}^\otimes,\otimes)\text{.}$$ This can be done with the Euclidean algorithm and Bézout’s identity.
3. Bob decrypts the message by computing $$X\otimes s^{-1\otimes}=22\otimes 24=528\fmod 29=6\text{,}$$ which is Alice’s original message.
In Checkpoint 16.25 work through the steps of key generation, encryption, and decryption yourself.

### Checkpoint16.25.ElGamal with small numbers.

Alice and Bob use the ElGamal cryptosystem for their secure communication.
Bob: Key Generation
Bob chooses the prime $$p=11\text{.}$$ So he will work in the group $$(\mathbb{Z}_{11}^{\otimes},\otimes)$$ where $$a\otimes b = (a\cdot b)\bmod 11\text{.}$$ He chooses $$g=2 \in\mathbb{Z}_{11}^\otimes\text{.}$$
Bob chooses his secret key $$b=7$$ and computes $$B=(g^b)\bmod p=$$.
Bob publishes $$p\text{,}$$ $$g\text{,}$$ and $$B$$ in the public key directory.
Directory of Public Keys
Aaron: $$p=53\text{,}$$ $$g=33\text{,}$$ $$B=29$$
Alice: $$p=23\text{,}$$ $$g=2\text{,}$$ $$B=16$$
Bob: $$p=$$, $$g=$$, $$B=$$
Sebastian: $$p=23\text{,}$$ $$g=2\text{,}$$ $$B=4$$
Victoria: $$p=43\text{,}$$ $$g=39\text{,}$$ $$B=4$$
Alice: Encryption
Alice wants to send the message $$m=4$$ to Bob.
Alice gets Bob’s public key from the directory: $$p=$$, $$g=$$, $$B=$$
Alice chooses her secret $$a=2\text{.}$$
Alice computes the shared secret $$s = (B^a)\bmod p=$$.
She computes $$A=(g^a)\bmod p=$$.
Alice encrypts the message by computing $$X=(m\cdot s)\bmod p=$$.
Alice sends $$A$$ and $$X$$ to Bob.
Bob: Decryption
Bob receives $$A$$ and $$X$$ from Alice.
Bob computes the shared secret $$s =(A^b)\bmod p=$$ .
Bob finds the inverse $$s^{-1\otimes}=$$ of $$s$$ in the group $$(\mathbb{Z}^\otimes_{11},\otimes)\text{.}$$
Bob decrypts the message by computing $$M=(X\cdot s^{-1})\bmod p=$$ .
Hint:
In $$(\mathbb{Z}_{11}^{\otimes},\otimes)$$ we have
$$1^{-1\otimes}=1\text{,}$$
$$2^{-1\otimes}=6\text{,}$$
$$3^{-1\otimes}=4\text{,}$$
$$4^{-1\otimes}=3\text{,}$$
$$5^{-1\otimes}=9\text{,}$$
$$6^{-1\otimes}=2\text{,}$$
$$7^{-1\otimes}=8\text{,}$$
$$8^{-1\otimes}=7\text{,}$$
$$9^{-1\otimes}=5\text{,}$$
$$10^{-1\otimes}=10\text{,}$$
Considering only Bob’s side we get:

### Problem16.26.ElGamal decryption.

Bob has published his public key $$p=13\text{,}$$ $$g=7\text{,}$$ $$B=10\text{.}$$ His private key is $$b=2\text{.}$$ Alice sends his the encrypted message $$(3,8)\text{.}$$ What is the plain text of the message ?
Solution.
From Alice’s message Bob gets $$A=3$$ and $$X=8\text{.}$$ So the shared secret is $$s=A^b=3^2=9\text{.}$$ The inverse of $$s=9$$ is $$s^{-1\otimes}=3\text{,}$$ since $$9\otimes 3=27\fmod 13=1\text{.}$$ Bob decrypts the message by computing $$X\otimes s^{-1}=8\otimes 3=24\fmod 13=11\text{.}$$

### Checkpoint16.27.ElGamal: Bob’s perspective.

Alice and Bob use the ElGamal cryptosystem for their secure communication.
Bob: Key Generation
Bob chooses the prime $$p=19813$$ and the generator $$g=2 \in\mathbb{Z}_{19813}^\otimes\text{.}$$
Bob chooses his secret key $$b=2 \in\mathbb{Z}_{19813}^\otimes$$ and computes $$B=(g^b)\bmod 19813=$$.
Bob publishes $$p\text{,}$$ $$g\text{,}$$ and $$B$$ in the public key directory.
Directory of Public Keys Aaron: $$p=19861\text{,}$$ $$g=2163\text{,}$$ $$B=4818$$
Beth: $$p=19861\text{,}$$ $$g=3530\text{,}$$ $$B=17045$$
Bob: $$p=$$, $$g=$$, $$B=$$
Sebastian: $$p=19861\text{,}$$ $$g=2163\text{,}$$ $$B=12868$$
Victoria: $$p=19867\text{,}$$ $$g=128\text{,}$$ $$B=4040$$
Bob: Decryption
Bob receives $$A=8$$ and $$X=19077$$ from Alice.
Bob computes the shared secret $$s =(A^b)\bmod 19813=$$ .
Bob computes the inverse $$s^{-1}=5882$$ of $$s$$ in the group $$(\mathbb{Z}^\otimes_{19813},\otimes)\text{.}$$
Bob decrypts the message by computing $$M=(X\cdot s^{-1})\bmod 19813=$$ .
Bob finds the expanded base $$27$$ form of $$M\text{,}$$ namely $$M=$$$$\cdot 27^2+$$$$\cdot 27+$$.
Decoding these numbers with $$C^{-1}$$ yields the message .
Considering only Alice’s side we get:

### Problem16.28.ElGamal encryption.

Alice and Bob use the ElGamal crypto system for their secure communication. From the key directory Alice obtains Bob’s public key is $$p=5\text{,}$$ $$g=2\text{,}$$ $$B=4\text{.}$$ Alice chooses her secret $$a=2\text{.}$$ Alice encrypts the message $$m=4\text{.}$$ What does she send to Bob ?
Solution.
Alice computes:
\begin{align*} A \amp = (g^a) \fmod 5 = 22 \fmod 5 = 4 \fmod 5 = 4\\ s \amp = (B^a) \fmod 5 = 42 \fmod 5 = 16 \fmod 5 = 1\\ X \amp = (m\cdot s) \fmod p = (4\cdot 1) \fmod 5 = 4 \end{align*}
Thus Alice sends $$(A,X)=(4,4)$$ to Bob.

### Checkpoint16.29.ElGamal: Alice’s perspective.

Alice and Bob use the ElGamal cryptosystem for their secure communication. Alice sends an encrypted message to Bob.
Directory of Public Keys
Bob: $$p=19813\text{,}$$ $$g=2\text{,}$$ $$B=4$$
Nathan: $$p=19861\text{,}$$ $$g=3530\text{,}$$ $$B=17045$$
Thom: $$p=19861\text{,}$$ $$g=2163\text{,}$$ $$B=12868$$
Alice: Encryption
Alice wants to send the message ’$$\mathtt{mom}$$’ to Bob.
Alice gets Bob’s public key from the directory: $$p=$$, $$g=$$, $$B=$$
She applies the encoding function $$C:\lbrace \mathtt{-},\mathtt{a},\mathtt{b},\mathtt{c},...\mathtt{z} \rbrace \to \lbrace 0,1,2,3,...26\rbrace$$ with $$C(\mathtt{-}) = 0\text{,}$$ $$C(\mathtt{a}) = 1\text{,}$$ $$\dots\text{,}$$ $$C(\mathtt{z}) = 26$$ to the characters in message. She obtains $$C(\mathtt{m})=$$, $$C(\mathtt{o})=$$, and $$C(\mathtt{m})=$$.
She encodes this into one number by computing $$m=C(\mathtt{m})\cdot 27^2+C(\mathtt{o})\cdot27+C(\mathtt{m})=$$.
Alice chooses her secret $$a=2\text{.}$$
Alice computes the shared secret $$s = (B^a)\bmod p=$$.
She computes $$A=(g^a)\bmod p=$$.
Alice encrypts the message by computing $$X=(m\cdot s)\bmod p=$$.
Alice sends $$A$$ and $$X$$ to Bob.
We end with an example that includes the encoding of a message.

### Example16.30.ElGamal with encoding and decoding.

Alice and Bob use the ElGamal crypto system for their secure communication. In the following we present all steps involved in Alice sending an encrypted message to Bob. For encoding text into numbers we apply the method from Chapter 12.
Bob: Key Generation
Bob chooses the prime $$p=19777$$ and the generator $$g=11 \in\mathbb{Z}_{19777}^\otimes\text{.}$$ Bob chooses his secret key $$b=3$$ and computes $$B=(g^b)\bmod p=1331\text{.}$$ Bob publishes $$p\text{,}$$ $$g\text{,}$$ and $$B$$ in the public key directory.
Directory of Public Keys
 Aaron: $$p=19841$$ $$g=243$$ $$B=4821$$ Beth: $$p=19867$$ $$g=128$$ $$B=15522$$ Bob: $$p=19777$$ $$g=11$$ $$B=1331$$ Sebastian: $$p=19891$$ $$g=32$$ $$B=7297$$ Victoria: $$p=19913$$ $$g=2187$$ $$B=5531$$
Alice: Encoding and Encryption
Alice wants to send the message $$\mathtt{bat}$$ to Bob. Alice gets Bob’s public key from the directory: $$p=19777\text{,}$$ $$g=11\text{,}$$ $$B=1331\text{.}$$ She applies the encoding function
\begin{equation*} C:\lbrace -,a,b,c,...z \rbrace \to \lbrace 0,1,2,3,...26\rbrace \end{equation*}
with $$C(-) = 0\text{,}$$ $$C(a) = 1\text{,}$$ $$\ldots\text{,}$$ $$C(z) = 26$$ to the characters in the message. She obtains $$C(\mathtt{b})=2\text{,}$$ $$C(\mathtt{a})=1\text{,}$$ and $$C(\mathtt{t})=20\text{.}$$ She encodes this into one number by computing $$m=C(\mathtt{b})\cdot 27^2+C(\mathtt{a})\cdot27+C(\mathtt{t})=1505\text{.}$$
Alice chooses her secret $$a=2\text{.}$$ Alice computes the shared secret $$s = (B^a)\bmod p=11408\text{.}$$ She computes $$A=(g^a)\bmod p=121$$
Alice encrypts the message by computing $$X=(m\cdot s)\bmod p=2604\text{.}$$ Alice sends $$A$$ and $$X$$ to Bob.
Bob: Decryption and Decoding
Bob receives $$A$$ and $$X$$ from Alice.
Bob computes the shared secret $$s =(A^b)\bmod p=11408\text{.}$$ Bob computes the inverse $$s^{-1\otimes}=14727$$ of $$s$$ in the group $$(\mathbb{Z}^\otimes_{19777},\otimes)\text{.}$$
Bob decrypts the message by computing $$M=(X\cdot s^{-1})\bmod p=1505\text{.}$$
Bob finds the expanded base $$27$$ form of $$M\text{,}$$ namely $$M=2\cdot 27^2+1\cdot 27+20\text{.}$$ Decoding these numbers with $$C^{-1}$$ yields the message bat.

### Checkpoint16.31.ElGamal with encoding and decoding.

Alice and Bob use the El Gamal crypto system for their secure communication.
Bob: Key Generation
Bob chooses the prime $$p=19853$$ and the generator $$g=2 \in\mathbb{Z}_{19853}^\otimes\text{.}$$
Bob chooses his secret key $$b=2$$ and computes $$B=(g^b)\bmod p=$$.
Bob publishes $$p\text{,}$$ $$g\text{,}$$ and $$B$$ in the public key directory.
Directory of Public Keys Aaron: $$p=19843\text{,}$$ $$g=15567\text{,}$$ $$B=14339$$
Beth: $$p=19853\text{,}$$ $$g=128\text{,}$$ $$B=6782$$
Bob: $$p=$$, $$g=$$, $$B=$$
Sebastian: $$p=19861\text{,}$$ $$g=2163\text{,}$$ $$B=12868$$
Victoria: $$p=19913\text{,}$$ $$g=2187\text{,}$$ $$B=11065$$
Alice: Encryption
Alice wants to send the message ’$$\mathtt{hit}$$’ to Bob.
Alice gets Bob’s public key from the directory: $$p=$$, $$g=$$, $$B=$$
She applies the encoding function $$C:\lbrace \mathtt{-},\mathtt{a},\mathtt{b},\mathtt{c},...\mathtt{z} \rbrace \to \lbrace 0,1,2,3,...26\rbrace$$ with $$C(\mathtt{-}) = 0\text{,}$$ $$C(\mathtt{a}) = 1\text{,}$$ $$\dots\text{,}$$ $$C(\mathtt{z}) = 26$$ to the characters in message. She obtains $$C(\mathtt{h})=$$, $$C(\mathtt{i})=$$, and $$C(\mathtt{t})=$$.
She encodes this into one number by computing $$m=C(\mathtt{h})\cdot 27^2+C(\mathtt{i})\cdot27+C(\mathtt{t})=$$.
Alice chooses her secret $$a=3\text{.}$$
Alice computes the shared secret $$s = (B^a)\bmod p=$$.
She computes $$A=(g^a)\bmod p=$$.
Alice encrypts the message by computing $$X=(m\cdot s)\bmod p=$$.
Alice sends $$A$$ and $$X$$ to Bob.
Bob: Decryption
Bob receives $$A$$ and $$X$$ from Alice.
Bob computes the shared secret $$s =(A^b)\bmod p=$$ .
Bob computes the inverse $$s^{-1}=18302$$ of $$s$$ in the group $$(\mathbb{Z}^\otimes_{19853},\otimes)\text{.}$$
Bob decrypts the message by computing $$M=(X\cdot s^{-1})\bmod p=$$ .
Bob finds the expanded base $$27$$ form of $$M\text{,}$$ namely $$M=$$$$\cdot 27^2+$$$$\cdot 27+$$.
Decoding these numbers with $$C^{-1}$$ yields the message .
In real world applications $$p$$ is chosen much larger.