Vigenère cipher/Cryptanalysis

Vigenère cipher/Cryptanalysis is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Given some text you suspect has been encrypted with a Vigenère cipher, extract the key and plaintext. There are several methods for doing this. See the Wikipedia entry for more information. Use the following encrypted text:

MOMUD EKAPV TQEFM OEVHP AJMII CDCTI FGYAG JSPXY ALUYM NSMYH
VUXJE LEPXJ FXGCM JHKDZ RYICU HYPUS PGIGM OIYHF WHTCQ KMLRD
ITLXZ LJFVQ GHOLW CUHLO MDSOE KTALU VYLNZ RFGBX PHVGA LWQIS
FGRPH JOOFW GUBYI LAPLA LCAFA AMKLG CETDW VOELJ IKGJB XPHVG
ALWQC SNWBU BYHCU HKOCE XJEYK BQKVY KIIEH GRLGH XEOLW AWFOJ
ILOVV RHPKD WIHKN ATUHN VRYAQ DIVHX FHRZV QWMWV LGSHN NLVZS
JLAKI FHXUF XJLXM TBLQV RXXHR FZXGV LRAJI EXPRV OSMNP KEPDT
LPRWM JAZPK LQUZA ALGZX GVLKL GJTUI ITDSU REZXJ ERXZS HMPST
MTEOE PAPJH SMFNB YVQUZ AALGA YDNMP AQOWT UHDBV TSMUE UIMVH
QGVRW AEFSP EMPVE PKXZY WLKJA GWALT VYYOB YIXOK IHPDS EVLEV
RVSGB JOGYW FHKBL GLXYA MVKIS KIEHY IMAPX UOISK PVAGN MZHPW
TTZPV XFCCD TUHJH WLAPF YULTB UXJLN SIJVV YOVDJ SOLXG TGRVO
SFRII CTMKO JFCQF KTINQ BWVHG TENLH HOGCS PSFPV GJOKM SIFPR
ZPAAS ATPTZ FTPPD PORRF TAXZP KALQA WMIUD BWNCT LEFKO ZQDLX
BUXJL ASIMR PNMBF ZCYLV WAPVF QRHZV ZGZEF KBYIO OFXYE VOWGB
BXVCB XBAWG LQKCM ICRRX MACUO IKHQU AJEGL OIJHH XPVZW JEWBA
FWAML ZZRXJ EKAHV FASMU LVVUT TGK

Letter frequencies for English can be found here.

Specifics for this task:

• Take only the ciphertext as input. You can assume it's all capitalized and has no punctuation, but it might have whitespace.
• Assume the plaintext is written in English.
• Find and output the key.
• Use that key to decrypt and output the original plaintext. Maintaining the whitespace from the ciphertext is optional.
• The algorithm doesn't have to be perfect (which may not be possible) but it should work when given enough ciphertext. The example above is fairly long, and should be plenty for any algorithm.

C++

Not guaranteed to give a 100% correct answer, but it works here. Requires C++0x.

<lang cpp>#include <iostream>

1. include <string>
2. include <vector>
3. include <map>
4. include <algorithm>

using namespace std;

class VigenereAnalyser { public:

 vector<double> targets;
 vector<double> sortedTargets;

 VigenereAnalyser(vector<double> targetFreqs)
 {
   targets = targetFreqs;
   sortedTargets = targets;
   sort(sortedTargets.begin(), sortedTargets.end());
 }

 vector<pair<char, double>> frequency(string input)
 {
   vector<pair<char, double>> out;
   for(char c = 'A'; c <= 'Z'; ++c)
     out.push_back(make_pair(c, 0));

   for(int i = 0; i < input.size(); ++i)
     ++out[input[i] - 'A'].second;

   return out;
 }

 double correlation(string input)
 {
   double out = 0.0;
   vector<pair<char, double>> freq = frequency(input);

   sort(freq.begin(), freq.end(), [](pair<char, double> u, pair<char, double> v)->bool
     { return u.second < v.second; });

   for(int i = 0; i < 26; ++i)
     out += freq[i].second * sortedTargets[i];

   return out;
 }

 pair<string, string> analyze(string input)
 {
   string cleaned;
   for(int i = 0; i < input.size(); ++i)
   {
     if(input[i] >= 'A' && input[i] <= 'Z')
       cleaned += input[i];
     else if(input[i] >= 'a' && input[i] <= 'z')
       cleaned += input[i] + 'A' - 'a';
   }

   string out;
   string key;

   int bestLength = 0;
   double bestCorr = -100.0;

   // Assume that if there are less than 20 characters per column, the key's too long to guess
   for(int i = 2; i < cleaned.size()/20; ++i)
   {
     vector<string> pieces(i);
     for(int j = 0; j < cleaned.size(); ++j)
       pieces[j % i] += cleaned[j];

     // The correlation seems to increase for smaller pieces/longer keys, so weigh against them a little
     double corr = -0.5*i;
     for(int j = 0; j < i; ++j)
       corr += correlation(pieces[j]);

     if(corr > bestCorr)
     {
       bestLength = i;
       bestCorr = corr;
     }
   }

   if(bestLength == 0)
     return make_pair("Text is too short to analyze", "");

   vector<string> pieces(bestLength);
   for(int i = 0; i < cleaned.size(); ++i)
     pieces[i % bestLength] += cleaned[i];

   vector<vector<pair<char, double>>> freqs;
   for(int i = 0; i < bestLength; ++i)
     freqs.push_back(frequency(pieces[i]));

   key = "";
   out = "";
   for(int i = 0; i < bestLength; ++i)
   {
     sort(freqs[i].begin(), freqs[i].end(), [](pair<char, double> u, pair<char, double> v)->bool
       { return u.second > v.second; });

     int m = 0;
     double corr, mCorr = 0.0;
     for(int j = 0; j < 26; ++j)
     {
       corr = 0.0;
       char c = 'A' + j;
       for(int k = 0; k < 26; ++k)
       {
         int d = (freqs[i][k].first - c + 26) % 26;
         corr += freqs[i][k].second * targets[d];
       }

       if(corr > mCorr)
       {
         m = j;
         mCorr = corr;
       }
     }

     key += m + 'A';
   }

   for(int i = 0; i < cleaned.size(); ++i)
     out += (cleaned[i] - key[i % key.length()] + 26) % 26 + 'A';

   return make_pair(out, key);
 }

};

int main() {

 string input = 
   "MOMUD EKAPV TQEFM OEVHP AJMII CDCTI FGYAG JSPXY ALUYM NSMYH"
   "VUXJE LEPXJ FXGCM JHKDZ RYICU HYPUS PGIGM OIYHF WHTCQ KMLRD"
   "ITLXZ LJFVQ GHOLW CUHLO MDSOE KTALU VYLNZ RFGBX PHVGA LWQIS"
   "FGRPH JOOFW GUBYI LAPLA LCAFA AMKLG CETDW VOELJ IKGJB XPHVG"
   "ALWQC SNWBU BYHCU HKOCE XJEYK BQKVY KIIEH GRLGH XEOLW AWFOJ"
   "ILOVV RHPKD WIHKN ATUHN VRYAQ DIVHX FHRZV QWMWV LGSHN NLVZS"
   "JLAKI FHXUF XJLXM TBLQV RXXHR FZXGV LRAJI EXPRV OSMNP KEPDT"
   "LPRWM JAZPK LQUZA ALGZX GVLKL GJTUI ITDSU REZXJ ERXZS HMPST"
   "MTEOE PAPJH SMFNB YVQUZ AALGA YDNMP AQOWT UHDBV TSMUE UIMVH"
   "QGVRW AEFSP EMPVE PKXZY WLKJA GWALT VYYOB YIXOK IHPDS EVLEV"
   "RVSGB JOGYW FHKBL GLXYA MVKIS KIEHY IMAPX UOISK PVAGN MZHPW"
   "TTZPV XFCCD TUHJH WLAPF YULTB UXJLN SIJVV YOVDJ SOLXG TGRVO"
   "SFRII CTMKO JFCQF KTINQ BWVHG TENLH HOGCS PSFPV GJOKM SIFPR"
   "ZPAAS ATPTZ FTPPD PORRF TAXZP KALQA WMIUD BWNCT LEFKO ZQDLX"
   "BUXJL ASIMR PNMBF ZCYLV WAPVF QRHZV ZGZEF KBYIO OFXYE VOWGB"
   "BXVCB XBAWG LQKCM ICRRX MACUO IKHQU AJEGL OIJHH XPVZW JEWBA"
   "FWAML ZZRXJ EKAHV FASMU LVVUT TGK";

 double fs[] = {0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 
   0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074};

 vector<double> english(&fs[0], &fs[26]);
 VigenereAnalyser va(english);
 pair<string, string> output = va.analyze(input);

 cout << "Key: " << output.second << endl << endl;
 cout << "Text: " << output.first << endl;

}</lang>

D

Works with: DMD 2.054

Translation of: C++

<lang d>import std.stdio, std.algorithm, std.typecons, std.string;

string[2] vigenereDecrypt(in double[] targetFreqs, string input) {

   enum size_t nchars = uppercase.length;
   double[] sortedTargets = targetFreqs.dup;
   sortedTargets.sort();

   Tuple!(char, double)[] frequency(string input) {
       Tuple!(char, double)[] result;
       foreach (char c; uppercase)
           result ~= tuple(c, 0.0);

       foreach (c; input)
           result[c - 'A'][1]++;
       return result;
   }

   double correlation(string input) {
       double result = 0.0;
       auto freq = frequency(input);
       sort!q{a[1] < b[1]}(freq);

       foreach (i; 0 .. nchars)
           result += freq[i][1] * sortedTargets[i];
       return result;
   }

   const string cleaned = input.toupper().removechars("^A-Z");
   size_t bestLength = 0;
   double bestCorr = -100.0;

   // Assume that if there are less than 20 characters
   // per column, the key's too long to guess
   foreach (i; 2 .. cleaned.length / 20) {
       auto pieces = new string[i];
       foreach (j, c; cleaned)
           pieces[j % i] ~= c;

       // The correlation seems to increase for smaller
       // pieces/longer keys, so weigh against them a little
       double corr = -0.5 * i;
       foreach (c; pieces)
           corr += correlation(c);

       if (corr > bestCorr) {
           bestLength = i;
           bestCorr = corr;
       }
   }

   if (bestLength == 0)
       return ["Text is too short to analyze", ""];

   auto pieces = new string[bestLength];
   foreach (i, c; cleaned)
       pieces[i % bestLength] ~= c;

   Tuple!(char, double)[][] freqs;
   foreach (c; pieces)
       freqs ~= frequency(c);

   string key;
   foreach (i; 0 .. bestLength) {
       sort!q{a[1] > b[1]}(freqs[i]);

       size_t m = 0;
       double maxCorr = 0.0;
       foreach (j; 0 .. nchars) {
           double corr = 0.0;
           char c = cast(char)('A' + j);
           foreach (k; 0 .. nchars) {
               int d = (freqs[i][k][0] - c + nchars) % nchars;
               corr += freqs[i][k][1] * targetFreqs[d];
           }

           if (corr > maxCorr) {
               m = j;
               maxCorr = corr;
           }
       }

       key ~= cast(char)(m + 'A');
   }

   string result;
   foreach (i, c; cleaned)
       result ~= cast(char)((c-key[i % $] + nchars) % nchars + 'A');
   return [key, result];

}

void main() {

   const encoded = "
       MOMUD EKAPV TQEFM OEVHP AJMII CDCTI FGYAG JSPXY ALUYM NSMYH
       VUXJE LEPXJ FXGCM JHKDZ RYICU HYPUS PGIGM OIYHF WHTCQ KMLRD
       ITLXZ LJFVQ GHOLW CUHLO MDSOE KTALU VYLNZ RFGBX PHVGA LWQIS
       FGRPH JOOFW GUBYI LAPLA LCAFA AMKLG CETDW VOELJ IKGJB XPHVG
       ALWQC SNWBU BYHCU HKOCE XJEYK BQKVY KIIEH GRLGH XEOLW AWFOJ
       ILOVV RHPKD WIHKN ATUHN VRYAQ DIVHX FHRZV QWMWV LGSHN NLVZS
       JLAKI FHXUF XJLXM TBLQV RXXHR FZXGV LRAJI EXPRV OSMNP KEPDT
       LPRWM JAZPK LQUZA ALGZX GVLKL GJTUI ITDSU REZXJ ERXZS HMPST
       MTEOE PAPJH SMFNB YVQUZ AALGA YDNMP AQOWT UHDBV TSMUE UIMVH
       QGVRW AEFSP EMPVE PKXZY WLKJA GWALT VYYOB YIXOK IHPDS EVLEV
       RVSGB JOGYW FHKBL GLXYA MVKIS KIEHY IMAPX UOISK PVAGN MZHPW
       TTZPV XFCCD TUHJH WLAPF YULTB UXJLN SIJVV YOVDJ SOLXG TGRVO
       SFRII CTMKO JFCQF KTINQ BWVHG TENLH HOGCS PSFPV GJOKM SIFPR
       ZPAAS ATPTZ FTPPD PORRF TAXZP KALQA WMIUD BWNCT LEFKO ZQDLX
       BUXJL ASIMR PNMBF ZCYLV WAPVF QRHZV ZGZEF KBYIO OFXYE VOWGB
       BXVCB XBAWG LQKCM ICRRX MACUO IKHQU AJEGL OIJHH XPVZW JEWBA
       FWAML ZZRXJ EKAHV FASMU LVVUT TGK";

   const englishFrequences = [
       0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015,
       0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749,
       0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758,
       0.00978, 0.02360, 0.00150, 0.01974, 0.00074];

   auto key_decoded = vigenereDecrypt(englishFrequences, encoded);
   writeln("Key: ", key_decoded[0]);
   writeln("\nText: ", key_decoded[1]);

}</lang>

Python

Translation of: D

<lang python>from string import uppercase from operator import itemgetter

def vigenere_decrypt(target_freqs, input):

   nchars = len(uppercase)
   ordA = ord('A')
   sorted_targets = sorted(target_freqs)

   def frequency(input):
       result = [[c, 0.0] for c in uppercase]
       for c in input:
           result[c - ordA][1] += 1
       return result

   def correlation(input):
       result = 0.0
       freq = frequency(input)
       freq.sort(key=itemgetter(1))

       for i in xrange(nchars):
           result += freq[i][1] * sorted_targets[i]
       return result

   cleaned = [ord(c) for c in input.upper() if c.isupper()]
   best_len = 0
   best_corr = -100.0

   # Assume that if there are less than 20 characters
   # per column, the key's too long to guess
   for i in xrange(2, len(cleaned) // 20):
       pieces = [[] for _ in xrange(i)]
       for j, c in enumerate(cleaned):
           pieces[j % i].append(c)

       # The correlation seems to increase for smaller
       # pieces/longer keys, so weigh against them a little
       corr = -0.5 * i + sum(correlation(c) for c in pieces)

       if corr > best_corr:
           best_len = i
           best_corr = corr

   if best_len == 0:
       return ("Text is too short to analyze", "")

   pieces = [[] for _ in xrange(best_len)]
   for i, c in enumerate(cleaned):
       pieces[i % best_len].append(c)

   freqs = [frequency(c) for c in pieces]

   key = ""
   for i in xrange(best_len):
       freqs[i].sort(key=itemgetter(1), reverse=True)

       m = 0
       max_corr = 0.0
       for j in xrange(nchars):
           corr = 0.0
           c = ordA + j
           for k in xrange(nchars):
               d = (ord(freqs[i][k][0]) - c + nchars) % nchars
               corr += freqs[i][k][1] * target_freqs[d]

           if corr > max_corr:
               m = j
               max_corr = corr

       key += chr(m + ordA)

   r = [chr((c - ord(key[i % best_len]) + nchars) % nchars + ordA)
        for i, c in enumerate(cleaned)]
   return (key, "".join(r))

def main():

   encoded = """
       MOMUD EKAPV TQEFM OEVHP AJMII CDCTI FGYAG JSPXY ALUYM NSMYH
       VUXJE LEPXJ FXGCM JHKDZ RYICU HYPUS PGIGM OIYHF WHTCQ KMLRD
       ITLXZ LJFVQ GHOLW CUHLO MDSOE KTALU VYLNZ RFGBX PHVGA LWQIS
       FGRPH JOOFW GUBYI LAPLA LCAFA AMKLG CETDW VOELJ IKGJB XPHVG
       ALWQC SNWBU BYHCU HKOCE XJEYK BQKVY KIIEH GRLGH XEOLW AWFOJ
       ILOVV RHPKD WIHKN ATUHN VRYAQ DIVHX FHRZV QWMWV LGSHN NLVZS
       JLAKI FHXUF XJLXM TBLQV RXXHR FZXGV LRAJI EXPRV OSMNP KEPDT
       LPRWM JAZPK LQUZA ALGZX GVLKL GJTUI ITDSU REZXJ ERXZS HMPST
       MTEOE PAPJH SMFNB YVQUZ AALGA YDNMP AQOWT UHDBV TSMUE UIMVH
       QGVRW AEFSP EMPVE PKXZY WLKJA GWALT VYYOB YIXOK IHPDS EVLEV
       RVSGB JOGYW FHKBL GLXYA MVKIS KIEHY IMAPX UOISK PVAGN MZHPW
       TTZPV XFCCD TUHJH WLAPF YULTB UXJLN SIJVV YOVDJ SOLXG TGRVO
       SFRII CTMKO JFCQF KTINQ BWVHG TENLH HOGCS PSFPV GJOKM SIFPR
       ZPAAS ATPTZ FTPPD PORRF TAXZP KALQA WMIUD BWNCT LEFKO ZQDLX
       BUXJL ASIMR PNMBF ZCYLV WAPVF QRHZV ZGZEF KBYIO OFXYE VOWGB
       BXVCB XBAWG LQKCM ICRRX MACUO IKHQU AJEGL OIJHH XPVZW JEWBA
       FWAML ZZRXJ EKAHV FASMU LVVUT TGK"""

   english_frequences = [
       0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015,
       0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749,
       0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758,
       0.00978, 0.02360, 0.00150, 0.01974, 0.00074]

   (key, decoded) = vigenere_decrypt(english_frequences, encoded)
   print "Key:", key
   print "\nText:", decoded

main()</lang>