AES(Advanced Encryption Standard) - 2

3. Key Expansion

각 라운드에 사용하는 라운드 키를 생성하기 위해서 AES는 키 확장 과정을 사용한다.

$N_r$을 라운드 수라고 하면 키 확장 과정을 통해서 하나의 128비트 암호 키로부터 $N_r+1$개의 128비트 라운드 키를 생성한다.

 

처음 생성한 라운드 키는 알고리즘을 시작하기 전에 평문과 XOR하고(AddRoundKey),

나머지 라운드 키들은 각 라운드의 마지막 단계에서 XOR 연산을 한다.

 

워드는 4개의 바이트로 이루어진 단위이다.

키 확장 루틴은 워드 단위로 라운드 키를 생성한다.

루틴은 $4 x (N_r+1)$ 워드를 생성한다.

즉 10라운드로 이루어진 AES-128의 경우 44워드, 12라운드로 이루어진 AES-192의 경우 52워드, 14라운드로 이루어진 AES-256의 경우 60개의 워드가 필요하다.

 

각 라운드의 키는 4개의 워드로 이루어진다.

 

3-1. AES-128의 Key Expansion

 

1. 키 분할

• 16바이트 키를 4바이트씩 잘라서 $w_0, w_1, w_2, w_3$을 만든다.

 

2. $w_i$ 생성 ($4 \leq i \leq 43$)

   

   (1) $i$가 4의 배수

• 먼저, 직전 워드 $w_{i-1}$로 임시값 $t_i$를 만든다.
• RotWord
  • 바이트를 왼쪽으로 한 칸 회전시킨다.
  • 예) [a b c d] → [b c d a]
• SubWord
  • 각 바이트에 S-box 치환을 적용한다.
• Rcon[ i / 4 ]
  • 라운드 상수와 XOR 연산을 한다.

   (2) 그 외

• $w_i = w_{i-4} \oplus w_{i-1}$

 

3. 라운드 키 만들기

• 이렇게 만든 워드들을 4개시 묶으면 한 라운드 키가 된다.
  • rk0 = [w0 w1 w2 w3] (초기 AddRoundKey에 사용)
  • rk1 = [w4 w5 w6 w7]
  • …
  • rk10 = [w40 w41 w42 w43]

 

[ 라운드 상수 ]

• 각 라운드 상수 Rcon은 4바이트 값이다.
• 가장 오른쪽 3바이트는 모두 0이다.

 

 

키 확장 루틴은 가장 왼쪽에 있는 바이트를 계산하기 위해 위의 테이블을 이용하거나, 체 GF($2^8$)을 이용하여 상수들의 최상위 바이트들을 계산을 통해 얻을 수 있다.

 

AES의 라운드 키는 이전 라운드에서 사용한 라운드 키를 사용하여 생성된다.

그러나 키 확장 과정의 SubWord는 라운드 키들 사이에 비선형성을 제공하고 라운드 상수 덧셈 연산을 통과하면서 이전 단계의 라운드 키와 그 다음으로 생성되는 라운드 키는 다르게 된다.

즉, 아주 약간의 비트만 다르더라도 매우 다른 라운드 키들이 생성된다.

 

 

3-2. AES-192와 AES-256의 Key Expansion

AES-128의 키 확장 과정과 유사하지만 다음과 같은 차이점이 있다.

 

1. AES-192

• 6개의 워드 단위로 계산한다.
• 192비트 암호키로 처음의 6개의 워드 $w_0, w_1, w_2, w_3, w_4, w_5$를 생성한다.
• i가 6의 배수가 아닌 경우,  $w_i = w_{i-6} \oplus w_{i-1}$
• i가 6의 배수인 경우, $w_i = t \oplus w_{i-1}$

2. AES-256

• 8개의 워드 단위로 계산한다.
• 256비트 암호키로 처음의 6개의 워드 $w_0, w_1, w_2, w_3, w_4, w_5, w_6, w_ 7$를 생성한다.
• i가 8의 배수가 아닌 경우,  $w_i = w_{i-6} \oplus w_{i-1}$
• i가 4의 배수이면서 8의 배수가 아닌 경우, $w_i = \text{SubWord}(w_{i-1}) \oplus w_{i-8}$

 

3.3 Key Expansion 과정의 의의

1. 공격자가 암호키의 일부나 라운드키의 일부를 얻는다 해도 모든 라운드 키를 알기 위해서는 남은 암호키 값을 복구해야한다.

• 이는 키 확장 과정에서 사용된 SubWord 변환에 의해 발생하는 비선형성에 기반한다.

2. 두 개의 암호키가 오진 한 비트만 다른 값을 갖더라도 라운드 키 확장 과정을 통해 적은 수의 라운드 만에 서로 다른 라운드 키를 생성한다.

 

3. 암호 키의 각 비트는 여러 라운드에 영향을 준다.

• 암호하다 한 비트를 바꿀 경우 여러 라운드에서 여러 비트가 바뀌게 된다.

4. 키 확장 과정에서 사용하는 상수 RCons는 다른 변환 과정에서 발생할 수 있는 라운드 키들의 대칭성을 제거한다.

 

5. 취약한 키가 존재하지 않는다.

 

6. 쉽게 구현할 수 있다.

 

 

 

4. 암호

AES가 암호화 복호화를 위해서 네 가지 유형의 Transformation을 어떻게 사용하는지 살펴보자.

 

AES는 non-Feistel 암호이다.

즉, 각 변환들은 자신의 역변환을 가진다.

 

4-1. 기본 설계

 

복호화 과정에서

1. SubBytes와 ShiftRows의 순서가 바뀐다.

2. MixColumns와 AddRoundKey의 순서가 바뀐다.

 

이와 같은 순서 사이는 암호화에서 각 변환을 복호화에서 자신의 역변환과 동일하게 대응하기 위해서 필요하다.

결론적으로, 복호 알고리즘은 암호 알고리즘의 역함수이다.

 

 

SubBytes / ShiftRows

SubBytes는 State 값에서 바이트의 순서를 변경하지 않고 각각의 바이트 값을 S-box를 이용해 변경한다.

반면, ShiftRows는 바이트 값을 변경하지 않고 순서만 변경한다.

 

> 이는 복호화 과정에서 알고리즘의 가역성을 유지하면서 이 두 변환의 순서를 바꿀 수 있음을 의미한다.

 

쉽게 말해서, 값을 바꾸고 위치를 바꾸는 것이나 위치를 바꾸고 값을 바꾸는 것 둘 다 수학적으로 동일한 효과를 준다는 것이다.

 

 

MixColumns / AddRoundkey

MixColumns와 AddRoundkey는 SubBytes, ShiftRows와 다른 특성을 가진다.

 

두 조합이 역함수 관계임을 증명해보자.

암호에서 이 조합의 입력 상태 값을 S로 표기하고, 출력 상태 값을 T로 표기하자.

그러면, 역암호에서 입력 상태 값이 T가 되고, 출력 상태 값이 T임을 증명해야한다.

 

암호 : $ T = CS \oplus K $

역 암호 : $ C^{-1}T \oplus C^{-1}K = C^{-1}(CS \oplus K) \oplus C^{-1}K = C^{-1}CS \oplus C^{-1}K \oplus C^{-1}K = S$

 

여기서, MixColumn 변환은 입력 상태 값 C에 상수 행렬 C를 곱하는 것이다.