22 Jul 2010

Caesar Encoding

Julius Caesar verschlüsselte seine militärische Korrespondenz, indem er jeden Buchstaben des Alphabets um 3 Buchstaben verschob. Aus A wird C, aus B D, … Diese Verschlüsselung ist natürlich nicht sehr sicher und über eine Häufigkeitsanalyse leicht zu knacken.

Im Rahmen der Technikerschule bekamen wir als Projekt, eine Kommandozeilen-Version eines Cäsar-Verschlüsselungs-Programmes zu bauen. Die Aufgabe musste in Zweier-Teams erledigt werden. Das hier ist unsere Lösung. Es werden folgende Funktionen unterstützt: Verschlüsseln, Entschlüsseln, Ein- und Ausgabe über stdin / stdout oder Dateien, Knacken des Schlüssels über eine Häufigkeitsanalyse.

Benutzungs-Beispiel dieses Programms:

Kompilieren des Sourcecodes

chrissie@balearen ~/my_c $ gcc caesar.c -o caesar

Andwendung: Verschlüsseln

chrissie@balearen ~/my_c $ echo "Das ist ein streng geheimer Text, \
den niemand wissen darf. Deshalb wird er auch verschl_sselt" | \
./caesar -e -o enc.txt -c 13
chrissie@balearen ~/my_c $ cat enc.txt
QNFVF GRVAF GERAT TRURV ZREGR
KG,QR AAVRZ NAQJV FFRAQ NES.Q
PUY_F RFUNY OJVEQ RENHP UIREF
FRYG

Andwendung: Entschlüsseln mit bekanntem Schlüssel

chrissie@balearen ~/my_c $ ./caesar -d -i enc.txt -c 13
The decrypted message is:
DASISTEINSTRENGGEHEIMERTEXT,DENNIEMANDWISSENDARF.DESHALBWIRDERAUCHVERSCHL_SSELT

Die Verschlüsselung mit einer Häufigkeitsanalyse knacken: Annahme in diesem Fall: E ist der häufigste Buchstabe. Das kann dann variiert werden, für deutsch ist E, S, H, C . der Reihe nach empfohlen.

chrissie@balearen ~/my_c $ ./caesar -f E -i enc.txt
The frequency-analyzed message is:
DASISTEINSTRENGGEHEIMERTEXT,DENNIEMANDWISSENDARF.DESHALBWIRDERAUCHVERSCHL_SSELT

Hilfe:

chrissie@balearen ~/my_c$ ./caesar -h

simple caesar code implementation
-i FILENAME    infile
-o FILENAME    outfile (optional, use stdout if nothing given)
-d             decrypt
-e             encrypt
-c 13          code for enc / dec (value 0 ... 25, optional, default 13 if no -c)
-f E           decrypt using frequency analysis if key is lost (try e, n, i, r, s, h, c for german)
-h             print this help
Examples:
caesar -i test.txt -o secret.txt -e -c 8
caesar -f E -i secret.txt
caesar -h

Der Source-Code(new BSD license).

  • Download: caesar.c

  • Source-Code-Listing

/***
 *
 * caesar.c
 *
 * simple caesar code command line program
 * written by chrissie and justass 06/2010
 * for IT9.09 project
 * released under the new BSD license
 * just plain C works under Windows/MS VisualC
 * and Linux/GNU gcc
 *
 * 22072010
 *
 */

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

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

#define DECRYPT 0x01
#define ENCRYPT 0x02
#define CODE	0x04
#define FREQ	0x08
#define INFILE	0x10
#define OUTFILE 0x20
#define HELP	0x40

#define true 1
#define false 0
#define MAXINT 32767

void wrongUsage(void);
void printHelp(void);
char *caesarDecrypt(char *instring, int caesarKey);
char *caesarEncrypt(char *instring, int caesarKey);
char *caesarFreqDec(char *instring, char *freqChar);
char *readIt ( FILE* infile);
void printIt(char *outstring, FILE *stream, char mode );
void upperCase(char *instring);
void swapC (char *a, char *b);
void swapI (int *a, int *b);

/***
 * Main
 */
int main (int argc, const char* argv[])
{
	int i;
	char *inFileName=NULL, *outFileName=NULL;
	char parseError = false;
	char mode=0;
	char *caesarKeyString;
	int caesarKey = 13;
	char *freqChar;
	FILE *infile;
	FILE *outfile;
	char *instring=NULL;
	char *outstring=NULL;

	// no additional arg given
	if (argc==1)
		parseError=true;

	/*
	 * simple command line parser
	 */
	for (i=0; i<argc; i++) {
		if (strcmp(argv[i],"-i")==0) {
			// next argument normally is filename
			inFileName=(char *)argv[++i];
			mode|=INFILE;
		}
		else if (strcmp(argv[i],"-o")==0) {
			outFileName=(char *)argv[++i];
			mode|=OUTFILE;
		}
		else if (strcmp(argv[i],"-d")==0) {
			mode|=DECRYPT;
		}
		else if (strcmp(argv[i],"-e")==0) {
			mode|=ENCRYPT;
		}
		else if (strcmp(argv[i],"-f")==0) {
			mode|=FREQ;
			freqChar=(char *)argv[++i];
			if (strlen(freqChar)>1)
				freqChar[1]=0;
			upperCase(freqChar);
		}
		else if (strcmp(argv[i],"-h")==0) {
			mode|=HELP;
		}
		else if (strcmp(argv[i],"-c")==0) {
			caesarKeyString=(char *)argv[i+1];
			i++;
			mode|=CODE;
		}
	}

	/*
	 * check for correct usage
	 */
	if ((mode & DECRYPT) && (mode & ENCRYPT))
		parseError=true;

	if (!(mode & DECRYPT) && !(mode & ENCRYPT) && !(mode & FREQ))
		parseError=true;

	if ( ((mode & DECRYPT) || (mode & ENCRYPT)) && (mode & FREQ))
		parseError=true;

	/*
	 * do the stuff - order matters!
	 */

	if (mode & HELP) {
		printHelp();
		return 0;
	}

	if (parseError) {
		wrongUsage();
		return -1;
	}

	// parse codevalue
	if (mode & CODE) {
		caesarKey = atoi(caesarKeyString);
		if (caesarKey<0)
			caesarKey=0;
		if (caesarKey>26)
			caesarKey=26;
	}
	
	// open infile or stdin
	if (mode & INFILE) {
		// read from file
		if ((infile=fopen(inFileName, "r"))==NULL ) {
			printf("Cannot open the file.\n");
			return -1;
		}
		instring=readIt(infile);
		if (instring==NULL) return -1;
	} else {
		// read from stdin
		if (mode&DECRYPT || mode&ENCRYPT || mode&FREQ) {
			instring=readIt(stdin);
			if (instring==NULL)
				return -1;
		}
	}

	// encrypt / decrypt / freq analysis
	if (mode & DECRYPT) {
		outstring=caesarDecrypt(instring, caesarKey);
		if (outstring==NULL)
			return -1;
	}

	if (mode & ENCRYPT) {
		outstring=caesarEncrypt(instring, caesarKey);
		if (outstring==NULL)
			return -1;
	}

	if (mode & FREQ) {
		outstring=caesarFreqDec(instring,freqChar);
		if (outstring==NULL)
			return -1;
	}

	// write to outfile or stdout
	if (mode & OUTFILE) {
		// write to file
		if ((outfile=fopen(outFileName, "w"))==NULL)  {
			printf("Cannot write to the file.\n");
			return -1;
		}
		if (outfile) {
			printIt (outstring,outfile,mode);
			fclose(outfile) ;
		}
	} else {
		// write to stdout
		if (mode & ENCRYPT)
			printf("\nThe encrypted message is:\n");
		if (mode & DECRYPT)
			printf("\nThe decrypted message is:\n");
		if (mode & FREQ)
			printf("\nThe frequency-analyzed message is:\n");
		printf( "-------------------------\n");
		printIt(outstring, stdout,mode);
	}

	free(instring);
	free(outstring);
	return 0;
}

/***
 * Encrypt
 */
char *caesarEncrypt(char *instring, int caesarKey)
{
	char *c;
	char *helper=(char *)malloc((strlen(instring)+1)*sizeof(char));
	if (helper==NULL) {
		printf("Cannot allocate memory!");
		return NULL;
	}

	strcpy(helper,instring);
	upperCase(helper);
	for (c=helper; *c; c++) {
		if (*c>='A' && *c<='Z') {
			*c+=caesarKey;
			if (*c>'Z') *c-=26;
		}
	}
	return helper;
}

/***
 * Decrypt
 */
char *caesarDecrypt(char *instring, int caesarKey)
{
	char *c;
	char *helper=(char *)malloc((strlen(instring)+1)*sizeof(char));
	if (helper==NULL) {
		printf("Cannot allocate memory!");
		return NULL;
	}

	strcpy(helper,instring);
	upperCase(helper);
	for (c=helper; *c; c++) {
		if (*c>='A' && *c<='Z') {
		    *c-=caesarKey;
		    if (*c<'A') *c+=26;
		}
	}
	return helper;
}

/***
 * possible decryption via char frequency counting
 */
char *caesarFreqDec(char *instring, char *freqChar) 
{
	char *helper=(char *)malloc((strlen(instring)+1)*sizeof(char));
	if (helper==NULL) {
		printf("Cannot allocate memory!");
		return NULL;
	}

	strcpy(helper,instring);
	upperCase(helper);

	int frequency[26]; 
	char alphabet[26];
	char guessedKey;
	char in,i,j;
	char ch, *m;
	
	// fill arrays for counting char frequency
	for (i=0; i<26; i++)
		alphabet[i]=i+'A';
	memset(frequency,0,sizeof(frequency));
	
	// count frequency of characters in the string
	// only count A-Z ignore other characters
	for (m=helper; *m; m++) {
		i=(int)*m-'A';
		if (i>=0 && i<=25){
			if (frequency[i]<MAXINT)
				frequency[i]++;
			else
				break;
		}
	}

	// bubble sort for getting chars with max fequency
	for (i=25; i>=0; i--) {
		for (j=0; j<=i; j++) {
			if (frequency[i]>frequency[j]) {
				swapI (&frequency[i],&frequency[j]);
				swapC (&alphabet[i],&alphabet[j]);
			}
		}
	}
	// the most frequent char is now at the beginning of the array
	// others ar following descending

	// use the most frequent char as the possible most frequent
	// char which ist given at command line
	// calculate key
	guessedKey=alphabet[0]-(int)freqChar[0];
	if (guessedKey<0)
		guessedKey +=26;

	// return possible result - user has to check ist
	return caesarDecrypt(helper, guessedKey);
}

/***
 * swap helper functions
 */
void swapC(char *a, char *b)
{
	static char c;
	c =*a;
	*a=*b;
	*b=c;
}
void swapI(int *a, int *b)
{
	static int c;
	c=*a;
	*a=*b;
	*b=c;
}

/***
 * turn all into uppercase, modify string directly
 */
void upperCase(char *instring)
{
	char *c;
	for (c=instring; *c; c++) {
		if (*c>='a' && *c<='z')
			*c-=('a'-'A');
	}
}

/***
 * read a multiline file into one continous string
 * remove cr/lf
 * reallocate size of the array as needed
 */
char *readIt ( FILE* infile) 
{
	char mystring[250];
	char *helper;
	helper=(char *)malloc(sizeof(char));
	*helper=0;

	for (;;) {
		// read one line
		fgets (mystring,250,infile);
		if (feof(infile))
			break;

		// remove lf, cr/lf, cr (lin, win, mac line endings)
		if (strlen(mystring)>=1) {
			if (mystring[strlen(mystring)-1]=='\r')
			mystring[strlen(mystring)-1]='\0';
			if (mystring[strlen(mystring)-1]=='\n')
			mystring[strlen(mystring)-1]='\0';
		}

		// realloc, concatenate
		if (mystring) {
			helper=(char *)realloc(helper, (strlen(helper)+strlen(mystring)+1)*sizeof(char));
			if (helper==NULL) {
				printf("Cannot allocate memory!");
				return NULL;
			}
			strcat(helper, mystring);
		}
	}
	fclose(infile);
	return helper;
}

/***
 * write the message in nice Enigma style into a file stream
 * ex. TQXXB JBEXP MNO
 */
void printIt(char *outstring, FILE *stream, char mode)
{
	int i,j;
	char *c;
	char linefeed=false;

	//format message in enigma style at encryption
	for (j=i=0,c=outstring; *c; c++) {
		if (*c==' ')
			c++;
		putc(*c, stream);
		linefeed=false;

		if (mode & ENCRYPT) {
			if(++i==5){
				i=0;
				if(++j==5) {
					j=0;
					putc('\n',stream);
					linefeed=true;
				} else {
					putc(' ',stream);
				}
			}
		}
	}

	if (linefeed==false)
		putc('\n',stream);
}

/***
 * usage / helper functions
 */
void wrongUsage(void)
{
	printf(
	"\nAechz, you are doing it WRONG!\n"
	"Please use option -h for help.\n\n"
	);
}

void printHelp(void)
{
	printf(
	"\nsimple caesar code implementation\n"
	"-i FILENAME    infile\n"
	"-o FILENAME    outfile (optional, use stdout if nothing given)\n"
	"-d             decrypt\n"
	"-e             encrypt\n"
	"-c 13          code for enc / dec (value 0 ... 25, optional, default 13 if no -c)\n"
	"-f E           decrypt using frequency analysis if key is lost (try e, n, i, r, s, h, c for german)\n"
	"-h             print this help\n"
	"Examples:\n"
	"caesar -i test.txt -o secret.txt -e -c 8\n"
	"caesar -f E -i secret.txt\n"
	"caesar -h\n"
	"\n"
	);
}