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).

/*
 * 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
#include
#include

/*
-i infile
-o outfile
-d decrypt
-e encrypt
-c code
-f freq analysis
-h help
*/

#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);
inline void swapC (char *a, char *b);
inline 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 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]=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
 */
inline void swapC (char *a, char *b) {
    static char c;
    c =*a;
    *a=*b;
    *b=c;
}
inline 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"
    );
}

Have fun!