Integers and Modern Applications for the Uninitiated

Example 16.22. ElGamal interactive.

Example 16.24. ElGamal with small numbers.

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=\gexp{g}{a}{\otimes}=\gexp{2}{4}{\otimes}\)\(=(2^4)\fmod 29\)\(=16\fmod 29=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.

Example 16.30. ElGamal with encoding and decoding.

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.