April 15, 2014
Beating Caesar’s Cipher with Wheel-of-Fortune
While on vacation my wife showed me a children’s riddle book. When she was young her family went crazy for a few days trying to solve the riddle before giving up. The book contains a cipher at the end which can be used to validate your solution and finish the story. I knew it would be trivial to brute-force, but I wanted to demonstrate a statistical attack with nothing more than Wheel-of-Fortune’s free letters – R,S,T,L,N,E.
Approach
- Create baseline distribution of english letter usage
- Calculate distribution of letters in the secret message
- Check the correlation coefficient between the distributions
- Shift the distribution and check the correlation
- Find shifted distribution with best correlation
- Decrypt the message
I’ve added my toolbox methods at the end.
English Distributions of Letters
I’m sure google could find a better distribution, but who’s got time for that? My mother’s love of Wheel-of-Fortune has taught me the six most common letters.
var wofLetters = 'RSTLNE';
// code of 'A'
var cA = 'A'.charCodeAt(0);
// array of letter codes where 'A' = 0
var wofLettersZero = arrayOffset(stringAsCodes(wofLetters), -cA);
// distribution of letters
var wofHist = Algebra.histPercent(wofLettersZero, 26);
// WHEEL OF FORTUNE DISTRIBUTION
// 0.10 | | | | | |
// 0.08 | | | | | |
// 0.06 | | | | | |
// 0.04 | | | | | |
// 0.02 | | | | | |
// 0.00 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Secret Message
To stay free of any copyright trouble I’ve provided my own secret message:
var text = ''+
'OT ZNK HKMOTTOTM MUJ IXKGZKJ ZNK NKGBKTY GTJ ZNK KGXZN.\n'+
'TUC ZNK KGXZN CGY LUXSRKYY GTJ KSVZE, JGXQTKYY CGY UBKX\n'+
'ZNK YAXLGIK UL ZNK JKKV, GTJ ZNK YVOXOZ UL MUJ CGY NUBKXOTM\n'+
'UBKX ZNK CGZKXY. GTJ MUJ YGOJ, "RKZ ZNKXK HK ROMNZ," GTJ\n'+
'ZNKXK CGY ROMNZ. MUJ YGC ZNGZ ZNK ROMNZ CGY MUUJ, GTJ NK\n'+
'YKVGXGZKJ ZNK ROMNZ LXUS ZNK JGXQTKYY. MUJ IGRRKJ ZNK ROMNZ\n'+
'"JGE," GTJ ZNK JGXQTKYY NK IGRRKJ "TOMNZ." GTJ ZNKXK CGY\n'+
'KBKTOTM, GTJ ZNKXK CGY SUXTOTM—ZNK LOXYZ JGE.';
// get rid of all spaces, etc.
var textJustLetters = lettersOnly(text);
// array of letter codes where 'A' = 0
var textLettersZero = arrayOffset(stringAsCodes(textJustLetters), -cA);
// distribution of letters
var textHist = Algebra.histPercent(textLettersZero);
// CIPHER DISTRIBUTION
// 0.10 | |
// 0.08 | | | |
// 0.06 | | | | | | | |
// 0.04 | | | | | | | | | | |
// 0.02 | | | | | | | | | | | | |
// 0.00 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Shift and Find Best Correlation
var i, oHist, r,
bestR = 0, bestI = -1;
for (i = 0; i < 26; i++) {
// shift distribution
oHist = arrayRotate(textHist, i);
// check correlation
r = Algebra.correl(oHist, wofHist);
// save if better
if (r > bestR) {
bestR = r;
bestI = i;
}
}
Best Distribution
I won’t tell which one it is, but it looks like:
// BEST DISTRIBUTION (r=0.57734)
// 0.10 | |
// 0.08 | | | |
// 0.06 | | | | | | | |
// 0.04 | | | | | | | | | | |
// 0.02 | | | | | | | | | | | | |
// 0.00 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
* * * * * *
*Wheel of Fortune letters
Basic Toolbox
var Algebra = (function () {
var api = {};
// sum of an array of numbers
api.sum = function (a) {
var i, s = 0;
for (i = 0; i < a.length; i++) {
s += a[i];
}
return s;
};
// average of an array of numbers
api.mean = function (a) {
var s = api.sum(a);
return s / a.length;
};
// correlation coefficient between two arrays
api.correl = function (x, y) {
if (x.length !== y.length) {
throw new Error('correl() Must be same length!');
}
var i,
dmx, dmy,
sdmxy = 0, ssx = 0, ssy = 0,
mx = api.mean(x),
my = api.mean(y);
for (i = 0; i < x.length; i++) {
dmx = x[i] - mx;
dmy = y[i] - my;
sdmxy += dmx * dmy;
ssx += dmx * dmx;
ssy += dmy * dmy;
}
return sdmxy / Math.sqrt(ssx * ssy);
};
// histogram of an array or numbers
// returns array with accumulation
api.hist = function (a, bins) {
var i, x;
if (!bins) {
bins = bins || [];
} else if (!bins.length && bins > 0) {
i = bins;
bins = [];
while (i > bins.length) {
bins.push(0);
}
}
for (i = 0; i < a.length; i++) {
x = a[i];
while (x > (bins.length - 1)) {
bins.push(0);
}
bins[x]++;
}
return bins;
};
// histogram percentages of an array of numbers
// returns array with accumulation percentage
api.histPercent = function (a, bins) {
var i,
binsp = api.hist(a, bins);
for (i = 0; i < binsp.length; i++) {
binsp[i] = binsp[i] / a.length;
}
return binsp;
};
return api;
}());
// add 'offset' to each number in the array of numbers
var arrayOffset = function (a, off) {
var i;
for (i = 0; i < a.length; i++) {
a[i] += off;
}
return a;
};
// rotate the last 'n' array entries around to the beginning
var arrayRotate = function (a, n) {
return a.slice(n).concat(a.slice(0, n));
};
// convert string to array of number codes
var stringAsCodes = function (s) {
var out = [];
out.length = s.length;
for (i = 0; i < s.length; i++) {
out[i] = s.charCodeAt(i);
}
return out;
};
// string with only uppercase letters
var lettersOnly = function (s) {
return s.replace(/[^A-Z]/g, '');
};
// decrypt caesar cipher by shifting letter to A
var caesarDecrypt = function (text, letter) {
var i, n, q,
out = [],
cA = 'A'.charCodeAt(0),
cZ = 'Z'.charCodeAt(0),
k = letter.charCodeAt(0) - cA;
for (i = 0; i < text.length; i++) {
n = text.charCodeAt(i);
if (n < cA || n > cZ) {
out[i] = n;
continue;
}
q = n - k;
if (q < cA) {
q = cZ + (q - cA) + 1;
} else if (q > cZ) {
q = cA + (q - cZ) - 1;
}
out[i] = q;
}
return String.fromCharCode.apply(String, out);
};
var solve = function (text) {
var i;
var cA = 'A'.charCodeAt(0);
var textLettersZero = arrayOffset(stringAsCodes(lettersOnly(text)), -cA);
var textHist = Algebra.histPercent(textLettersZero);
var wofLettersZero = arrayOffset(stringAsCodes('RSTLNE'), -cA);
var wofHist = Algebra.histPercent(wofLettersZero, 26);
var oHist, r;
var bestR = 0, bestI = -1;
for (i = 0; i < 26; i++) {
oHist = arrayRotate(textHist, i);
r = Algebra.correl(oHist, wofHist);
if (r > bestR) {
bestR = r;
bestI = i;
}
}
var c;
if (bestI > -1) {
return String.fromCharCode(bestI + cA);
} else {
throw new Error('No Solution?!');
}
};
var key = solve(...text...);
console.log('MESSAGE: (shifted ' + key + ' to A)');
console.log(caesarDecrypt(text, key));
// Toolbox unit tests
var assert = require('assert');
assert.equal(Algebra.sum([1, 2, 3]), 6, 'Test Sum');
assert.equal(Algebra.mean([1, 2, 3]), 2.0, 'Test Mean');
assert.equal(Algebra.correl([1, 2, 3], [1, 2, 3]), 1.0, 'Test Correl');
assert.equal(Algebra.correl([3, 2, 1], [1, 2, 3]), -1.0, 'Test -Correl');
assert.equal(arrayOffset([0], 2)[0], 2, 'Test Offset');
assert.equal(Algebra.hist([1, 1, 1])[1], 3, 'Test Hist');
assert.equal(Algebra.hist([1], 3).length, 3, 'Test Hist Num Bins');
assert.equal(Algebra.histPercent([1,1,1,2,2,2])[1], 0.5, 'Test Hist Percent');
assert.equal(caesarDecrypt('M NO!', 'M'), 'A BC!', 'Test Caesar Decrypt');
assert.equal(caesarDecrypt('XYZABC', 'Z'), 'YZABCD', 'Test Caesar Decrypt');
assert.equal(stringAsCodes('ABC')[1], 'B'.charCodeAt(0), 'Test stringAsCodes');
assert.equal(lettersOnly('!-ABC Zaz'), 'ABCZ', 'Test Letters Only');
assert.equal(arrayRotate([1,2,3,4,5], -1)[0], 5, 'Test Rotate Right');
assert.equal(arrayRotate([1,2,3,4,5], 1)[3], 5, 'Test Rotate Left');