Yesterday I dropped an article about the Caesar Cipher encryption “scheme”. Now, it’s time to break it.
This one will be easy. Think about it. Our key can only be between 0 and 25. Sounds like a brute-forcable problem.
Method 1: Brute Force
First, here are the encryption and decryption functions we’ll be using.
encrypt.cpp
#include <vector>
#include <string>
#include <iostream>
namespace Caesar {
std::string encrypt(const std::string& str, const int& key) {
std::string s = str;
for (auto& c : s) {
if (c >= 'a' && c <= 'z') {
c = ((c - 'a' + key) % 26) + 'a';
} else if (c >= 'A' && c <= 'Z') {
c = ((c - 'A' + key) % 26) + 'A';
}
}
return s;
}
std::string decrypt(const std::string& str, const int& key) {
return encrypt(str, 26 - key);
}
};
Straight forward, right? If not, read my last article again.
Now let’s get down to decrypting with brute force. We’re just going to use a simple for loop:
brute.cpp
#include "./encrypt.cpp"
int main() {
std::string s; std::getline(std::cin, s);
std::cout << std::endl;
for (int i = 1; i < 26; i++) {
std::cout << "[ " << i << " ] ";
std::cout << Caesar::decrypt(s, i) << std::endl;
}
return 0;
}
Let’s say I encrypt a message.
$ ./caesar-cipher
Hello World
5
Mjqqt Btwqi
Now let’s metaphorically swallow the key and then try to unlock our message via brute force.
$ ./brute
Mjqqt Btwqi
[ 1 ] Lipps Asvph
[ 2 ] Khoor Zruog
[ 3 ] Jgnnq Yqtnf
[ 4 ] Ifmmp Xpsme
[ 5 ] Hello World
[ 6 ] Gdkkn Vnqkc
[ 7 ] Fcjjm Umpjb
[ 8 ] Ebiil Tloia
[ 9 ] Dahhk Sknhz
[ 10 ] Czggj Rjmgy
[ 11 ] Byffi Qilfx
[ 12 ] Axeeh Phkew
[ 13 ] Zwddg Ogjdv
[ 14 ] Yvccf Nficu
[ 15 ] Xubbe Mehbt
[ 16 ] Wtaad Ldgas
[ 17 ] Vszzc Kcfzr
[ 18 ] Uryyb Jbeyq
[ 19 ] Tqxxa Iadxp
[ 20 ] Spwwz Hzcwo
[ 21 ] Rovvy Gybvn
[ 22 ] Qnuux Fxaum
[ 23 ] Pmttw Ewztl
[ 24 ] Olssv Dvysk
[ 25 ] Nkrru Cuxrj
A quick look-through reveals our message, “Hello World,” with a key of 5.
Now, that’s not all that efficient. Plus, we must burden our eyes with looking through each of the 25 results.
Let’s make the computer do the work instead.
Method 2: Frequency Analysis
#include "./encrypt.cpp"
#define REG_MAX 4 // the index of 'e' in alpha ('a' = 0)
int main() {
std::string s; std::getline(std::cin, s);
std::vector<unsigned int> freq(26, 0);
/*
Collect frequencies
*/
for (auto& c : s) {
if (c >= 'a' && c <= 'z') {
freq[c - 'a']++;
} else if (c >= 'A' && c <= 'Z') {
freq[c - 'A']++;
}
}
// find most frequent letter
unsigned int max_idx = 0;
for (int i = 1; i < 26; i++) {
if (freq[i] > freq[max_idx]) {
max_idx = i;
}
}
int key = max_idx - REG_MAX;
while (key < 0) {
key += 26;
}
std::cout << Caesar::decrypt(s, key) << std::endl;
}
We count the occurrences of each letter and store it in freq. Taking advantage of the fact that ‘e’ is the most common letter in English, finding the most frequent letter and calculating its distance from ‘e’ reveals the key.
This will sometimes fail on smaller sample sets. For example, “Hello” only has ‘e’ once, but ‘l’ appears twice. I’ll be using a larger input to ensure that we have enough data to make a good key assumption.
Here’s the ciphertext we’ll be using:
Wg obm ct wh fsoz? W asob, zccy oh hvwg. Zccy oh wh! O kcfzr piwzh cb tobhogm. Gmbhvshwq sachwcbg wb hvs tcfa ct dwzzg. Dgmqvczcuwqoz koftofs wb hvs tcfa ct orjsfhwgwbu. Awbr-ozhsfwbu qvsawqozg wb hvs tcfa ct… tccr! Pfowbkogvwbu gsawbofg wb hvs tcfa ct asrwo. Qcbhfczzsr wgczohsr pippzsg wb hvs tcfa ct gcqwoz bshkcfyg. Fsoz? Mci kobh hc hozy opcih fsozwhm? Ks vojsb’h zwjsr wb obmhvwbu fsachszm qzcgs hc wh gwbqs hvs hifb ct hvs qsbhifm. Ks hifbsr wh ctt, hccy cih hvs pohhsfwsg, gboqysr cb o pou ct UACg kvwzs ks hcggsr hvs fsabobhg wb hvs sjsf-sldobrwbu Riadghsf ct hvs viaob qcbrwhwcb. Ks zwjs wb pfobrsr vcigsg hforsaofysr pm qcfdcfohwcbg piwzh cb pwdczof biapsfg xiadwbu id obr rckb cb rwuwhoz rwgdzomg, vmdbchwnwbu ig wbhc hvs pwuusgh gziapsf aobywbr vog sjsf gssb. Mci vojs hc rwu dfshhm rssd, ywrrc, pstcfs mci qob twbr obmhvwbu fsoz. Ks zwjs wb o ywburca ct pizzgvwh. O ywburca mci’js zwjsr wb tcf tof hcc zcbu. Gc rcb’h hszz as opcih bch pswbu fsoz. W’a bc zsgg fsoz hvob hvs tiqywbu psst dohhm wb mcif Pwu Aoq.
I’ve given you all the tools you need. You can decrypt it yourself. Bonus brownie points if you get the key, too!
Later…
@oaktree
So, do you recognize the message? How about where it’s from?
.