Midterm: Vigenère Cipher

Around 1550 Blaise de Vigenère, a French diplomat from the court of Henry III of France, developed a new scrambling technique that uses 26 alphabets to cipher a text. To be precise, de Vigenère modified a cipher invented earlier by the Italian Giovan Battista Bellaso, and turned it into a autokey cipher that incorporates the message into the key. The Vigenère Cipher is a polyalphabetic substitution technique based on a mapping table like the one shown below:

The Vigenère cipher uses this table together with a keyword to encode a message.

To illustrate the use of this encryption method, suppose we wish to scramble the following message (Hamlet 3/1):

To be, or not to be: that is the question:

using the keyword Relations. First, we notice that the table provides only mappings for upper case characters. But this is not really a problem. The mapping is identical for upper and lower case characters. We just rewrite the keyword to consist of upper case characters only. When encoding a message, we convert each character to an upper case one, perform the corresponding encryption function, and output the result in either upper case or lower case depending on the original spelling. All characters not covered in the Vigenère cipher remain unchanged in the output. No keyword character is consumed in this case!

We begin by writing the keyword, followed by the message. To derive the encoded text using the mapping table, for each letter in the message, one has to find the intersection of the row given by the corresponding keyword letter and the column given by the message letter itself to pick out the encoded letter.

Keyword: RE LA TI ONS TO BE ORNO TT OBE THATISTH

Message: To be, or not to be: that is the question:

Scrambled Message: Lt nf, ia ccm nd dj: izoi cm ijj kcfmcbiv:

Decoding of an encrypted message is equally straightforward. One writes the keyword repeatedly above the message:

Keyword: RE LA TI ONS TO BE ORNO TT OBE THATISTH

Scrambled Message: Lt nf, ia ccm nd dj: izoi cm ijj kcfmcbiv:

Decoded Message: To be, or not to be: that is the question:

This time one uses the keyword letter to pick a row of the table and then traces the row to the column containing the encoded letter. The index of that column is the decoded letter. 

Problem 1

To implement the Vigenère cipher, we need a data type, called KeyProvider, to represent the keyword. Initially, the keyword is populated with the keyword string that starts the scrambling process. For instance, in the above example the keyword string is “Relations” which is mapped to the initially keyword “RELATIONS”. Every time a keyword character is consumed, either to encode or to decode a message, that character needs to be replaced with the “clear character” being processed. You can think of the keyword data type and implement it as a circular buffer. This buffer gets continuously updated with new keyword characters for the message, once the scrambling process in on the way. This behavior yields the required autokey cipher.

A suggested specification of class KeyProvider is shown below:

#pragma once #include <string> class KeyProvider

{

private:

char * fKeyword; // keyword

size_t fSize; // length of keyword

size_t fIndex; // index to current keyword character

public:

// Initialize key provider. [10]

// aKeyword is a string of letters. KeyProvider( const std::string& aKeyword );

// Destructor, release resources. [4]

~KeyProvider();

// Initialize (or reset) keyword [30]

void initialize( const std::string& aKeyword );

// Dereference, returns current keyword character. [4]

char operator*() const;

// Push new keyword character. [18]

// aKeyCharacter is a letter (isalpha() is true).

// aKeyCharacter replaces current keyword character.

// Key provider advances to next keyword character. KeyProvider& operator<<( char aKeyCharacter );

};

Class KeyProvider maintains a keyword array whose length depends on the size of aKeyword. That is, the constructor for KeyProvider has to allocate the required heap memory for fKeyword, initialize its contents with the uppercase versions of the letters in aKeyword, and set fIndex to the start of the keyword. The method initialize performs those steps. To function properly, however, all instance variables have to be initialized with sensible values first, ideally using member initializers.

As we maintain resources in KeyProvider, we are required to define a destructor. The destructor has to properly release resources.

The method initialize() sets or resets the keyword to its initial value. This method has to release previously allocated heap memory, acquire fresh heap memory, and initialize the memory with the initial keyword aKeyword. After calling initialize(), the KeyProvider starts with the first keyword character. 

The service interface of KeyProvider consists of two operators:

• operator*(): We use the dereference operator to access the current keyword character. If the keyword is not updated intermittently, the dereference operator has to return the same keyword character. As we use a circular buffer scheme, the current index into fKeyword is always valid.

• operator<<(): We use the shift-left operator to update the keyword with aKeyCharacter. That is, aKeyCharacter replaces the current keyword character with its uppercase variant and the keyword index advances to the next keyword character.

Class KeyProvider yields the fundamental abstraction for a Vigenère autokey cipher. Make sure that all necessary header files are explicitly included in KeyProvider.cpp.

You may test your implementation of KeyProvider using the following test driver (enable

#define P1 in main.cpp):

#include "KeyProvider.h"

int runP1( string argv[2] )

{

cout << "Testing KeyProvider with \"" << argv[0]

<< "\" and \"" << argv[1] << "\"" << endl;

KeyProvider lKeyWord( argv[0] ); string& lMessage = argv[1];

for ( char c : lMessage )

{

if ( isalpha( c ) )

{

cout << *lKeyWord; lKeyWord << c;

}

else

{

cout << ' ';

}

}

cout << "\n";

for ( char c : lMessage )

{

cout << (isalpha( c ) ? static_cast<char>(toupper( c )) : c);

}

cout << "\nCompleted" << endl;

return 0;

}

Running the test driver should produce the following output:

Testing KeyProvider with "Relations" and "To be, or not to be: that is the question:" RE LA TI ONS TO BE ORNO TT OBE THATISTH

TO BE, OR NOT TO BE: THAT IS THE QUESTION:

Completed

vigenere.cpp

main.cpp