# Problem of the DayA 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!

• Anonymous - 3 years, 2 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.

• Anonymous - 3 years, 2 months ago

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

Runtime is irrelevant.

• J. D. - 3 years, 2 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>

• Max Burstein - 3 years, 2 months ago

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

• Anonymous - 3 years, 2 months ago

I think is 'mod 26', no?

• Max Burstein - 3 years, 2 months ago

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

• Anonymous - 3 years, 2 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
``````
• Anonymous - 3 years, 2 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.

• Larry - 3 years, 2 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?'.

• Anonymous - 3 years, 2 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?

• Crow - 3 years, 2 months ago

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

• Anonymous - 3 years, 2 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('');

• Ezekiel B - 3 years, 2 months ago

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

• Anonymous - 3 years, 2 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

• Anonymous - 3 years, 2 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
``````
• Cautious Poke - 3 years, 2 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);
}
}
``````
• Anonymous - 3 years, 2 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>";
?>
``````
• Anonymous - 3 years, 2 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))))
``````
• Egon Wilzer - 3 years, 2 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)));
}
``````
• Michae Von Hell - 3 years, 2 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>

• Michae Von Heaven - 3 years, 2 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>

• Anonymous - 3 years, 2 months ago

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

• icendoan - 3 years, 2 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.

• Grant McConnaughey - 3 years, 2 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}

• Luke Brooks - 3 years, 2 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])) ] )

• Ben Lucyk - 3 years, 2 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?! :)

• rekh127 - 3 years, 2 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;
}
``````
• AndreaM - 3 years, 2 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("");
}
``````
• factorial720 - 3 years, 2 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

• Michae Von Heaven - 3 years, 2 months ago

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

• Michae Von Heaven - 3 years, 2 months ago

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

• CF - 3 years, 2 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"; `

• Anonymous - 3 years, 2 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.

• Anonymous - 3 years, 2 months ago

Can you paste your go code?

• Anonymous - 3 years, 2 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;

?>
``````
• Anonymous - 3 years, 2 months ago

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

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>

• Anonymous - 3 years, 2 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;
}
``````
• Tornchi - 2 years, 11 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);

}
``````
• James - 3 years, 2 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>

• David - 3 years, 2 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 ```

• David - 3 years, 2 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')
``````
• Pascal Seitz - 3 years, 2 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('');
``````

}

• Michael Mulqueen - 3 years, 2 months ago

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

Cracks the code in about 8 seconds.

• K - 3 years, 2 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>

• El Ninja - 3 years, 2 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 =]

• Anonymous - 3 years, 2 months ago

Fortran! http://pastebin.com/LtxrSHL3

• Anonymous - 3 years, 2 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>

• Derek - 3 years, 2 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

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.

• Dave - 3 years, 2 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>

• paluche - 3 years, 2 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);

}
}
``````
• im not telling you - 3 years, 2 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))); }```

• Jacob - 3 years, 2 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.

• Jacob - 3 years, 2 months ago

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

• Anonymous - 3 years, 2 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;
}
}
``````
• Alex - 3 years, 2 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;
}
``````
• Alex - 3 years, 2 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.

• - 2 years, 6 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]);}
}
``````

}

• Anonymous - 2 years, 4 months ago

welcometoproblemoftheday

• ١юὸⅻѾἄTṂW⇑ - 1 year, 8 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

• 0x7c00 - 1 year, 4 months ago

Key = DAY

Message = welcometoproblemoftheday

Content curated by @MaxBurstein