191 lines
8.3 KiB
JavaScript
191 lines
8.3 KiB
JavaScript
// Encoded text
|
|
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";
|
|
|
|
// Standard English letter frequencies (normalized probabilities)
|
|
const freq = [
|
|
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,
|
|
];
|
|
|
|
const A_CODE = 'A'.charCodeAt(0); // ASCII code for 'A'
|
|
const Z_CODE = 'Z'.charCodeAt(0); // ASCII code for 'Z'
|
|
|
|
// Helper function to calculate the sum of elements in an array
|
|
function sum(arr) {
|
|
return arr.reduce((acc, val) => acc + val, 0);
|
|
}
|
|
|
|
// Finds the rotation (shift, 0-25) for a given frequency distribution
|
|
// 'arr' that best matches the standard English frequencies 'freq'.
|
|
// Uses a chi-squared-like measure for goodness of fit.
|
|
function bestMatch(arr) {
|
|
const total = sum(arr);
|
|
let bestFit = Infinity; // Use Infinity for a large initial value
|
|
let bestRotate = 0;
|
|
|
|
for (let rotate = 0; rotate < 26; rotate++) {
|
|
let fit = 0.0;
|
|
for (let i = 0; i < 26; i++) {
|
|
const expectedFreq = freq[i];
|
|
// Calculate normalized frequency for the current rotation
|
|
const actualFreq = total > 0 ? arr[(i + rotate) % 26] / total : 0;
|
|
const d = actualFreq - expectedFreq;
|
|
// Chi-squared like goodness of fit: (observed - expected)^2 / expected
|
|
// The Go code uses (actualFreq - expectedFreq)^2 / expectedFreq
|
|
// This is a standard form of chi-squared contribution per bin.
|
|
fit += (d * d) / expectedFreq;
|
|
}
|
|
|
|
if (fit < bestFit) {
|
|
bestFit = fit;
|
|
bestRotate = rotate;
|
|
}
|
|
}
|
|
return bestRotate; // Return the best shift (0-25)
|
|
}
|
|
|
|
// Analyzes the frequency distribution of characters at intervals
|
|
// equal to the potential key length. It determines the best shift
|
|
// for each position in the key, populates `keyArray` with these
|
|
// shifts (0-25), and calculates an overall goodness-of-fit score
|
|
// for this key length against standard English frequencies.
|
|
function freqEveryNth(msg, keyArray) {
|
|
const l = msg.length;
|
|
const interval = keyArray.length; // This is the potential key length
|
|
const out = Array(26).fill(0); // Temporary frequency count for one key position (e.g., all 1st chars, all 2nd chars, etc.)
|
|
const accu = Array(26).fill(0); // Accumulated frequency counts across all key positions after applying their best shifts
|
|
|
|
for (let j = 0; j < interval; j++) { // Loop through each position in the potential key (0 to keyLength-1)
|
|
// Reset out for the current key position's characters
|
|
out.fill(0);
|
|
|
|
// Count frequencies for characters at indices j, j+interval, j+2*interval, ...
|
|
// These characters were all encrypted using the j-th character of the key.
|
|
for (let i = j; i < l; i += interval) {
|
|
out[msg[i]]++; // msg[i] is the 0-25 index of the character
|
|
}
|
|
|
|
// Find the best rotation (shift) for this specific frequency distribution ('out').
|
|
// This shift corresponds to the Vigenère key character used at this position 'j'.
|
|
const rot = bestMatch(out);
|
|
keyArray[j] = rot; // Store the best shift (0-25) found for this key position
|
|
|
|
// Apply the determined shift ('rot') to the current frequency counts ('out')
|
|
// and add them to the accumulator ('accu'). This simulates shifting each set
|
|
// of characters back as if they were decrypted by the correct key character.
|
|
for (let i = 0; i < 26; i++) {
|
|
accu[i] += out[(i + rot) % 26];
|
|
}
|
|
}
|
|
|
|
// Calculate the overall fit score based on the total accumulated frequencies ('accu').
|
|
// This measures how well the combined frequencies, after applying the determined
|
|
// shifts for each key position, match the standard English frequencies.
|
|
const totalAccu = sum(accu);
|
|
let ret = 0.0;
|
|
for (let i = 0; i < 26; i++) {
|
|
const expectedFreq = freq[i];
|
|
const actualFreq = totalAccu > 0 ? accu[i] / totalAccu : 0;
|
|
const d = actualFreq - expectedFreq;
|
|
// Chi-squared like fit score for the overall distribution
|
|
ret += (d * d) / expectedFreq;
|
|
}
|
|
|
|
return ret; // Return the overall fit score for this key length hypothesis
|
|
}
|
|
|
|
// Decrypts the text using the Vigenère cipher with the given key.
|
|
// Skips non-A-Z characters in the ciphertext and does not advance the
|
|
// key index for them, replicating the Go code's behavior.
|
|
function decrypt(text, key) {
|
|
let result = '';
|
|
let keyIndex = 0;
|
|
|
|
for (let i = 0; i < text.length; i++) {
|
|
const cCode = text.charCodeAt(i);
|
|
|
|
if (cCode >= A_CODE && cCode <= Z_CODE) {
|
|
const textCharIndex = cCode - A_CODE; // 0-25 index of ciphertext char
|
|
// Use the key character cyclically
|
|
const keyCharIndex = key.charCodeAt(keyIndex % key.length) - A_CODE; // 0-25 index of key char
|
|
|
|
// Vigenere decryption formula: (ciphertext_index - key_index + 26) % 26
|
|
// Adding 26 ensures the result is non-negative before modulo.
|
|
const decryptedCharIndex = (textCharIndex - keyCharIndex + 26) % 26;
|
|
|
|
result += String.fromCharCode(decryptedCharIndex + A_CODE);
|
|
keyIndex++; // Advance key index ONLY for processed A-Z characters
|
|
} else {
|
|
// Skip non-A-Z characters entirely, just like the Go code's 'continue'.
|
|
// They are neither decrypted nor cause the key index to advance.
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
// Main execution logic
|
|
function main() {
|
|
// Remove spaces from the encoded text
|
|
const cleanedEncoded = encoded.replace(/ /g, '');
|
|
|
|
// Convert cleaned text to an array of 0-25 integer indices ('A' -> 0, 'B' -> 1, ...)
|
|
const txt = [];
|
|
for (let i = 0; i < cleanedEncoded.length; i++) {
|
|
txt.push(cleanedEncoded.charCodeAt(i) - A_CODE);
|
|
}
|
|
|
|
let bestFit = Infinity; // Initialize with a very large value to find the minimum fit score
|
|
let bestKey = "";
|
|
|
|
console.log(" Fit Length Key");
|
|
|
|
// Iterate through potential key lengths from 1 to 26
|
|
for (let j = 1; j <= 26; j++) {
|
|
const keyArray = Array(j); // Array to hold the calculated shifts (0-25) for this length
|
|
const fit = freqEveryNth(txt, keyArray);
|
|
|
|
// Convert the array of shifts (0-25) into a key string (A-Z)
|
|
const currentKey = keyArray.map(shift => String.fromCharCode(shift + A_CODE)).join('');
|
|
|
|
// Format output line for the current key length
|
|
// toFixed(6) for 6 decimal places, padStart(2, ' ') for 2 characters, space-padded
|
|
let outputLine = `${fit.toFixed(6)} ${j.toString().padStart(2, ' ')} ${currentKey}`;
|
|
|
|
// Check if this key length gives a better fit than the best found so far
|
|
if (fit < bestFit) {
|
|
bestFit = fit;
|
|
bestKey = currentKey;
|
|
outputLine += " <--- best so far"; // Indicate the best fit found up to this point
|
|
}
|
|
console.log(outputLine);
|
|
}
|
|
|
|
console.log("\nBest key :", bestKey);
|
|
|
|
// Decrypt the original cleaned text using the best key found
|
|
const decryptedText = decrypt(cleanedEncoded, bestKey);
|
|
console.log("\nDecrypted text:\n" + decryptedText);
|
|
}
|
|
|
|
// Execute the main function
|
|
main();
|