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.
We say that two integers a and b are congruent modulo a positive integer n, written a ≡ b (mod n), if we can find some other integer q such that a = q × n + b.
For example, since 25 = 3 × 7 + 4, we have 25 ≡ 4 (mod 7). Also, 40 = 5 × 7 + 5, and so 40 ≡ 5 (mod 7).
Note that 25 + 40 = 65 = 9 × 7 + 2, and so 25 + 40 ≡ 2 (mod 7). But 4 + 5 = 9 ≡ 2 (mod 7), since 9 = 1 × 7 + 2. This works in general -- if we want to find the sum of any two numbers modulo n, then we can make things easier by finding the sum of two smaller numbers they are congruent to modulo n.
This also works for multiplication. For example, 25 × 40 = 1000 = 142 × 7 + 6, and so 25 × 40 ≡ 6 (mod 7). But 4 × 5 = 20 = 2 × 7 + 6, and so 4 × 5 ≡ 6 (mod 7), the same thing!
Now suppose we're working modulo a prime number p. A prime number is a number whose only factors are 1 and itself. For example, 7 is prime, but 9 is not, since 3 is a factor of 9.
Observe that:
1 × 1 ≡ 1 (mod 7)
2 × 4 = 8 ≡ 1 (mod 7)
3 × 5 = 15 ≡ 1 (mod 7)
6 × 6 = 36 ≡ 1 (mod 7)
This always works. That is, for every number between 1 and p - 1, we can find some other number, called its inverse, so that if we multiply them together, the result is congruent to 1 modulo p.
This allows us do some algebra modulo p. For example,
2x + 3 ≡ 6 (mod 7)
2x ≡ 3 (mod 7) (subtracting 3 from both sides)
x ≡ 12 ≡ 5 (mod 7) (multiplying both sides by 4, which is the inverse of 2)
Suppose Alice wants to send Bob a message. They've agreed on a prime number p and a pair of numbers k1 and k2 between 1 and p - 1, which will serve as their key.
Alice takes the message (which is some number m between 1 and p - 1), and computes k1m + k2. She sends the result to Bob, who then solves for m as in the example above. This is known as an affine cipher.
Like the XOR cipher, affine ciphers are vulnerable to known plaintext attacks. If Alice and Bob's enemy Eve intercepts two plaintext/ciphertext pairs, then she can solve for k1 and k2, which she can then use to decrypt any further messages.
To find this geocache below, decrypt the coordinates below. The degrees are correct, but the minutes have been encrypted using an affine cipher with p = 60,013 (ignoring the decimal point). Furthermore, you are given that the plaintext 10,240 is encrypted as the ciphertext 38,560 and that the plaintext 37,923 is encrypted as the ciphertext 38,263.
N 34° 04.037' W 083° 55.047'
Congratulations to Lizzybeth13 and KalahariFox for FTF!