Fatherhood and Encryption

If you're a parent, you know quite well: it is just a matter of time until it happens. One day you'll get home to find an encrypted note written by your seven-year old daughter (or son, but mainly daughters). Fathers throughout history struggled to decipher encrypted notes written by their beloved daughters. The famous Pierre de Fermat once said:

  "I'm a father struggling to decipher encrypted notes written by my beloved daughter"
               Fermat

Indeed, very touchy words. Unfortunately for Fermat during those years there were no computers abroad for him to just chill, grab a glass of wine and crack up some code to decrypt his daughters' notes.

Times have changed.

Few days back while on vacation, I came back to the apartment to find the following encrypted note written by my daughter:

 

It blew me away. Fortunately, there was still wine, it was late and everyone was sleeping, and the laptop was around.

From the get-go I did not believe she used a sophisticated encryption method such as One-Time Pad or a DES-like algorithm - trust me, if that was the case, I'd be rich now. The more plausible approach for a 7-year old little girl would have been to use a Caesar-Cypher algorithm: basically mapping each letter of the alphabet to a different letter (building a code map). The text was very small, which posed some challenges to apply Frequency Analysis, so I discarded that approach immediately. Instead, and still assuming that Caesar-Cypher was utilized, I decided to go brute-force.

It might seem like a daunting task to try to brute-force such a problem given the exponential possibilities - actually, it isn't. The trick is the following: as we try all the possible mappings, we trim down the search space considerably since we only continue if and only if we're finding valid English words along the way. Ahhhh! Valid English words! Getting somewhere. For that, then, we need a dictionary - which is easy, just Bing the web and you'll find countless ones. The other thing that came very handy and it was probably an oversight on my daughter's part, was that the encrypted note already had the words separated out (word breakers). Had that not been the case, it would have added another level of complexity to the problem.

Hence, the approach:

1. Start the brute-force: try to map each character to each other character
2. Every time we are done with a word, check that word against a dictionary (loaded in a Hashtable, where else?!)
3. If the answer is "no, not there", cut the search short - pointless to continue
4. If the answer is "yes, it is there", keep going until you get to the end of the encrypted note

Now, you'll potentially find "funny" words and sentences along the way - but chances are that at the end one, and only one of those messages will make sense based on the context. So I did that. This is a short snippet of the result:

 

act
act chair
act chair be
act chair be top
act chair be two
[...]
cut
cut uncle
cut uncle ah
cut uncle ah top
cut uncle ah try
cut uncle ah two
[...]
hey
hey ethan
hey ethan do
hey ethan go
hey ethan if
hey ethan if you
hey ethan if you have
hey ethan if you have any
hey ethan if you have any exciting
hey ethan if you have any exciting news
hey ethan if you have any exciting news please
hey ethan if you have any exciting news please write
hey ethan if you have any exciting news please write back

[...]
ice
ice child
ice child am
ice child an
ice child as
ice child at
ice child by
ice child by ear
ice child by eat
ice child go
[...]
may
may admit
may admit be
may admit be you
may admit go
may admit go yes
[...]
red
red early
red early go
red early hi
red early hi dog
[...]

Voila!!! The message in the middle was the decrypted one!!!! Which, I got to say, I was looking for something more exciting than that message, but in any case. Notice that along the way many potential sentences are being constructed, but with little or no sense. Takes less than 5 seconds to run. Code below - Happy 2015!!!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;
namespace BreakingBellasCode
{
    class Program
    {
        static void Main(string[] args)
        {
            string dictionaryFile = "dictionary.txt";
            string encryptedMessage = "miq igmpb nt qdh mpji pbq iklngnbw bioe vfipei oyngi rpls";
            string[] encryptedWords = encryptedMessage.Split(' ');
            Hashtable htDictionary = new Hashtable();
            ReadDictionary(dictionaryFile, htDictionary);
            Hashtable htMapping = new Hashtable();
            Hashtable htUsed = new Hashtable();
            Process(encryptedWords,
                    0,
                    0,
                    htMapping,
                    htUsed,
                    htDictionary,
                    "");
        }
        static void WriteEncryptedMessage(string message,
                                          Hashtable htMapping)
        {
            Console.WriteLine(message);
            for (int i = 0; i < message.Length; i++)
            {
                if (htMapping.ContainsKey(message[i]))
                {
                    Console.Write("{0}", (char)htMapping[message[i]]);
                }
                else
                {
                    Console.Write("{0}", message[i].ToString().ToUpper());
                }
            }
            Console.WriteLine();
        }
        static void Process(string[] encryptedWords,
                            int wordIndex,
                            int charIndex,
                            Hashtable htMapping,
                            Hashtable htUsed,
                            Hashtable htDictionary,
                            string decryptedMessage)
        {
            if (wordIndex >= encryptedWords.Length)
            {
                Console.WriteLine("*** " + decryptedMessage + " ***");
                Console.ReadLine();
                return;
            }
            if (charIndex >= encryptedWords[wordIndex].Length)
            {
                string[] parts = decryptedMessage.Split(' ');
                if(htDictionary.ContainsKey(parts[parts.Length - 1]))
                {
                    Console.WriteLine(decryptedMessage);
                    Process(encryptedWords,
                            wordIndex + 1,
                            0,
                            htMapping,
                            htUsed,
                            htDictionary,
                            decryptedMessage + " ");
                }
            }
            else if (htMapping.ContainsKey(encryptedWords[wordIndex][charIndex]))
            {
                Process(encryptedWords,
                        wordIndex,
                        charIndex + 1,
                        htMapping,
                        htUsed,
                        htDictionary,
                        decryptedMessage + ((char)htMapping[encryptedWords[wordIndex][charIndex]]).ToString());
            }
            else
            {
                for (int i = 0; i < 26; i++)
                {
                    char n = (char)('a' + i);
                    if (!htUsed.ContainsKey(n))
                    {
                        htMapping.Add(encryptedWords[wordIndex][charIndex], n);
                        htUsed.Add(n, true);
                        Process(encryptedWords,
                                wordIndex,
                                charIndex + 1,
                                htMapping,
                                htUsed,
                                htDictionary,
                                decryptedMessage + ((char)htMapping[encryptedWords[wordIndex][charIndex]]).ToString());
                        htUsed.Remove(n);
                        htMapping.Remove(encryptedWords[wordIndex][charIndex]);
                    }
                }
            }
        }
        static void ReadDictionary(string fileName, Hashtable htDictionary)
        {
            FileInfo fi = new FileInfo(fileName);
            StreamReader sr = fi.OpenText();
            while (!sr.EndOfStream)
            {
                string word = sr.ReadLine().Trim().ToLower();
                if (!htDictionary.Contains(word))
                {
                    htDictionary.Add(word, true);
                }
            }
            sr.Close();
        }
    }
}