Crack a Vigenère Cipher

Question

A Vigenère Cipher is encrypted by repeating a keyword to be the length of the plaintext, and summing each character in that text with the corresponding letter in the plaintext modulo 26. (using A=0,B=1 etc.)

For example, if the keyword is LEMON and the plaintext is ATTACKATDAWN, then the key is repeated to form LEMONLEMONLE, which is summed with the plaintext to form the ciphertext, LXFOPVEFRNHR.

Write a program or function which, given a list of words and a ciphertext, outputs all possible plaintexts for that ciphertext, such that the plaintext is the concatenation of words in the list, and the key is also a word from the list.

All words use only upper-case letters A to Z.

Your code must run in polynomial time with respect to the total length of the ciphertext and words list.

Shortest code (in bytes) wins.

Example Inputs/Outputs

The input/output format for your program is flexible, but here I'm giving the list of words separated by commas followed by the ciphertext as input, and the output is the list of plaintexts separated by commas.

Inputs

LEMON,ATTACK,AT,DAWN,BUNNY
LXFOPVEFRNHR

A,AA,AAA,AAAA,AAAAA,AAAAAA,AAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA


XHQT,GIXIIR,QTIA,AZXO,KSECS,THIS,CIPHER,IS,EASY,TO,CRACK,CODE,GOLF
ZVTXIWAMKFTXKODDZCNWGQV

A,B,C,D,E,F,G,H,Z
DBCCBHF

A,AA
AAA

Outputs

ATTACKATDAWN

(none)

THISCIPHERISEASYTOCRACK,XHQTGIXIIRQTIAAZXOKSECS

BZAAZFD,CABBAGE,DBCCBHF

AAA

Answer 1

Doesn’t respect specifications – OCaml - 118 bytes

I’ll get back to it when I’ll have time on my hand.

open Char;;
fun m->List.map(fun k->String.mapi(fun i c->chr(65+(code c-code k.[i mod String.length k]+26)mod 26))m);;

- : string -> string list -> string list = <fun>

As the function type shows, the function expect as arguments:

• a string: the encoded message
• a list of strings: the keys

It returns a list of strings, the messages as decoded by each string in the same order.

The function is anonymous, you can call it by inserting putting it inside parentheses (i.e. 2 bytes) and entering its arguments as follows:

open Char;;
(fun m->List.map(fun k->String.mapi(fun i c->chr(65+(code c-code k.[i mod String.length k]+26)mod 26))m)"ZVTXIWAMKFTXKODDZCNWGQV"["XHQT";"GIXIIR";"QTIA";"AZXO";"KSECS";"THIS";"CIPHER";"IS";"EASY";"TO";"CRACK";"CODE";"GOLF"];;

Ungolfed

(* unshift the character x back to what it was before being shifted by k *)
(* Char.chr and Char.code translate from ASCII int to char and back      *)
(* '+ 26' because the modulo operator can return negative numbers -__-   *)
open Char;;
let unshift k x = chr ( 65 + (code x - code k + 26) mod 26 );;
(* Use the n-th character of the key to decrypt x, loops when necessary  *)
let unshiftWithKeyAtPos key n x = unshift key.[n mod String.length key] x;;

(* Maps unshiftWithKeyAtPos key i x for each position i in cipherText    *)
(* where x = cipherText.[i] is the i-th character of cipherText.         *)
let decrypt key cipherText = String.mapi (unshiftWithKeyAtPos key) cipherText;;

(* Maps decrypt cipherText key for each key in keyList                   *)
let tryHard cipherText keyList = List.map (fun key -> decrypt key cipherText) keyList;;

(* And finally, call the function                                        *)
let hiddenMessage = "LXFOPVEFRNHR";;
let keys = ["LEMON";"CODE";"GOLF"];;
tryHard hiddenMessage keys;;

Answer 2

Python 2.7 - 235

Example solution to start things off. Should be pretty easy to beat.
Input is given as a python tuple from stdin (ex. (["A","AA"],"AAA").

W,c=input();M={}
def s(t,r):M[t]=r;return r
g=lambda t:M[t]if t in M else not t or s(t,any(t.startswith(w)and g(t[len(w):])for w in W))
print filter(g,set(''.join(chr((ord(a)-ord(w[i%len(w)]))%26+65)for i,a in enumerate(c))for w in W))