Decipher a Vigenère ciphertext

Question

The Vigenère cipher was a simple polyalphabetic cipher that basically applied one of several Caesar ciphers, according to a key. Basically 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.

Task

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
146 – Haskell
195 – C
197 – C
267 – VB.NET

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

108 – Ruby
139 – PowerShell

Answer 1

Golfscript -- 48 chars

n%~.,@*\{\(123,97>91,65>+58,48>+:|?@|?\-|=}%\0<+

No tricks in this one!

Answer 2

MS-DOS 16bit .COM file - 87 bytes

Base64 encoded binary (following this link for a decoder)

v1cBi8/oQACJ/ovv6DkAi9msitAqF3MDgMI+gMJhgPp6dguA6jqA+lp2A4DqK80hO/d0IkM563TW69YsYXMIBCB9AgQrBBqqtAHNITwNdev+xLIKzSHD

Answer 3

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.

Answer 4

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)])]}

Answer 5

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)))

Answer 6

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

Answer 7

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

Answer 8

Python - 144 143 140 136 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()))

Answer 9

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\=}%

Answer 10

K,81 61

k:0:0;,/$(m!+(`$'m)!+{(1_x),1#x}\m:,/.Q`a`A`n)[(#v)#k]?'v:0:0

.

k)k:0:0;,/$(m!+(`$'m)!+{(1_x),1#x}\m:,/.Q`a`A`n)[(#v)#k]?'v:0:0
ThisIsAKey
CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu
"ThisWorksEquallyWellWithNumbers123894576"

Answer 11

Perl, 115 chars

$a=join'',@A=(a..z,A..Z,0..9);$_=<>;chop;@K=split//;$_=<>;s/./$A[(index($a,$&)-index($a,$K[$-[0]%@K]))%@A]/ge;print

Answer 12

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 
}%
\;
\;
\;

Answer 13

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!

Answer 14

C,186

A bit late but .. (lines broken to avoid horizontal scrollbar).

char a[99],*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[2])
putchar(a[s=strchr(a,v[1][k++%strlen(v[1])])
,t=strchr(a,*v[2]++),s>t?t-s+62:t-s]);}

Nonbroken lines

char a[99],*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[2])putchar(a[s=strchr(a,v[1][k++%strlen(v[1])]),t=strchr(a,*v[2]++),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

Answer 15

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}

Answer 16

Uiua, 42 characters

A←⊂/⊂⊞+"aA"⇡26+@0⇡10
&p⊏-∩(⊗∶A)↯△,∶&sc&scA

-4 thanks to Unrelated String

Answer 17

Haskell (169)

import List
main=do c<-y;t<-y;putStrLn$map((k!!).(`mod`62))$zipWith(-)(g t)(cycle$g c)
k=['a'..'z']++['A'..'Z']++['0'..'9']
y=getLine
f(Just x)=x
g=map$f.(`elemIndex`k)

Answer 18

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

Answer 19

Scala, 156 bytes

Golfed version. Try it online!

(K,T)=>{val L=('a'to'z')++('A'to'Z')++('0'to'9');T.zip(Stream.continually(K).flatten).map{case(i,j)=>L((L.indexOf(i)-L.indexOf(j)+L.size)%L.size)}.mkString}

Ungolfed version. Try it online!

object Main extends App {
  def transform(K: String, T: String): String = {
    val letters = ('a' to 'z') ++ ('A' to 'Z')
    val digits = '0' to '9'
    val L = letters ++ digits
    (T.zip(Stream.continually(K).flatten))
      .map { case (i, j) =>
        L((L.indexOf(i) - L.indexOf(j) + L.length) % L.length)
      }
      .mkString
  }

  val K = "Key"
  val T = "miQ2eEO"
  val result = transform(K, T)
  println(result)
}

Answer 20

Vyxal s, 136 bits^v2, 17 bytes

LẎZƛ÷kr₀Ǔ:£~ḟǓ∇_ḟ¥i

Try it Online!

Bitstring:

0110000111010001100100100100100010010101101010000010110100010111011110111110110000101100000011001010100000111000011100111110110100111001

Takes message then key

Explained

LẎZƛ÷kr₀Ǔ:£~ḟǓ∇_ḟ¥i­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁢⁡⁡‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌­
LẎ                   # ‎⁡Repeat the key to the length of the message
  Z                  # ‎⁢Zip each character in the message to the extended key
   ƛ                 # ‎⁣To each pair:
     kr₀Ǔ            # ‎⁤  Push the string a-zA-Z0-9
         :£          # ‎⁢⁡  and store a copy in the register
    ÷      ~ḟ        # ‎⁢⁢  Find the position of the key character, not popping the alphabet string
             Ǔ       # ‎⁢⁣  Rotate the alphabet string left that many times
    ÷         ∇_     # ‎⁢⁤  Put the message character at the top of the stack, followed by the rotated alphabet
                ḟ    # ‎⁣⁡  Find the index of the message character in that alphabet
                 ¥i  # ‎⁣⁢  And index into the original alphabet string
💎

Created with the help of Luminespire.