Alas! It’s time for the next iteration of my Crypto Algs series. Now, a lot of what’s to be seen this time around is founded upon what I’ve said in past articles. In order to be best prepared for this article’s teachings, you should start from the beginning.
The Vigenere Cipher is often referred to as the next step up from the Caesar Cipher. While this algorithm is certainly more robust and secure, it is still definitely possible to break. That said, please don’t secure your mom’s secret meatloaf recipe with the Vigenere Cipher. Your dang neighbor, Fred, may be able to decrypt it. After all, if your mom’s meatloaf is as good as Fred has heard, he’d be willing to take the time to break your Vigenere Cipher.
Okay. Enough about meatloaf! Let’s get onto the concept.
Concept
The Vigenere Cipher is two parts. Like all encryption schemes, it takes in a plaintext and outputs a ciphertext. The Vigenere Cipher also expects a key. Unlike the Caesar Cipher, whose key was limited to a number between 0 and 25 (inclusive), this cipher takes in a key phrase. For example, meatloaf could be your encryption key. A stronger key would be MyMomMakesGreatMeatloaf. Each letter in the key is used as an offset.
A phrase allows us to eliminate any all-too-obvious patterns. Frequency Analysis would not work the way it did with the Caesar Cipher. Here’s an example.
Plaintext: Lemming
Key: meatloaf
Ciphertext: Ximftbg
Pay attention to the two m's in Lemming. Notice how the Ciphertext does not have two of the same letter side-by-side. This is because each letter in Lemming is offset by a different letter in meatloaf, our key.
When our plaintext is bigger than the key, the key will wrap to fit:
P: L E M M I N G S A R E C O O L
K: M E A T L O A F M E A T L O A
C: X I M F T B G X M V E V Z C L
Note: The key-wrapping is what leads to a vulnerability in the cipher. Sooner or later, the same word (“and,” for example) could be encrypted by the same three letters in the key. By noting the distance between the identically-obfuscated "and"s, we can determine possible lengths of the key. More on this later.
That’s it for the concept. Now, let’s code it. With our Caesar Cipher knowledge freshly in mind, this will be rather straightforward.
Code
encrypt.cpp
#include <vector>
#include <iostream>
#include <string>
#include <ctype.h>
namespace Vigenere {
std::string encrypt(const std::string& str, const std::string& key) {
std::string s = str;
std::vector<int> k(key.length());
int key_len = key.length();
// let's make the key into an array of offset values
int i;
for (i = 0; i < key_len; i++) {
k[i] = tolower(key[i]) - 'a';
}
i = 0;
for (auto& c : s) {
if (islower(c)) {
c = (c - 'a' + k[i++ % key_len]) % 26 + 'a';
} else if (isupper(c)) {
c = (c - 'A' + k[i++ % key_len]) % 26 + 'A';
}
}
return s;
}
std::string decrypt(const std::string& str, const std::string& key) {
std::string k = key;
for (auto& c : k) {
c = tolower(c) - 'a' - 1;
c = 'z' - c;
}
return encrypt(str,k);
}
};
The first step in my implementation is turning the key phrase into an array (vector) of offset values. We standardize this by ensuring that each letter in the key is lowercase:
std::vector<int> k(key.length());
int key_len = key.length();
int i;
for (i = 0; i < key_len; i++) {
k[i] = tolower(key[i]) - 'a';
}
Above is the specific code in which we load up k with the offset values. After doing that, all that is left is to apply the correct offsets to each alphabetical character in our plaintext.
i = 0;
for (auto& c : s) {
if (islower(c)) {
c = (c - 'a' + k[i++ % key_len]) % 26 + 'a';
} else if (isupper(c)) {
c = (c - 'A' + k[i++ % key_len]) % 26 + 'A';
}
}
This is very similar to what we did with the Caesar Cipher. Rather than a constant, numerical key k, however, we are using an array k, which is a series of offset values. By using the modulo operator, we can wrap the key to fit the plaintext’s length.
Notice that we only increment our index in the key if c is alphabetical. We wouldn’t want to offset any spaces or skip an offset.
For non-C/C++ people, one aspect might be strange:
c = (c - 'a' + k[i++ % key_len]) % 26 + 'a';
In this line, k[i++ % key_len] is to be read like so:
Access the `(i % key_len)`th element of `k`.
Increment `i`.
The Decryption Routine
You’ll notice that the file (encrypt.cpp) also has a Vigenere::decrypt(...) function.
std::string decrypt(const std::string& str, const std::string& key) {
std::string k = key;
for (auto& c : k) {
c = tolower(c) - 'a' - 1;
c = 'z' - c;
}
return encrypt(str,k);
}
What we do in this function is something I call complementing, in that we take the complement of each letter in the key. Since we are using the key to offset our plaintext, we can use the complement of the key to turn ciphertext back into plaintext using just the encrypt(...) function. For example:
P: H I
K: B B
C: I J
If we encrypt with BB, we are essentially offsetting our plaintext by 1. If we offset our ciphertext by 1's alphabetical complement, 25, we return to our plaintext. An offset of 25 is the same as encrypting with the key ZZ. By using this complement method, we avoid having to write a full-fledged decryption function, which would just subtract the offset instead of adding.
vigenere.cpp
#include "./encrypt.cpp"
int main() {
std::string s; std::getline(std::cin, s);
std::string k; std::getline(std::cin, k);
std::string result = Vigenere::encrypt(s,k);
std::cout << result << std::endl;
std::cout << Vigenere::decrypt(result, k) << std::endl;
return 0;
}
Alright. That’s all the code. We can now compile and run.
$ g++ -std=c++11 -Wall -Werror vigenere.cpp -o vigenere.o
$ ./vigenere.o
You'll never have my mom's recipe, Fred!
meatloaf
Ksu'ew beaqv htgs md ysm'l cscnbi, Fkpr!
You'll never have my mom's recipe, Fred!
Conclusion
That’s it for the implementation of the Vigenere Cipher. In Part 2.1, I will be showcasing more thoroughly some of this scheme’s weaknesses.
I appreciate feedback, as always. Any questions can be asked below or via PM.
Happy Ciphering
@oaktree
