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.
Suppose p is a prime number. A common question in number theory is that for a given nonzero integer a, does there exist some x such that x2 ≡ c (mod p)? If so, then a is known as a quadratic residue modulo p.
For example, for p = 7, we have
12 ≡ 1 (mod 7)
22 ≡ 4 (mod 7)
32 ≡ 2 (mod 7)
42 ≡ 2 (mod 7)
52 ≡ 4 (mod 7)
62 ≡ 1 (mod 7)
So 1, 2, and 4 are the quadratic residues modulo 7.
One way of keeping tracking of whether a given number is a quadratic residue modulo p or not is by looking at its Legendre symbol, (a|p). If a is a quadratic residue modulo p, then (a|p) = 1. If it's not, then (a|p) = -1. (We also define (a|p) = 0 if a ≡ 0 (mod p).)
So for example:
(0|7) = 0
(1|7) = 1
(2|7) = 1
(3|7) = -1
(4|7) = 1
(5|7) = -1
(6|7) = -1
Legendre symbols have a few nice properties. They're multiplicative, so (a × b|p) = (a|p) × (b|p). And also, we can "flip" them using the Law of Quadratic Reciprocity. That is, if p and q are both odd primes, then
(p|q) = (-1)(p-1)/2 × (q-1)/2 × (q|p).
For example, let's say we want to determine whether 143 is a quadratic residue modulo 151, or equivalently, we want to find the value of the Legendre symbol (143|151). Since 143 = 11 × 13, we know that (143|151) = (11|151) × (13|151).
Let's tackle each term individually. By the Law of Quadratic Reciprocity, we know that
(11|151) = (-1)(11-1)/2 × (151-1)/2 × (151|11) = (-1)375 × (151|11) = -(151|11).
Now 151 ≡ 8 (mod 11), so (151|11) = (8|11). At this point, it's easy enough to just compute all the squares modulo 11. None of the numbers between 1 and 10 have squares congruent to 8 modulo 11, so (8|11) = -1. It follows that (11|151) = -(-1) = 1.
Playing the same game, we get (13|151) = -1, and so (143|151) = 1 × (-1) = -1. In other words, 143 is not a quadratic residue modulo 151.
One problem with some public key encryption schemes is that they are vulnerable to a chosen plaintext attack. If Eve has Alice's public key, then she knows how to encrypt messages to her. So she can just encrypt a bunch of plaintext messages to see what ciphertexts she gets. With this information, she might be able to break the encryption.
One way to get around this is to use a probabilistic encryption, where there is some random process which is part of the encryption. So encrypting the same plaintext message will produce a different ciphertext every time it is encrypted.
One example of a probabilistic encryption scheme is ElGamal. However, the first probabilistic encryption scheme was developed by Shafi Goldwasser and Silvio Micali in 1982. Thirty years later, the pair won the Turing Award for their many contributions to the field of cryptography.
The Goldwasser-Micali cryptosystem is based on the quadratic residue problem as described above. Bob chooses two odd prime numbers p and q, computes their product N = p × q, and finds some number a with (a|p) = (a|q) = -1. His public key is (N, a).
Suppose Alice wants to send Bob a message. She encodes her message in binary (see Broad River Cryptography #5: XOR Cipher for a review of binary), and then encrypts each bit separately. For each bit m, she picks a random number r and then computes c ≡ r2 (mod N) if m = 0, or c ≡ ar2 (mod N) if m = 1. Note that in the first case, c is a quadratic residue modulo N, and in the second case, it isn't.
In practice, it is difficult to compute Legendre symbols if N is large. But it turns out that instead of computing (c|N), Bob can instead compute (c|p) or (c|q) and get the same result, which will be much easier. Their enemy Eve can't do this unless she can factor N.
The coordinates to this geocache have been encrypted using the Goldwasser-Micali cryptosystem. The degrees are the same as the posted coordinates, but the minutes (ignoring the decimal points) have been encoded in binary, and then each bit encrypted using Bob's public key, which is (88013, 17).
Nate sends Bob the minutes for the latitude using the ciphertexts (14678, 66093, 26582, 86479, 11367, 84099, 31086, 50509, 76552, 45800, 55230, 31092, 87277, 50098, 33988).
Wanda sends Bob the minutes for the longitude using the ciphertexts (65838, 33557, 8740, 41694, 4762, 77999, 23487, 37575, 46923, 47992, 54374, 75264, 24795, 61161, 25451).
Congratulations to PackADad for FTF!