AES-128 Decryption Algorithm

<AES Decryption Algorithm>

AES 복호화 알고리즘은 아래와 같이 구성되어 있다.

박스안에 있는 내용은 Inverse Shift rows, Inverse Sub Bytes, Add Round Key, Inverse mix cols 순인데

마지막 박스(마지막 라운드)에서는 Inverse mix cols이 존재하지 않는다는 점을 유의하자.

   Ciphertext
        ↓
  Add Round Key
        ↓

Inverse Shift rows
    ↓
Inverse Sub Bytes
    ↓
Add Round Key
    ↓
Inverse mix cols

        ↓

Inverse Shift rows
    ↓
Inverse Sub Bytes
    ↓
Add Round Key
    ↓
Inverse mix cols

        ↓

Inverse Shift rows
   ↓
Inverse Sub Bytes
   ↓
Add Round Key
   ↓
Inverse mix cols

       ↓
       ...
      ↓

Inverse Shift rows
   ↓
Inverse Sub Bytes
   ↓
Add Round Key

       ↓
   Plain text

 

 

 

 

AES-128 Algorithm을 제작하므로 먼저 특징을 살펴보자면,

키 길이(word/byte/bit)	4/16/128
평문 블록 사이즈(word/byte/bit)	4/16/128
라운드 수	10
라운드 키 길이(word/byte/bit)	4/16/128
확장 키 길이(word/byte)	44/176

 

 

또한 코드에서

AES 블록의 크기는 Nb 

AES 키 길이는 Nk 

로 둘 것이기 때문에 사용하는 코드에 따라 #define Nb 4, #define Nk 4....등으로 미리 정의해두어야 한다.

 

 

 

Key Expansion

128비트의 사용자 키를 이용하여 Nb(Nr+1)개의 비밀 키 워드를 생성하는 단계이다. 

 

RotByte()는 1바이트 왼쪽 순환이동을 의미한다.

개인적으로 Rotword, Subword, Rcon의 코드 구현을 이해하느라 처음부터 가장 어려웠던 대목이다.
아래 그림을 보면, 왜 코드에 SubWord(RotWord(temp))^Rcon[i/Nk-1]가 나온 것인지 이해하기 쉬울 것이다. 설명도 꼼꼼히 읽어보자.

 

C

 

typedef unsigned int WORD;
typedef unsigned char BYTE;


WORD RotWord(WORD W)
{
	return((W & 0XFF000000) >> 24 | (W<<8);
}


WORD SubWord(Word W)
{
	int i;
    WORD out = 0, mask=0xFF000000;
    BYTE shift=24;
    
    for(i=0;i<4;i++)
    {
    	out+=(WORD)S_box[HIHEX((W&mask)>>shift)]
        [LOWHEX((W&mask) >> shift] <<shift;
        mask >>=8;
        shift-=8;
        
        W[i]=W[i-Nk]^temp;
   }
}


static WORD Rcon[11] = {0x01000000,0x02000000,0x04000000,0x08000000,0x10000000,0x20000000,0x40000000,0x80000000,0x1b000000,0x36000000};



void KeyExpansion(BYTE* key, WORD* W)
{	WORD temp; 
	int i=0; 
	while(i<Nk) 
    {
    	W[i]=(Key[4*i],Key[4*i+1], Key[4*i+2], Key[4*i+3]); 
        i=i+1; 
    } 
          
        
    i=Nk; 
    
    while(i<Nb*(Nr+1))) 
    { 
    	temp = W[i-1]; 
        temp=SubWord(RotWord(temp))^Rcon[i/Nk-1]; 
        W[i]=W[i-Nk]^temp; 
        i+=1; 
     } 
} 

 

Add Round Key

각 입력 블록에 각 라운드의 서브 키를 XOR하는 단계이다.

라운드 키는 AES키로부터 도출.

Before any round-based processing for encryption can begin, the input state array is XORed with the first four words of the key schedule. The same thing happens during decryption — except that now we XOR the ciphertext state array with the last four words of the key schedule.

 

 

Python

def addRoundKey(state, roundKey): 
	for i in range(len(state)): 
    	state[i] = state[i] ^ roundKey[i] 
        
state=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 
roundkey=[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,1] 
addRoundKey(state,roundkey) 
print state 

C

void AddRoundKey(BTYE state[][4], WORD* rKey) 
{
	int i,j;
    WORD mask,shift; 
    for(i=0;i<4;i++) 
    {
    	shift=24; mask=0xFF000000; 
        for(j=0;j<4;j++) { 
        	state[j][i] = ((rKey[i]&mask) >> shift) ^ state[j][i]; mask >> = 8; shift -= 8; } } }

state의 각각의 바이트와 라운드 키를 XOR연산하는 코드임.
중간 for문이 나오는데, state의 첫 번째 열부터 차례대로 라운드 키와 XOR연산을 수행하기 위해서 32비트 단위인 라운드 키와 8비트 씩 추출하여 state와 XOR 연산을 수행한다. -> 최종적으로 128비트의 state와 128비트의 라운드 키의 XOR연산이 되는 것!

 

 

Inverse Shift Rows

Shift = 순환(Cycle)이동이며 상태를 행 단위로 쉬프트 한다.

Inverse Shift Rows는 말그대로 반대로 오른쪽으로 쉬프트 하면 된다.


Python

def rotate(word, n): 
	return word[n:]+word[0:n] 
    
    
def shiftRowsInv(state): 
	for i in range(4): 
    	state[i*4:i*4+4] = rotate(state[i*4:i*4+4],-i) 
        
        
        
state=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 
shiftRowsInv(state) 
print state

python에서는 rotate함수를 사용할 수 있다.

 

rotate함수 사용의 예)

>>> l = [1,2,3,4]

>>> l.rotate(0) [1,2,3,4]

>>> l.rotate(1) [4,1,2,3]

>>> l.rotate(-1) [2,3,4,1]

 

C

void Inv_ShiftRows(BYTE state[][4]) 
{ 
	int i,j;
    for(i=1;i<4;i++) 
    	for(j=0;j<i;j++) 
        	Inv_CirShiftRows(state[i]); 
} 
void Inv_CirShiftRows(BYTE* row) 
{ 
	BYTE temp=row[3]; 
    row[3]=row[2]; 
    row[2]=row[1]; 
    row[1]=row[0]; 
    row[0]=temp; 
}

Inverse Sub Bytes

테이블 룩업을 이용하여 바이트 변환을 하는 과정이다.  

Python

sboxInv = [
        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
]


def subBytesInv(state):
    for i in range(len(state)):
		state[i] = sboxInv[state[i]]

state=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]


subBytesInv(state)
print state

C

void Inv_SubBytes(BYTE state[][4]) 
{ 
	int i,j; 
    for(i=0;i<4;i++) 
    	for(j=0;j<4;j++) 
        	state[i][j] = Inv_S_box[HIHEX(state[i][j])][LOWHEX(state[i][j])]; 
}

Inv_S_Box 테이블을 이용하여 state의 값을 변환하고,
이중 for문이 나오는 부분은 그냥 state의 바이트 값을 행/열로 나눈 거라고 생각하면 된다.
C에서는 매크로 함수를 돌려서 계산이 가능해서 HIHEX 로 상위 4비트 LOWHEX로 하위 4비트를 추출할 것이다.

/*매크로 함수임 구현시 선언할 것*/ 
#define HIHEX(x) (x>>4) //상위 4비트 
#define LOWHEX(x) (x&0x0F) //하위 4비트

 

 

Inv_S_Box는 아래 링크에서 가져오자.
https://en.wikipedia.org/wiki/Rijndael_S-box#Inverse_S-box

Rijndael S-box - Wikipedia

Inverse mix Columns

mixcolumns에서 곱하기 행렬 c의 역행렬을 곱하는 과정이다.

Python

unsigned char a[0x04], b[0x04], h; for (int i = 0; i<4; i++) { for (int j = 0; j<4; j++) { a[j] = plan_text[j][i]; h = (unsigned char)((signed char)plan_text[j][i] >> 7); b[j] = plan_text[j][i] << 1; b[j] ^= 0x1b & h; } plan_text[0][i] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; plan_text[1][i] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; plan_text[2][i] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; plan_text[3][i] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; }

C

void Inv_MixColumns(BYTE state[][4]) 
{ 
	int i,j; 
    BYTE a[4][4]={0x0E, 0x0B, 0x0D, 0x09,0x09, 0x0E, 0x0B, 0x0D, 0x0D, 0x09, 0x0E, 0x0B,0x0B, 0x0D, 0x09, 0x0E}; 
    BYTE b[4][4]={0,}; 
    for(i=0;i<4;i++) 
    	{ for(j=0;j<4;j++) 
        	for(k=0;k<4;k++)
            	b[i][j]^=x_time(a[i][k], state[k][j]); 
        } 
    for(i=0;i<4;i++) 
    	for(j=0;j<4;j++) 
        	state[i][j]=b[i][j];
} 

두번째 for문에서 각각의 열을 역변환 행렬과 곱한다. i는 state의 열을 의미하고, 이중 for문을 사용하여
state의 한 열과 역변환 행렬의 곱을 수행한다. 곱셈은 GF(2^8)상태에서 수행해야 하므로

여기서 곱셈을 할 때 x_time 함수를 사용한다.
Mixcolumns의 행렬 곱셈 연산을 할 때 (X2)연산과 (+1)연산을 통해 구한다는 것은 익히 알고 있는 사실일 것이다.
여기서 (X2) 연산을 AES에서 x_time 으로 부르는 것이다.
코드를 보면 다음과 같다.

BYTE x_time(BYTE b, BYTE n) 
{ 
	int i; 
    BYTE temp=0, mask=0x01; 
    for(i=0;i<8;i++) 
    { 
    	if(n&mask) temp^=b; 
        if(b&0x80) b=(b<<1)^0x1B; 
    else 
    	b<<=1; 
        mask<<=1; 
    }
    return temp; 
}

GF(2^8) 곱셈 연산 프로그램으로 보자. 그래도 이해하기 복잡하다면 그냥 b와 n의 곱셈 연산을 수행하는 함수라고 보면 된다.






참고자료

Lecture8.pdf (purdue.edu)

AES Standard Decryption Algorithm (herongyang.com)

AES Standard Decryption Algorithm

https://en.wikipedia.org/wiki/Rijndael_MixColumns

Rijndael MixColumns - Wikipedia

Implementing AES (nindalf.com)

Implementing AES

AES 암호화 – 로우폴리 저장소 (wordpress.com)

AES 암호화

AES Encryption (asecuritysite.com)

AES Encryption

 

+) 직접 테스트 해보는 사이트도 찾았다.
AES (Rijndael) Encryption Test in JavaScript (hanewin.net)

AES (Rijndael) Encryption Test in JavaScript