September 25, 2006

A Coding Puzzle

If you are in the mood for a programming puzzle, read on.

Mirror Cipher

This weekend, Anthony and I played with ciphers in python.

The python interactive terminal is a good place to play with one-line programs. We just ran "python" without any arguments, and then Anthony and I took turns running commands. If you have python, you can follow along.

Here is a simple substitution cipher we made:

alph  = 'abcdefghijklmnopqrstuvwxyz'
ralph = 'zyxwvutsrqponmlkjihgfedcba'
def code(word): return ''.join([ralph[alph.find(letter)] for letter in word])

This cipher replaces every letter with its opposite: it swaps a with z; b with y; and so on. So you get:

>>> code('monster')
>>> code ('nlmhgvi')

Because each letter is replaced by its mirror opposite, applying the same encryption on the ciphertext gives you the plaintext back out. Anthony had great fun encoding different secret messages.

An Unbreakable Code

After we showed our secret code program to Mom, she understood the cipher right away. And she proved she was able to decode the ciphertext, without any machine assistance. That Mom - she is a smart one.

The first rule of secret codes is that if Mom can read a code, it is not hard enough.

So Anthony got an idea for making the cipher harder. Here is what he did:

>>> ralph = 'qazwsxedcrfvtgbyhnujmikolp'
>>> code('monster')

Now, instead of replacing every letter with its opposite, he replaced every letter with a "random" letter. (Can you see how he picked his random letters?)

But then when he tried to decipher his code, the old trick of re-encoding the ciphertext did not work.

>>> code('tbgujsn')

What to do now?

I wanted Anthony to learn how to reverse the roles of "ralph" and "alph" to write a secret decoder function. That would have been educational!

But he had other plans.

Trying Harder

Instead of decoding in a rational way, he decided to try repeating his encryption of 'jaemrug' again to see if anything better would come out the second time. All he got was another jumble of letters 'rqstnme'.

But he still didn't give up. He wanted to try harder. He did it again and again several times:

>>> code('monster')
>>> code('tbgujsn')
>>> code('jaemrug')
>>> code('rqstnme')
>>> code('nhujgts')
>>> code('gdmreju')
>>> code('ewtnsrm')
>>> code('skjgunt')
>>> code('ufremgj')

Suddenly he struck gold.

"Dad! Look at that, 'mxnster' is almost right!" His crazy idea worked.

Things were not perfect, but surely this almost-monster result could be no mere coincidence.

Encircling the Solution

Anthony had discovered something neat. To save us from manually encrypting things over and over again, I wrote this short program for him:

def reps(word):
   c, cipher = 1, code(word)
   while cipher != word:
     c, cipher = c + 1, code(cipher)
     print cipher
   print c

When we typed in reps('monster'), the program reencrypted the word 90 times, and then came back to exactly the same word 'monster'. No mistakes this time.

Anthony was so excited he ran to tell his his mom about his new discovery. Mom was impressed. "That shouldn't happen," she said.

But, of course, it does happen.

The first rule of mathematics is that if it surprises Mom, it must be good math.

Why did encrypting the word 90 times return to the same text? Mom imagined that even though it was believable you might return to the original text by encrypting over and over, it should have taken a very long time. 90 repetitions did not seem very long. Was it because Anthony had accidentally chosen a special key? It seemed that if Anthony's "ralph" key had been different, he might have taken a different number of encryptions to return to the plaintext.

The Puzzle

So here is the puzzle.

  • Try to find a "ralph" key with the most possible reps before returning plaintext.
  • How many repetitions will it take?
  • Was Anthony's key unusual?
  • Is there a magic number of reps that decodes anything, for any "ralph"?
Posted by David at September 25, 2006 10:17 AM

I am not in the mood to do any programing myself right now but I believe that with Anthony's ralph, the word would repeat in 7 (lip), 9 (gun), 10(food), 63 (ring), 70 (bid), 90 (name), or 630 (ace) since his letters loop in 10 (aboxfkwdhq), 7 (civlypz), and 9 (egnrjtmus) loops.

Therefore the maximum number of reps would be created when a1*a2*a3*...*an is max and a1+a2+a3+...+an=26. Then you just need to make a ralph with loops equal to all the a's.

Or I could be completely wrong.

Posted by: KD at September 25, 2006 03:25 PM

Using my previously stated logic, I want to add that in to find the max number of reps none of the a's should equal one another.

Posted by: KD at September 25, 2006 03:45 PM

Max reps of 1155 for the word "monster" in the ralph = 'fmghcijklopqtrenudabvwxyzs'.


Posted by: KD at September 25, 2006 03:52 PM

Bravo for picking up a pencil first instead of a computer. But can your ralph be bettered?

Sometimes in the search for a perfect solution you miss an even better one....

Posted by: David at September 25, 2006 05:45 PM

The maximum number of repetitions isn't actually the product, but the least common multiple (LCM) of the numbers adding up to 26. (That tends to be the same, though, for an optimal solution.)

I wrote a little Perl (sorry, better than my Python) script to calculate the optimal combination of numbers - - and the optimal numbers are: 1,4,5,7,9, with an LCM of 1260.
A 'ralph' with the corresponding loops, which actually is worst case for "monster", is: 'bcdefgaijklnmrpqsyoxtuvwzh'.

Now to answer your other questions:
Was the key unusual? Not at all.
Magic number of repetitions? Well, I doubt if it's optimal, but the LCM of 1..26 will do: 26771144400.

- Michael

Posted by: Michael Schaap at September 25, 2006 05:46 PM


Isn't it curious that achieving the longest shuffle requires leaving one letter in the clear? In your cipher, 'm' is encoded as 'm', a fact Anthony will notice as soon as he encodes his 'monster' plaintext. KD's solution is probably the best that changes every letter.

The German Enigma was a World War II cipher machine that never allowed a letter to be encoded as itself. In retrospect that was probably not a very good feature, because it helped Alan Turing guess the location of cribs. The Enigma was famously cracked by the Poles and the British, and that accomplishment may have been decisive in the war.

Interestingly, the method used by the Polish cryptanalysts to crack the early versions of the Enigma was based on building a catalog of "cycle" patterns like the ones you have analyzed for Anthony's iterating "ralph" cipher. They had about 100,000 shuffle patterns to analyze, which of course they did without benefit of perl or python.

If you haven't read it before, Simon Singh's "The Code Book" has an excellent detailed description of Marian Rejewski's brilliant - yet remarkably simple - cracking of the early Enigma. (Singh also describes Alan Turing's more complex attack on the later, more impenetrable versions of the Enigma codes.)

Posted by: David at September 25, 2006 10:24 PM

qazwsxedcrfvtgbyhnujmikolp is great

Posted by: josie at January 28, 2007 08:44 AM
Post a comment

Remember personal info?