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.
See Broad River Cryptography #6: Affine Cipher for a review of modular arithmetic.
Note that:
30 ≡ 1 (mod 7)
31 ≡ 3 (mod 7)
32 ≡ 2 (mod 7)
33 ≡ 6 (mod 7)
34 ≡ 4 (mod 7)
35 ≡ 5 (mod 7)
Every number between 1 and 6 appears as a power of 3 modulo 7. We say that 3 is a primitive root modulo 7. It is a fact that for every prime number p, there exists at least one primitive root g modulo p, i.e., every number between 1 and p - 1 may be written as a power of g modulo p.
Given a prime number p, a primitive root g, and some number h between 1 and p - 1, we might wonder which power x gives us
gx ≡ h (mod p)
We say that x is the discrete logarithm of h, written logg h = x. For example, modulo 7:
log3 1 = 0
log3 2 = 2
log3 3 = 1
log3 4 = 4
log3 5 = 5
log3 6 = 3
It turns out that discrete logarithms are much more difficult to compute than powers. This is great for cryptography!
Suppose Alice and Bob would like to share a key they can later use to encrypt and decrypt messages. They agree on some prime number p and primitive root g. Alice picks a secret integer a and Bob picks a secret integer b. They don't share this information with anyone. What they do share are their public keys. Alice's public key is A ≡ ga (mod p) and Bob's public key is B ≡ gb (mod p).
Alice then computes Ba (mod p) and Bob computes Ab (mod p). This ends up being the same number! Indeed,
Ba ≡ (gb)a ≡ gab ≡ (ga)b ≡ Ab (mod p)
This ends up being their shared key. Their enemy Eve can't recover the shared key unless she can compute one of the discrete logarithms a = logg A or b = logg B.
In 1976, Whitfield Diffie and Martin Hellman published a paper outlining this process, and so it is known as the Diffie-Hellman Key Exchange
However, it was later learned that it was discovered 7 years earlier by a team working for the British government, but this was classified until 1997.
The coordinates to this geocache have been encrypted using the Diffie-Hellman key exchange. The degrees are the same as the posted coordinates, but the minutes (ignoring the decimal points) are the shared keys of two pairs of geocachers. Both pairs have picked the prime p = 60,013 and primitive root g = 6.
The minutes for the latitude correspond to the shared key belonging to Nora and Nate. Nora's public key is 37,875 and Nate's public key is 18,416.
The minutes for the longitude correspond to the shared key belonging to Wanda and Wally. Wanda's public key is 10,404 and Wally's public key is 44,995.
Congratulations to Lizzybeth13 and KalahariFox for FTF!