|
#include <map>
#include <algorithm>
#include <array>
using namespace std;
typedef array<pair<char, double>, 26> FreqArray;
struct VigenereAnalyser {
vector<double> targets;
vector<double> sortedTargets;
class VigenereAnalyser(vector<double> targetFreqs) {
{
targets = targetFreqs;
private:
sortedTargets = targets;
array<double, 26> targets;
sort(sortedTargets.begin(), sortedTargets.end());
array<double, 26> sortedTargets;
}
FreqArray freq;
// Update the freqs array
vector<pair<char, double>> frequency(string input) {
FreqArray& frequency(const string& input)
vector<pair<char, double>> result(26);
{
for (char c = 'A'; c <= 'Z'; ++c)
for (char result[c -= 'A']; c <= make_pair(c,'Z'; 0++c);
freq[c - 'A'] = make_pair(c, 0);
for (size_t i = 0; i < input.size(); ++i)
resultfreq[input[i] - 'A'].second++;
return resultfreq;
}
double correlation(const string& input) {
{
double result = 0.0;
vector<pair<char, double>> freqresult = frequency(input)0.0;
frequency(input);
sort(freq.begin(), freq.end(), [](pair<char, double> u, pair<char, double> v)->bool
{ return u.second < v.second; });
for (size_t i = 0; i < 26; ++i)
result += freq[i].second * sortedTargets[i];
return result;
}
public:
pair<string, string> analyze(string input) {
VigenereAnalyser(const array<double, 26>& targetFreqs)
string cleaned;
{
for (size_t i = 0; i < input.size(); ++i) {
targets = targetFreqs;
if (input[i] >= 'A' && input[i] <= 'Z')
sortedTargets = targets;
cleaned += input[i];
sort(sortedTargets.begin(), sortedTargets.end());
else if (input[i] >= 'a' && input[i] <= 'z')
}
cleaned += input[i] + 'A' - 'a';
}
pair<string, string> analyze(string input)
size_t bestLength = 0;
{
double bestCorr = -100.0;
string cleaned;
for (size_t 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';
}
size_t bestLength = 0;
// Assume that if there are less than 20 characters
double bestCorr = -100.0;
// per column, the key's too long to guess
for (size_t i = 2; i < cleaned.size() / 20; ++i) {
vector<string> pieces(i);
for (size_t j = 0; j < cleaned.size(); ++j)
pieces[j % i] += cleaned[j];
// Assume that if there are less than 20 characters
// The correlation seems to increase for smaller
// pieces/longerper keyscolumn, sothe weighkey's againsttoo themlong ato littleguess
for (size_t i = 2; i < cleaned.size() double/ corr20; = -0.5*++i;)
{
for (size_t j = 0; j < i; ++j)
vector<string> pieces(i);
corr += correlation(pieces[j]);
for (size_t j = 0; j < cleaned.size(); ++j)
pieces[j % i] += cleaned[j];
// The correlation increases artificially for smaller
if (corr > bestCorr) {
// pieces/longer keys, so weigh against them a little
bestLength = i;
double bestCorrcorr = corr-0.5*i;
for (size_t j = 0; j }< i; ++j)
}corr += correlation(pieces[j]);
if (bestLengthcorr ==> 0bestCorr)
{
return make_pair("Text is too short to analyze", "");
bestLength = i;
bestCorr = corr;
}
}
if (bestLength == 0)
vector<string> pieces(bestLength);
return for make_pair(size_t"Text iis =too 0;short ito <analyze", cleaned.size(""); ++i)
pieces[i % bestLength] += cleaned[i];
vector<vector<pair<char, double>>string> freqspieces(bestLength);
for (size_t i = 0; i < bestLengthcleaned.size(); ++i)
pieces[i % bestLength] += cleaned[i];
freqs.push_back(frequency(pieces[i]));
vector<FreqArray> freqs;
string key = "";
for (size_t i = 0; i < bestLength; ++i) {
freqs.push_back(frequency(pieces[i]));
sort(freqs[i].begin(), freqs[i].end(), [](pair<char, double> u, pair<char, double> v)->bool
{ return u.second > v.second; });
string size_t mkey = 0"";
for (size_t i = 0; i < bestLength; double++i) mCorr = 0.0;
{
for (size_t j = 0; j < 26; ++j) {
sort(freqs[i].begin(), freqs[i].end(), [](pair<char, double> u, pair<char, double> v)->bool
double corr = 0.0;
{ return u.second > v.second; char c = 'A' + j});
for (size_t k = 0; k < 26; ++k) {
int d = (freqs[i][k].first - c + 26) % 26;
corr += freqs[i][k].second * targets[d];
}
size_t m = if (corr > mCorr) {0;
double mmCorr = j0.0;
for (size_t j = 0; j < 26; ++j) mCorr = corr;
}{
double corr = }0.0;
char c = 'A' + j;
for (size_t k = 0; k < 26; ++k)
{
int d = (freqs[i][k].first - c + 26) % 26;
corr += freqs[i][k].second * targets[d];
}
if (corr > mCorr) key += m + 'A';
{
m = j;
mCorr = corr;
}
}
key += stringm result =+ ""'A';
for (size_t i = 0; i < cleaned.size(); ++i)
result += (cleaned[i] - key[i % key.length()] + 26) % 26 + 'A';
return make_pair(result, key);
}
string result = "";
for (size_t i = 0; i < cleaned.size(); ++i)
result += (cleaned[i] - key[i % key.length()] + 26) % 26 + 'A';
return make_pair(result, key);
}
};
int main() {
{
string input =
string input =
"MOMUD EKAPV TQEFM OEVHP AJMII CDCTI FGYAG JSPXY ALUYM NSMYH"
"VUXJEMOMUD LEPXJEKAPV FXGCMTQEFM JHKDZOEVHP RYICUAJMII HYPUSCDCTI PGIGMFGYAG OIYHFJSPXY WHTCQALUYM KMLRDNSMYH"
"ITLXZVUXJE LJFVQLEPXJ GHOLWFXGCM CUHLOJHKDZ MDSOERYICU KTALUHYPUS VYLNZPGIGM RFGBXOIYHF PHVGAWHTCQ LWQISKMLRD"
"FGRPHITLXZ JOOFWLJFVQ GUBYIGHOLW LAPLACUHLO LCAFAMDSOE AMKLGKTALU CETDWVYLNZ VOELJRFGBX IKGJBPHVGA XPHVGLWQIS"
"ALWQCFGRPH SNWBUJOOFW BYHCUGUBYI HKOCELAPLA XJEYKLCAFA BQKVYAMKLG KIIEHCETDW GRLGHVOELJ XEOLWIKGJB AWFOJXPHVG"
"ILOVVALWQC RHPKDSNWBU WIHKNBYHCU ATUHNHKOCE VRYAQXJEYK DIVHXBQKVY FHRZVKIIEH QWMWVGRLGH LGSHNXEOLW NLVZSAWFOJ"
"JLAKIILOVV FHXUFRHPKD XJLXMWIHKN TBLQVATUHN RXXHRVRYAQ FZXGVDIVHX LRAJIFHRZV EXPRVQWMWV OSMNPLGSHN KEPDTNLVZS"
"LPRWMJLAKI JAZPKFHXUF LQUZAXJLXM ALGZXTBLQV GVLKLRXXHR GJTUIFZXGV ITDSULRAJI REZXJEXPRV ERXZSOSMNP HMPSTKEPDT"
"MTEOELPRWM PAPJHJAZPK SMFNBLQUZA YVQUZALGZX AALGAGVLKL YDNMPGJTUI AQOWTITDSU UHDBVREZXJ TSMUEERXZS UIMVHHMPST"
"QGVRWMTEOE AEFSPPAPJH EMPVESMFNB PKXZYYVQUZ WLKJAAALGA GWALTYDNMP VYYOBAQOWT YIXOKUHDBV IHPDSTSMUE EVLEVUIMVH"
"RVSGBQGVRW JOGYWAEFSP FHKBLEMPVE GLXYAPKXZY MVKISWLKJA KIEHYGWALT IMAPXVYYOB UOISKYIXOK PVAGNIHPDS MZHPWEVLEV"
"TTZPVRVSGB XFCCDJOGYW TUHJHFHKBL WLAPFGLXYA YULTBMVKIS UXJLNKIEHY SIJVVIMAPX YOVDJUOISK SOLXGPVAGN TGRVOMZHPW"
"SFRIITTZPV CTMKOXFCCD JFCQFTUHJH KTINQWLAPF BWVHGYULTB TENLHUXJLN HOGCSSIJVV PSFPVYOVDJ GJOKMSOLXG SIFPRTGRVO"
"ZPAASSFRII ATPTZCTMKO FTPPDJFCQF PORRFKTINQ TAXZPBWVHG KALQATENLH WMIUDHOGCS BWNCTPSFPV LEFKOGJOKM ZQDLXSIFPR"
"BUXJLZPAAS ASIMRATPTZ PNMBFFTPPD ZCYLVPORRF WAPVFTAXZP QRHZVKALQA ZGZEFWMIUD KBYIOBWNCT OFXYELEFKO VOWGBZQDLX"
"BXVCBBUXJL XBAWGASIMR LQKCMPNMBF ICRRXZCYLV MACUOWAPVF IKHQUQRHZV AJEGLZGZEF OIJHHKBYIO XPVZWOFXYE JEWBAVOWGB"
"BXVCB XBAWG LQKCM ICRRX "FWAMLMACUO ZZRXJIKHQU EKAHVAJEGL FASMUOIJHH LVVUTXPVZW TGKJEWBA";
"FWAML ZZRXJ EKAHV FASMU LVVUT TGK";
array<double, 26> english = {
double fs[] = {0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228,
0.0201508167, 0.0609401492, 0.0696602782, 0.0015304253, 0.0077212702, 0.0402502228,
0.0240602015, 0.0674906094, 0.0750706966, 0.0192900153, 0.0009500772, 0.0598704025,
0.0632702406, 0.0905606749, 0.0275807507, 0.0097801929, 0.0236000095, 0.0015005987,
0.06327, 0.09056, 0.02758, 0.00978, 0.0197402360, 0.00074};00150,
0.01974, 0.00074};
VigenereAnalyser va(english);
vector<double> english(&fs[0], &fs[26]);
pair<string, string> output = va.analyze(input);
VigenereAnalyser va(english);
pair<string, string> output = va.analyze(input);
cout << "Key: " << output.second << endl << endl;
cout << "Text: " << output.first << endl;
}</lang>
|