Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I am trying to find a string S that if encrypted using a Vigenère cipher with Key K, it gets an English statement/word that makes sense. Additionally, if the same string S is decrypted using Vigenère cipher and again using the same key K, it gets another English statement/word that makes sense as well.

I think if I try to find a string that has a certain structure I could find such a case, any other hints from security experts that could help me find such a string and key?

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

I was bored last night, it only takes about 1 minute to brute force a 27143 word word-list.

String             |Key                |Encrypted          |Decrypted
-------------------+-------------------+-------------------+-------------------
ANAL               |PREACH             |PEEL               |PEEP
ANTS               |BEHOLD             |BRAG               |BROW
AURA               |JOKER              |JIBE               |JUTE
AWRY               |TARIFF             |TWIG               |TEAK
BLOC               |SPORADIC           |TACT               |REAP
BINS               |JAYWALK            |KILO               |ISLE
CANE               |REROUTE            |TEES               |PEEK
CANE               |ROACH              |TONG               |PONY
CARP               |RODENT             |TOUT               |POMP
CART               |FAULTED            |HALE               |DADS
CART               |FIELDED            |HIVE               |DINS
CART               |PENMANSHIP         |REEF               |NEWT
CAPE               |TETHER             |VEIL               |REED
CUED               |BURBLE             |DOVE               |ZANY
DENS               |WEAKEN             |ZINC               |TANS
DENT               |GEOLOGICAL         |JIBE               |DABS
DENT               |PEEL               |SIRE               |MARS
DEAN               |PERFECTED          |SIRS               |MARS
FADS               |WAIL               |BALD               |RAFT
FATS               |GABLE              |LAUD               |BAIT
FATS               |WAYLAID            |BARD               |RAFT
FAWN               |ROOFED             |WOKS               |MOSS
FEUD               |METHODICAL         |RINK               |HAZE
HART               |WAIL               |DAZE               |PARS
GAPE               |NOTHINGNESS        |TOIL               |HOED
GASH               |JOLLIED            |PODS               |DOTE
HIPS               |AMPLER             |HUED               |TEAT
GALA               |MARS               |SACS               |GAGS
HAUL               |YOGA               |FOAL               |ROMP
HURL               |LUMPED             |SODA               |EAVE
JELL               |BEAD               |KILO               |SAPS
LARD               |SONOROUS           |DOER               |HOWL
LASH               |COLLABORATE        |NODS               |ROTE
LATH               |RAILED             |CABS               |GAPE
LINT               |SMALLPOX           |DUNE               |HENS
LONE               |LABORATORIES       |WOOS               |AMOK
MATH               |TOLLED             |FOES               |HOSE
MATS               |HELLISH            |TEED               |VEST
MAIM               |UNSKILLED          |GNAW               |INKY
LAVA               |RAGS               |CABS               |GALS
MALT               |FIELDED            |RIPE               |TITS
MUSH               |BULLDOG            |NODS               |PATE
MAMA               |BADE               |NAPE               |PARE
MAMA               |DABS               |PANS               |RAPS
MAMA               |DISSATISFACTION    |PIES               |RIGS
MAMA               |FADS               |RAPS               |TARS
MAMA               |FUSSED             |RUES               |TUGS
MAMA               |RAPS               |DABS               |FADS
MAMA               |RODENT             |DOPE               |FORE
MAMA               |TOSSED             |FOES               |HOGS
NAPE               |POROUS             |COGS               |COCK
OUCH               |BURLAP             |POTS               |NAPE
OUST               |FOLLIES            |TIDE               |RUTS
LAIR               |COWBOY             |NOES               |ROOK
PAIL               |GELD               |VETO               |REDS
LIEU               |EMIGRANT           |PUMA               |TEEM
PANS               |SURLIER            |HUED               |DUET
PAPA               |EELS               |TEAS               |PEWS
PAPA               |HARSHER            |WAGS               |SACS
OKRA               |MONSOON            |AYES               |YEWS
PARE               |QUIVER             |FUZZ               |BURR
OXEN               |SHIFTIER           |GEMS               |EKES
MART               |FAILINGS           |RAZE               |TARS
PEPS               |HAPLESS            |WEED               |SWAT
PACT               |HECKLE             |WEED               |SEAR
MASH               |DOLL               |PODS               |ROTE
MASH               |FOLLIES            |RODS               |TOTE
PREY               |GROCER             |VISA               |RAKE
PUMA               |DUDS               |SOPS               |OARS
PUMA               |GOSSAMER           |VIES               |RUGS
QUAY               |RUNGS              |HONE               |BANI
RAYS               |CANKER             |TALC               |LAPS
PAWN               |SORRIER            |HONE               |DOVE
PAWN               |WORRISOME          |LONE               |HOVE
RUNE               |JOYOUS             |AILS               |SULK
RUNT               |QUARANTINE         |HONK               |ZANY
PEAL               |PREHISTORIC        |EVES               |ANEW
PEEK               |SERUM              |HIVE               |DANK
RUED               |SUPPER             |JOTS               |BALM
SNUB               |DRYS               |VEST               |LEER
SASH               |VOLLEY             |NODS               |DOTE
SNAP               |UNREAL             |MART               |CARP
SAUNA              |DEXTERITY          |VERGE              |LEDGE
TOOT               |HOTLY              |ACHE               |OAFS
TANS               |MEALIER            |FEND               |TENT
TUNA               |MOOS               |FIBS               |TUBS
TUNA               |WORSEN             |PIES               |DUES
TART               |MAILBOXES          |FAZE               |TARS
TOTS               |HILLBILLIES        |AWED               |OUST
TONG               |AIRY               |TWEE               |HUES
VENT               |BEFALL             |WIST               |GASH
WAXY               |LEPROSY            |HEMP               |PEST
WANE               |XENOPHOBIA         |TEAS               |BEAK
WANNA              |LAIRS              |HAVES              |PAVES
YUCK               |FUTURES            |DOVE               |HARK
VATS               |MULL               |HUED               |RUST
YARN               |FAIRIES            |DAZE               |HARE
WAFT               |HAUL               |DAZE               |LAPS

I used english-words.35 from this word list. I also limited myself to 4 letter words or longer. You can use a larger dictionary to get more results.

Here is the program to brute force the list.

//Program.cs - Runs the Vigenere brute forcer and displays the result.
using System;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox_Console
{
    class Program
    {
        public static void Main()
        {
            Stopwatch runtime = new Stopwatch();
            runtime.Start();


            var vigenere = new Vigenere(@"C:\scowl\final\english-words.10", @"C:\scowl\final\english-words.20", @"C:\scowl\final\english-words.35",
            @"C:\scowl\final\english-words.40", @"C:\scowl\final\english-words.50", @"C:\scowl\final\english-words.55",
            @"C:\scowl\final\english-words.60", @"C:\scowl\final\american-words.10", @"C:\scowl\final\american-words.20",
            @"C:\scowl\final\american-words.35", @"C:\scowl\final\american-words.40", @"C:\scowl\final\american-words.50",
            @"C:\scowl\final\american-words.55", @"C:\scowl\final\american-words.60");

            Console.WriteLine("Wordlist size: {0:N0}", vigenere.WordListSize);

            //Console.WriteLine("{0,-19}|{1,-19}|{2,-19}|{3,-19}", "String", "Key", "Encrypted", "Decrypted");
            //Console.WriteLine("{0,-19}+{1,-19}+{2,-19}+{3,-19}", new String('-', 19), new String('-', 19), new String('-', 19), new String('-', 19));

            //vigenere.StartTest();
            vigenere.JibberishKeys();

            List<Vigenere.TwoStrings> resultsForFile = new List<Vigenere.TwoStrings>();

            foreach (var result in vigenere.Results.GetConsumingEnumerable())
            {
                //Console.WriteLine("{0,-19}|{1,-19}|{2,-19}|{3,-19}", result.Word, result.Key, Vigenere.Encrypt(result.Word, result.Key), Vigenere.Decrypt(result.Word, result.Key));
                resultsForFile.Add(result);

                ShowOnlyProgress(vigenere, resultsForFile.Count);
            }
            runtime.Stop();

            Console.WriteLine("Done in {0}", runtime.Elapsed);

            using (var sr = new StreamWriter("WordKeys.txt", false))
            {
                sr.WriteLine("Wordlist size: {0:N0}", vigenere.WordListSize);
                sr.WriteLine("Build time: {0}", runtime.Elapsed);

                sr.WriteLine("{0,-19}|{1,-19}|{2,-19}|{3,-19}", "String", "Key", "Encrypted", "Decrypted");
                sr.WriteLine("{0,-19}+{1,-19}+{2,-19}+{3,-19}", new String('-', 19), new String('-', 19), new String('-', 19), new String('-', 19));

                foreach (var result in resultsForFile.OrderBy(a => a.Word).ThenBy(a=> a.Key))
                {
                    sr.WriteLine("{0,-19}|{1,-19}|{2,-19}|{3,-19}", result.Word, result.Key, Vigenere.Encrypt(result.Word, result.Key), Vigenere.Decrypt(result.Word, result.Key));
                }
            }


            Console.ReadLine();

        }

        static public void ShowOnlyProgress(Vigenere vigenere, int count)
        {
            Console.CursorTop = 1;
            Console.CursorLeft = 0;
            Console.WriteLine("Processed Records: {0:N0}", vigenere.ProcessedRecords);
            Console.WriteLine("Found Pairs: {0:N0}", count);

        }
    }
}

.

//Vigenere.cs - Written by Scott Chamberlain
//Brute forces a Vingenere encryption to find pairs where S, the encrypted
// and decrypted output of S are English words.

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Threading;

namespace Sandbox_Console
{
    class Vigenere
    {
        public Vigenere(params string[] wordLists)
        {
            _WordList = new HashSet<string>();

            foreach(var wordList in wordLists)
            {
                using (var wordListStream = new System.IO.StreamReader(wordList))
                {
                    string line;
                    while ((line = wordListStream.ReadLine()) != null)
                    {
                        line = line.ToUpperInvariant();
                        if(line.Contains('\'') == false //No Apostrophes
                           && line.Length >= 4) // Words 4 or longer.
                            _WordList.Add(Regex.Replace(line, "[^A-Z]", "")); //Replace all non letter chars then add to wordlist.
                    }
                }
            }


            //Create the Vigenère square


            Results = new BlockingCollection<TwoStrings>();
            ResultSeen = new ConcurrentDictionary<TwoStrings, object>();

            _processedRecords = 0;
        }

        const int ALPHABIT_SIZE = 26;
        const int LETTER_OFFSET = 'A';

        HashSet<string> _WordList;

        public int WordListSize { get { return _WordList.Count; } }


        static Lazy<char[,]> _CryptTable = new Lazy<char[,]>( () =>
            {
                var tmpTable = new char[ALPHABIT_SIZE, ALPHABIT_SIZE];

                for (int i = 0; i < ALPHABIT_SIZE; i++)
                {
                    for (int j = 0; j < ALPHABIT_SIZE; j++)
                    {
                        tmpTable[i, j] = (char)(((i + j) % ALPHABIT_SIZE) + LETTER_OFFSET);
                    }
                }

                return tmpTable;
            });

        static Lazy<char[,]> _DecryptTable = new Lazy<char[,]>( () =>
            {
                var tmpTable = new char[ALPHABIT_SIZE, ALPHABIT_SIZE];

                for (int i = 0; i < ALPHABIT_SIZE; i++)
                {
                    for (int j = 0; j < ALPHABIT_SIZE; j++)
                    {
                        int result = i - j;
                        if (result < 0)
                            result = ALPHABIT_SIZE + result;
                        tmpTable[i, j] = (char)(result + LETTER_OFFSET);
                    }
                }

                return tmpTable;
            });

        public BlockingCollection<TwoStrings> Results { get; private set; }

        public class TwoStrings : IEquatable<TwoStrings>
        {
            public TwoStrings(string word, string key)
            {
                this.Word = word;
                this.Key = key;
            }

            public string Word {get; private set;}
            public string Key {get; private set;}

            public bool Equals(TwoStrings other)
            {
                if (other == null)
                    return false;
                if (this.Word == other.Word)
                {
                    if (this.Key == other.Key)
                        return true;
                    else
                    {
                        //If the word is shorter than the key, only compare keys up to the length of the word.
                        var thisLen = this.Word.Length;
                        if (thisLen > this.Key.Length)
                            thisLen = this.Key.Length;

                        var otherLen = other.Word.Length;
                        if (otherLen > other.Word.Length)
                            otherLen = other.Key.Length;

                        return this.Key.Substring(0, thisLen) == other.Key.Substring(0, otherLen);
                    }
                }
                else
                {
                    return false;
                }
            }

            private int TrimmedKeyHashCode()
            {
                if (this.Key.Length <= this.Word.Length)
                    return this.Key.GetHashCode();
                else
                    return this.Key.Substring(0, this.Word.Length).GetHashCode();
            }

            public override bool  Equals(object obj)
            {
                return this.Equals(obj as TwoStrings);
            }

            public override int GetHashCode()
            {
                //Use unchecked to suppress arithmetic overflow exceptions
                unchecked
                {
                    return 7 +
                        (this.Word.GetHashCode() * 11) +
                        (TrimmedKeyHashCode() * 13);
                }
            }
}

        public ConcurrentDictionary<TwoStrings, object> ResultSeen;

        private int _processedRecords;

        public int ProcessedRecords { get { return _processedRecords; } }

        public void StartTest()
        {
            Task.Factory.StartNew(() =>
                {
                    Parallel.ForEach(_WordList, TestWord);
                    Results.CompleteAdding();
                }, TaskCreationOptions.LongRunning);

        }

        private void TestWord(string word)
        {
            foreach (string key in _WordList)
            {
                if (_WordList.Contains(Encrypt(word, key)) && 
                    _WordList.Contains(Decrypt(word, key)))
                {
                    var testResult = new TwoStrings(word, key);
                    if(ResultSeen.TryAdd(testResult, null) == true) //Check that we don't have a similar key already.
                        Results.Add(testResult);
                }
            }
            Interlocked.Increment(ref _processedRecords);
        }
        public static string Encrypt(string word, string key)
        {
            int keyLength = key.Length;
            StringBuilder sb = new StringBuilder(word);
            for (int i = 0; i < sb.Length; i++)
            {
                sb[i] = _CryptTable.Value[key[i % keyLength] - LETTER_OFFSET, sb[i] - LETTER_OFFSET];
            }
            return sb.ToString();
        }

        public static string Decrypt(string word, string key)
        {
            int keyLength = key.Length;
            StringBuilder sb = new StringBuilder(word);
            for (int i = 0; i < sb.Length; i++)
            {
                sb[i] = _DecryptTable.Value[key[i % keyLength] - LETTER_OFFSET, sb[i] - LETTER_OFFSET];
            }
            return sb.ToString();
        }


        //does the same as TestWord but the key does not need to be in the dictionary.
        public void JibberishKeys()
        {
            Task.Factory.StartNew(() =>
            {
                Parallel.ForEach(_WordList, TestJibberish);
                Results.CompleteAdding();
            }, TaskCreationOptions.LongRunning);
        }

        private void TestJibberish(string word)
        {
            HashSet<string> keyList = new HashSet<string>();

            //Build the list of all possible keys;
            foreach (var keyGenWord in _WordList)
            {
                //Prevent a key of "AAAAA"
                if (keyGenWord != word)
                {
                    //Due to the behavior of the table
                    //"word == Decrypt(encryptedWord, key)" and "key == Decrypt(word, EncryptedWord)" are both true.
                    keyList.Add(Decrypt(word, keyGenWord));
                }
            }

            foreach (string key in keyList)
            {
                //We don't need to check the wordlist for the encrypted version as that word is what generated
                // the key in the first place.
                if (_WordList.Contains(Decrypt(word, key)))
                {
                    var testResult = new TwoStrings(word, key);
                    if (ResultSeen.TryAdd(testResult, null) == true) //Check that we don't have a similar key already.
                        Results.Add(testResult);
                }
            }

            Interlocked.Increment(ref _processedRecords);
        }

    }
}
share|improve this answer
    
That's closest to what I had in mind, except that the string and the key do not have to be meaningful words, but its okay i'll just do some changes in the code and reuse it, thanks :) –  Mohamed Khamis Oct 18 '12 at 14:14
1  
Actually I have a updated version. I updated my code. Call vigenere.JibberishKeys(); to get what you want. –  Scott Chamberlain Oct 18 '12 at 14:58
1  
One last change to not clutter the console, saves output to a sorted txt file. –  Scott Chamberlain Oct 18 '12 at 15:13
add comment

If you're looking for a simple and novel way to do this, why not assign each word w an integer value, and each word m in the message an integer value, then map them across based on the key? As long as your mapping w <==> m doesn't exceed word group boundaries (e.g. nouns, pronouns, verbs, adjectives, etc. are mapped to the same group) and your conjunctives are appropriately mapped, you could feasibly produce semi-legible sentences as your ciphertext. The mapping could quite easily be generated by seeding a PRNG with your key value.

Assuming that you don't care about leaking the grammatical structure of your plaintext, and that your mapping w <==> m is uniform and random within groups, you actually have a reasonable level of security for large plaintexts.

I certainly wouldn't use such a cipher for anything important, but it'd be very interesting to see the kinds of ciphertexts you might produce.

share|improve this answer
add comment

There's the trivial solution of using a key which is all As. As an A in the Vigenère cipher substitutes each letter with itself, this will simply give you the same string S no matter how many times you decrypt or encrypt. But I guess that's not what you're looking for.

The first problem ("a string S that if encrypted using a Vigenère cipher with Key K, it gets an English statement/word that makes sense") is easy to solve. If you use a string S that is the same length or shorter than your key K, then for any given S and cipher text C you can easily calculate a K for which the encrypted S is C. For example, let's say your S is PEOPLE and your C is CIPHER, then you can choose K = JEBSSV. This is done by simply reversing the Vigenère cipher.

The second problem ("if the same string S is decrypted using Vigenère cipher and again using the same key K, it gets another English statement/word that makes sense as well") is also easy to solve in it's own, by choosing any two English strings for which the Alphabet distance between the letter in one string and the equivalent letter in another string is even (e.g. 'A' and 'C' but not 'A' and 'D') and building a key which is half the distance between the letters. You can do this easily by using only odd letters (i.e. A, C, E, G, I, K etc). So if S is SICK and you want the twice decrypted string to be MICE, you would get a key of DAAD.

Solving both problems for the same K is less trivial. I believe the best way to do this would be brute force. In other words, choose some English word/phrase as S, randomly choose Ks and test for each K if the encrypted S and twice decrypted S are English phrases. For short strings S this should be quite fast - about one percent of possible four letter strings are English words, so on average you'll find a good K after trying ten thousand Ks. The longer the string the more Ks you'll need to try.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.