# Bogglers

By Scott Kim|Saturday, September 1, 2001

H'ud Fns z Rdbqds

Human history has witnessed both a gradual decay of personal privacy and escalating attempts to keep some matters from prying eyes. Here are three methods of encryption that demonstrate how, over the centuries, we've become better at keeping secrets

[Easy] Julius Caesar is said to have invented one of the first ciphers by replacing each letter of a message with the letter three places later in the alphabet. Such schemes are still called Caesar alphabets. The title of this puzzle has been encoded in each of the seven ciphers below. Can you determine the encryption scheme used for each?

1. BMM DPEFT MFBE UP SPNF
2. ZOO XLWVH OVZW GL ILNV
3. AEL ALDCT OODR EO SMLE
4. ACE ETOLO SAOM LD LDRE
5. HPR URWGD HOVH GR FOOD
6. AMN FSIKZ TNKO FB FDCV
7. BNZ CRVAT FKLP JY QFSX

A Riddle Wrapped in a Mystery

[Harder] The famous German World War II-era Enigma machine used multiple rotors to produce enormously complicated codes that could be decoded only by someone who had the correct machine settings— the key. In this puzzle, the key shown above can be used to reveal five letters that have been encoded in the 5x5 grids below. As shown below, image 1 is a capital A. Can you figure out how to use the key to decipher the other four letters? The five decoded letters can be rearranged to spell a word. What is it? And if you compare three of the decrypted letters using the same method you employed above, you'll create the bonus image shown below. Which three letters were used? (Both answers are related to the word key.)

Public Displays of Encryption

[Hardest] Today more sophisticated encoding techniques eliminate the need to send a key with each message. Ron Rivest, Adi Shamir, and Leonard Adleman invented the first practical public-key scheme, known as the RSA algorithm, now used in Web transactions. Decoding a public-key encrypted message requires a public key and a separate private key. Public-key schemes work because it's tough to factor large numbers, particularly the products of large primes. Try factoring these small numbers to see how hard it is: 57, 551, 5,063, and 52,961.

Here's how the RSA scheme works. The first few powers of 3 are 3, 9, 27, 81, 243, 729, 2,187, and 6,561. If you divide each by a number, say, 7, the remainders form a cycle (3, 2, 6, 4, 5, 1, 3, 2) that repeats after six terms as shown in this diagram.

Raising a number m to successive powers and dividing by a prime p yields a pattern of remainders that cycles after p-1 terms. (The cycle may be shorter, but any shorter cycle will divide evenly into p-1.) So, mp divided by p yields a remainder of m. If instead of the prime p we use the product of two primes p and q, then the pattern cycles after (p-1)(q-1) terms, which means that m(p - 1)(q - 1)+1 divided by pq yields a whole number plus a remainder m. Draw the diagram obtained by raising 3 to successive powers and dividing by 35. How long is the cycle?

To encrypt a message using the RSA algorithm, choose two large primes, p and q. Let n be the product pq and f the product (p)(q-1). Convert your message to a number m between 1 and n (use substitution, such as A=1, B=2, C=3). Choose any number e (the encrypting number) that doesn't share any common factors with (p - 1)(q - 1). These two numbers, n and e (a random number) form the public key.

Computers are not now powerful enough to factor a number as huge as n, so the message can't be "read" using only this public key. With e and a private key (d) provided by the same people who provided the public key, you can get to m without having to factor n.

To encipher your message, raise your coded message m to the randomly selected power e, and divide by n. The remainder c is your coded message. The private key is another number d (the decrypting number). To decipher the enciphered message c, raise it to the power d, and divide by n. This operation takes you back around the cycle and returns the original message number m. In other words, cd divided by n has remainder m, which means that (me)d = med divided by n also has remainder m.

Suppose I send you a series of messages— c = 24, c = 15, c = 5, c = 9, c = 25— each encoded with this public key (n = 55, e = 27). You now have everything you need to solve it, except for the private key (d). Can you break this immensely simplified version of a public-key encryption? First, figure out the private key decryption exponent d and use it to deduce the original message numbers m. Translate the series of unencrypted message numbers into a word related to key.

Solution

Want to see the solution to this puzzle?

Got new solutions for the puzzle? Want to see other people's solutions? Talk to the puzzle master in his discussion forum at www.scottkim.com.

For more puzzles and inventions by Scott Kim, see www.scottkim.com or his book Inversions: A Catalog of Calligraphic Cartwheels, Key Curriculum Press, 1996.

For the complete technical details of the RSA encryption algorithm, see the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (CRC Press, 1996). The entire text is available for free online. See Chapter 8 for the RSA algorithm.

The Mathematical Explorer by Stan Wagon, (Wolfram Research).