# Broad River Cryptography #8: ElGamal Cryptosystem Mystery Cache

- Difficulty:

- Terrain:

Size: (small)

#### Watch

How Geocaching Works

**Please note**Use of geocaching.com services is subject to the terms and conditions in our disclaimer.

## Geocache Description:

The purposes of this geoart series are twofold: to bring cachers to the watershed of the North Fork of the Broad River in Stephens and Franklin Counties and to serve as an introduction to the fascinating field of cryptography.

Taher Elgamal, an Egyptian cryptographer who received his PhD in electrical engineering from Stanford in 1984, published a paper outlining a new cryptosystem a year later. Similar to the Diffie-Hellman key exchange (see Broad River Cryptography #7: Diffie-Hellman), its security relies on the difficulty of solving the discrete logarithm problem.

Alice and Bob both decide on a prime number *p* and a primitive root *g*. Alice chooses a private key *a*, which she shares with no one, and then computes her public key *A* ≡ *g ^{a}* (mod

*p*), which she shares with everyone.

Bob wants to send Alice a message encoded as a number *m*. He picks an *ephemeral key* *k* and computes two numbers: *c*_{1} ≡ *g ^{k}* (mod

*p*) and

*c*

_{2}≡

*mA*(mod

^{k}*p*). He then sends Alice the ciphertext (

*c*

_{1},

*c*

_{2}).

Alice then computes (*c*_{1}^{a})^{-1}*c*_{2} (recall that numbers have inverses modulo a prime -- see Broad River Cryptography #6: Affine Cipher). It turns out that this gives her *m*.

Indeed, even though Alice doesn't know *k* and Bob doesn't know *a*, it works out that

(*c*_{1}^{a})^{-1}*c*_{2} ≡ ((*g ^{k}*)

^{a})

^{-1}

*m*(

*A*) (mod

^{k}*p*)

≡ (

*g*)

^{ak}^{-1}

*m*(

*g*)

^{a}^{k}(mod

*p*)

≡ (

*g*)

^{ak}^{-1}

*m*(

*g*) (mod

^{ak}*p*)

≡

*m*(mod

*p*)

Their enemy Eve can only break the encryption if she can compute *a*, which is the discrete logarithm of *A*.

The coordinates to this geocache have been encrypted using the ElGamal cryptosystem. The degrees are the same as the posted coordinates, but the minutes (ignoring the decimal points) have been encrypted using prime *p* = 60,013 and primitive root *g* = 6. Alice's public key is *A* = 20,263.

Nate sends Alice the minutes for the latitude using the ciphertext (50,950, 26,374).

Wanda sends Alice the minutes for the longitude using the ciphertext (29,283, 15,981).

Congratulations to Lizzybeth13 and KalahariFox for FTF!

**
Additional Hints**
(Decrypt)

Decryption Key

A|B|C|D|E|F|G|H|I|J|K|L|M

-------------------------

N|O|P|Q|R|S|T|U|V|W|X|Y|Z