학부 수업에서 다룬 AES 암호화 알고리즘에 대해 정리하고자 합니다. 과제를 위해서 정리한 내용이다보니 틀린 내용이 있을 수 있으니 주의해 주세요.
AES 알고리즘이 등장하기 이전에는 DES 알고리즘이 표준으로 사용되고 있었지만, 알고리즘의 취약점이 발견되고 나서 대책이 필요해지기 시작했다. 단순하게 DES를 3번 돌리는 Triple-DES도 사용했지만, 여전히 취약점은 존재했고 특히 S/W상에서 구현할 때 속도가 빠르지 않았다고 한다. 이후 NIST에서 새로운 알고리즘을 모집하였고 이로 인해 선택된 Rijndael의 알고리즘을 AES 알고리즘으로 채택하였다.
AES 알고리즘은 128/192/256 비트의 키, 128 비트의 데이터 블럭을 가지고 실행된다.
AES의 구조
AES는 4가지의 서로 다른 스테이지로 이루어져 있으며, permutation에 관한 스테이지가 하나, substitution에 관한 스테이지가 셋이다. 각각의 라운드마다 이 스테이지를 반복하고 새로운 word를 만들어 ciphertext가 나올 때까지 반복한다. 위에서 언급한 것과 같이 AES는 128/192/256 비트의 키를 가질 수 있는데, 가지는 키의 길이에 따라 반복하는 라운드의 수가 달라진다.
1. Substitute Bytes
각 블럭을 바이트 단위로 쪼개서 S-box를 통해 다른 바이트로 치환한다. 예를 들어, 바이트가 95라면 2A로 치환되는 것이다. 복호화하는 과정에서는 해당 치환을 복구할 수 있는 inverse S-box가 사용된다.
원래, S-box는 무작위로 생성된 것이 아니라 암호학에 기반하여 아주 신중하게 설계되었고, S-box가 없더라도 행렬 연산을 통하여 바이트를 치환할 수 있다. 그러나, 이렇게 되면 모든 바이트의 치환에 있어서 행렬 연산을 계속해서 반복해 주어야 한다는 단점이 있다. 이를 개선하기 위해 S-box를 미리 계산해 놓고, 실질적인 치환은 table lookup 연산 한 번으로 가능하도록 해서 속도를 향상시켰다.
2. Shift Rows
각각의 블럭을, 바이트를 하나의 원소로 가지는 4*4 크기의 행렬로 본 후, 각 행을 왼쪽으로 0, 1, 2, 3 바이트씩 민다. 물론 범위를 벗어난 원소는 가장 오른쪽에 다시 배치된다.
복호화할 때에는 첫번째 행부터 0, 3, 2, 1번씩 왼쪽으로 밀면 된다.
3. Mix Columns
위 스테이지와 같이 4*4 행렬을 만들어서, 열 단위로 섞는다.
맨 왼쪽의 식이 본 스테이지에서 필요한 행렬이며, 언제나 고정되어 있다. 이 역시 암호학에 기반하여 정해진 행렬이다. AES에서는 특별한 연산을 사용하게 된다.
- 두 바이트의 덧셈은 XOR 연산으로 행한다.
- 101 + 111 = 101 XOR 111 = 010
- 두 바이트의 곱셈은 shift 연산 후 XOR 연산으로 행한다.
- 011 * 101 = (101 << 1) XOR (101 << 0) = 1010 XOR 101 = 1111
그리고, AES에서는 GF(2^8)에서 연산이 이루어지므로 곱셈 연산에서 shift를 행했을 때 8자리를 넘어간다면 modulo reduction을 위해 XOR 0001 1011을 행해 준다.
예를 들어, 02 * 87 = 0000 0010 * 1000 0111 = 1000 0111 << 1 = 1 0000 1110이므로 최상위의 1을 제외하고 0000 1110 XOR 0001 1011 = 0001 0101이 최종 결과가 된다.
4. Add Round Key
이제 각 값에다가 라운드에 고유한 키를 더해 준다.
AES Key Expansion
라운드 키를 구하기 위해서 필요한 과정을 말한다. 각각의 바이트를 4개씩 묶어서 하나의 워드를 만들고, 해당 워드를 이전 워드와의 연산을 통하여 새로운 워드를 만들어내는 과정이다.
먼저, 첫 라운드 키는 그냥 키를 그대로 가져다 쓴다. 128비트 키의 경우, 각 바이트가 8비트이므로 16바이트가 나오고, 각 워드는 4바이트이므로 4개의 워드가 나오므로 하나의 라운드 키는 4개의 워드로 이루어져 있다.
이후, 다음 라운드 키는 이전 키를 워드끼리 연산하는 것으로 이루어진다.
이번 라운드 키의 워드들을 w0, w1, w2, w3이라고 하고, 다음 라운드 키의 워드들을 w4, w5, w6, w7이라 하자. 그렇다면 아래와 같이 식이 성립한다.
- w4 = w0 + g(w3)
- w5 = w1 + w4
- w6 = w2 + w5
- w7 = w3 + w6
여기서, 추가적으로 g 함수에 대해 알아야 한다.
g 함수는 위와 같은 구조로 되어 있다. 먼저, 각각의 바이트에 대해 left shift 연산을 실행한다. 그 후, 각각의 바이트를 S-box에 넣어 치환한다. 그리고, 가장 왼쪽의 바이트에만 round constant를 더해 준다. 이렇게 해서 나온 워드가 새로운 워드가 된다. round constant는 아래와 같다.
귀납적으로 정의하면, RC[1] = 1이고 RC[j] = 2*RC[j-1]이라고 정의할 수 있다. j는 round의 번호이다.
마무리
AES 암호화 과정은 여러 라운드에 걸쳐서 반복되고, Substitute Bytes -> Shift Rows -> Mix Columns -> Add Round Key의 순으로 실행하게 된다. 처음 시작할 때, 앞의 세 스테이지를 거르고 초기의 키만 더해 주는 과정이 한 번 필요하고, 이는 라운드로 치지 않는 것 같다.
128비트 키를 사용하는 AES는 10라운드로 암호화된다고 하는데, 위 예시를 보면 라운드 키를 한 번 적용하는 라운드를 제외하고 10라운드로 이루어져 있음을 알 수 있다.
참조
AES 암호화 과정을 라운드와 스테이지 별로 직접 알아볼 수 있는 시뮬레이션 사이트가 있으니 참고하면 좋을 것 같다.