[c] AES 구조 및 코드

AES 구조

AES(Advanced Ecryption Standard)는 1997년 DES를 대체할 목적으로 NIST 암호 표준 공모를 하여 2001년에 채택된 암호 표준이다.

feistel 구조인 DES와 달리 SPN구조로 되어있어서 복호화시 역연산의 알고리즘을 따로 구현해야 하지만 병렬 처리를 하기 용이하다..

확장성을 고려하여 설계되어서 키 길이는 128/192/256 bit를 가지고 키 길이에 상관없이 블록 길이는 128 bit이며 라운드 수는 10/12/14를 가진다.

대략 적인 순서는

1. 라운드키와 xor한다. (AddRoundKey)

2. 바이트를 치환한다. (SubBytes)

3. 행별로 바이트를 옮긴다. (ShiftRows)

4. 열 별로 바이트를 섞는다. (MixColumns)

5. 라운키와 xor한다. (AddRoundKey)

6. (라운드 수 - 1) 만큼 2~5를 반복한다.

7. 마지막 라운드는 MixColumns를 제외하고 수행한다.

복호화는 각 단계의 역연산을 거꾸로 수행하면 된다.

이제 각 단계를 살펴보자.

aes는 입력 블럭을 위 그림과 같은 행렬로 구성하여 처린한다. 최 상위 한바이트씩 총 16바이트 가 들어가는데 주의할 점은

S00 , S01, S02, ......., S33 순이 아닌 S00, S10, S20, ......, S33순으로 즉 열 우선으로 넣어야 한다.

void AddRoundKey(BYTE 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한다.

Subbytes

SubBytes는 위 행렬식을 곱하여 바이트를 치환한다. X0 ~ X7순으로 바이트의 최상위 비트를 위치하여 계산한다.

메모리가 부족한 시스템이라면 직접 계산을 하여 구하지만 보통은 미리 모든 바이트가 계산된 치환표를 사용한다.

SubBytes 치환표

가령 0x37을 치환하면 0xb2로 바뀐다. 복호화시에는 동일하게 역 치환표도 있다.

치환표를 사용하지 않고 계산할 때에는 해당 바이트에 [1 0 1 0 0 0 0 0]을 빼고 위 8x8행렬의 역행렬을 곱해주면 된다.

void SubBytes(BYTE state[][4]) {
	int i, j;

	for (i = 0; i < 4; i++)
		for (j = 0; j < 4; j++)
			state[i][j] = S_box[HIHEX(state[i][j])][LOWHEX(state[i][j])];
}

* HIHEX(), LOWHEX()는 각각 상위4비트 하위4비트를 반환하는 함수.

각각의 바이트에 대하여 구해준다.

ShiftRows

첫행은 움직이지 않고 둘째행은 1번, 셋째행은 2번, 넷째행은 3번 바이트단위로 왼쪽순환쉬프트를 한다.

void ShiftRow(BYTE state[][4]) {
	int i, j;

	for (i = 1; i < 4; i++)
		for (j = 0; j < i; j++)
			CirshiftRows(state[i]);
}

void CirshiftRows(BYTE state[]) {
	BYTE temp = state[0];

	state[0] = state[1];
	state[1] = state[2];
	state[2] = state[3];
	state[3] = temp;
}

코드도 간단하다.

MixColumns 행렬식

MixColumns는 배열의 각 열에 대하여 위 그림과 같은 연산을 수행하는데 기약다항식 x^8 + x^4 + x^3 + x + 1 = 0 상에서 하게 되며 따라서

캐리 발생시 0001 1011을 xor한다.

void MixColumns(BYTE state[][4]) {
	int i, j, k;
	BYTE a[4][4] = { 0x2, 0x3 , 0x1, 0x1,
		0x1, 0x2, 0x3, 0x1,
		0x1, 0x1, 0x2, 0x3,
		0x3, 0x1, 0x1, 0x2 };

	for (i = 0; i < 4; i++) {
		BYTE temp[4] = { 0, };

		for (j = 0; j < 4; j++)
			for (k = 0; k < 4; k++)
				temp[j] ^= x_time(state[k][i], a[j][k]);

		state[0][i] = temp[0];
		state[1][i] = temp[1];
		state[2][i] = temp[2];
		state[3][i] = temp[3];
	}
}

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;
}

x_time() 함수는 곱하려는 행렬 값에 따라 기약다항식 상에서 값을 배수해주는 함수이다.

역 MixColumns함수의 경우 4x4행렬의 역행렬을 사용한다.

키 확장

라운드 키는 128비트 기준 총 11개(첫 Addroundkey포함)이고 각 키는 4개의 의 워드로 구성되기때문에 총 44개의 워드가 필요하다.

키 확장의 순서는 이렇다.

1. 키를 4바이트씩 나누어 4개의 워드로 만든다.

2. 이전 번의 워드와 4번째전 워드를 xor하여 새 워드를 생성한다. ( 4의 배수 번째의 경우 이전 워드를 g함수에 통과시킨다.)

    

    2-1. 입력의 워드를 1바이트만큼 왼쪽 순환시프트를 한다.

  

    2-2. Subbytes에 썼던 치환을 여기서도 사용한다.

    2-3. 상수값 R과 xor하여 결과를 반환한다.

3. 워드가 44개 생성될때까지 2를 반복한다.

R상수

void KeyExpansion(BYTE key[], WORD w[]) {
	int i = 0;
	WORD temp;

	while (i < Nk) {
		w[i] = BTOW(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];
		if (i%Nk == 0)
			temp = SubWord(RotWord(temp)) ^ Rcon[i / Nk - 1];
		else if ((Nk > 6) && (i%Nk == 4))
			temp = SubWord(temp);

		w[i] = w[i - Nk] ^ temp;
		i += 1;
	}
}

* Nk : 키 바이트수(4), Nb : 블럭 수(4), Nr : 라운드수(10)

이상 AES의 알고리즘에 대해 알아보았다...