**All Codes Lead to Rome**

1. Shift each letter forward one place in the alphabet.

2. Replace each letter with the letter at the same position, counting from the opposite end of the alphabet.

3. Read every other letter.

4. Write the 18 letters, ignoring spaces, in a 3x6 grid. The first two rows will be ALL and COD. Read the message down the columns instead of across the rows. Finally, put the spaces back in the original places.

5. Shift each letter forward three places in the alphabet and reverse the order of the letters.

6. Leave the first letter alone, shift the second letter forward one place in the alphabet, shift the third letter by three places, the fourth letter by four places, etc.

7. Write the numbers 1 through 26 clockwise around a circle, and write the letters A through Z clockwise around the same circle, so that A =1, B = 2, and so on. Convert the letters of the phrase into numbers (ALL = 1, 12, 12; CODES = 3, 15, 4, 5, 19). Starting at 1, count around the circle clockwise the same number of places as the number assigned to each letter. From 1, count forward 1 place (since A = 1); the code for the first letter is now 2. Now starting from 2, count forward 12 places (since L = 12); the code for this second letter is now 14. Now starting from 14, count forward 12 (since L = 12); the code for the third letter is now 26. Convert the new series of numbers back into letters (A = 1; B = 2; etc.).

**A Riddle Wrapped in a Mystery**

The remaining four letters are INOP. To decipher an image, compare each square of the image with the corresponding square of the key. If both squares are the same color, color the corresponding square in the answer white. If the squares are different colors, color the corresponding square in the answer black.

The letters spell *PIANO* (as in piano keys). The bonus word spells *PIN* (as in the pins inside a lock). How was this deduced? The bonus image has a black upper left corner square, so it must contain the letter *P.* Since the final image and *P* both have a white upper right corner square, *A* cannot be one of the letters, since it is the only letter with a black upper right corner square. On the other hand the word must contain the letter *N,* the only remaining letter with a black lower right corner square.

**Public Displays of Encryption**

In case you're wondering, here are the prime factors of the four numbers mentioned in the explanation: 57 = 3 x 19; 551 = 19 x 29; 5,063 = 61 x 83; 52,961 = 211 x 251.

The diagram of the remainders obtained by raising the number 3 to successive powers and dividing by 35 is shown at right. The cycle has length 12 (3, 9, 27, 11, 33, 29, 17, 16, 13, 4, 12, 1). Note that the cycle length divides evenly into (5 - 1)(7 - 1) = 4 x 6 = 24.

By factoring *n* = 55, deduce that *p* and *q* are 5 and 11. So (*p*-1)(*q*-1) is 40. This means that raising any number *m* to the power 41 and dividing by 55 yields the original number. The same thing happens if we raise *m* to the power 81, 121, 161, and so on, since the cycle has length 40. So in order for

*(m**^e**)**^d** = m**^ed*

to yield the original message number *m,* the product *ed* = 27*d* needs to be one more than a multiple of 40. If we write out multiples of 27, we quickly find that the 27 x 3 = 81 is one more than a multiple of 40, so *d*=3. Raising each of the enciphered numbers *c* to the third power and dividing by 55 we get the following deciphered numbers *c.* Each of the five deciphered numbers represents a position in the alphabet. The final answer is the word "stone," as in "keystone".

Real public keys are much harder to break, since the numbers are hundreds of digits long; computers cannot factor such immense numbers. For the mathematical details of public-key encryption, see *Handbook of Applied Cryptography* by Menezes, Oorschot, and Vanstone (CRC Press), and the CD-ROM *Mathematical Explorer* by Stan Wagon (Wolfram Research).

Want to go back to the 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 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).