AES

Rijndael 알고리즘을 기반으로하는 AES 암호화 알고리즘은 국제 표준으로 자리잡은 대칭형 암호화 알고리즘이다. AES는 128, 192, 256비트로 3가지 종류의 가변 크기 길이를 제공해준다.

동작원리

AES의 암호화 동작 원리는 크게 4가지 부분으로 나눌 수 있다. 4가지 부분을 합쳐서 Round라고 부르고 가변 크기 길이에 따라 여러 라운드를 반복하게 된다. 마지막 라운드는 Mix Columns를 수행하지 않는다.

복호화에는 암호화의 반대 순서로 진행되며 이를 위해 Inv. Shift Row, Inv. Sub Bytes, Inv. Mix Columns의 과정이 필요하다.

Sub Bytes

S-Box를 통해 Value를 변환하는 과정이다
다음과 같은 S-box 테이블을 참조하여 바이트값 a4는 1d로 치환된다

Shift Rows

Shift Rows는 바이트 배열을 Shift하는 과정이다
다음과 같은 형태로 Shift를 진행한다

Mix Columns

Mix Columns는 행렬과 곱연산을 통해 데이터를 변환한다
복호화시에는 역행렬로 복호화를 수행한다

Add Round Key

Add Round Key는 Round Key와 ^연산을 진행한다
XOR연산 특성상 Invert는 필요없다

구현

구현한 AES 코드는 다음과 같다

#include <stdio.h>
#include <stdint.h>
#include <memory.h>
#include <sys/types.h>
#include <sys/sysctl.h>
#define ROTL8(x,shift) ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift))))
#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0x1b))
#define Multiply(x,y) (((y & 1) * x) ^ ((y>>1 & 1) * xtime(x)) ^ ((y>>2 & 1) * xtime(xtime(x))) ^ ((y>>3 & 1) * xtime(xtime(xtime(x)))) ^ ((y>>4 & 1) * xtime(xtime(xtime(xtime(x))))))
#define Nb 4
int Log_Flag;
int Nr = 0;
int Nk = 0;
unsigned char in[16], out[16], state[4][4];
unsigned char RoundKey[240];
unsigned char Key[32];
int Rcon[255] = {
    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 };

void flushall(){
    fflush(stdin);
    getchar();
}


int get_cpu_info(int num){
    char buffer[1024];
    size_t size=sizeof(buffer);
    if (sysctlbyname("machdep.cpu.brand_string", &buffer, &size, NULL, 0) < 0) {
        perror("sysctl");
        return 0;
    }
    return buffer[num%size];
}

/*
 * Initilizing Sbox Table
 */
void initialize_aes_sbox(uint8_t sbox[256]) {
    printf("Initialize SBOX\n");
    uint8_t p = 1, q = 1;
    do {
        p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0);
        q ^= q << 1;
        q ^= q << 2;
        q ^= q << 4;
        q ^= q & 0x80 ? 0x09 : 0;
        uint8_t xformed = q ^ ROTL8(q, 1) ^ ROTL8(q, 2) ^ ROTL8(q, 3) ^ ROTL8(q, 4);
        sbox[p] = xformed ^ 0x63;
    } while (p != 1);
    sbox[0] = 0x63;
}

/*
 * return Sbox Value
 */
int getSboxValue(int num){
    static uint8_t SBOX[256] = {};
    if(!SBOX[0x00]) initialize_aes_sbox(SBOX);
    return SBOX[num];
}

int getrSboxValue(int num){
    static const uint8_t RSBOX[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 };
    return RSBOX[num];
}
/*
 * Produce RoundKey witch uses in each round encryption
 */
void KeyExpansion(){
    if(Log_Flag)
        printf("Key Expension\n");
    int i, j;
    unsigned char temp[4], k;
    // First Round Key is the key it self
    for(i = 0; i < Nk; i++){
        RoundKey[i<<2] = Key[i<<2];
        RoundKey[(i<<2)+1] = Key[(i<<2)+1];
        RoundKey[(i<<2)+2] = Key[(i<<2)+2];
        RoundKey[(i<<2)+3] = Key[(i<<2)+3];
    }
    
    // All other Round Key is caculate from itself
    while(i < Nb * (Nr + 1)){
        for(j = 0; j < 4; j++){
            temp[j] = RoundKey[((i-1)<<2)+j];
        }
        if(!(i % Nk)){
            // Rotate function()
            // [a0, a1, a2, a3] to [a1, a2, a3, a0]
            k = temp[0];
            temp[0] = temp[1];
            temp[1] = temp[2];
            temp[2] = temp[3];
            temp[3] = k;
            
            // Sub-bytes function()
            // mapping value with Sbox Table
            temp[0] = getSboxValue(temp[0]);
            temp[1] = getSboxValue(temp[1]);
            temp[2] = getSboxValue(temp[2]);
            temp[3] = getSboxValue(temp[3]);
            
            temp[0] ^= Rcon[i/Nk];
        }
        else if(Nk > 6 && (!(i % Nk)^4)){
            // Sub-bytes function()
            // mapping value with Sbox Table
            temp[0] = getSboxValue(temp[0]);
            temp[1] = getSboxValue(temp[1]);
            temp[2] = getSboxValue(temp[2]);
            temp[3] = getSboxValue(temp[3]);
        }
        
        RoundKey[(i<<2)] = RoundKey[(i-Nk)<<2] ^ temp[0];
        RoundKey[(i<<2) + 1] = RoundKey[((i-Nk)<<2) + 1] ^ temp[1];
        RoundKey[(i<<2) + 2] = RoundKey[((i-Nk)<<2) + 2] ^ temp[2];
        RoundKey[(i<<2) + 3] = RoundKey[((i-Nk)<<2) + 3] ^ temp[3];
        i++;
    }
}
/*
 * Add Round Key
 */
void AddRoundKey(int round){
    if(Log_Flag) {
        printf("Add Round Key\n");
        printf("Round :: %d\nKey :: ", round);
    }
    int i, j;
    for (i = 0; i<4; i++){
        for (j = 0; j<4; j++){
            state[j][i] ^= RoundKey[round * (Nb<<2) + i * Nb + j];
            if(Log_Flag) printf("%2x ",RoundKey[round * (Nb<<2) + i * Nb + j]);
        }
    }
    if(Log_Flag) printf("\n");
}

/*
 * Sub bytes
 * mapping values with Sbox Table
 */
void SubBytes(){
    int i, j;
    for(i = 0; i < 4; i++)
        for( j = 0; j < 4; j++)
            state[i][j] = getSboxValue(state[i][j]);
}

/*
 * Reverse Sub bytes
 * mapping values with reverse Sbox Table
 */
void rSubBytes(){
    int i, j;
    for (i = 0; i<4; i++){
        for (j = 0; j<4; j++){
            state[i][j] = getrSboxValue(state[i][j]);
        }
    }
}

/*
 * Shift Rows
 * Shift values
 */
void ShiftRows(){
    unsigned char temp;
    
    temp = state[1][0];
    state[1][0] = state[1][1];
    state[1][1] = state[1][2];
    state[1][2] = state[1][3];
    state[1][3] = temp;
    
    temp = state[2][0];
    state[2][0] = state[2][2];
    state[2][2] = temp;
    temp = state[2][1];
    state[2][1] = state[2][3];
    state[2][3] = temp;
    
    temp = state[3][3];
    state[3][3] = state[3][2];
    state[3][2] = state[3][1];
    state[3][1] = state[3][0];
    state[3][0] = temp;
    
}

/*
 * reverse Shift Rows
 */
void rShiftRows(){
    unsigned char temp;
    
    // Rotate first row 1 columns to right
    temp = state[1][3];
    state[1][3] = state[1][2];
    state[1][2] = state[1][1];
    state[1][1] = state[1][0];
    state[1][0] = temp;
    
    // Rotate second row 2 columns to right
    temp = state[2][0];
    state[2][0] = state[2][2];
    state[2][2] = temp;
    
    temp = state[2][1];
    state[2][1] = state[2][3];
    state[2][3] = temp;
    
    // Rotate third row 3 columns to right
    temp = state[3][0];
    state[3][0] = state[3][1];
    state[3][1] = state[3][2];
    state[3][2] = state[3][3];
    state[3][3] = temp;
}


/*
 * Mix Columns
 */
void MixColumns(){
    int i;
    unsigned char Tmp, Tm, t;
    for (i = 0; i<4; i++){
        t = state[0][i];
        Tmp = state[0][i] ^ state[1][i] ^ state[2][i] ^ state[3][i];
        Tm = state[0][i] ^ state[1][i]; Tm = xtime(Tm); state[0][i] ^= Tm ^ Tmp;
        Tm = state[1][i] ^ state[2][i]; Tm = xtime(Tm); state[1][i] ^= Tm ^ Tmp;
        Tm = state[2][i] ^ state[3][i]; Tm = xtime(Tm); state[2][i] ^= Tm ^ Tmp;
        Tm = state[3][i] ^ t; Tm = xtime(Tm); state[3][i] ^= Tm ^ Tmp;
    }
}

/*
 * reverse Mix Columns
 */
void rMixColumns(){
    int i;
    unsigned char a, b, c, d;
    for (i = 0; i<4; i++){
        
        a = state[0][i];
        b = state[1][i];
        c = state[2][i];
        d = state[3][i];
        
        state[0][i] = Multiply(a, 0x0e) ^ Multiply(b, 0x0b) ^ Multiply(c, 0x0d) ^ Multiply(d, 0x09);
        state[1][i] = Multiply(a, 0x09) ^ Multiply(b, 0x0e) ^ Multiply(c, 0x0b) ^ Multiply(d, 0x0d);
        state[2][i] = Multiply(a, 0x0d) ^ Multiply(b, 0x09) ^ Multiply(c, 0x0e) ^ Multiply(d, 0x0b);
        state[3][i] = Multiply(a, 0x0b) ^ Multiply(b, 0x0d) ^ Multiply(c, 0x09) ^ Multiply(d, 0x0e);
    }
}

/*
 * Cipher is the main function that encrypts the PlainText.
 */
void Cipher(){
    int i, j, round = 0;
    //Copy the input PlainText to state array.
    for (i = 0; i<4; i++)
        for (j = 0; j<4; j++)
            state[j][i] = in[i * 4 + j];
    
    // Add the First round key to the state before starting the rounds.
    AddRoundKey(0);
    // There will be  rounds.
    // The first Nr-1 rounds are identical.
    // These Nr-1 rounds are executed in the loop below.
    for (round = 1; round<Nr; round++)
    {
        SubBytes();
        ShiftRows();
        MixColumns();
        AddRoundKey(round);
    }
    // The last is given below.
    // The MixColumns function is not here in the last round.
    SubBytes();
    ShiftRows();
    AddRoundKey(Nr);
    // The encryption process is over.
    // Copy the state array to output array.
    for (i = 0; i<4; i++)
        for (j = 0; j<4; j++)
            out[i * 4 + j] = state[j][i];
}

void rCipher(){
    int i, j, round = 0;
    
    //Copy the input CipherText to state array.
    for (i = 0; i<4; i++)
        for (j = 0; j<4; j++)
            state[j][i] = in[i * 4 + j];
    
    // Add the First round key to the state before starting the rounds.
    AddRoundKey(Nr);
    
    // There will be Nr rounds.
    // The first Nr-1 rounds are identical.
    // These Nr-1 rounds are executed in the loop below.
    for (round = Nr - 1; round>0; round--){
        rShiftRows();
        rSubBytes();
        AddRoundKey(round);
        rMixColumns();
    }
    
    // The last round is given below.
    // The MixColumns function is not here in the last round.
    rShiftRows();
    rSubBytes();
    AddRoundKey(0);
    
    // The decryption process is over.
    // Copy the state array to output array.
    for (i = 0; i < 4; i++)
        for (j = 0; j < 4; j++)
            out[i * 4 + j] = state[j][i];
}

void Encryption(){
    int i;
    // Receive the length of key here.
    while (Nr != 128 && Nr != 192 && Nr != 256){
        printf("Enter the length of Key(128, 192 or 256 only): ");
        scanf("%d", &Nr);
    }
    // Calculate Nk and Nr from the received value.
    Nk = Nr / 32;
    Nr = Nk + 6;
    // Part 1 is for demonstrative purpose. The key and plaintext are given in the program itself.
    //     Part 1: ********************************************************
    // The array temp stores the key.
    // The array temp2 stores the plaintext.
    unsigned char temp[16] = { 0x00  ,0x01  ,0x02  ,0x03  ,0x04  ,0x05  ,0x06  ,0x07  ,0x08  ,0x09  ,0x0a  ,0x0b  ,0x0c  ,0x0d  ,0x0e  ,0x0f };
    unsigned char temp2[16] = { 0x00  ,0x11  ,0x22  ,0x33  ,0x44  ,0x55  ,0x66  ,0x77  ,0x88  ,0x99  ,0xaa  ,0xbb  ,0xcc  ,0xdd  ,0xee  ,0xff };
    // Copy the Key and PlainText
    for (i = 0; i<Nk * 4; i++){
        Key[i] = temp[i];
        in[i] = temp2[i];
    }
    //           *********************************************************
    // Uncomment Part 2 if you need to read Key and PlainText from the keyboard.
    //     Part 2: ********************************************************
    
    //Clear the input buffer
    //Recieve the Key from the user
    flushall();
    printf("Build the Key in hexadecimal: ");
    for (i = 0; i<Nk * 4; i++) {
        Key[i] = get_cpu_info(i);
        printf("%x ",Key[i]);
    }
    printf("\n");
    
    printf("Enter the PlainText in hexadecimal: ");
    for (i = 0; i<Nb * 4; i++) {
        scanf("%c",&in[i]);
    }
    
    //             ********************************************************
    // The KeyExpansion routine must be called before encryption.
    KeyExpansion();
    // The next function call encrypts the PlainText with the Key using AES algorithm.
    Cipher();
    // Output the encrypted text.
    printf("\nText after encryption:\n");
    for (i = 0; i<Nk * 4; i++)
        printf("%2x ", out[i]);
    
    printf("\n\n");
}

void Decryption(){
    int i;
    flushall();
    printf("\nThe CipherText in hexadecimal: ");
    memcpy(in,out,sizeof(in));
    for(i=0;i<Nb*4;i++)
        printf("%x ",in[i]);
    printf("\n");
    
    //The Key-Expansion routine must be called before the decryption routine.
    //KeyExpansion();
    
    // The next function call decrypts the CipherText with the Key using AES algorithm.
    rCipher();
    
    // Output the decrypted text.
    printf("\nText after decryption : \n");
    for (i = 0; i<Nb<<2; i++){
        printf("%c ", out[i]);
    }
    printf("\n\n");
}
int main(void){
    printf("[Show Log ? 1 : 0 ] : ");
    scanf("%d",&Log_Flag);
    Encryption();
    Decryption();
    return 0;
}

참조

http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf
http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
https://www.crocus.co.kr/1230