AES
AES는 연산 능력의 향상으로 DES가 더 이상 안전하지 않게 되자, 새롭게 표준으로 선정된 블록 암호 알고리즘입니다.
내부적인 논의만으로 표준으로 선정된 DES와 달리, AES는 전세계에서 암호 알고리즘을 공모받고, 전문가들의 심사를 거쳐 그 중에서 가장 뛰어난 알고리즘이 선정되었습니다.
당시 공모에 제안된 21개의 암호 알고리즘들 중, 보안성, 효율성, 하드웨어 이식의 적합성, 유연성 등을 고려하여 심사한 결과, Vincent Rijmen, Joan Daemen이 제안한 Rijndael 구조가 채택되었습니다.
표준으로 선정된 이후부터 지금까지, AES에는 기밀성을 위협하는 치명적인 취약점이 발견되지 않았습니다. 또한 CPU 제조사들이 AES 연산을 위한 명령어를 따로 정의해 주어서 암호화, 복호화의 성능도 뛰어납니다. 이런 이유로 현대에는 대칭키 암호 알고리즘을 사용할 때, 일반적으로 AES가 사용됩니다.
AES는 SPN(Substitution Permutation Network)이라는 암호 구조를 사용합니다. SPN은 곱 암호의 일종으로,
S-Box를 사용하는 치환(Substitution)과 P-Box를 사용하는 순열(Permutation)을 여러 라운드에 걸쳐 반복합니다.
페이스텔 구조와 달리 라운드마다 입력 전체에 라운드 함수를 적용하므로,
같은 수의 라운드를 사용할 때 SPN이 페이스텔 구조에 비해 암호학적으로 두 배 더 안전합니다.
AES 구조
AES는 라운드마다 128비트 크기의 블록을 암호화하는 블록 암호입니다.
키의 길이는 128, 192, 256비트 중 하나를 선택할 수 있고, 라운드 수는 키의 길이에 따라 10, 12, 14로 결정됩니다.
키의 길이가 128비트이면 AES-128, 192비트이면 AES-192, 256비트이면 AES-256이라고 부릅니다.
AES는 암호화를 할 때, 가장 먼저 각 블록을 4행 4열의 상태 배열(State)로 재구성합니다.
State의 각 칸에는 8비트(1바이트)가 저장됩니다.
입력 1F3CF203B211C5AA6EB27A45E4D98130은 다음과 같은 state로 재구성됩니다.
$$\begin{bmatrix} 1F&3C&F2&03\\B2&11&C5&AA\\6E&B2&7A&45\\E4&D9&81&30 \end{bmatrix}$$
이후에는 재구성된 입력에 대해 AddRoundKey 함수를 적용하고,
마지막 라운드 전까지 매 라운드마다 SubBytes, ShiftRows, MixColumns, AddRoundKey 함수를 반복하여 적용합니다.
마지막 라운드에서는 MixColumns를 제외한 나머지 함수들만 적용합니다.
AES의 라운드 함수들은 역함수가 존재하므로, 역함수를 이용하여 AES 복호화가 이뤄집니다.
이제부터는 라운드를 구성하는 각 함수들에 대해 알아보겠습니다.
AES 라운드 함수
SubBytes
SubBytes는 State의 각 바이트를 S-Box를 참조하여 치환하는 함수입니다. 바이트의 상위 4비트가 행, 하위 4비트가 열을 결정합니다. 예를 들어 어떤 바이트가 2A라면, 해당 바이트는 S-box의 2행 A열을 참조하여 E5로 치환됩니다.
$$SubBytes \begin{pmatrix}
\begin{bmatrix}
D7 & 32 & 97 & 71 \\
12 & AA & F2 & EC \\
04 & 00 & CA & F9 \\
5E & 13 & B1 & 16 \\
\end{bmatrix}
\end{pmatrix} =
\begin{bmatrix}
0E & C9 & F2 & 58 \\
23 & AC & 63 & 7D \\
88 & 89 & 74 & C8 \\
A3 & CE & 99 & 47 \\
\end{bmatrix}$$
ShiftRows
ShiftRows는 State의 각 행을 구성하는 바이트들을 쉬프트하는 함수입니다. 이 함수는 4가지 함수 중에서 유일하게 순열의 역할을 수행합니다. 아래와 같이 2행은 왼쪽으로 1칸, 3행은 왼쪽으로 2칸, 4행은 왼쪽으로 3칸을 밉니다. 복호화할 때는 반대로 2행, 3행, 4행을 각각 오른쪽으로 1칸, 2칸, 3칸씩 밉니다.
$$ShiftRows \begin{pmatrix}
\begin{bmatrix}
AE & 72 & 3C & 7E \\
83 & 1A & 32 & D3 \\
97 & 18 & 6A & C1 \\
56 & 0C & 29 & 86 \\
\end{bmatrix}
\end{pmatrix} =
\begin{bmatrix}
AE & 72 & 3C & 7E \\
1A & 32 & D3 & 83 \\
6A & C1 & 97 & 18 \\
86 & 56 & 0C & 29 \\
\end{bmatrix}$$
MixColumns
MixColumns는 열 단위로 치환을 수행하는 함수입니다.
$$\begin{bmatrix}
b_{0} \\
b_{1} \\
b_{2} \\
b_{3} \\
\end{bmatrix} =
\begin{bmatrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02 \\
\end{bmatrix}
\begin{bmatrix}
a_{0} \\
a_{1} \\
a_{2} \\
a_{3} \\
\end{bmatrix}$$
AddRoundKey
이 함수는 키 생성 함수(Key Schedule)로 생성된 라운드 키의 state를 각 바이트별로 XOR합니다. 복호화할 때는 XOR의 성질을 이용하여 동일한 키를 state에 XOR합니다.
$$AddRoundKey\begin{pmatrix}
state =
\begin{bmatrix}
63 & A9 & 24 & 0D \\
5C & 2A & 74 & B6 \\
A3 & 30 & 5D & 11 \\
C5 & 2C & 34 & 7C \\
\end{bmatrix},
key =
\begin{bmatrix}
21 & 3C & C5 & 71 \\
CC & 6A & 82 & C1 \\
75 & 20 & 53 & 9C \\
15 & 7C & 63 & 1E \\
\end{bmatrix}
\end{pmatrix} =
\begin{bmatrix}
42 & 95 & E1 & 7C \\
90 & 40 & F6 & 77 \\
D6 & 10 & 0E & 8D \\
D0 & 50 & 57 & 62 \\
\end{bmatrix}$$
키 생성 함수는 입력된 키로부터 각 라운드에 쓰일 라운드 키를 생성합니다. AES는 암복호화를 시작할 때와 매 라운드마다 AddRoundKey를 적용합니다. 따라서 AES-128에서는 라운드 키가 11개 필요합 합니다.
각 라운드 키는 4행 4열의 행렬이므로, 4행 44열의 키 행렬을 하나 만들고, 이를 4열씩 나눠서 매 AddRoundKey마다 사용하면 됩니다.
첫번째 AddRoundKey에서는 입력된 키를 그대로 사용합니다.
\(w_{i\geq4}\)는 \(W_{i-1}\)에 RotWord, SubWord, Rcon을 적용하고, 이를 \(W_{i-4}\)와 XOR하여 생성합니다.
