1. AES 란?
AES (Advanced Encryption Standard) 란 표준 암호화 알고리즘으로 Rijmen과 Daemen이 개발한 Rijndael 알고리즘이 AES 공모에서 선정되면서 AES로 암호화 표준이 되었다.
AES 알고리즘은 128비트 단위로 이루어 지며, AES 알고리즘은 Add Round Key , Sub Byte, Shift Row, Mix Column 이 반복 되어 이루어진다. AES 암/복호화의 전체적인 알고리즘은 아래 그림과 같다. AES 알고리즘 중 각각 부분의 알고리즘은 아래에서 설명하겠다.
2. AES 암호화 알고리즘
※ AES 알고리즘의 설명 전에 알아야 할점
(1) AES 알고리즘의 연산은 GF(Galois Field) 중 GF(2^8) 에서 이루어지며, AES 에서 사용하는 기약다항식은 m(x)=x^8+x^4+x^3+x+1로 정해져 있다.
(2). AES 알고리즘에서 덧셈 연산은 XOR로 대체된다. 따라서 AES 내에서 뺄셈도 동일하게 XOR로 연산된다.
(3). AES 알고리즘에서 8비트 곱셈 연산이 등장하는데, AES에서는 곱셈 연산을 (x2) 연산과 (+1) 연산을 통해 구한다. 이때 (x2) 연산을 AES에서는 보통 xtime 이라 부른다.
이때 xtime 연산은 8비트 입력값을 왼쪽으로 1비트 쉬프트하여 구현되는데, 이때 최상위 비트가 1인 경우 0x1b(00011011)를 XOR 한다. 이는 우선 2진수에서 왼쪽으로 1비트 쉬프트하면 곱하기2 연산이 된다는점과 AES에서 사용하는 기약다항식이 x^8+x^4+x^3+x+1이기 때문이다 기약다항식을 최상위 비트인 x^8을 제외하고 8비트 바이너리로 표현하면 0x1b가 된다.
AES 알고리즘에서 (x2) 연산과 (+1)을 통해 곱셈을 구현하는 법은 예를 들어 표현하겠다. a 에 9를 곱한다고 가정하겠다. 이는 a*(2^3) + a 로 쓸수있다.(x2)연산이 xtime이므로 a를 xtime에 3번 통과시킨 결과와 a를 XOR 하면 a에 9를 곱한 결과가 나오는 식이다.
(4) AES 알고리즘에서는 아래와 같이 128비트를 4x4 행렬로 표현하며, 행렬의 한칸은 1바이트(8비트)를 뜻하며 각각은 16진수로 표현하였다.
아래는 AES 암호화에서 입력값 00112233445566778899aabbccddeeff을 나타낸것으로 왼쪽 위에서부터 세로로 배열된다.
1) Add round key
데이터와 키를 XOR 한다.
2) Sub byte
Sub byte 연산은 8비트 단위로 데이터를 치환하는 연산으로서, 실제 연산은 1바이트를 GF(2^8) 상에서의 역원을 구한후 아핀 변환을 하는 연산이다. 8비트씩의 연산을 반복하여 128비트 모두를 치환한다.
메모리의 여유가 있다면 모든 입력에 대한 연산을 계산한 표인 S-Box를 만들고 이를 사용해 치환하는 방법도 많이 사용한다. S-Box를 사용한 치환 방법은 그림을 통해 설명하겠다.
아래 그림은 S-box를 사용하여 0x7a을 치환하는 것을 나타낸 그림이다. 아래 표에서 X부분에 16진수의 앞자리를 선택하고, Y부분에 뒷자리를 선택하여 만나는 곳이 Sub Byte 연산의 결과가 된다. 따라서 0x7a의 연산 결과는 0xda가 된다.
※ GF(2^8)에서의 역원은 확장된 유클리드 호제법을 사용하여 구할 수 있다.
※ AES 에서 아핀 변환은 아래와 같이 연산된다. 이때 b0~b7이 입력되는 데이타로, 상위비트가 아래 위치한다.
3) Shift row
행단위로 Shift 연산을 한다.
4) Mix column
각각의 바이트에 특정행렬과 곱연산을 가하여 변환한다. 아래 그림에서 왼쪽의 2311 행렬부분이 암호화에 쓰이는 행렬이며, 곱해지는 것은 예시로 입력한 32비트 입력이다. 연산은 행렬의 곱연산과 동일하게 이루어진다. 따라서 2*d4 + 3*bf + 5d + 30이 될것이다. 이때 곱연산은 '알고리즘의 설명 전에 알아야 할점' 에서 소개한 방식으로 xtime으로 구현하고, 덧셈은 XOR로 바꾸만 하면 된다. 이와 같이 연산하면 아래그림과 같이 04가 나올것이다. 각 행에 대해 연산하여 32비트를 모두 연산한다.
3. Key Schedule
AES 암복호화에 쓰이는 전체 알고리즘을 보면 Add Round Key에 Round Key 1부터 Round key 9까지가 입력되는 것을 볼 수 있다. 이때 AES 알고리즘에 사용되는 Round Key들을 입력된 key를 통해 생성하는 알고리즘을 Key Schedule 이라 한다.
AES 모듈에 아래와 같이 Key가 입력되었다고 가정하겠다.
우선 가장 마지막 4바이트를 뽑아 한칸 쉬프트하고 Sub Byte 연산을 한다.
그 후 R Con과 XOR 연산을 하는데 R Con은 아래와 같은 행렬로 1 라운드마다 하나씩 앞에서 부터 순서대로 사용한다. 그 다음 Key의 첫번째 열과 XOR 한 결과가 첫번째 Round Key의 첫번째 열이 된다.
다음으로는 이렇게 계산된 첫번째 열과 Key의 두번째 열을 XOR하여 Round Key의 두번째 열을 계산한다.
이 방식으로 세번째, 네번째 행을 계산하면 첫번째 Round Key가 생성된다. 또한 첫번째 Round Key로 처음부터 다시 반복하면 두번째 Round Key를 생성할 수 있다.
1lime
아두이노와 프로그래밍, 전자공학 학생의 개인적 프로젝트 모음