Vigenere Shift Cipher

A Multi-Path SDR Engine Example

(Last Mod: 27 November 2010 21:37:20 )

Overview
The Radio Architecture
- The Driver Program
- The Top Level Radio Definition
Implementing a Caesar Cipher Encoder
- The Key Source Block
- The Keyed Shift Block

Overview

The purpose of this example is to show how blocks with multiple input and output ports can be implemented and used to create a multi-path radio. The framework for this example will be an engine that implements a Vigenere Cipher and that is capable of both enciphering and deciphering a data stream.

This particular example was chosen because it represents only a modest step beyond the Caesar Shift Cipher engine that was previously implemented and from which we can reuse nearly all of the blocks without modification. Since numerous references are made to the Caesar engine, readers should first become familiar with it and its implementation.

For those unfamiliar with a Vigenere Cipher, it is actually only a mild enhancement to the Caesar Shift Cipher in which each letter is shifted by a different amount based on a key phrase. For example, if the key phrase was "Ride a fast horse", this would reduce to the key "RIDEAFASTHORSE". Thus, since 'R' is the 18th character of the alphabet, the key for the first character of plaintext would be 17 (the keys, like in the Caesar Shift cipher, run from 0 through 25). The second plaintext character would be enciphered using a shift of 8 (since 'I' is the 9th character), and so on down the line until the 14th character would be enciphered with 'E' (key = 4). The key phrase would then be recycled so that the 15th plaintext character would be enciphered with 'R'. This process continues until all of the plaintext has been enciphered. The deciphering process is simply the reverse of this.

Our Vigenere engine will utilize the same formatting rules that the Caesar engine did, namely that the output will consist of five letter groups, all upper case, with at most five groups on a given line. Furthermore, the output will be padded so that the last block is a complete set of five characters. The padding will consist of a 'Z' appended after the last ciphertext character and then appending 'X's, as necessary, to fill out the remainder of the final block.

The Radio Architecture

To implement the Vigenere enciphering engine (we will deal with deciphering later), we will simply replace the shifting block in the Caesar with a block that has a second input port into which we feed the ciphering key over and over. Thus our engine will have two source blocks, one feeding it the plaintext and the other feeding it the key steam. To generate the key stream, we will merely make a slightly modified copy of the Caesar source block that rewinds the file and starts again from the beginning when it reaches the end, instead of going inactive.

As the saying goes, the astute observer may have already noticed a potential problem: if the key stream's source never goes inactive, then how can our radio ever halt? The answer is that if it relies on the SDR Engine's normal block status marking, it won't. But we've already seen that blocks sometimes have to override the normal marking process in order to stay active. In this case, our shift block will have to override the normal marking process in order to go inactive.

The resulting radio that we will implement is therefore represented by the following diagramm with 'ksource' and 'kshift' being the blocks that we need to create.

The Driver Program

The driver program for the Vigenere engine is very similar to that for the Caesar engine, with the primary difference being that the name of the file containing the key text is supplied as the first argument instead of the single key value. Since passing the key material this way defeats the trick (using the negative of the key)that we used to get the Caesar engine to decipher the ciphertext, we have simply deleted this portion of the driver.

#include <stdio.h>
#include <stdlib.h>

#include "vigenere.h"

int main(void)
{
	SDR *radio;

	radio = vigenere_build("key.txt", "plain.txt", "cipher.txt");
	SDR_run(radio);
	SDR_delete(radio);

	printf("\n\nHit RETURN to exit");
	getc(stdin);
	return EXIT_SUCCESS;
}

The Top Level Radio Definition

The code for the vigenere_build() function is very similar to that for the Caesar engine. First, the radio data block has been altered so as to store a file pointer for the keytext file, instead of storing the key itself.

//---------------------------------------------------------------------------
// Radio Data Block
//---------------------------------------------------------------------------

typedef struct VIGENERE_DB VIGENERE_DB;
struct VIGENERE_DB
{
	FILE *fp_in;
	FILE *fp_out;
	FILE *fp_key;
};

The code for the build function itself has been modified so as to open the keytext file (and it requires that the keytext come from a file) and then the additional blocks have been added to the radio as well as the additional connections. Notice that the output from the key path is connected to Input Port 1 of the kshift block. Also notice that several block functions have been used twice. This is perfectly fine, as long as the each block is assigned a unique block name. However, a very critical point has to be observed in order to instantiate multiple blocks that use the same block function: The block function cannot use static variables to store information about the block, since that same function is going to be called from every block that uses it. As long as the block data is kept in that block's data structure, everything will work fine.

//---------------------------------------------------------------------------
// Radio Construction Function
//---------------------------------------------------------------------------

SDR *vigenere_build(char *keyfilename, char *infilename, char *outfilename)
{
	SDR *radio;
	VIGENERE_DB *db; // Radio-level Data Block

	//-----------------------------------------------------------------------
	// Prepare the radio-level datablock
	//-----------------------------------------------------------------------
	
	db = malloc(sizeof(VIGENERE_DB));
	if (!db)
		return NULL;
	
	// Set up the key file pointer
	if (NULL == keyfilename)     // NULL: Error
		return NULL;
	else if (0 == *keyfilename)  // "": Error
		return NULL;
	else                        // Open the specified file
		db->fp_key = fopen(keyfilename, "rt");

	if (!db->fp_key) // File didn't open
	{
		free(db); 
		return NULL;
	}

	// Set up the input file pointer
	if (NULL == infilename)     // NULL: Use the keyboard
		db->fp_in = stdin;
	else if (0 == *infilename)  // "": Use the internal test generator
		db->fp_in = NULL;
	else                        // Open the specified file
		db->fp_in = fopen(infilename, "rt");

	if ((infilename)&&(0!=*infilename)&&(!db->fp_in)) // File didn't open
	{
		free(db); 
		return NULL;
	}

	// Set up the output file pointer
	if (NULL == outfilename)    // NULL: Send output to screen
		db->fp_out = stdout;
	else if (0 == *outfilename) // "": Send output to screen
		db->fp_out = stdout;
	else                        // Open the specified file
		db->fp_out = fopen(outfilename, "wt");

	if ((outfilename)&&(!db->fp_out)) // File didn't open
	{
		free(db); 
		if ((db->fp_in)&&(!(stdin == db->fp_in)))
			fclose(db->fp_in);
		return NULL;
	}

	//-----------------------------------------------------------------------
	// Build the Radio
	//-----------------------------------------------------------------------

	// Instantiate the radio chassis
	radio = SDR_new(db, NULL);

	// Define Blocks (main path)
	SDR_add_block(radio, "source", source);
	SDR_add_block(radio, "alpha",  alpha);
	SDR_add_block(radio, "upper",  upper);
	SDR_add_block(radio, "tonum",  tonum);
	SDR_add_block(radio, "shift",  kshift);
	SDR_add_block(radio, "mod26",  mod26);
	SDR_add_block(radio, "tochar", tochar);
	SDR_add_block(radio, "pad5",   pad5);
	SDR_add_block(radio, "group5", group5);
	SDR_add_block(radio, "line5",  line5);
	SDR_add_block(radio, "sink",   sink);

	// Define Blocks (key path)
	SDR_add_block(radio, "ksource", ksource);
	SDR_add_block(radio, "kalpha",  alpha);
	SDR_add_block(radio, "kupper",  upper);
	SDR_add_block(radio, "ktonum",  tonum);

	// Connect Blocks (main path)
	SDR_connect(radio, "source:0", "alpha:0",  1, 16);
	SDR_connect(radio, "alpha:0",  "upper:0",  1, 16);
	SDR_connect(radio, "upper:0",  "tonum:0",  1, 16);
	SDR_connect(radio, "tonum:0",  "shift:0",  1, 16);
	SDR_connect(radio, "shift:0",  "mod26:0",  1, 16);
	SDR_connect(radio, "mod26:0",  "tochar:0", 1, 16);
	SDR_connect(radio, "tochar:0", "pad5:0",   1, 16);
	SDR_connect(radio, "pad5:0",   "group5:0", 1, 16);
	SDR_connect(radio, "group5:0", "line5:0",  1, 16);
	SDR_connect(radio, "line5:0",  "sink:0",   1, 16);

	// Connect Blocks (key path)
	SDR_connect(radio, "ksource:0", "kalpha:0", 1, 16);
	SDR_connect(radio, "kalpha:0",  "kupper:0", 1, 16);
	SDR_connect(radio, "kupper:0",  "ktonum:0", 1, 16);
	SDR_connect(radio, "ktonum:0",  "shift:1",  1, 16);

	// Tell the radio which block to monitor for end-of-run
	SDR_add_monitor(radio, "sink");
	
	//Reset the radio
	SDR_reset(radio);

	// If there have been any errors, output the SDR structure report,
	// delete the radio and return a NULL pointer
	if (SDR_errors(radio))
	{
		SDR_report(radio, stdout);
		SDR_delete(radio);
		radio = NULL;
	}

	return radio;
}

The Key Source Block

The key source block is actually quite a bit simpler than the plaintext source block, primarily because a decision was made to require that the key be read from a file. It would certainly be reasonable to write a block that permits the key to be entered from the keyboard, but this is more than sufficient for our needs.

Other than stripping out code no longer needed to support keyboard and self-generated text, the only substantive change was to change the line that previously marked the block as inactive when the end of the file is detected so that it merely rewinds the file.

//---------------------------------------------------------------------------
// Key Source Data Block and Function
//---------------------------------------------------------------------------

int ksource(SDRB *p, int when)
{
	int retvalue;
	VIGENERE_DB *radio_db;
	FILE *fp;
	unsigned char c;
	int c_int;

	retvalue = 0;
	switch (when)
	{
		case SDRB_INI:
			// Copy keyfile pointer to data block for faster access.
			radio_db = SDR_datablock(SDRB_radio(p));
			SDRB_set_data(p, radio_db->fp_key);
			if (!SDRB_get_data(p))
				retvalue = !SDRB_get_data(p);
			break;

		case SDRB_RST:
			break;

		case SDRB_RUN:
	
			fp = SDRB_get_data(p);

			if (!SDRB_is_full(p, 0))
			{
				c_int = fgetc(fp);
				c = (unsigned char) c_int;
				if (EOF == c_int)
					rewind(fp);
				else
					SDRB_push(p, 0, &c);
			}
			break;

		case SDRB_DEL:
			fp = SDRB_get_data(p);

			if (fp)
				fclose(fp);
			SDRB_set_data(p, NULL);
			break;

		default:
			retvalue = 1;
	}

	return retvalue;
}

The Keyed Shift Block

The kshift block that combines the plaintext and keytext streams to produce the ciphertext stream is actually a bit simpler than its Caesar engine counterpart because it has no need to store or access a static key value -- it merely pops a new key character from it's second input port each time it needs one. As can be seen, the port checks have been expanded to ensure that the necessary data is available at both input ports as well as sufficient space at the output port. Finally, the block always asks if its plaintext input port has gone inactive and, if so, marks itself as inactive.

int kshift(SDRB *p, int when)
{
	int retvalue;
	char c;
	char key;

	retvalue = 0; // Set retvalue to 1 to indicate errors.
	switch (when)
	{
		case SDRB_INI: // Initialation Behavior
			break;

		case SDRB_RST: // Reset Behavior
			break;

		case SDRB_RUN: // Runtime Behavior
			if ((!SDRB_is_empty(p, 0))&&(!SDRB_is_empty(p, 1))&&(!SDRB_is_full(p, 0)))
			{
				SDRB_pop(p, 0, &c);
				SDRB_pop(p, 1, &key);
				c += key;
				SDRB_push(p, 0, &c);
			}
			if (!SDRB_is_port_active(p, 0))
				SDRB_set_active(p, FALSE);
			break;

		case SDRB_DEL: // Deletion Behavior
			break;

		default: // Should never reach this point.
			retvalue = 1;
	}

	return retvalue;
}