Help on making program run more efficiently

This is a discussion on Help on making program run more efficiently within the C Programming forums, part of the General Programming Boards category; Hi all, I wrote a program that is supposed to break a ciphertext that was generated using the AES algorithm. ...

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    7

    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
    Last edited by peeweearies; 03-22-2009 at 08:51 PM.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Let me get this straight... You're brute-force cracking AES and you expect it to be fast?!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    7
    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
    Last edited by peeweearies; 03-23-2009 at 02:32 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Run dos program invisibly?
    By chico1st in forum Windows Programming
    Replies: 2
    Last Post: 01-07-2009, 09:07 AM
  2. Help me with my basic program, nothing I create will run
    By Ravens'sWrath in forum C Programming
    Replies: 31
    Last Post: 05-13-2007, 02:35 AM
  3. Replies: 2
    Last Post: 12-22-2006, 07:45 PM
  4. Making standalone APP run in background
    By hart in forum Windows Programming
    Replies: 3
    Last Post: 02-27-2005, 10:20 AM
  5. help making a program run
    By Dummies102 in forum C++ Programming
    Replies: 3
    Last Post: 02-22-2002, 11:51 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21