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 - 10 years, 1 month 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 - 10 years, 1 month ago

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

    Runtime is irrelevant.

    reply permalink

  • J. D. - 10 years, 1 month 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 - 10 years, 1 month ago

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

    reply permalink

  • Anonymous - 10 years, 1 month ago

    I think is 'mod 26', no?

    reply permalink

  • Max Burstein - 10 years, 1 month ago

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

    reply permalink

  • Anonymous - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month ago

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

    reply permalink

  • Anonymous - 10 years, 1 month 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 - 10 years, 1 month ago

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

    reply permalink

  • Anonymous - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month ago

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

    reply permalink

  • icendoan - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month ago

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

    reply permalink

  • Michae Von Heaven - 10 years, 1 month ago

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

    reply permalink

  • CF - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month ago

    Can you paste your go code?

    reply permalink

  • Anonymous - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 9 years, 10 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 - 10 years, 1 month 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 - 10 years, 1 month 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) (1..@key_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 - 10 years, 1 month 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)
    (1..@key_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 - 10 years, 1 month 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 - 10 years, 1 month ago

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

    Cracks the code in about 8 seconds.

    reply permalink

  • K - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month ago

    Fortran! http://pastebin.com/LtxrSHL3

    reply permalink

  • Anonymous - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 10 years, 1 month 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 - 9 years, 5 months 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 - 9 years, 3 months ago

    welcometoproblemoftheday

    reply permalink

  • ١юὸⅻѾἄTṂW⇑ - 8 years, 7 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 - 8 years, 4 months ago

    Key = DAY

    Message = welcometoproblemoftheday

    reply permalink

Content curated by @MaxBurstein