Una stringa che se crittografata o decifrata con la stessa chiave ottiene una parola / istruzione inglese in entrambi i casi

Ero annoiato ieri sera, ci vuole solo 1 minuto per forzare la forza bruta di un elenco di parole di 27143 parole.

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

Ho usato english-words.35 da questo elenco di parole . Mi sono anche limitato a 4 lettere o più a lungo. Puoi utilizzare un dizionario più grande per ottenere più risultati.

Ecco il programma per forzare la lista.

//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);
        }

    }
}

Se stai cercando un modo semplice e innovativo per farlo, perché non assegna ad ogni parola w un valore intero e ogni parola m nel messaggio un valore intero, quindi mappali in base al chiave? Finché il tuo mapping w <==> m non supera i limiti del gruppo di parole (ad esempio nomi, pronomi, verbi, aggettivi, ecc. Sono mappati allo stesso gruppo) e i tuoi congiuntivali sono mappati in modo appropriato, potresti produrre frasi semi-leggibili come il tuo testo cifrato. La mappatura potrebbe essere facilmente generata seminando un PRNG con il valore della chiave.

Supponendo che non ti preoccupi di perdere la struttura grammaticale del tuo testo in chiaro e che il tuo mapping w <==> m è uniforme e casuale all'interno di gruppi, in realtà hai un ragionevole livello di sicurezza per i grandi testi in chiaro.

Certamente non userò un tale codice per qualcosa di importante, ma sarebbe molto interessante vedere i tipi di testi cifrati che potresti produrre.

C'è la soluzione banale di usare una chiave che è tutta As. Come una A nel codice Vigenère sostituisce ogni lettera con se stessa, questo ti darà semplicemente la stessa stringa S, non importa quante volte decifri o cripti. Ma immagino che non sia quello che stai cercando.

Il primo problema ("una stringa S che, se crittografata usando un codice Vigenère con Key K, ottiene una dichiarazione / parola inglese che ha senso") è facile da risolvere. Se usi una stringa S che è della stessa lunghezza o più corta della tua chiave K, allora per ogni dato S e testo cifrato C puoi facilmente calcolare una K per cui la S cifrata è C. Ad esempio, supponiamo che la tua S sia PERSONE e la tua C è CIPHER, quindi puoi scegliere K = JEBSSV. Ciò avviene semplicemente invertendo il codice Vigenère.

Il secondo problema ("se la stessa stringa S viene decifrata usando il codice Vigenère e di nuovo usando la stessa chiave K, ottiene anche un'altra affermazione / parola inglese che abbia senso") è anche facile da risolvere nel suo proprio, scegliere qualsiasi due stringhe inglesi per cui la distanza dell'alfabeto tra la lettera in una stringa e la lettera equivalente in un'altra stringa è pari (ad esempio "A" e "C" ma non "A" e "D") e la costruzione di una chiave che è metà della distanza tra le lettere. Puoi farlo facilmente usando solo lettere dispari (cioè A, C, E, G, I, K ecc.). Quindi se S è SICK e vuoi che la stringa doppiamente decodificata sia MICE, otterrai una chiave di DAAD.

Risolvere entrambi i problemi per lo stesso K è meno banale. Credo che il modo migliore per farlo sarebbe la forza bruta. In altre parole, scegli una parola / frase inglese come S, scegli a caso K e prova per ogni K se la S crittografata e S decrittografata due volte sono frasi inglesi. Per le stringhe brevi S questo dovrebbe essere abbastanza veloce - circa l'un percento delle possibili stringhe di quattro lettere sono parole inglesi, quindi in media troverete una buona K dopo aver provato diecimila K. Più lunga è la corda, più K dovrai provare.