[암호] AES (Advanced Encryption Standard) - 1

References

• 리얼월드 알고리즘

Contents

• AES란?
• AES 암호화/복호화 알고리즘
• Key Scheduling
• C++ 구현

---

AES (Advanced Encryption Standard) ?

현대 암호 기술은 특정한 수학적 방법을 사용하여 암호문을 생성합니다. 이러한 방법에는 상대적으로 짧은 몇백 또는 몇천 비트 길이의 키를 사용하는데, 평문과 이 암호화 키를 함께 취하여 암호화 키가 없다면 역으로 평문을 얻을 수 ㅇ벗는 복잡한 방식으로 암호화합니다.

 

AES 또한 이 방법을 사용하고 있으며, 거의 모든 곳에서 사용되는 방법입니다. AES는 미국 국립표준기술연구소에서 2001년에 채택한 표준으로, 기존 데이터 암호화 표준인 DES를 대체하기 위해 채택되었습니다.

이 프로세스에서 Rijndael(레인달) 알고리즘이 채택되었으며, 엄밀하게는 암호화 블럭의 크기가 128비트이고, 암호화 키의 길이가 128, 192, 256비트인 세 가지 종류가 AES 표준으로 지정되었습니다. 이는 각각 AES-128, AES-192, AES-256으로 불립니다.

---

AES 암호화

AES는 복잡한 알고리즘입니다. 특히나 완벽히 이해하지 위해서는 수학적 지식도 필요한데, 이번 글에서 수학적으로는 깊게 다루지는 않을 예정입니다. S-box나 MixColumns에서 왜 특정 고정 행렬을 사용하는지 등등..

(저의 부족한 지식 때문에 ㅠ.ㅠ)

 

AES는 평문에 연속된 연산을 수행하는데, 그 과정은 다음과 같습니다.

 

먼저, 평문을 128비트 또는 16바이트의 블록(Block)으로 쪼갭니다.

AES는 비트들의 블록에서 작동하므로 블록 암호(block cipher)입니다.
대조적으로 스트림 암호(stream cipher)가 있는데, 이것은 개별 바이트나 비트 단위로 작동합니다.

위에서 언급했듯이 AES는 128, 192, 또는 256비트 길이의 암호화 키를 사용합니다.

우선 128비트 길이의 키를 사용한다고 가정하고 설명하겠습니다.

 

바이트들은 열 우선 행렬에 열 단위로 채워지는데, 이 행렬을 상태 행렬(state matrix)라고 합니다.

CreateState 연산

위 그림처럼 블록이 \(p_0, p_1, ..., p_{15}\)로 구성되어 있다면, 바이트 \(p_i\)는 바이트 \(b_{j, k}\)로 상태 행렬에 채워지는데, 이때 j = i mod 4 이고, k = i/4 입니다.

위 그림에서 상태 행렬 s를 반환하는 함수가 CreateState라는 함수에 구현되어 있다고 가정하겠습니다.

 

초기 상태 행렬을 얻었다면, 이제 다음 단계로 넘어가게 됩니다.

바로 암호화 키를 가져와서 상태 행렬과 유사하게 열 순서로 정렬된 일련의 추가 키를 생성하게 되는데, 이 추가 키는 AES 알고리즘에서 각 라운드(round)마다 키 하나를 생성하여 사용하기 때문에 라운드 키(round key)라고 합니다.

사실 라운드 반복이 시작되기 전에 추가 키 하나가 필요하므로 사용할 추가 키는 반복되는 라운드 수보다 하나 더 많습니다.

이렇게 추가로 키를 생성하는 것을 KeyExpansion이라고 하고, 암호가 어떤 종류의 공격에도 견고하도록 키를 변경하는 것을 키 화이트닝(Key whitening)이라고 합니다. KeyExpansion에 대해서는 깊게 다루지는 않고, 아래의 Key Schedule에서 다시 설명하겠습니다.

 

이렇게 추가 키, 즉 라운드 키를 얻게 된다면 이 라운드 키를 가지고 와서 라운드 키의 각 바이트에 해당하는 상태 행렬의 바이트와 XOR 연산을 수행합니다. 이 연산은 AddRoundKey라고 하는 \(x_{i, j} = p_{i, j} \oplus k_{i, j}\) 연산의 결과로 원소들의 새로운 상태를 얻습니다.

AddRoundKey 연산

 

다음 단계는 AddRoundKey 연산의 결과에 일련의 라운드를 수행하는 것입니다. 여기서 라운드의 수는 키의 길이에 종속되어 128비트 키는 10 rounds, 192비트 키는 12 rounds, 256비트 키는 14 rounds를 수행합니다.

 

각 라운드의 첫 번째 연산은 SubBytes라고 하며, 현재 상태 행렬에서 S-box라는 다른 행렬에서 바이트를 가져와 각 바이트를 대체합니다.

S-box는 갈루아 필드 GF(\(2^8\)) 상에의 매핑된 값으로 구성되어 있습니다.
(참조 : https://en.wikipedia.org/wiki/Rijndael_S-box)

S-box는 16x16 행렬이며, 다음과 같이 계산됩니다.

출처 : https://en.wikipedia.org/wiki/Rijndael_S-box

SubBytes에서 변환은 다음과 같은 방법으로 이루어집니다.

 

상태 행렬의 요소인 \(x_{i, j}\)는 1바이트의 크기를 가지고 있기 때문에 두 개의 16진수 \(h_1 h_2\)로 표현할 수 있습니다. SubBytes 연산의 결과는 이렇게 표현된 \(h_1\)과 \(h_2\)를 가지고, S-box의 \((h_1, h_2)\) 원소입니다.

 

아래의 예를 들면, 0x19라는 상태 행렬 요소 값이 있다면, SubBytes 연산을 수행하고 나면 0x19값은 S-box의 (1, 9)번째 원소의 값인 0xD4로 변하게 됩니다.

 

따라서, 위 상태 행렬에 SubBytes 연산을 하게 되면, 아래의 결과를 얻을 수 있습니다.

 

라운드의 두 번째 연산은 ShiftRows 연산이라고 합니다. 이 연산은 첫 번째 위치부터 각 행의 위치가 증가되는 수 만큼 상태 행렬의 각 행을 왼쪽으로 이동하게 합니다. 

1행은 그대로 두고, 2행은 1만큼, 3행은 2만큼, 4행은 3만큼 왼쪽으로 이동합니다.

아래와 같이 변환됩니다.

 

라운드의 세 번째 연산은 MixColumns 라고 하며, 현재 상태 행렬에서 각 열을 가져와 새로운 열로 변환합니다. 이때 새로운 열로 변환하기 위해서 4x4의 고정된 행렬을 사용하는데, 모든 열에 대해서 동일하게 사용됩니다.

\[\begin{bmatrix} 2 & 3 & 1 & 1\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2 \end{bmatrix}\]

사용되는 고정 행렬은 위와 같습니다.

2, 3, 1, 1 이라는 숫자만 사용되는 이는 의도적으로 사용되는 숫자입니다.
bit 단위에서 1을 곱하는 것은 아무 변화가 없으며,
2를 곱하는 것은 왼쪽으로 1 shift 하는 것이고, 3을 곱하는 것은 왼쪽으로 1 shift하고 기존 값과 XOR 하는 것입니다.

위 이미지의 왼쪽의 상태 행렬에서 각 열을 가져와서 오른쪽의 식처럼 계산하면 됩니다만, 통상적인 행렬 곱셈이 아닌 갈루아 필드 GF(\(2^8\)) 안에서 8차수의 기약다항식을 이용한 모듈로 다항식에서 수행됩니다. 덧셈은 기본 비트 패턴에 대한 간단한 XOR 연산이고, 곱셈은 조금 더 복잡하지만 아래와 같이 간단하게 계산할 수 있습니다.

(기약다항식 참조 : https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%95%BD_%EB%8B%A4%ED%95%AD%EC%8B%9D)

따라서 1 바이트 값에 1, 2, 3에 의한 곱셈을 정의하면 다음과 같습니다.

\[\begin{matrix} 1 \cdot a = a\\ 3 \cdot a = 2 \cdot a \oplus a \end{matrix}\]

\[2 \cdot a = \begin{cases} (a_6, ..., a_0, 0) & \text{ if } a_7=0 \\ (a_6, ..., a_0, 0) \oplus (0, 0, 0, 1, 1, 0, 1, 1) & \text{ if } a_7=1 \end{cases}\]

 

위 예제 1열의 계산 결과에서 1행 1열(0x04)에 대한 계산 과정을 풀어보면 다음과 같습니다.

\[\begin{align*}
\text{0x}02 \cdot \text{0x}D4 &= (\text{0b}11010100 \ll 1) \oplus \text{0b}00011011\\ 
 &= \text{0b}10101000 \oplus \text{0b}00011011 \\
 &= \text{0b}10110011 \\
\text{0x}03 \cdot \text{0x}BF &= \text{0x}BF \oplus (\text{0x}02 \cdot \text{0x}BF) \\
 &= \text{0b}10111111 \oplus ((\text{0b}10111111 \ll 1) \oplus \text{0b}00011011) \\
 &= \text{0b}10111111 \oplus (\text{0b}01111110 \oplus \text{0b}00011011) \\
 &= \text{0b}10111111 \oplus \text{0b}01100101 \\
 &= \text{0b}11011010 \\
\text{0x}01 \cdot \text{0x}5D &= \text{0b}01011101 \\
\text{0x}01 \cdot \text{0x}30 &= \text{0b}00110000
\end{align*}\]

각 계산 결과를 전부 XOR 하면,

\[\begin{align*} \text{0b}10110011 \oplus \text{0b}11011010 \oplus \text{0b}01011101 \oplus \text{0b}00110000 \\ = \text{0b}00000100 = \text{0x}04 \end{align*}\]

가 됩니다.

동일한 방법으로 모든 열을 구하게 되면, 다음의 상태 행렬을 얻을 수 있습니다.

그리고 MixColumns 연산은 마지막 라운드에서는 수행하지 않습니다.

 

라운드의 마지막 연산은 상태 행렬에 라운드를 시작하기 전에 수행했던 라운드 키를 추가하는 AddRoundKey 연산입니다.

 

요약하면 AES 암호화 알고리즘은 다음과 같이 동작합니다.

b : 16바이트 블록
k : 암호화 키
n : 라운드 수(128비트 키의 경우 10)
s : b에 대응하는 암호문

s <- CreateState(b)
rk <- ExpandKey(k)
s <- AddRoundKey(s, rk[0])
for i <- 1 to n do
	s <- SubBytes(s)
    s <- ShiftRows(s)
    s <- MixColumns(s)
    s <- AddRoundKey(s, rk[i])
s <- SubBytes(s)
s <- ShiftRows(s)
s <- AddRoundKey(s, rk[n])
return s;

---

Key Schedule

암호화키(Cipher Key)를 가지고 라운드 키를 생성하는 작업을 Key Schedule이라고 합니다.

위에서 ExpandKey 연산이 이에 해당되는데, 이 과정에서도 암호화에 사용했던 S-box와 또 다른 특정 행렬이 사용되며 이 특정 행렬은 Round Contants라고 합니다. 

Key Schedule은 RotWord와 SubWord라는 연산과 일련의 XOR 연산으로 이루어져 있습니다.

 

먼저 RotWord 연산은 왼쪽으로 한 바이트씩 shift하는 연산입니다.

RotWord 연산

위와 같은 암호화키가 있을때, 4열에 위치하는 하나의 Word(32bit)에 RotWord 연산을 수행하면 위쪽으로 한 칸씩 shift 됩니다.

 

SubWord는 암호화 과정의 SubBytes와 동일합니다. 각 바이트의 값에 매핑되는 S-Box의 값을 가져오면 됩니다.

SubBytes

 

Round Constants에 대한 자세한 내용은 저도 아직 다 파악하지 못해서, 위키의 설명을 가져왔습니다.

(참조 : https://en.wikipedia.org/wiki/AES_key_schedule)

rcon이라고 불리는 행렬을 사용하는데, AES128인 경우 총 10개의 라운드를 수행하므로 4행 10열인 행렬을 사용하게 됩니다. 위 설명을 토대로 rcon을 구하면 아래와 같습니다. 1행만 채워져있고 나머지는 값이 모두 0입니다.

이제 원래 암호화키를 가지고 어떻게 라운드키로 확장하는지 아래 예제를 통해 살펴보겠습니다.

라운드키를 확장하는 과정은 아래의 과정의 반복입니다. 하나의 라운드키를 어떻게 구하는지 살펴보겠습니다.

처음 \(W_{i-4}\)에서 \(W_{i-1}\) 까지의 행렬이 원래의 암호화키입니다. 그리고 첫 번째 라운드키는 \(W_{i}\)에서 \(W_{i+3}\) 까지의 행렬이 됩니다.

 

여기서 먼저 첫 번째 라운드키에 해당되는 \(W_i\)열을 구해보겠습니다.

\(W_i\)열을 구하기 위해서는 현재 구하고자하는 열의 이전 열(\(W_{i-1}\)를 가져와서 RotWords와 SubBytes 연산을 수행합니다. 

그 다음으로 \(W_{i-3}\) 열과 Rcon의 첫 번째 열을 가져와서 XOR 연산을 수행합니다. 그 과정은 위 이미지에 잘 나와있습니다. 첫 번째 행의 XOR 연산만 해보면, 다음과 같이 계산됩니다.

\[\begin{align*} \text{0x}2B \oplus \text{0x}8A \oplus \text{0x}01 &= \text{0b}00101011 \oplus \text{0b}10001010 \oplus \text{0b}00000001 \\ &= \text{0b}10100001 \oplus \text{0b}00000001 \\ &= \text{0b}10100000 \\ &= \text{0x}A0 \end{align*}\]

 

그 다음 열을 구하는 것은 방금 전과 조금 다른데, RotWords와 SubBytes 연산이 수행되지 않습니다.

남은 두 개의 열도 마찬가지로 \(W_{i-4} \oplus W_{i}\)로 구하면 된다. 그렇게 첫 번째 라운드키를 구하면 다음과 같은 결과를 얻을 수 있습니다.

그리고 다음 라운드는 처음으로 돌아가서 반복하면 되는데, 이때 사용되는 Rcon이 변경됩니다.

첫 번째 라운드 키를 구할 때는 [0x01 0x00 0x00 0x00]을 사용했다면, 두 번째 라운드 키를 구할 때는 [0x02 0x00 0x00 x00]을 사용하는 것입니다. 나머지 라운드키는 다음 글에서 직접 C++로 구현한 뒤에 결과를 살펴보도록 하겠습니다 !

---

AES 복호화

AES로 암호화된 암호문을 복호화하는 것은 암호화에서 사용한 연산의 간단한 변형입니다. 연산 순서에서 일부 변화 외에 로직은 거의 같다고 보시면 됩니다.

 

중요한 차이점은 다음과 같습니다.

1. Inverse S-Box 사용
2. Round Key는 역순으로 사용
3. ShiftRows는 왼쪽이 아닌 오른쪽으로 shift
4. MixColumns에서 사용되는 특정 행렬은 암호화 과정에서 사용된 행렬의 역행렬
5. SubBytes와 ShiftRows의 순서 변경 / MixColumns와 AddRoundKey 순서 변경

알고리즘은 다음과 같습니다.

s <- CreateState(b)
rk <- ExpandKey(k)
s <- InvAddRoundKey(s, rk[n])
for i <- 1 to n do
	s <- InvShiftRows(s)
    s <- InvSubBytes(s)
    s <- InvAddRoundKey(s, rk[n-i])
    s <- InvMixColumns(s)
s <- InvShiftRows(s)
s <- InvSubBytes(s)
s <- InvAddRoundKey(s, rk[0])
return s;

암호화에서 사용된 연산의 간단한 변형임을 나타내기 위해서 각 연산에 Inv라는 접두어를 붙였습니다.

복호화의 각 연산은 다음 글에서 C++로 구현된 코드를 살펴보면서 다시 설명하도록 하겠습니다.

 

이상 AES 알고리즘에 대해서 간단하게 알아보았고, 다음 글에서 직접 C++로 구현해보도록 하겠습니다.

 

코드는 여기서 미리 확인해볼 수 있습니다.

https://github.com/junstar92/DataStructure_Algorithm/tree/master/Algorithm/AES

GitHub - junstar92/DataStructure_Algorithm