ElGamal crypto system

Section 16.3 ElGamal crypto system

The ElGamal encryption system is a public key encryption algorithm proposed by Taher Elgamal [3] in 1985. It is based on the Diffie-Hellman key exchange. We give an introduction to the El Gamal encryption system and an example in the video in Figure 16.17.

🔗

Figure 16.17. ElGamal Encryption System by Matt Farmer and Stephen Steward

🔗

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.

🔗

Bob chooses a prime \(p\) and and a generator \(g\in\Z_p^\otimes\text{.}\)
🔗

🔗
Bob chooses a random \(b\in\N\text{.}\)
🔗

🔗
Bob computes \(B=\gexp{g}{b}{\otimes}\) in \((\Z_p^\otimes,\otimes)\text{.}\)
🔗

🔗
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.

🔗

Alice gets Bob’s public key \(p\text{,}\) \(g\text{,}\) \(B\) from the key directory.
🔗

🔗
Alice chooses a random \(a\in\N\text{.}\)
🔗

🔗
Alice computes the shared secret \(s=\gexp{B}{a}{\otimes}\text{.}\)
🔗

🔗
Alice computes \(A=\gexp{g}{a}{\otimes}\text{.}\)
🔗

🔗
Alice encrypts \(m\) by computing \(X=m\otimes s\text{.}\)
🔗

🔗
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.

🔗

Bob receives \((A,X)\) from Alice.
🔗

🔗
Bob computes the shared secret \(s=\gexp{A}{b}{\otimes}\text{.}\)
🔗

🔗
Bob computes the inverse \(s^{-1\otimes}\) of \(s\) in \((\Z_p^\otimes,\otimes)\text{.}\)
🔗

🔗
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*}

🔗

Figure 16.18. ElGamal Encryption System using the group \((\Z_p^\otimes,\otimes)\) where \(\otimes:\Z_p\times\Z_p\to\Z_p\) is given by \(a\otimes b=(a\cdot b)\fmod p\text{.}\) The inverse of \(s\in\Z_p^\otimes\) with respect to \(\otimes\) is denoted by \(s^{-1\otimes}\) and \(\gexp{b}{n}{\otimes}=(b^n)\fmod p\text{.}\)

🔗

Investigate the dependencies of the steps in the ElGamal crypto system in the interactive Example 16.19.

🔗

Example 16.19. ElGamal interactive.

🔗

We work through a small example.

🔗

Example 16.20. 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.

🔗

Bob chooses the prime \(p=29\) and \(g=2\text{.}\)
🔗

🔗
Bob chooses \(b=5\) as his private key,
🔗

🔗
Bob computes \(B=\gexp{2}{5}{\otimes}=(2^5)\fmod 29=32\fmod 29=3\text{.}\)
🔗

🔗
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.

🔗

Alice obtains \(p=29\text{,}\) \(g=2\text{,}\) \(B=3\) from the public key directory.
🔗

🔗
Alice chooses her secret \(a=4\text{.}\)
🔗

🔗
Alice computes the shared secret \(s=\gexp{B}{a}{\otimes}\) \(=\gexp{3}{4}{\otimes}=\) \((3^4)\fmod 29\) \(=81\fmod 29=23\text{.}\)
🔗

🔗
Alice computes \(A=\gexp{g}{a}{\otimes}=\gexp{2}{4}{\otimes}\)\(=(2^4)\fmod 29\)\(=16\fmod 29=16\text{.}\)
🔗

🔗
Alice encrypts the message \(m=6\) as \(X=m\otimes s\) \(=6\otimes 23\) \(=138\fmod 29=22\text{.}\)
🔗

🔗
Alice sends \((A,X)=(16,22)\) to Bob.
🔗

🔗

🔗

Bob: Decryption 🔗

Bob uses \(A\) and his private key \(b\) to decrypt the message

🔗

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.\)
🔗

🔗
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.
🔗

🔗
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.
🔗

🔗

🔗

Considering only Bob’s side we get:

🔗

Problem 16.21. 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{.}\)

🔗

Considering only Alice’s side we get:

🔗

Problem 16.22. 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.

🔗

We end with an example that includes the encoding of a message.

🔗

Example 16.23. 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.

🔗

In real world applications \(p\) is chosen much larger.

🔗

Prev Top Next