Thread: Help on making program run more efficiently

Hi all,

I wrote a program that is supposed to break a ciphertext that was generated using the AES algorithm. Before writing this program, I wrote the program that implemented the AES algorithm which includes ciphering a plaintext into ciphertext using a key and deciphering that ciphertext back into plaintext using the same key.

In order to decipher a ciphertext, I need a 16 byte key. Each byte of the key is generated using the same seed. When ciphering the plaintext, the seed itself is randomly generated then used in making a 16 bytes key. What the program does is starting from seed one and incrementing, we generate a key using the seed and see if it deciphers the message. If the ciphertext is decipehered using the correct key, it prints out a message in plain english, if not, you get garbage (that we don't print out). I finished writing the program and tested a ciphertext that deciphers if seed = 5000000. That took me 20 minutes when it should've taken only about 15 seconds. Can anyone help me find a way to make my code run more efficiently? I have a ciphertext I would have to break that takes 200 times as long as that text ciphertext. For the time that it took me to break that test ciphertext, the program will have to run approximately 3 days to break the other ciphertext!

Code:

#include <stdio.h>
#define A 16807
#define M 2147483647
#define Q 127773   /*  = M/A  */
#define R 2836     /*  = M%A  */

void KeyExpansion(unsigned char [16]);
void SubWord(unsigned char *);
void RotWord(unsigned char *);

void AddRoundKey(unsigned char (*)[4], int);

void InvCipher(unsigned char *, unsigned char *);
void InvShiftRows(unsigned char (*)[4]);
void InvSubBytes(unsigned char (*)[4]);
void InvMixColumns(unsigned char (*)[4]);

void PrintState(unsigned char [4][4]);
void PrintPlaintext(unsigned char *);
int times(int, int);
int CheckBlock(unsigned char *);
unsigned long irandom(void);
unsigned char Rcon[] = {
0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 
0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a, 
0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 
0xd4, 0xb3, 0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39, 
0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 
0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 
0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04, 0x08, 
0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 
0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 
0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef, 
0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 
0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 
0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 
0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 
0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 
0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 
0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 
0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 
0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 
0xcb, 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 
0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 
0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 
0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef, 0xc5, 0x91, 
0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 
0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 
0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04, 
0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 
0xd8, 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 
0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 
0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 
0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 
0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb};

/* GF(256) logarithm      */
int L[256] = {
-1,      0, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 
0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03, 
0x64, 0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 
0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1, 
0x7d, 0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 
0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78, 
0x65, 0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 
0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e, 
0x96, 0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 
0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38, 
0x66, 0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 
0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10, 
0x7e, 0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 
0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba, 
0x2b, 0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 
0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57, 
0xaf, 0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 
0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8, 
0x2c, 0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 
0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0, 
0x7f, 0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 
0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7, 
0xcc, 0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 
0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d, 
0x97, 0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 
0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1, 
0x53, 0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 
0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab, 
0x44, 0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 
0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5, 
0x67, 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 
0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07};

/* GF(256) antilogarithm  */
int F[256] = {
0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 
0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35, 
0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 
0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa, 
0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 
0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31, 
0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 
0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd, 
0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 
0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88, 
0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 
0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a, 
0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 
0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3, 
0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 
0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0, 
0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 
0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41, 
0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 
0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75, 
0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 
0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80, 
0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 
0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54, 
0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 
0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca, 
0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 
0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e, 
0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 
0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17, 
0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 
0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x01};

/* S-Box                  */
int SB[256] = {
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 
0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, 
0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 
0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, 
0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 
0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, 
0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 
0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, 
0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 
0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, 
0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 
0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, 
0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 
0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 
0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 
0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 
0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 
0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 
0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 
0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 
0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 
0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 
0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 
0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 
0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 
0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 
0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 
0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 
0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 
0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, 
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 
0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16};

/* S-Box Inverse          */
int SBI[256] = {
0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 
0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb, 
0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 
0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb, 
0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 
0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e, 
0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 
0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25, 
0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 
0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92, 
0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 
0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84, 
0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 
0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06, 
0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 
0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b, 
0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 
0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73, 
0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 
0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e, 
0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 
0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b, 
0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 
0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4, 
0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 
0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f, 
0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 
0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef, 
0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 
0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61, 
0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 
0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d};

int Nr = 10; int Nb = 4; int Nk = 4; 
unsigned int seed;
unsigned char w[44][4];
unsigned char characters[72] = {0x20, 0x21, 0x24, 0x25, 0x2C, 0x2d, 0x2e, 0x30, 0x31, 0x32,
                                0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A, 0x3b, 0x3F,
                                0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 
                                0x4b, 0x4c, 0x4d, 0x4e, 0X4f, 0x50, 0x51, 0x52, 0x53, 0x54, 
                                0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x61, 0x62, 0x63, 0x64, 
                                0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e,
                                0X6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
                                0x79, 0x7a};

void main() {
    int i, j, round = 1;

    unsigned char key[16], output[16], input[16];
    unsigned char ciphertext[] = {0x64,0x5e,0xae,0x0d,0x03,0xbf,0x30,0xa1,0x97,0x39,0xa0,0xf5,0xcb,0x66,0x35,0xc9,
                                   0xd5,0x02,0x70,0xd2,0xf8,0xb9,0xa4,0xdb,0x6e,0xf2,0x85,0x3e,0x38,0xdb,0xe5,0x55};

    while(round > 0) {
        seed = round;
        if(round%1000000 == 0) 
            printf("checking at round %d\n", round);

        /*generating key using seed*/
        for(i=0;i<16;i++)
            key[i] = irandom()>>23;
                                
        /*generate key schedule*/
        KeyExpansion(key);
    
        /*loop through each set of 16 bytes in the cipher text*/
        for(i=0;i<2;i++) {
            for(j=0;j<16;j++)
                input[j] = ciphertext[i*16+j];
    
            /*decipher the text and put in output*/
            InvCipher(input, output);
            if(i==0) {                              /*check first block*/
                if(CheckBlock(output) == 1) {       /*if there is an invalid character*/
                    i++;                            /*increment block so that program loops back to the begining to generate a new key*/
                } else {
                    printf("Plaintext found at seed %d\n", round);  /*print the first block of plaintext*/
                    PrintPlaintext(output);
                }
            }else {
                PrintPlaintext(output);        /*if the outer for loops to the second block,*/
                printf("\n");                  /*the first block contains valid characters, now print the second block*/
            }
        }
        round++;               /*increment round to set a new seed to generate a new key*/
    }
}

/*CheckBlock checks each byte in a plaintext
  to see if it contains any invalid characters.
  The function returns 0 for a block that consists
  of only valid characters, else 1*/
int CheckBlock(unsigned char *out) {
    int j, i = 0;
    int valid = 0;
 
    /*while loop to check each character of the plaintext*/
    while(valid == 0 && i<16) {  /*while a non-character has not been found, valid will = 0*/
       valid = 1;              /*set valid = 1 at start of check*/
       j=0;
       while(valid == 1 && j<72) {     /*loop through the array that contains a list of valid characters*/
           if(out[i] == characters[j]) {
               valid = 0;      /*if the character is found in the character array, set valid to 0*/
           }
           j++;
       }
       i++;                    /*increment i to check the next character in the block*/
    }
    return valid;              /*return the value 0 if entire block consists of valid characters, else return 1*/
}

/*KeyExpansion generates a series of  */
/*round keys from the input key       */
void KeyExpansion(unsigned char k1[16]){
    unsigned char temp[4];
    int i, j;
   
   /*putting the key into w*/
   for(i=0;i<Nk;i++) {
        for(j=0;j<4;j++) {
            w[i][j] = k1[4*i+j]; 
        }
    }
   /*set i to nk to begin on 4th row 5th row of w*/
   i = Nk;

   while(i<(Nb*(Nr+1))) {
        /*get the hex values for the row prior to current row*/
        for(j=0;j<4;j++) {
            temp[j] = w[i-1][j];
        }
       if((i % Nk) == 0) {
            RotWord(temp);
            SubWord(temp);
            temp[0] = temp[0] ^ Rcon[i/Nk];
        }
        else if (Nk > 6 && (i % Nk) == 4) {
            SubWord(temp);
        }
        for(j=0;j<4;j++) {
            w[i][j] = temp[j]^w[i-Nk][j];
        }
        i++;
    }
}

/*SubWord takes a four-byte input word     */
/*SubWord takes a four-byte input word     */
/*and applies an S-box to each of the four */ 
/*bytes to produce and output word         */
void SubWord(unsigned char * t1) {
    int i;

    for(i=0;i<4;i++) {
        t1[i] = SB[t1[i]];
   }
}

/*RotWord takes a four-byte word            */
/*and performs a cyclic permutation         */
void RotWord(unsigned char * t1) {
   unsigned char a1 = t1[0];
   t1[0] = t1[1];
   t1[1] = t1[2];
   t1[2] = t1[3];
   t1[3] = a1;
}


/*AddRoundKey adds a round key to the state       */
/*using an XOR operation                          */
void AddRoundKey(unsigned char (*s)[4], int round) {
    int i,j;
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++) {
            s[j][i] = s[j][i] ^ w[round*Nb+i][j];
        }
   }
}


/*InvCipher is the inverse of AES(Cipher)           */
/*takes in a ciphertext and a 16 bytes key and      */
/*deciphers the text into plaintext                 */
void InvCipher(unsigned char * in, unsigned char * out) { 
    unsigned char state[4][4];
    int i, j;
    /*Copy input into the state matrix*/
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++) {
            state[j][i] = in[4*i+j];
        }
    }
 
    /*generate a key schedule*/
    AddRoundKey(state, Nr);

    /*loop through 10 rounds to decipher ciphertext*/
    for(i=(Nr-1);i>0;i--) {
        InvShiftRows(state);
        InvSubBytes(state);
        AddRoundKey(state, i);
        InvMixColumns(state);
    }
    InvShiftRows(state);
    InvSubBytes(state);
    AddRoundKey(state, 0);
    /*place plaintext into out array*/
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++) {
            out[i*4+j] = state[j][i]; 
        }
    }
}

/*InvShiftRows is the inverse of ShiftRows     */
/*The last three rows of the state matrix      */
/*are shifted to the right over incrementing   */
/*offsets                                      */
void InvShiftRows(unsigned char (*s)[4]) {
    unsigned char temp;

    /*shifts all bytes by one places to the right*/
    temp = s[1][3];
    s[1][3] = s[1][2];
    s[1][2] = s[1][1];
    s[1][1] = s[1][0];
    s[1][0] = temp;

    /*shifts all bytes by two places to the right*/
    temp = s[2][3];
    s[2][3] = s[2][1];
    s[2][1] = temp;
    temp = s[2][2];
    s[2][2] = s[2][0];
    s[2][0] = temp;

    /*shift all bytes by three places to the right*/
    temp = s[3][3];
    s[3][3] = s[3][0];
    s[3][0] = s[3][1];
    s[3][1] = s[3][2];
    s[3][2] = temp;
}

/*InvSubByes is the inverse of SubBytes        */
/*Each byte of the state is substituted using  */
/*the values obtained from the inverse S-box   */
void InvSubBytes(unsigned char (*s)[4]) {
    int i,j;
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++) {
            s[i][j] = SBI[s[i][j]];
       }
   }    
}

/*InvMixColumns is the inverse of MixColumns*/
void InvMixColumns(unsigned char (*s)[4]) {
    int i;
    unsigned char temp[4][4];

    /*perform calculations in temp matrix using values from state matrix that was passed into function*/
    for(i=0;i<4;i++) {
        temp[0][i] = times(0x0e, s[0][i])^times(0x0b, s[1][i])^times(0x0d, s[2][i])^times(0x09, s[3][i]);
        temp[1][i] = times(0x09, s[0][i])^times(0x0e, s[1][i])^times(0x0b, s[2][i])^times(0x0d, s[3][i]);
        temp[2][i] = times(0x0d, s[0][i])^times(0x09, s[1][i])^times(0x0e, s[2][i])^times(0x0b, s[3][i]);
        temp[3][i] = times(0x0b, s[0][i])^times(0x0d, s[1][i])^times(0x09, s[2][i])^times(0x0e, s[3][i]);        
    }
    /*places results calculated in temp matrix into state matrix that was passed into fuction*/
    for(i=0;i<4;i++) {
        s[0][i] = temp[0][i];
        s[1][i] = temp[1][i];
        s[2][i] = temp[2][i];
        s[3][i] = temp[3][i];
    }
}

int times(int x, int y) {
	if(x==0 || y==0) return 0;
	return F[(L[x]+L[y])%255];
}

/* In the array s[i][j], i is the row number and j is  */
/* the column number. I had this mixed up originally.  */
void PrintState(unsigned char s[4][4])
{
    int i, j;
    for(i = 0; i<4; i++) {
        for(j = 0; j<4; j++) {
            printf("%02x  ", s[i][j]);
        }
        printf("\n");
    }
}

/*Prints out a plaintext in ascii*/
void PrintPlaintext(unsigned char *out) {
    int i;
    /*loop through the array*/
    for(i=0;i<16;i++){
        /*prints out the value in each index*/
        printf("%c", out[i]);
    }
}

/**********************************************************************/
/*                                                                    */
/*       irandom(void) returns a long between 1 and M-1=2^31-2. Every */
/*   integer between 0 and M-1 will occur before the sequence starts  */
/*   to repeat.                                                       */
/*                                                                    */
/*   Method is based on Park and Miller, "Random number generators:   */
/*   good ones are hard to find", Comm. ACM Vol. 31 pp. 1192-1201,    */
/*   October, 1989. If you want a different initial random number,    */
/*   put some randomly chosen value such as current time into the     */
/*   global variable "seed".  (WP--12/89)                             */
/*                                                                    */
/**********************************************************************/
unsigned long irandom(void)
{
    long lo, hi;
    hi = R*(seed/Q);
    lo = A*(seed%Q);
    if(lo>hi) seed = lo-hi;
    else seed = (M-hi) + lo;
    return(seed);
}

Regards,
Jenn

Let me get this straight... You're brute-force cracking AES and you expect it to be fast?!

I don't expect brute-force cracking to be fast, because one of my assignments required me to use the Jack the Ripper software to crack as many given passwords as I can that uses some hash function to store them. I was able to crack four easy ones but one had the program running for two days and still, it wasn't able to crack that one password.

The first problem I was given was to write a program that implemented the AES algorithm. This new problem, I'm given a ciphertext ciphered using the AES algorithm with a key generated by a random seed. So the code above is half of what I wrote for my first program since I only need the deciphering algorithm plus a little more code to check every seed. Given that you know the algorithm that is used to calculate the key using a random seed, then to brute-force crack it is to find the seed by checking from 1 to infinity and see what seed(s) prints out plain english. Of course, if the seed is a massive number, then it will take some time. I have a ciphertext with a given seed of 5000000. But assuming that the seed of 5000000 wasn't given and I have to find it, I start an infinite loop at 1 and increment until the program prints in plain english which happens when seed is 5000000. My teacher said it took his code 15 seconds to loop the check on the ciphertext until the seed = 5000000 to decipher the ciphertext. My program works but takes 20 minutes so I think one of the reasons why is due to how I wrote the code.

Regards,
Jenn