MAT 112 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=2^{5\otimes }=(2^5)mod29=32mod29=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=B^{a\otimes }$ $=3^{4\otimes }=$ $(3^4)mod29$ $=81mod29=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$ $=138mod29=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=A^{b\otimes }$ $={16}^{5\otimes }$ $={16}^{4\otimes }\otimes 16$ $={\left({16}^{2\otimes }\right)}^{2\otimes }$ $={24}^{2\otimes }\otimes 16$ $=25\otimes 16=$ $400mod29=23.$
2. Bob finds the inverse $s^{-1\otimes }=24$ of $s=23$ in $({\mathbb{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=528mod29=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)modp=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

$$C:\{-,a,b,c,...z\}\to \{0,1,2,3,...26\}$$

🔗

with $C(-)=0\text{,}$ $C(a)=1\text{,}$ $\dots \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})\cdot 27+C(\mathtt{t})=1505\text{.}$

🔗

Alice chooses her secret $a=2\text{.}$ Alice computes the shared secret $s=(B^a)modp=11408\text{.}$ She computes $A=(g^a)modp=121$

🔗

Alice encrypts the message by computing $X=(m\cdot s)modp=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)modp=11408\text{.}$ Bob computes the inverse $s^{-1\otimes }=14727$ of $s$ in the group $({\mathbb{Z}}_{19777}^{\otimes },\otimes )\text{.}$

🔗

Bob decrypts the message by computing $M=(X\cdot s^{-1})modp=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.