Problem of the Day
A new programming or logic puzzle every Mon-Fri

Vigenère cipher

The Vigenère cipher made its rounds in the mid-1550s up until the end of the American Civil War. It was very easy for soldiers to encode messages and pass them around to all the allied camps.

The cipher requires a key and a message. It works like this:

Key:
REDDIT
Message:
TODAYISMYBIRTHDAY

REDDITREDDITREDDI
TODAYISMYBIRTHDAY
--------------------------
KSGDGBJQBEQKKLGDG

Using a 0 based alphabet (A=0), R is the 17th letter of the alphabet and T is the 19th letter of the alphabet. (17 + 19) mod 26 = 11 which is where K resides in the alphabet. Repeat for each key/message letter combination until done.

Today's problem of the day is two part. The first part is to implement a Vigenère cipher in the programming language of your choice. Feel free to post solutions or links to solutions in the comments.

The second part is to try and implement something to crack the message below (the key is 5 or less characters).

ZEJFOKHTMSRMELCPODWHCGAW

Good luck!

Permalink: http://problemotd.com/problem/vigenere-cipher/

Comments:

  • Anonymous - 3 years, 8 months ago

    From what I know of Vigenere ciphers, the message you've given us can't really be cracked (it's too short) without brute force. I can confirm that the key isn't 1 or 2 characters long (I tried brute forcing it), but short of using a dictionary to automatically find possible solutions, it'll take far too long to parse the results of keys that are 3+ characters.

    reply permalink

  • Anonymous - 3 years, 8 months ago

    The goal is "to try and implement something to crack the message".

    Runtime is irrelevant.

    reply permalink

  • J. D. - 3 years, 8 months ago

    Got a basic python script down, but keeps printing out wrong answer. Anyone fix it?

    <pre><code>import string

    alphabet=list(string.ascii_uppercase) encodedKey="" maths=0 counter=0 key=(str(input("Key: "))).upper() cipher=(str(input("Encode: "))).upper()

    while len(key)<len(cipher): key+=key[counter] counter+=1

    for i in range(0,len(cipher)): maths=(int(alphabet.index(key[i]))+int(alphabet.index(cipher[i])))%25 encodedKey+=alphabet[maths]

    print(encodedKey) </code></pre>

    reply permalink

  • Max Burstein - 3 years, 8 months ago

    If you mod by 26 instead of 25 it works. That was my mistake in the description.

    reply permalink

  • Anonymous - 3 years, 8 months ago

    I think is 'mod 26', no?

    reply permalink

  • Max Burstein - 3 years, 8 months ago

    You're correct. 25 was my mistake. I updated the problem to reflect that.

    reply permalink

  • Anonymous - 3 years, 8 months ago

    This is my python attempt:

    from itertools import cycle, izip
    
    
    NORMALISER = ord('A')
    
    
    def vigenere(key, message):
        key = key.upper()
        message = message.upper()
        ciphered_message = ''
        for k, m in izip(cycle(key), message):
            k_ord = ord(k) - NORMALISER
            m_ord = ord(m) - NORMALISER
            code = ((k_ord + m_ord) % 25) + NORMALISER - 1
    
        ciphered_message = ciphered_message + chr(code)
    
        return ciphered_message
    

    reply permalink

  • Anonymous - 3 years, 8 months ago

    I found two bugs in your code

    The first is that the line

    ciphered_message = ciphered_message + chr(code)
    

    isn't wrapped in your for Loop, so it outputs "G"

    The second is in your algorithm. The characters that do not exceed 25 when being converted comes out 1 character off.

    My hats off to you though, I had never used itertools before today, so after I had solved it, I resolved it using a variation of your strategy.

    from itertools import cycle, izip
    
    NORMALISER = ord('A')
    
    def vigenere(key, string):
        cipher = ''
        for k, s in izip(cycle(key.upper()), string.upper()):
            cipher = cipher + transpose(k, s)
        return cipher
    
    def transpose(k, s):
        k_ord = ord(k) - NORMALISER
        s_ord = ord(s) - NORMALISER
        if k_ord + s_ord > 26:
            return chr(((k_ord + s_ord) % 25) + (NORMALISER - 1))
        return chr((k_ord + s_ord) + NORMALISER)
    

    I had originally written the transpose method I just liked the way you did the NORMALISER variable instead of explicitly calling out the 65. And I also implemented your for loop style into what I already had instead of a separate indexer for the key that would reset.

    reply permalink

  • Larry - 3 years, 8 months ago

    You should definitely use a monospaced font for the example. It looks like the result is longer than the original message. My first thought was 'where did these extra characters come from?'.

    reply permalink

  • Anonymous - 3 years, 8 months ago

    When I encrypt the authors code I get the following: Assuming A=0 for the encryption => LSGDHCKQCEQLLLGDH Assuming A=1 for the encryption => KRFCGBJPBDPKKKFCG

    Anyone could confirm that either his encrypted string is wrong or am I?

    reply permalink

  • Crow - 3 years, 8 months ago

    You're indexing the alphabet starting from 1. He's indexing it starting from 0.

    reply permalink

  • Anonymous - 3 years, 8 months ago

    Javascript with jQuery (though without jQuery isn't much different) var phrase = 'TodayIsMyBirthday', key = 'Reddit'; phrase.toUpperCase().split('').map(function(v, i) { return String.fromCharCode((((v.charCodeAt(0) - 65) + (key.toUpperCase().split('')[i % key.length].charCodeAt(0) - 65)) % 25) + 65) }).join('');

    reply permalink

  • Ezekiel B - 3 years, 8 months ago

    (17 + 19) mod 26 = 10, which does then translate to K. Thinking that was another typo.

    reply permalink

  • Anonymous - 3 years, 8 months ago

    My ruby attempt:

    key = ARGV[0].split(//) message = ARGV[1].split(//)

    cipher = "" char_offset = 'A'.ord

    (0..(message.length - 1)).each do |i| key_num = key[i % key.length].ord - char_offset message_num = message[i].ord - char_offset

    cipher = cipher + ((key_num + message_num) % 26) + char_offset).chr end

    puts cipher

    reply permalink

  • Anonymous - 3 years, 8 months ago

    key = ARGV[0].split(//)
    message = ARGV[1].split(//)
    
    cipher = ""
    char_offset = 'A'.ord
    
    (0..(message.length - 1)).each do |i|
      key_num = key[i % key.length].ord - char_offset
      message_num = message[i].ord - char_offset
    
      cipher = cipher + ((key_num + message_num) % 26 + char_offset).chr
    end
    
    puts cipher
    

    reply permalink

  • Cautious Poke - 3 years, 8 months ago

    c# solution to Code a message

    public static class VigenereCipher
    {
        public static string CodeMessage(string code, string message)
        {
            code = code.ToUpper();
            message = message.ToUpper();
            byte[] codedMessageBytes = new byte[message.Length];
            int theZeroIndex = (int)"A"[0];
            for (int i = 0; i < message.Length; i++)
            {
                byte codePosition = (byte)((int)code[i % code.Length] - theZeroIndex);
                byte messagePosition = (byte)((int)message[i] - theZeroIndex);
                codedMessageBytes[i]= (byte)(((codePosition+messagePosition) %26) + theZeroIndex);
            }
            return System.Text.Encoding.ASCII.GetString(codedMessageBytes);
        }
    }
    

    reply permalink

  • Anonymous - 3 years, 8 months ago

    PHP

      <?
      $message = 'TODAYISMYBIRTHDAY';
      $key = 'REDDIT';
      $alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
      $encryptedMessage = '';
      $keyCounter=0;
    
      for ($i=0; $i < strlen($message); $i++) {
          $thisMessageLetter = substr($message, $i, 1);
          $thisKeyLetter = substr($key, $keyCounter % strlen($key), 1);
          $encryptedLetterPos = (strpos($alphabet, $thisKeyLetter) + strpos($alphabet, $thisMessageLetter)) % strlen($alphabet);
          $encryptedMessage .= substr($alphabet, $encryptedLetterPos, 1);
          $keyCounter ++;
      }
      echo "<pre>$message\n$encryptedMessage</pre>";
      ?>
    

    reply permalink

  • Anonymous - 3 years, 8 months ago

    I wanted to give it a shot in Clojure in a point-free (aka "pointless") style.

    (defn vig
      [key text]
      (apply str (map (comp char
                            (partial + (int \A))
                            (comp (partial apply mod) reverse (partial list 26))
                            (partial apply +)
                            (partial map (comp (partial - 0)
                                               (partial - (int \A))))
                            (partial map int)
                            vector)
                      text
                      (cycle key))))
    

    reply permalink

  • Egon Wilzer - 3 years, 8 months ago

    PHP

    function vigenere($key, $word) {
    
        $word = strtolower($word);
        $totalkey = strtolower(substr(str_repeat($key,  ceil(strlen($word)/strlen($key)) ), 0, strlen($word)));
    
        for ($i=0; $i < strlen($word); $i++) { 
            $code[] = chr((((ord($word[$i])-97)+(ord($totalkey[$i])-97)) % 26) + 97);
        }
        return strtoupper((implode($code)));
    }
    

    reply permalink

  • Michae Von Hell - 3 years, 8 months ago

    A simple implementation in c++ <code> string crypt(string key, string message){ for (int x = 0; x < message.length(); x++){ message[x] = (message[x] - 'A' + (key[x%key.length()] - 'A'))%26 + 'A'; } return message; } </code>

    reply permalink

  • Michae Von Heaven - 3 years, 8 months ago

    I give up <pre><code>string crypt(string key, string message){ for (int x = 0; x < message.length(); x++){ message[x] = (message[x] - 'A' + (key[x%key.length()] - 'A'))%26 + 'A'; } return message; } </code></pre>

    reply permalink

  • Anonymous - 3 years, 8 months ago

    <script src="https://gist.github.com/anonymous/9399359.js"></script>

    reply permalink

  • icendoan - 3 years, 8 months ago

    encode :: String -> String -> String -> String
    encode (k:ks) [] t = t
    encode (k:ks) (s:ss) t = encode ks ss (t ++ [(wheel k s)])
        where wheel k s = cycle [' '..'~'] !! ((ord k - 32) + (ord s - 32) + 1)
    
    -- the +1 is to not map ' ' -> ' '.
    decode :: String -> String -> String -> String
    decode (k:ks) [] s = s
    decode (k:ks) (t:ts) s = decode ks ts (s ++ [(wheel k t)])
        where wheel k t = cycle [' '..'~'] !! (((ord t - 32) - (ord k - 32) + 94) `mod` 95)
    

    This is my haskell attempt, using the way haskell has an ordering on characters as unicode. There's another couple of functions to tidy the i/o up a little, as well as a nice main :: IO () to get the command line working.

    reply permalink

  • Grant McConnaughey - 3 years, 8 months ago

    In Groovy:

    {code} def convertLetterToNumber(letter) { ((int) letter?.toUpperCase()) - 65 }

    def convertNumberToLetter(number) { (char) (number + 65) }

    def vigenereCipher(key, message) {
    def encryptedMessage = ''

    message.eachWithIndex { m, i ->
        def keyPos = (i) % key.size()
    
        def num1 = convertLetterToNumber(m)
        def num2 = convertLetterToNumber(key[keyPos])
    
        encryptedMessage += convertNumberToLetter((num1 + num2) % 26)
    }
    
    encryptedMessage
    

    }

    assert vigenereCipher('REDDIT', 'TODAYISMYBIRTHDAY') == 'KSGDGBJQBEQKKLGDG' {code}

    reply permalink

  • Luke Brooks - 3 years, 8 months ago

    I did something kind of naughty but I couldn't help myself. Hard to read code and no validation but it works (with correct inputs).

    print ''.join( [ chr( (ord(sys.argv[1][i])+ord(sys.argv[2][i%len(sys.argv[2])])) % 26 + 65) for i in range(len(sys.argv[1])) ] )

    reply permalink

  • Ben Lucyk - 3 years, 8 months ago

    Here's a very simple javascript implementation: http://codepen.io/anon/pen/taHIx

    Now do I waste more time on to the codebreaking?! :)

    reply permalink

  • rekh127 - 3 years, 8 months ago

    Heres a complete encrypt/decrypt solution in C.

    #include <stdio.h>
    
    int printUsage(){
        return printf("Usage: -[(e)ncrypt|(d)ecrypt] key text\n");
    }
    
    char toUpper(char c){
        if(c>=32 && c<58){
            return c-32;
        }
        return c;
    }
    
    int encrypt(char* key, char* text){
        printf("Encrypted:");
        int index, keyindex; 
        for(index=keyindex=0;text[index];index++,keyindex++){
            if(!key[keyindex]){
                keyindex=0;
            }
            char enc_letter = toUpper(text[index] - 'A');   
            char key_letter = toUpper(key[keyindex]-'A');
            enc_letter = enc_letter + key_letter;
            text[index] = (enc_letter%26)+'A';
        }
        return 0;
    }
    
    int decrypt(char* key, char* text){
        printf("Decrypted:");
        int index, keyindex; 
        for(index=keyindex=0;text[index];index++,keyindex++){
            if(!key[keyindex]){
                keyindex=0;
            }
            char enc_letter = toUpper(text[index] - 'A');
            char key_letter = toUpper(key[keyindex] - 'A');
            if(enc_letter < key_letter){
                enc_letter = enc_letter + 26;
            }
            text[index] = (enc_letter-key_letter)+'A';
        }
        return 0;
    }
    
    
    int main(int argc, char* argv[]){
        if(argc!=4){
            return printUsage();
        }
        char* key = argv[2];
        char* text = argv[3];
        if(argv[1][1] == 'e'){
            encrypt(key, text);
        }else if(argv[1][1] == 'd'){
            decrypt(key, text);
        }else {
            return printUsage();
        }
        printf("%s\n", text);
        return 0;
    }
    

    reply permalink

  • AndreaM - 3 years, 8 months ago

    Javascript one liner (to encode). Supports a custom alphabet.

    function vigenere(key, text, a) {
        return text.split("").map(function(r, i){ var a = a || "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; return a.charAt( (a.indexOf(r) + a.indexOf(key[i%key.length]) ) % a.length); }).join("");
    }
    

    reply permalink

  • factorial720 - 3 years, 8 months ago

    Code (in Python):

    def convert(in_char, key, index, invert=False):
        BASE = ord('A')
        in_ord = ord(in_char) - BASE
        index = index % len(key)
        key_ord = ord(key[index]) - BASE
        if invert:
            key_ord = -key_ord
        out_ord = (26 + key_ord + in_ord) % 26 + BASE
        return chr(out_ord)
    
    BASE = ord('A')
    key = 'REDDIT'
    message = 'TODAYISMYBIRTHDAY'
    output = ""
    index = 0
    for char in message:
        output += convert(char, key, index)
        index += 1
    print output
    
    encrypted_message = "KSGDGBJQBEQKKLGDG"
    output = ""
    index = 0
    for char in encrypted_message:
        output += convert(char, key, index, True)
        index += 1
    print output
    
    possible_keys = set()
    alphabet = []
    for i in range(26):
        alphabet.append(chr(i + BASE))
    
    encrypted_message = "ZEJFOKHTMSRMELCPODWHCGAW"
    
    import itertools
    for i in range(1, 6):
        print "I={}".format(i)
        #iterate through every possible solution
        possibles = [''.join(j) for j in itertools.product(alphabet, repeat = i)]
        for key in possibles:
            output = ""
            index = 0
            for char in encrypted_message:
                output += convert(char, key, index, True)
                index += 1
            if "WELCOME" in output:
                print "Key: {}, Output: {}".format(key, output)
    

    One small cheat in the above code, originally I had it displaying all possible keys which contained the word THE. There were a lot of course, but in glancing over the list the actual key showed up and for the posted code instead looked for WELCOME.

    Output: KSGDGBJQBEQKKLGDG TODAYISMYBIRTHDAY I=1 I=2 I=3 Key: DAY, Output: WELCOMETOPROBLEMOFTHEDAY I=4 I=5

    reply permalink

  • Michae Von Heaven - 3 years, 8 months ago

    Damn it, didn't thought about the "THE" chear :\

    reply permalink

  • Michae Von Heaven - 3 years, 8 months ago

    I've brute forced up to 3 letter password, here are the results: 1 letter 2 lletters 3 letters

    reply permalink

  • CF - 3 years, 8 months ago

    Perl: `#!/usr/bin/perl use strict;

    my $encryption="reddit"; my $cleartext="todayismybirthday"; my $encrypted;

    for( my $i = 0 ; $i < length($cleartext) ; $i ++ ) { my $chr = ord(substr($cleartext,$i,1)) - 97; my $key = ord(substr($encryption,$i % length($encryption), 1)) - 97; my $enc = chr((($chr+$key) % 26) + 97); $encrypted = $encrypted . $enc; }

    print "$cleartext\n$encrypted\n"; `

    reply permalink

  • Anonymous - 3 years, 8 months ago

    I was curious about the brute force approach so I wrote a program which systematically attempts keys and then matches the results against words > 4 chars long from a dictionary file.

    My approach looks like this (written in go):

    1) Read the dictionary file in (/usr/share/dict/web2 is what I used, on Debian testing)

    2) If a word is more than 4 chars long, create a new regexp object whose pattern is the lowercased word. If there's an error in compiling the regex (dictionary words with weird characters in it) skip it. Store this regex in a list, and then as the key to a map (with the original word as the value of the map).

    3) Via a recursive permutation function, get all of the keys up to and including MAX_KEY_LENGTH (in this case, I set it to 5 since that was in the problem parameter). So it does a-z, then aa-az, ba-bz... up until zzzzz.

    Each time you generate a key, use it to create a decrypt attempt of the ciphertext.

    4) Test this decrypt attempt against all of the regexes in the list. If there's a match, report it (along with the word stored in the regex - string map to show which word triggered the match).

    It didn't take especially long to find the message - eliminating all of the things that didn't contain dictionary words made it way easier to eyeball-grep the results and find the right answer.

    As for run time, I didn't let the program finish because I was tailing the results as they were coming through and stopped it when I hit the answer.

    The longer the max key length gets, the longer this will take (dramatically). 5 was already pushing it - 7 or 8 would take absolutely forever.

    reply permalink

  • Anonymous - 3 years, 8 months ago

    Can you paste your go code?

    reply permalink

  • Anonymous - 3 years, 8 months ago

    Here's complete encrypt/decrypt/all possible combinations in PHP for 3 letters. I was grepping the output (including up to 5 letter ciphers) for words like "SECRET" and "MESSAGE" etc... didn't think to try "WELCOME". :)

        <?
        $alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    
        function encryptVigenere ($key, $message) {
            global $alphabet;
            $encryptedMessage = '';
            $keyCounter=0;
            for ($i=0; $i < strlen($message); $i++) {
              $thisMessageLetter = substr($message, $i, 1);
              $thisKeyLetter = substr($key, $keyCounter % strlen($key), 1);
              $encryptedLetterPos = (strpos($alphabet, $thisKeyLetter) + strpos($alphabet, $thisMessageLetter)) % strlen($alphabet);
              $encryptedMessage .= substr($alphabet, $encryptedLetterPos, 1);
              $keyCounter ++;
            }
            return ($encryptedMessage);
        }
    
        function decryptVigenere ($key, $encryptedMessage) {
            global $alphabet;
            $decryptedMessage = '';
            $keyCounter=0;
            for ($i=0; $i < strlen($encryptedMessage); $i++) {
              $thisMessageLetter = substr($encryptedMessage, $i, 1);
              $thisKeyLetter = substr($key, $keyCounter % strlen($key), 1);
              $decryptedLetterPos = (strlen($alphabet) + (strpos($alphabet, $thisMessageLetter) - strpos($alphabet, $thisKeyLetter)))% strlen($alphabet);
              $decryptedMessage .= substr($alphabet, $decryptedLetterPos, 1);
              $keyCounter ++;
            }
            return ($decryptedMessage);
        }
    
        $secretMessage = 'ZEJFOKHTMSRMELCPODWHCGAW';
        $keyindex = 0;
        $key = '';
    
        echo "<pre>";
    
        $alphaArray = str_split($alphabet);
    
        foreach ($alphaArray as $p1) {
            foreach ($alphaArray as $p2) {
                foreach ($alphaArray as $p3) {
                            $key = $p1.$p2.$p3;
                            $tryDecrypt = decryptVigenere ($key, $secretMessage);
                            echo str_pad($key, 6); echo $tryDecrypt; echo "\n";
                }
            } 
        } 
        exit;
    
        ?>
    

    reply permalink

  • Anonymous - 3 years, 8 months ago

    Only did the first part in Haskell. Haven't got a clue about the rest.

    <code> import Control.Monad import Data.List

    f = fmap ((!!) alphabet . flip rem 26 . sum) . sequence . fmap (flip elemIndex alphabet) where alphabet = ['A'..'Z']

    main = do x <- getLine y <- getLine let z = sequence $ fmap f [[x, y] | (x, y) <- (zip y $ cycle x)] print z </code>

    reply permalink

  • Anonymous - 3 years, 8 months ago

    D solution for the encoding/decoding of a Vigenère cipher :

    import std.stdio;
    import std.string;
    import std.getopt;
    import std.range : lockstep;
    
    int main(string[] args)
    {
        string key, msg, cipher;
        getopt(args,
            "k|key", &key,
            "m|msg", &msg,
            "c|cipher", &cipher
        );
    
        if(msg == "")
            writeln(decode(key, cipher));
        else if(cipher == "")
            writeln(encode(key, msg));
    
    
        return 0;
    }
    
    string encode(string key, string msg)
    {
        string cipher;
        string charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
        do
        {
            key ~= key;
        }
        while(key.length < msg.length);
        key = key[0 .. msg.length];
    
        foreach(k, m; lockstep(key, msg))
        {
            int pos = charset.indexOf(k) + charset.indexOf(m);
            cipher ~= charset[pos < 26 ? pos : pos % 26];
        }
    
        return cipher;
    }
    
    string decode(string key, string cipher)
    {
        string msg;
        string charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
        do
        {
            key ~= key;
        }
        while(key.length < cipher.length);
        key = key[0 .. cipher.length];
    
        foreach(k, c; lockstep(key, cipher))
        {
            int pos = charset.indexOf(c) - charset.indexOf(k);
            if(pos > 26)
                pos %= 26;
            else if(pos < 0)
                pos += 26;
            msg ~= charset[pos];
        }
    
        return msg;
    }
    

    reply permalink

  • Tornchi - 3 years, 5 months ago

    My Solution also in D. Also includes a solution to the second part.

    // Vigenère cipher
    import std.stdio, std.algorithm, std.range, std.conv, std.string;
    import std.ascii: UPCASE = uppercase;
    
    string VigenèreEncoder(string aKey, string aMessage)
    { 
        return aMessage.zip(aKey.cycle).map!(a => ((a[0]+a[1])%26 + 'A').to!char).text;
    }
    
    string VigenèreDecoder(string aKey, string aMessage)
    {
        return aMessage.zip(aKey.cycle).map!(a => ((26+a[0]-a[1])%26 + 'A').to!char).text;
    }
    
    void main() 
    {
        auto key = "REDDIT";
        auto message = "TODAYISMYBIRTHDAY";
        auto secretMessage = "KSGDGBJQBEQKKLGDG";
    
        assert(key.VigenèreEncoder(message) == secretMessage);
        assert(key.VigenèreDecoder(secretMessage) == message);
        assert(key.VigenèreDecoder(key.VigenèreEncoder(message)) == message);
    
        // Decode the following message.  Hint- the key is 5 or less characters
        auto secret = "ZEJFOKHTMSRMELCPODWHCGAW";
    
        auto combo = cartesianProduct(UPCASE, UPCASE, UPCASE )
            .map!(a => a[0].to!string ~ a[1].to!string ~ a[2].to!string )
            .map!(a => a, a => VigenèreDecoder(a, secret))
    
            // Cull Decoded messages that use the least used letters
            .filter!(a =>  a[1].indexOf('X') == -1 
                        && a[1].indexOf('Z') == -1 
                        && a[1].indexOf('J') == -1  
                        && a[1].indexOf('Q') == -1 
                        && a[1].indexOf('V') == -1 
            )
            .filter!(a => a[1].indexOf("THE") >= 0)
            ;
    
        secret.writeln;
        foreach(i,j; combo)
            "%s (key == %s)".writefln(j,i);
    
    }
    

    reply permalink

  • James - 3 years, 8 months ago

    Here is my solution written in c# console for Part 1. <pre><code> using System; using System.Text;

    namespace Vigenère_cipher { class Program { static void Main(string[] args) { const string key = "REDDIT"; const string message = "TODAYISMYBIRTHDAY";

            string encoded = Encode(key, message);
        }
    
        private static string Encode(string key, string message)
        {
            var encoded = new StringBuilder(message.Length);
    
            int keyIndex = 0;
    
            for (int i = 0; i < message.Length; i++)
            {
                int keyValue = CreateAlphabeticalValueFromChar(key[keyIndex]);
                int messageValue = CreateAlphabeticalValueFromChar(message[i]);
    
                int encodedValue =  1+ (keyValue + messageValue) % 26;
    
                encoded.Append(CreateAlphabeticalValueFromInt(encodedValue));
    
                keyIndex = (keyIndex + 1)%key.Length;
            }
    
            return encoded.ToString();
        }
    
        private static int CreateAlphabeticalValueFromChar(char character)
        {
            return Char.ToLower(character) - 'a';
        }
    
        private static char CreateAlphabeticalValueFromInt(int character)
        {
            return (char) (('a' +  character)-1);
        }
    }
    

    } </code></pre>

    reply permalink

  • David - 3 years, 8 months ago

    an OO-style solution in Ruby.

    ```ruby class VigenereCipher def initialize(key) @key = key.downcase end

    def encode(message) cipher(message, :+) end

    def decode(message) cipher(message, :-) end

    private def index_for_char(char) char.ord - 'a'.ord end

    def char_for_index(index) ('a'.ord + index).chr end

    def cipher(message, direction) message.downcase! message.split('').map.with_index {|c, i| key_char = @key[i % @key.length] char_index = index_for_char(c).send(direction, index_for_char(key_char)) % 26 char_for_index(char_index) }.join end end

    class VigenereCipherCracker def initialize(key_max_length) @key_max_length = key_max_length end

    def crack(message) ([email protected]_max_length).each do |key_length| keys_of_length(key_length).each do |key| attempt = VigenereCipher.new(key).decode(message) return [attempt, key] if successful_attempt(attempt) end end end

    private def successful_attempt(attempt) puts attempt # TODO: verification of the attempt is out of scope for the prompt false end

    def keys_of_length(length) return [''] if length == 0 keys_of_length(length - 1).map {|shorter_key| ('a'..'z').map do |new_char| shorter_key + new_char end }.flatten end end ```

    reply permalink

  • David - 3 years, 8 months ago

    whoops, thought the markdown parser would take triple backticks for code blocks... let's see if it likes four spaces

    class VigenereCipher
      def initialize(key)
        @key = key.downcase
      end
    
      def encode(message)
        cipher(message, :+)
      end
    
      def decode(message)
        cipher(message, :-)
      end
    
      private
      def index_for_char(char)
        char.ord - 'a'.ord
      end
    
      def char_for_index(index)
        ('a'.ord + index).chr
      end
    
      def cipher(message, direction)
        message.downcase!
        message.split('').map.with_index {|c, i|
          key_char = @key[i % @key.length]
          char_index = index_for_char(c).send(direction, index_for_char(key_char)) % 26
          char_for_index(char_index)
        }.join
      end
    end
    
    class VigenereCipherCracker
      def initialize(key_max_length)
        @key_max_length = key_max_length
      end
    
      def crack(message)
        ([email protected]_max_length).each do |key_length|
          keys_of_length(key_length).each do |key|
            attempt = VigenereCipher.new(key).decode(message)
            return [attempt, key] if successful_attempt(attempt)
          end
        end
      end
    
      private
      def successful_attempt(attempt)
        puts attempt # TODO: verification of the attempt is out of scope for the prompt
        false
      end
    
      def keys_of_length(length)
        return [''] if length == 0
        keys_of_length(length - 1).map {|shorter_key|
          ('a'..'z').map do |new_char|
            shorter_key + new_char
          end
        }.flatten
      end
    end
    
    cipher = VigenereCipher.new('REDDIT')
    encoded = cipher.encode('TODAYISMYBIRTHDAY')
    puts "encoded to \"#{encoded}\""
    decoded = cipher.decode(encoded)
    puts "decoded to \"#{decoded}\""
    
    cracker = VigenereCipherCracker.new(5)
    cracker.crack('ZEJFOKHTMSRMELCPODWHCGAW')
    

    reply permalink

  • Pascal Seitz - 3 years, 8 months ago

    Javascript solution to encode a message

    var alphabet = ['a', 'b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'];

    function encrypt(key, string){

    key = key.toLowerCase();
    string = string.toLowerCase();
    
    var keyAsChar = matchKeyToString(string, key).split('');
    var stringAsChar = string.split('');
    
    var encryptedString = [];
    for (var i = 0; i < stringAsChar.length; i++) {
    
        var newIndex = (alphabet.indexOf(stringAsChar[i]) + alphabet.indexOf(keyAsChar[i])) %26;
        encryptedString.push(alphabet[newIndex]);
    }
    
    return encryptedString.join('');
    

    }

    reply permalink

  • Michael Mulqueen - 3 years, 8 months ago

    My Python code: https://gist.github.com/mmulqueen/9401026

    Cracks the code in about 8 seconds.

    reply permalink

  • K - 3 years, 8 months ago

    <pre> ordinal_difference = 65 def cipher(key, message): key = key.upper() lenkey = len(key)

    message = message.upper()
    result = ''
    
    for i in range(len(message)):
        cipher_index = (alpha_pos(key[i % lenkey]) + alpha_pos(message[i])) % 26
        result += chr(ordinal_difference + cipher_index)
    return result
    

    def alpha_pos(char): return ord(char) - ordinal_difference </pre>

    reply permalink

  • El Ninja - 3 years, 8 months ago

    Cracked it!

    Using a dictionary attack, with a multithreaded python application, here's the source:

    https://github.com/ibarrajo/problemoftheday-vigenere/blob/master/vigenere.py

    My plan was to sort all of the answers based on the score, but when I glanced at the console output, there it was =]

    reply permalink

  • Anonymous - 3 years, 8 months ago

    Fortran! http://pastebin.com/LtxrSHL3

    reply permalink

  • Anonymous - 3 years, 8 months ago

    Here is my working Python 2.7 code to create the cipher. Still working on being able to break one.

    <code>from string import ascii_lowercase

    def make_key(key,message):

    original_key,len_key = key, len(key)
    
    
    if len(key)>len(message):
        #if it's longer
        key = key[:len(message)]
    else:
        #if it's shorter
        for i in range(len(message)):
                if len(key)==len(message):
    
                    return key
    
    
                else:
    
                    key += original_key[i%len_key]
    

    def make_cipher(key, message): new_message = '' key, message = key.lower(),message.lower()

    letters = ascii_lowercase
    fullkey = make_key(key,message).lower()
    
    temp = zip(fullkey,message)
    
    
    for pair in temp:
    
        new_message += letters[sum((letters.find(pair[0]),letters.find(pair[1])))%26]
    return new_message.upper()
    

    print make_cipher('REDDIT','TODAYISMYBIRTHDAY')

    </code>

    reply permalink

  • Derek - 3 years, 8 months ago

    Here's my Ruby solution:

    def crypt(text, key)
      key = key.upcase
      key_index = 0
      text.upcase.bytes.collect do |b|
        b -= ?A
        k = key[key_index] - ?A
        key_index = (key_index + 1) % key.length
        ((b + k) % 26 + ?A).chr
      end.join
    end
    
    def crack(text, words)
      try_key = 'A'
      while try_key.length <= 5
        decrypt = crypt(text,try_key)
        candidates = []
        if words.count{|w| decrypt.include?(w) } > 2
          biggest = words.max{|a,b| (decrypt.include?(a) ? a.length : 0) <=> (decrypt.include?(b) ? b.length : 0)}
          candidates << "#{try_key}: #{crypt(text,try_key)} - #{biggest}"
          puts candidates.last
        end
        key_pos = try_key.length - 1
        loop do
          try_key[key_pos]+=1
          if try_key[key_pos] > ?Z
        try_key[key_pos] = 'A'
        key_pos -= 1
        if key_pos < 0
          try_key << 'A'
          break
        end
          else
        break
          end
        end
      end
      candidates.sort!{|a,b| b.length <=> a.length}[0..1000]
    end
    
    words = ["ABLE", "ABOUT", "ABOVE", "ACCESS", "ACTION", "ACTUALLY", "ADD", "ADDRESS", "ADVANCE", "AFTER", "AGAIN", "AGAINST", "AGO", "AGREE", "AIDS", "AIR", "ALAN", "ALBUM", "ALL", "ALLOW", "ALMOST", "ALONG", "ALREADY", "ALSO", "ALTHOUGH", "ALWAYS", "AMERICA", "AMERICAN", "AMERICANS", "AMIGA", "AMONG", "AMOUNT", "AND", "ANDREW", "ANOTHER", "ANSWER", "ANY", "ANYBODY", "ANYONE", "ANYTHING", "ANYWAY", "APPLE", "APPROPRIATE", "APR", "APRIL", "ARE", "AREA", "ARGUMENT", "AROUND", "ARPA", "ARTICLE", "ARTICLES", "ASK", "ASKED", "ASSUME", "ATT", "AUG", "AVAILABLE", "AWAY", "BACK", "BAD", "BARRY", "BASED", "BBS", "BECAUSE", "BECOME", "BEEN", "BEFORE", "BEHIND", "BEING", "BELIEVE", "BELL", "BELOW", "BERKELEY", "BEST", "BETTER", "BETWEEN", "BIG", "BILL", "BIT", "BITNET", "BLACK", "BOARD", "BOB", "BODY", "BOOK", "BOOKS", "BOTH", "BOX", "BREAK", "BSD", "BTW", "BUFFER", "BUSINESS", "BUT", "BUY", "CALIFORNIA", "CALL", "CALLED", "CALLS", "CAME", "CAN", "CANNOT", "CAR", "CARD", "CARE", "CASE", "CASES", "CAUSE", "CENTER", "CERTAIN", "CERTAINLY", "CHANCE", "CHANGE", "CHANGED", "CHANGES", "CHAR", "CHARACTER", "CHARACTERS", "CHECK", "CHILD", "CHILDREN", "CHINA", "CHINESE", "CHOICE", "CITY", "CLAIM", "CLASS", "CLEAR", "CLOSE", "CMU", "CODE", "COLOR", "COM", "COME", "COMES", "COMING", "COMMAND", "COMMENTS", "COMMON", "COMP", "COMPANY", "COMPLETE", "COMPLETELY", "COMPUTER", "CONSIDER", "CONSIDERED", "CONTACT", "CONTROL", "COPY", "CORRECT", "COST", "COULD", "COUNTRY", "COUPLE", "COURSE", "CREATE", "CULTURE", "CUP", "CURRENT", "CURRENTLY", "CUT", "DAILY", "DATA", "DATE", "DAVE", "DAVID", "DAY", "DAYS", "DEAD", "DEAL", "DEATH", "DEC", "DECIDED", "DECWRL", "DEDICATED", "DEFINE", "DEMAND", "DEPARTMENT", "DESIGN", "DEVELOPMENT", "DEVICE", "DID", "DIFFERENCE", "DIFFERENT", "DIFFICULT", "DIRECT", "DIRECTLY", "DIRECTORY", "DISCUSSION", "DISK", "DOES", "DOING", "DOMAIN", "DONE", "DOS", "DOUBT", "DOWN", "DRIVE", "DUE", "DURING", "EACH", "EARLY", "EASY", "EDU", "EFFECT", "EITHER", "ELSE", "END", "ENGLISH", "ENOUGH", "ENTIRE", "ENVIRONMENT", "ERROR", "ESPECIALLY", "ETC", "EVEN", "EVER", "EVERY", "EVERYONE", "EVERYTHING", "EVIDENCE", "EXACTLY", "EXAMPLE", "EXCEPT", "EXIST", "EXPECT", "EXPERIENCE", "FACT", "FAMILY", "FAR", "FAST", "FEB", "FEEL", "FEW", "FIELD", "FILE", "FILES", "FILM", "FIND", "FINE", "FIRST", "FOLKS", "FOLLOWING", "FOOD", "FOR", "FORCE", "FORM", "FORMAT", "FOUND", "FOUR", "FREE", "FRIEND", "FRIENDS", "FROM", "FRONT", "FULL", "FUN", "FUNCTION", "FUTURE", "GAME", "GAMES", "GENERAL", "GET", "GETS", "GETTING", "GIVE", "GIVEN", "GOD", "GOES", "GOING", "GOOD", "GOT", "GOV", "GOVERNMENT", "GREAT", "GROUP", "GROUPS", "GUESS", "GUN", "GUY", "HAD", "HALF", "HAND", "HAPPEN", "HAPPENED", "HARD", "HARDWARE", "HAS", "HAVE", "HAVING", "HEAD", "HEAR", "HEARD", "HELP", "HER", "HERE", "HIGH", "HIGHER", "HIM", "HIS", "HISTORY", "HIT", "HOLD", "HOME", "HOPE", "HOURLY", "HOURS", "HOUSE", "HOW", "HOWEVER", "HPLABS", "HUMAN", "IBM", "IDEA", "IDEAS", "IMPORTANT", "INC", "INCLUDE", "INCLUDING", "INFO", "INFORMATION", "INSTEAD", "INT", "INTEREST", "INTERESTED", "INTERESTING", "INTERFACE", "INTERNET", "INTO", "INVOLVED", "ISSUE", "ISSUES", "ITS", "ITSELF", "JAMES", "JAN", "JEFF", "JIM", "JOB", "JOE", "JOHN", "JUL", "JUN", "JUST", "KEEP", "KEY", "KILL", "KIND", "KNOW", "KNOWLEDGE", "KNOWN", "KNOWS", "LANGUAGE", "LARGE", "LAST", "LATER", "LAW", "LAWS", "LEARN", "LEAST", "LEAVE", "LEFT", "LEGAL", "LESS", "LET", "LEVEL", "LIFE", "LIGHT", "LIKE", "LIKELY", "LINE", "LINES", "LIST", "LITTLE", "LIVE", "LOCAL", "LONG", "LONGER", "LOOK", "LOOKING", "LOOKS", "LOST", "LOT", "LOTS", "LOVE", "LOW", "MAC", "MACHINE", "MACHINES", "MADE", "MAIL", "MAIN", "MAJOR", "MAKE", "MAKES", "MAKING", "MAN", "MANY", "MAR", "MARK", "MARKET", "MATTER", "MAY", "MAYBE", "MEAN", "MEANS", "MEMORY", "MEN", "MENTIONED", "MESSAGE", "MICHAEL", "MIGHT", "MIKE", "MIND", "MINE", "MINUTES", "MISC", "MIT", "MOD", "MODE", "MODEL", "MONEY", "MONTH", "MONTHS", "MORE", "MOST", "MOVE", "MOVIE", "MUCH", "MUSIC", "MUST", "MYSELF", "NAME", "NAMES", "NEAR", "NECESSARY", "NEED", "NEEDED", "NEEDS", "NET", "NETWORK", "NEVER", "NEW", "NEWS", "NEWSGROUP", "NEXT", "NICE", "NIGHT", "NON", "NORMAL", "NOT", "NOTE", "NOTHING", "NOV", "NOW", "NUMBER", "NUMBERS", "OBJECT", "OCT", "OFF", "OFTEN", "OLD", "ONCE", "ONE", "ONES", "ONLY", "OPEN", "OPINION", "OPINIONS", "ORDER", "ORIGINAL", "OTHER", "OTHERS", "OUR", "OUT", "OUTPUT", "OUTSIDE", "OVER", "OWN", "PAGE", "PAPER", "PART", "PARTICULAR", "PARTS", "PAST", "PAUL", "PAY", "PEOPLE", "PER", "PERFORMANCE", "PERHAPS", "PERSON", "PERSONAL", "PETER", "PHONE", "PLACE", "PLAY", "PLAYED", "PLAYING", "PLEASE", "POINT", "POINTS", "POLITICAL", "POSITION", "POSSIBLE", "POST", "POSTED", "POSTING", "POSTMASTER", "POWER", "PRESENT", "PRETTY", "PRICE", "PROBABLY", "PROBLEM", "PROBLEMS", "PROCESS", "PRODUCT", "PROGRAM", "PROGRAMS", "PROVIDE", "PUBLIC", "PUT", "QUALITY", "QUESTION", "QUESTIONS", "QUITE", "RADIO", "RATE", "RATHER", "READ", "READING", "REAL", "REALLY", "REASON", "REASONABLE", "REASONS", "REC", "RECEIVED", "RECENT", "RECENTLY", "RECORD", "RELATED", "RELEASE", "RELIGION", "REMEMBER", "REQUEST", "REQUIRED", "RESEARCH", "RESPONSE", "RESPONSES", "REST", "RESULT", "RESULTS", "RETURN", "RICHARD", "RIGHT", "RIGHTS", "ROBERT", "ROOM", "ROOT", "RULES", "RUN", "RUNNING", "RUTGERS", "SAID", "SAME", "SAN", "SAVE", "SAW", "SAY", "SAYING", "SAYS", "SCHOOL", "SCI", "SCIENCE", "SCOTT", "SCREEN", "SECOND", "SEE", "SEEM", "SEEMS", "SEEN", "SELF", "SEND", "SENSE", "SENT", "SEP", "SERIES", "SERVER", "SERVICE", "SET", "SEVERAL", "SEX", "SHE", "SHORT", "SHOULD", "SHOW", "SHOWS", "SIDE", "SIMILAR", "SIMPLE", "SIMPLY", "SINCE", "SINGLE", "SITE", "SITUATION", "SIZE", "SMALL", "SOC", "SOCIETY", "SOFTWARE", "SOLUTION", "SOME", "SOMEONE", "SOMETHING", "SOMETIMES", "SOON", "SORT", "SOUND", "SOUNDS", "SOURCE", "SOURCES", "SPACE", "SPECIAL", "SPECIFIC", "SPEED", "SPW", "STANDARD", "START", "STARTED", "STATE", "STATEMENT", "STEVE", "STILL", "STOP", "STORY", "STRING", "STUDENTS", "STUFF", "SUBJECT", "SUCH", "SUGGEST", "SUN", "SUPPORT", "SUPPOSED", "SURE", "SYS", "SYSTEM", "SYSTEMS", "TAKE", "TAKEN", "TAKES", "TAKING", "TALK", "TALKING", "TAPE", "TEAM", "TELL", "TERM", "TEST", "TEXT", "THAN", "THANKS", "THAT", "THE", "THEIR", "THEM", "THEMSELVES", "THEN", "THERE", "THESE", "THEY", "THING", "THINGS", "THINK", "THINKING", "THIS", "THOSE", "THOUGH", "THOUGHT", "THREE", "THROUGH", "TIME", "TIMES", "TODAY", "TOGETHER", "TOLD", "TOM", "TOO", "TOOK", "TOP", "TOTAL", "TRIED", "TRUE", "TRY", "TRYING", "TURN", "TWO", "TYPE", "UCBVAX", "UNDER", "UNDERSTAND", "UNIVERSITY", "UNIX", "UNLESS", "UNTIL", "UPON", "USA", "USE", "USED", "USEFUL", "USER", "USERS", "USES", "USING", "USR", "USUALLY", "UUCP", "UUNET", "VALUE", "VARIOUS", "VERSION", "VERY", "VIA", "VIEW", "VOTE", "WANT", "WANTED", "WANTS", "WAR", "WAS", "WATER", "WAY", "WEEK", "WEEKS", "WELL", "WENT", "WERE", "WHAT", "WHATEVER", "WHEN", "WHERE", "WHETHER", "WHICH", "WHILE", "WHITE", "WHO", "WHOLE", "WHY", "WILL", "WILLING", "WINDOW", "WISH", "WITH", "WITHIN", "WITHOUT", "WOMAN", "WOMEN", "WORD", "WORDS", "WORK", "WORKING", "WORKS", "WORLD", "WORTH", "WOULD", "WRITE", "WRITES", "WRITING", "WRITTEN", "WRONG", "WROTE", "YEAR", "YEARS", "YES", "YET", "YORK", "YOU", "YOUR", "YOURSELF"]
    
    puts crypt('TODAYISMYBIRTHDAY','REDDIT')
    
    puts crack('ZEJFOKHTMSRMELCPODWHCGAW',words).inspect
    

    The cracking algorithm uses a word list to check for matches - the word list is culled from a "most popular words on the internet" list I found, and pared down by removing words containing apostrophes and words two letters or shorter. It sorts potential candidates based on the longest word found and returns the first 1000. My thinking was that the longer the word, the less likely it is to be a fluke.

    However, it turns out this step is unnecessary. Under manual inspection the result comes up almost immediately, and it's not necessary to continue.

    reply permalink

  • Dave - 3 years, 8 months ago

    Here is my working Python 2.7 code to create the cipher. Still working on being able to break one.

    <pre><code>from string import ascii_lowercase

    def make_key(key,message):

    original_key,len_key = key, len(key)
    
    
    if len(key)>len(message):
        #if it's longer
        key = key[:len(message)]
    else:
        #if it's shorter
        for i in range(len(message)):
                if len(key)==len(message):
    
                    return key
    
    
                else:
    
                    key += original_key[i%len_key]
    

    def make_cipher(key, message): new_message = '' key, message = key.lower(),message.lower()

    letters = ascii_lowercase
    fullkey = make_key(key,message).lower()
    
    temp = zip(fullkey,message)
    
    
    for pair in temp:
    
        new_message += letters[sum((letters.find(pair[0]),letters.find(pair[1])))%26]
    return new_message.upper()
    

    print make_cipher('REDDIT','TODAYISMYBIRTHDAY')

    </code></pre>

    reply permalink

  • paluche - 3 years, 8 months ago

    Java:

    public class Cipher {
    
        public static void main(String args[]) {
    
            String key = "reddit";
            String msg = "todayismybirthday";
            String alpha = "abcdefghijklmnopqrstuvwxyz";
            String expected= "ksgdgbjqbeqkklgdg";
    
            char[] msgChars = msg.toCharArray();
    
            for (int i = 0; i < msg.length(); i++) msgChars[i] = alpha.charAt(((alpha.indexOf((msgChars[i])) + alpha.indexOf((key.charAt(i % key.length())))) % 26));
    
            System.out.println(expected);
            System.out.println(msgChars);
    
        }
    }
    

    reply permalink

  • im not telling you - 3 years, 8 months ago

    C# handling nulls and some other cases....sorry didn't know what the procedure is when the key has values outside 'A' - 'Z'...

    public string Encrypt(string key, string text) { return string.Concat((text ?? "").ToUpper().Select((ch, i) => (ch < 65 || ch > 90) ? ch : (char)(((string.IsNullOrWhiteSpace(key) ? 65 : key.ToUpper()[i % key.Length]) + ch - 130) % 26 + 65))); }

    reply permalink

  • Jacob - 3 years, 8 months ago

    Well, once I had encryption and decryption built, and possible key lengths known (1, 2, 3, 4), I figured the next problem would be to find out when I found the key - and I went with a full dictionary check on the decoded string.

    I hadn't made any assumptions on whether the key would be a word so I did it brute force and checked each decoded string against a subset of a dictionary, leaving me with about 400,000 words to check each output against.

    Once a second I output a sorted list of the decoded strings that have words in them, including the words it matched against, and the key. It takes about 6 minutes, 30 seconds to try 17,576 keys using multi-threaded word search on my quad-core Intel 2500K. It's slow but I'm sure I can do a lot to improve performance, especially by making my own match algorithm to make searching more efficient.

    reply permalink

  • Jacob - 3 years, 8 months ago

    Got it down to 1.7 seconds now, brute forcing all keys between AAA and ZZZ, that was fun. Thanks Max!

    reply permalink

  • Anonymous - 3 years, 8 months ago

    Here is a solution in C, doesn't crack the message though but bruteforces a list of keys and messages. #include<stdio.h> #include<ctype.h>

    #define ASCII_START 65
    #define MAX_KEY_LENGTH 5
    
    void encode(char * key, char * message);
    void crack(char * cipher);
    void string_toupper(char * string);
    int string_size(char * string);
    void string_to_int_array(int length, char * string, int * array);
    void int_array_to_string(int length, int * string, char * array);
    
    int main(int argc, char * argv[]) {
        if(argc == 2){
            crack(argv[1]);
        }else if(argc == 3){
            encode(argv[1], argv[2]);
        }
        return 0;
    }
    
    void encode(char * key, char * message) {
        printf("Encoding\n");
    
        string_toupper(key);
        string_toupper(message);
        printf("Key: %s Message: %s\n", key, message);
    
        int ki = 0;
        int mi = 0;
        int key_length = string_size(key);
        int message_length = string_size(message);
        char encoded_message[message_length];
        while(message[mi] != 0) {
            encoded_message[mi] = ((message[mi] - ASCII_START) +
                                  (key[ki] - ASCII_START)) % 26 + ASCII_START;
            ++mi;
            ki = (ki + 1)%key_length;
        }
        encoded_message[mi] = 0; // Terminate string
        printf("Encoded message is: %s\n", encoded_message);
    }
    
    void decode(char * key, char * cipher) {
        int ki = 0;
        int mi = 0;
        int key_length = string_size(key);
        int cipher_length = string_size(cipher);
        char decoded_message[cipher_length];
        while(cipher[mi] != 0) {
            decoded_message[mi] = ((cipher[mi] - ASCII_START) -
                                  (key[ki] - ASCII_START)) % 26 + ASCII_START;
            ++mi;
            ki = (ki + 1)%key_length;
        }
        decoded_message[mi] = 0; // Terminate string
        printf("%s\n", decoded_message);
    }
    
    void crack(char * cipher) {
        printf("Cracking\n");
    
        string_toupper(cipher);
        printf("Cipher: %s\n", cipher);
    
        int cipher_length = string_size(cipher);
        int int_cipher[cipher_length];
        string_to_int_array(cipher_length, cipher, int_cipher);
        int key[MAX_KEY_LENGTH];
        char key_string[MAX_KEY_LENGTH];
        key[0] = 1;
        key[1] = 0;
        key[2] = 0;
        key[3] = 0;
        key[4] = 0;
        key[5] = 0;
        while(1){
            if(key[0] == 26) {
                key[0] = 1;
                if(key[1] == 26) {
                    key[1] = 1;
                    if(key[2] == 26) {
                        key[2] = 1;
                        if(key[3] == 26) {
                            key[3] = 1;
                            if(key[4] == 26) {
                                key[4] = 1;
                                break;
                            }else{
                                key[4] += 1;
                            }
                        }else{
                            key[3] += 1;
                        }
                    }else{
                        key[2] +=1;
                    }
                }else{
                    key[1] += 1;
                }
            }else{
                key[0] += 1;
            }
            int_array_to_string(MAX_KEY_LENGTH, key, key_string);
            printf("key: %s\n", key_string);
            decode(key_string, cipher);
        }
    }
    
    void string_toupper(char * string) {
        int i = 0;
    
        // Make all chars uppercase
        while(string[i] != 0) {
            string[i] = toupper(string[i]);
            ++i;
        }
    }
    
    int string_size(char * string) {
        int i = 0;
        do{
            ++i;
        }while(string[i] != 0);
        return i;
    }
    
    void string_to_int_array(int length, char * string, int * array) {
        int i;
        for(i = 0; i < length; ++i) {
            array[i] = string[i] - ASCII_START + 1;
        }
    }
    
    void int_array_to_string(int length, int * array, char * string) {
        int i = 0;
        for(i = 0; i < length; ++i) {
            if(array[i] == 0){
                string[i] = 0;
                break;
            }
            string[i] = array[i] + ASCII_START - 1;
        }
    }
    

    reply permalink

  • Alex - 3 years, 8 months ago

    Complete solution for parts 1 and 2 in C

    #include <stdio.h>
    #include <string.h>
    #include <regex.h>
    #include <stdlib.h>
    #include <errno.h>
    
    /**
     * Lists the top matches for keys to crack a message encrypted using
     * the Vigenere cypher.  The program iterates through keys, generates
     * the decrypted message, then scores it by counting the number of
     * consonant-vowel-consonant regex matches.  A top-10 list of matches
     * is maintained and displayed once the program runs through
     * completion.
     */
    
    typedef struct
    {
       char key[6];
       char decoded[31];
       int score;
    } Candidate_t;
    
    typedef struct
    {
       Candidate_t *candidates;
       int n;
    } Database_t;
    
    void die(const char *message)
    {
       if (errno)
          perror(message);
       else
          printf("ERROR: %s\n", message);
    
       exit(1);
    }
    
    Candidate_t *Candidate_create(char *key, char *decoded, int score)
    {
       Candidate_t *candidate = malloc(sizeof *candidate);
    
       strncpy(candidate->key, key, strlen(key) + 1);
    
       strncpy(candidate->decoded, decoded, strlen(decoded) + 1);
    
       candidate->score = score;
    
       return candidate;
    }
    
    void Candidate_destroy(Candidate_t *candidate)
    {
       free(candidate);
    }
    
    void Candidate_print(Candidate_t *candidate)
    {
       printf("%d %s %s\n", candidate->score, candidate->key, candidate->decoded);
    }
    
    void Candidate_swap(Candidate_t *a, Candidate_t *b)
    {
       Candidate_t temp;
       temp = *a;
       *a = *b;
       *b = temp;
    }
    
    int Candidate_transfer(Candidate_t *c, Database_t *d)
    {
       int rank = -1;
       int score = c->score;
       int n = d->n;
    
       // If candidate scores better than the lowest scoring in the
       // database, replace the lowest scorer with our candidate.
       if (score > d->candidates[n-1].score)
       {
          d->candidates[n-1] = *c;
       }
       else
       {
          Candidate_destroy(c);
          return -1;
       }
       // Keep swapping the candidate up in rank until it is correctly ranked
       int i;
       for (i = d->n - 2; i >= 0; i--)
       {
          if (score > d->candidates[i].score)
          {
             rank = i;
             Candidate_swap(&d->candidates[i], &d->candidates[i + 1]);
          }
          else
          {
             break;
          }
       }
       Candidate_destroy(c);
       return rank;
    }
    
    Database_t *Database_create(int n)
    {
       Database_t *database = malloc(sizeof *database);
       if (!database) die("Memory error");
    
       database->candidates = malloc(n * sizeof *(database->candidates));
       if (!database->candidates) die("Memory error");
    
       database->n = n;
    
       int i = 0;
       for (i = 0; i < n; i++)
       {
          Candidate_t candidate = {0};
          database->candidates[i] = candidate;
       }
       return database;
    }
    
    void Database_destroy(Database_t *database)
    {
       if (database)
       {
          if (database->candidates)
          {
             free(database->candidates);
          }
          free(database);
       }
    }
    
    void Database_print(Database_t *database)
    {
       int i = 0;
       for (i = 0; i < database->n; i++)
       {
          Candidate_print(&(database->candidates[i]));
       }
    }
    
    int mod(int x, int y)
    {
        if (-13/5 == -2 && (x < 0) != (y < 0) && x%y != 0)
            return x%y + y;
        else
            return x%y;
    }
    
    int encrypt(int a, int b)
    {
       return mod(a + b, 26);
    }
    
    int decrypt(int a, int b)
    {
       return mod(a - b, 26);
    }
    
    typedef int (*convert_cb)(int a, int b);
    
    void code(char *key, char *input, char *output, convert_cb convert)
    {
       int inputLen = strlen(input);
       int keyLen = strlen(key);
       int i;
       for (i = 0; i < inputLen; i++)
       {
          char temp;
    
          temp = input[i] - 'a';
          temp = convert(temp, key[i % keyLen] - 'a');
          temp += 'a';
    
          output[i] = temp;
       }
       output[inputLen] = '\0';
    }
    
    int countRegex(regex_t *regex, char *s)
    {
       int score = 0;
       regmatch_t match[1] = {0};
    
       while (regexec(regex, s, 1, match, 0) == 0)
       {
          score++;
          s = s + match[0].rm_so + 1;
       }
       return score;
    }
    
    char alphabet[] = "abcdefghijklmnopqrstuvwxyz";
    
    void generateWords(char *build, int len, int pos, char *message, regex_t *regex, Database_t *d)
    {
       if (pos == len)
       {
          char *key = malloc(strlen(build) + 1);
          strncpy(key, build, strlen(build) + 1);
    
          char *decoded = malloc(strlen(message) + 1);
          code(key, message, decoded, decrypt);
    
          int score = countRegex(regex, decoded);
    
          Candidate_t *candidate = Candidate_create(key, decoded, score);
          Candidate_transfer(candidate, d);
    
          free(key);
          free(decoded);
    
          return;
       }
    
       int i;
       for (i = 0; i < strlen(alphabet); i++)
       {
          build[pos] = alphabet[i];
          generateWords(build, len, pos + 1, message, regex, d);
       }
    }
    
    int main(int arc, char *argv[])
    {
       char *myEncrypted = "zejfokhtmsrmelcpodwhcgaw";
       char build[6] = {0};
    
       Database_t *database = Database_create(10);
    
       regex_t regex;
       regcomp(&regex, "[bcdfghjklmnpqrtsvwxyz][aeiou][bcdfghjklmnpqrtsvwxyz]", 0);
    
       generateWords(build, 5, 0, myEncrypted, &regex, database);
    
       regfree(&regex);
    
       Database_print(database);
    
       Database_destroy(database);
    
       return 0;
    }
    

    reply permalink

  • Alex - 3 years, 8 months ago

    I copied and pasted the wrong code: Need to loop over generateWords from len = 1 to 5... forgot to include that. This could be optimized in the recursive generateWords functions since all n-1 length strings are a subset of n length strings.

    reply permalink

  • Rahul Sharma - 3 years ago

    below is the encryption code in JAVA Ill also try to do the decryption part

    package vignerecipher;

    public class Main {

    public static void main(String[] args) {
    
        String key="REDDIT";
        String message="TODAYISMYBIRTHDAY";
        int digest[]=new int[100];
        char new_key[]=new char[100];
        char key_arr[]=key.toCharArray();
        char message_arr[]=message.toCharArray();
        if(key.length()<message.length())
        {for(int i=0;i<message.length();i++)
        {
            new_key[i]=key_arr[i%key.length()];
        }
        }
    
        for(int i=0;i<message.length();i++)
        {
            int m=(int)new_key[i]%65;
            System.out.println(m);
    
            int n=(int)message_arr[i]%65;
            System.out.println(n);
            digest[i]=((m+n)%26)+65;
        }
        for(int i=0;i<message.length();i++){
        System.out.println((char)digest[i]);}
    }
    

    }

    reply permalink

  • Anonymous - 2 years, 10 months ago

    welcometoproblemoftheday

    reply permalink

  • ١юὸⅻѾἄTṂW⇑ - 2 years, 2 months ago

    this is a very simple crack, using a certain method (http://www.guballa.de/vigenere-solver) we know the key is day and the answer is WELCOMETOPROBLEMOFTHEDAY

    reply permalink

  • 0x7c00 - 1 year, 11 months ago

    Key = DAY

    Message = welcometoproblemoftheday

    reply permalink

Content curated by @MaxBurstein