# Decipher a Vigenère ciphertext

The Vigenère cipher was a simple polyalphabetic cipher that basically applied one of several Caesar ciphers, according to a key. Bascially the letters in the key indicate which shifted alphabet to use. To that end there was a simple tool, called the Vigenère square: Here each row is a separate alphabet, starting with the corresponding letter of the key. The columns then are used to determine the ciphered letter. Decryption works in very much the same fashion, only vice-versa.

Suppose we want to encrypt the string CODEGOLF. We also need a key. In this case the key shall be FOOBAR. When the key is shorter than the plaintext we extend it by repetition, therefore the actual key we use is FOOBARFO. We now look up the first letter of the key, which is F to find the alphabet. It starts, perhaps unsurprisingly, with F. Now we find the column with the first letter of the plaintext and the resulting letter is H. For the second letter we have O as the key letter and the plain text letter, resulting in C. Continuing that way we finally get HCRFGFQT.

Your task now is to decipher messages, given a key. However, since we have outgrown the 16th century and have computers we should at least support a slightly larger alphabet:

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789


The construction of the Vigenère square is still very much the same and the cipher still works in the same way. It's just a bit ... unwieldy to give here in full.

Input

Input is given on standard input as two separate lines of text, each terminated by a line break. The first line contains the key while the second contains the ciphertext.

Output

A single line, containing the deciphered message.

Winning condition

Since encryption is sometimes regarded as a weapon, the code should be short to facilitate easy smuggling. The shorter the better, as it reduces the likelihood of discovery.

Sample input 1

Key
miQ2eEO


Sample output 1

Message


Sample input 2

ThisIsAKey
CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu


Sample output 2

ThisWorksEquallyWellWithNumbers123894576


A week has passed. The currently shortest solution has been accepted. For those interested, in our contest we had the following submissions and lengths:

130 – Python
195 – C
197 – C
267 – VB.NET

And our own solutions that weren't ranked with the others:

108 – Ruby
139 – PowerShell

• It seems that this can be useful to print the Vigenère square. Sep 21, 2016 at 15:54
• Theoretically, using this cipher with a non-repeating key the same length as the message makes it completely and utterly unbreakable. Oct 14, 2020 at 14:01

n%~.,@*\{$$123,97>91,65>+58,48>+:|?@|?\-|=}%\0<+  No tricks in this one! • +1 I went to bed thinking there must be a way to get this down to ~50, now I see it's possible but I probably would not have managed it any time soon Feb 8, 2011 at 20:43 ## MS-DOS 16bit .COM file - 87 bytes Base64 encoded binary (following this link for a decoder) v1cBi8/oQACJ/ovv6DkAi9msitAqF3MDgMI+gMJhgPp6dguA6jqA+lp2A4DqK80hO/d0IkM563TW69YsYXMIBCB9AgQrBBqqtAHNITwNdev+xLIKzSHD  • Usually you write short source code yourself for golfing. While probably not impossible, I somehow doubt it with this. – Joey Feb 14, 2011 at 8:20 • @Joey: What, you've never hand encoded machine code instructions! Just what do they teach youngsters these days! ;-) Feb 14, 2011 at 9:15 • Skizz: I did. Not in Base64, though ;) (we had a class a few years ago where we had to write programs for a Siemens 80C167 in assembler – and in the exams also assemble them into machine code. I thought about digging out that knowledge for the Assembler Quine task, but we had no output facilities [at least, they varied]). – Joey Feb 14, 2011 at 9:32 • @Joey: The Base64 is just a convenience for the other users on this site, it's easy to decode and save as a binary file (the link in the answer has that option). Feb 14, 2011 at 20:36 • Aah, sorry. I thought you'd have given the length of the Base64. Well, Chris once included arbitrary characters into a solution and just gave a hexdump besides his answer. I did similar in Weather forecast. – Joey Feb 14, 2011 at 20:44 ## APL (45) ∆[⍙⍳⍨¨⌽∘∆¨(⍴⍙←⍞)⍴1-⍨⍞⍳⍨∆←⎕D,⍨⎕A,⍨⎕UCS 96+⍳26]  Explanation: • ∆←⎕D,⍨⎕A,⍨⎕UCS 96+⍳26: generate the alphabet (numbers (⎕D) follow letters (⎕A) follow lowercase letters (⎕UCS 96+⍳26, the unicode values from 97 to 122). • 1-⍨⍞⍳⍨∆: read a line (the key), find the position of each character in the alphabet, and subtract one (arrays are one-based by default, so shifting by those values directly would shift the alphabet one too far). • (⍴⍙←⍞)⍴: read another line (the message), and repeat the indices of the key so that it has the length of the message. • ⌽∘∆¨: rotate the alphabet by the indices belonging to the key • ⍙⍳⍨¨: look up each character in the message in the corresponding shifted alphabet • ∆[...]: look up the given indices in the normal alphabet, giving the corresponding characters. ## Ruby - 132 127 122 109 100 characters a,b=*< c=*?a..?z,*?A..?Z,*?0..?9 (b.size-1).times{|i|><<c[c.index(b[i])-c.index(a[i%(a.size-1)])]}  • Use *< instead of <.to_a and inline the lambda to save another few bytes. – Ventero 5 mins ago – Joey Feb 8, 2011 at 8:41 • Thanks @Joey, I pulled that lambda out to save characters and somehow missed that it actually cost more. Feb 8, 2011 at 8:47 ## Python - 122 chars from string import* L=letters+digits R=raw_input K,T=R(),R() F=L.find print"".join(L[F(i)-F(j)]for i,j in zip(T,K*len(T)))  ## J, 65 characters v=:4 : 'a{~x(62|[:-/"1 a i.[,.#@[])y[a=.a.{~62{.;97 65 48+/i.26'  Doesn't completely meet the spec since it's defined as a verb rather than taking input, but I'm posting it anyway with the intention of fiddling with it at a later date. Usage:  'miQ2eEO' v 'Key' Message 'CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu' v 'ThisIsAKey' ThisWorksEquallyWellWithNumbers123894576  ## Perl, 95 chars Perl 5.010, run with perl -E: %a=map{_,n++}@a=(a..z,A..Z,0..9);@k=<>=~/./g; _=<>;s/./a[(a{&}-a{k[i++%@k]})%62]/ge;say  ## Python - 144143140136 125 characters Probably not the best, but hey: from string import* l=letters+digits r=l.find q=raw_input k=q() print"".join(l[(r(j)-r(k[i%len(k)]))%62]for i,j in enumerate(q()))  • Huh, I was about to post something just like that. You can assign raw_input to a variable, 3 or so chars. – Juan Feb 8, 2011 at 2:31 ## Golfscript - 65 chars Still needs to be golfed more. For now, T is the text, K is the Key, L is the list of letters n%):T,\~*:K;''26,{97+}%+.{32^}%10,{48+}%++:L;T{L\?K(L\?\:K;-L\=}%  ## K,81 61 k:0:0;,/(m!+('m)!+{(1_x),1#x}\m:,/.QaAn)[(#v)#k]?'v:0:0  . k)k:0:0;,/(m!+('m)!+{(1_x),1#x}\m:,/.QaAn)[(#v)#k]?'v:0:0 ThisIsAKey CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu "ThisWorksEquallyWellWithNumbers123894576"  ## Perl, 115 chars a=join'',@A=(a..z,A..Z,0..9);_=<>;chop;@K=split//;_=<>;s/./A[(index(a,&)-index(a,K[-%@K]))%@A]/ge;print  ## Golfscript - 92 characters n%~\.,:l;{0\{1+$$\}%\;}:&;26'a'*&26'A'*&+10'0'*&+\@.,,{.l%3$=4$?\2$=4$?\- 62%3$\>1<}%\;\;\;  Probably much longer than it needs to be. Still trying to get my head around GS. Heres the "ungolfed" and commented version n%~\.,:l; {0\{1$+\)\}%\;}:&; # This would be sortof an equivalent for range applied to strings
26'a'*&26'A'*&+10'0'*&+\@., # This mess generates the dictionary string,
# l = len(key)
# 0 dictionary (letters + digits)
# 1 key
# 2 text
{
# 3 index
.   #+1 Duplicate the index

# Find the index of the key letter
l%  #+1 Indice modulo key
3$#+2 Duplicate the key = #+1 Get the key letter 4$? #+1 Search the letters index

# Find the index of the text letter
\   #+1 Get the index
2$#+2 Get the text = #+1 Get the text letter 4$? #+0 Search the letters index

# 3 key index
# 4 letter index

\-   #+1 get the index of the new letter

62% #+1 wrap the index around the dictionary

3$#+2 Get the dictionary \> #+1 remove the first part of the dict around the target letter 1< #+1 remove everythin after }% \; \; \;  ## VBA, 288 Doesn't quite beat the listed VB.NET score (but I'm getting close): Sub h(k,s) v=Chr(0) Z=Split(StrConv("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789",64),v) a=Split(StrConv(s,64),v):b=Split(StrConv(k,64),v) For l=0 To Len(s)-1 j=l Mod Len(k) g=0 For i=0 To 62:g=g+i*((Z(i)=b(j))-(Z(i)=a(l))):Next x=x &Z(IIf(g<0,g+62,g)) Next s=x End Sub  Usage: Sub test() k = "ThisIsAKey" s = "CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu" h k, s MsgBox s End Sub  Thanks to Joey for the tip! • g=g+IIf(Z(i)=c,i,0)-IIf(Z(i)=d,i,0) would be one candidate I can spot. As well as trying out whether LF line endings are understood by VBA. At least one space in x=x & Z(g) could be left out too, I guess. – Joey Apr 3, 2013 at 5:15 • Another way of writing the line: g=g+i*((Z(i)=d)-(Z(i)=c))  (because True is −1 in VB). Could be that it works. – Joey Apr 3, 2013 at 5:30 • Thanks for the feedback, @Joey. I'll look for any other improvements and add that in. Apr 3, 2013 at 11:34 C,186 A bit late but .. (lines broken to avoid horizontal scrollbar). char a,*s,*t;k,j;main(int m,char**v) {for(;j<26;++j)a[j]=32|(a[j+26]=65+j), a[52+j]=48+j;while(*v) putchar(a[s=strchr(a,v[k++%strlen(v)]) ,t=strchr(a,*v++),s>t?t-s+62:t-s]);}  Nonbroken lines char a,*s,*t;k,j;main(int m,char**v){for(;j<26;++j)a[j]=32|(a[j+26]=65+j),a[52+j]=48+j;while(*v)putchar(a[s=strchr(a,v[k++%strlen(v)]),t=strchr(a,*v++),s>t?t-s+62:t-s]);}  A discussion about the process of golfing this code can be found here: http://prob-slv.blogspot.com/2013/04/code-golf.html ## JavaScript 248 var v= 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789' function d(k,c){var a,b,o,x a=k.charAt(0) x=v.indexOf(a) b=v.substr(x)+v.substring(0,x) o= v.charAt(b.indexOf(c.charAt(0))) k=k.substr(1)+a c=c.substr(1) return (c)?o+d(k,c):o}  ## Haskell (169) import List main=do c<-y;t<-y;putStrLn$map((k!!).(mod62))$zipWith(-)(g t)(cycle$g c)
k=['a'..'z']++['A'..'Z']++['0'..'9']
y=getLine
f(Just x)=x
g=map$f.(elemIndexk)  # J: 91 characters [:{&{.&t({&t"0&(({.t=.1|.^:(i.62)a.{~(97+i.26),(65+i.26),48+i.10)&i.)"0@:$~#)|:@(i."1.,"0)]


For example:

    g=:[:{&{.&t({&t"0&(({.t=.1|.^:(i.62)a.{~(97+i.26),(65+i.26),48+i.10)&i.)"0@:\$~#)|:@(i."1.,"0)]
'ThisIsAKey' g 'CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu'
ThisWorksEquallyWellWithNumbers123894576