Problem of the Day -- Vigenère cipher

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, 9 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 - 10 years, 9 months ago
The goal is "to try and implement something to crack the message".

Runtime is irrelevant.

reply permalink
J. D. - 10 years, 9 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 - 10 years, 9 months ago

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

reply permalink
Anonymous - 10 years, 9 months ago
I think is 'mod 26', no?

reply permalink
Max Burstein - 10 years, 9 months ago

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

reply permalink

Anonymous - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 months ago
You're indexing the alphabet starting from 1. He's indexing it starting from 0.

reply permalink
Anonymous - 10 years, 9 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 - 10 years, 9 months ago
(17 + 19) mod 26 = 10, which does then translate to K. Thinking that was another typo.

reply permalink
Anonymous - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 months ago
<script src="https://gist.github.com/anonymous/9399359.js"></script>

reply permalink

icendoan - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 months ago
Damn it, didn't thought about the "THE" chear :\

reply permalink
Michae Von Heaven - 10 years, 9 months 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, 9 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 - 10 years, 9 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 - 10 years, 9 months ago
Can you paste your go code?

reply permalink

Anonymous - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 6 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, 9 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 - 10 years, 9 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) (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, 9 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)
    (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, 9 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 - 10 years, 9 months ago
My Python code: https://gist.github.com/mmulqueen/9401026

Cracks the code in about 8 seconds.

reply permalink

K - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 months ago
Fortran! http://pastebin.com/LtxrSHL3

reply permalink

Anonymous - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 9 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 - 10 years, 1 month 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, 11 months ago
welcometoproblemoftheday

reply permalink
١юὸⅻѾἄTṂW⇑ - 9 years, 3 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, 12 months ago
Key = DAY

Message = welcometoproblemoftheday

reply permalink

Content curated by @MaxBurstein