Crypto Algs (Part 2.0): Vigenere

algorithm
vigenerecipher
encryption

(oaktree) #1

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


Crypto Algs (Part 3.0): XOR
#2

Great article as always oak! :smile:


#3

Nice article @oaktree !

This crypto algorithm is inescapable. The vigenere cipher, also considered as a one-time pad, is one of the most computationally and cryptographically secure if, of course, the key generated is completely random with no redundancy and if the size of the key is at least, longer than the plaintext ! Statement established in 1964 by Claude Shannon, a well-known cryptographer.


(Command-Line Ninja) #4

Sweeeeeet post! I remember doing Caesar and Vigenere in school as part of my course. I’m really loving this series!


(oaktree) #5

This is true, @Nitrax… But you wouldn’t encrypt your disk with vigenere because imagine encrypting a 512 GB partition with a 512 GB key! Crazy!


#6

Yep, it depends on the purpose, I agree :joy:


(pico) #7

Well, it is mainly know for being the father of “Information Theory” and their theorems, despite of his works on cryptography. By the way, his original paper on Information Theory is just brilliant!. A must read!


#8

Thanks for the information mate, I take note :wink:


(oaktree) #9

Do you happen to have a link to the paper of which you speak, @0x00pf?


(pico) #10

@oaktree, there you go

http://www.essrl.wustl.edu/~jao/itrg/shannon.pdf


(oaktree) #11

This topic was automatically closed after 30 days. New replies are no longer allowed.