[AES 아키텍처 핵심 정리]

1. 데이터 단위: 128비트 블록 = 16개의 바이트 (4x4 행렬)
2. 초기 단계: Key Whitening (시작하자마자 키랑 XOR)
3. 라운드 구성 (4단계):
   (1) Byte Sub: S-Box 이용한 치환 (Confusion, 비선형성)
   (2) Shift Row: 행 단위로 위치 이동 (Diffusion, 단순 섞기)
   (3) Mix Column: 열 단위로 수학적 섞기 (Diffusion, GF 행렬곱)
   (4) AddRoundKey: 키와 XOR 연산

1. AES Motivatoin & Specs

• 블록 크기: 128비트 (고정).
• 키 길이: 128, 192, 256비트 중 선택 가능.
• Motivation (쇄도 효과):
  - 그림에서 입력값 $X_1$과 $X_2$가 단 1비트(one bit flip)만 달라도, AES 박스를 통과한 출력값 $Y_1$과 $Y_2$는 완전히 다른 값(Nothing similar)이 됩니다.
  • 이것이 바로 강력한 암호의 조건인 쇄도 효과(Avalanche Effect)입니다.

the last round does not have the mixcolumn layer
At the beginning of AES, a subkey is added.
<-> Key whitening

2. 128 bit, Key whitening

128비트 $\rightarrow$ 16바이트:

• AES는 128비트 데이터를 한 줄로 처리하는 것이 아니라, 1바이트(8비트)짜리 16개로 쪼개서 처리합니다. 128bits data path is split into 16 bytes (16 x 8 bits = 128bits)
• 필기에 적힌 "16 x 8 bits = 128 bits"가 바로 이 뜻입니다.
• 이 16개의 바이트($A_0 \sim A_{15}$)는 $4 \times 4$ 행렬(State Matrix) 형태로 다루어집니다.

Key Whitening:

• the last round does not have the mixcolumn layer
  At the beginning of AES, a subkey is added. <-> Key whitening

• 의미: 본격적인 1라운드가 시작하기 직전(Round 0)에, 원본 데이터와 첫 번째 키를 한 번 XOR 해주는 단계입니다.

• 목적: 암호화 초기 단계부터 데이터를 감추어(Whitening), 공격자가 입력값과 첫 라운드 사이의 관계를 파악하지 못하게 보호합니다.

3. AES Round Function

이 4단계가 모여서 하나의 라운드(Round)를 구성합니다.

① Byte Substitution
② Shift Row
③ Mix Column
④ Key Addition

① Byte Substitution, 바이트 치환

위치: 맨 위 Byte sub. 박스와 옆의 $S$라고 적힌 동그라미들.
역할 (Confusion): S-Box를 사용하여 각 바이트를 다른 값으로 1:1 교체합니다.
특징:이전 시간에 배운 $GF(2^8)$에서의 역원(Inverse)을 구하는 계산이 여기서 쓰입니다.
비선형성(Non-linearity)을 제공하여 암호를 수학적으로 풀기 어렵게 만듭니다.

S-Box table
S(Ai) = Bi

• 8bits 8bits
• all 16 s-box are identical

S-Box 사용법

상황: 입력값 $A_i$가 16진수로 $C2$ (1100 0010)라고 가정합시다.\행동: 미리 만들어진 S-Box Table을 참조합니다.앞자리 $C$를 행(Row), 뒷자리 $2$를 열(Column)로 찾습니다.
결과: 표에서 찾은 값 $B_i$는 $25$ (0010 0101)가 됩니다.

S-Box의 생성 원리

S-Box는 다음 두 단계를 거쳐서 만들어집니다.

• Inverse (역원 구하기): $GF(2^8)$에서 곱셈 역원을 구함.
• Affine Mapping (아핀 변환): 행렬 연산을 통해 비트들을 섞음.
  

[1단계] 역원 구하기 (Compute Inverse)

사진에 적힌 수학 식을 풀어드리면 다음과 같습니다.

• 입력 ($A_i$): $C2$ (2진수: 1100 0010)
• 다항식 변환:비트 1100 0010은 각각 $x^7, x^6, x^1$ 자리를 의미합니다.
• $A_i(x) = x^7 + x^6 + x$

목표: $A_i(x)$와 곱했을 때 나머지가 1이 되는 식($?$)을 찾아야 합니다.
$A_i(x) \cdot (?) \equiv 1 \pmod{P(x)}$

사용하는 모듈로 식 ($P(x)$):
AES에서 정해둔 기약 다항식 (AES Irreducible Polynomial)
$P(x) = x^8 + x^4 + x^3 + x + 1$

필기에 빨간색으로 적힌 EEA는 확장 유클리드 호제법 (Extended Euclidean Algorithm)을 뜻합니다. 이 알고리즘을 써서 역원을 구합니다.

1단계 계산의 결과값
계산해 보니 역원은 $x^5 + x^3 + x^2 + x + 1$이 나왔습니다.

이진수 변환:
$x^5, x^3, x^2, x^1, 1$ 자리에 1을 채우면?
0010 1111 (16진수로는 $2F$)

중요: 이것이 최종 S-Box 값이 아닙니다! 이건 중간 단계 값(Inverse)입니다.
이 값($2F$)을 가지고 2단계 아핀 변환(Affine Mapping)을 거쳐야 비로소 첫 번째 사진에 나왔던 $25$가 됩니다.

[2단계] Affine Mapping

1. 입력 ($b'_0 \sim b'_7$):
   오른쪽의 $b'$ 벡터는 1단계에서 구한 역원 값의 비트들입니다. (예: $2F$의 비트열)

2. 행렬 곱셈 ($8 \times 8$ Matrix):

• 가운데 있는 $0$과 $1$로 된 큰 행렬은 AES 표준에서 정해진 고정 행렬입니다.
• 이 행렬과 입력 비트들을 곱해서 비트들을 서로 섞습니다.

3. 상수 더하기 ($+ [1, 1, 0, 0, \dots]^T$):

• 마지막에 특정 상수 벡터(비트열)를 더합니다(XOR). 이 값은 16진수로 $63$(01100011)에 해당합니다.

4. 결과 ($b_0 \sim b_7$):
   최종적으로 나온 이 비트열이 바로 우리가 S-Box 표에서 보는 최종 값(예: $25$)이 됩니다.

Q: 왜 이렇게 복잡한 짓을 하나요?
A: 1단계(역원)만 쓰면 수학적으로 너무 깔끔해서 공격자가 공식을 유추해낼 위험이 있습니다. 이 아핀 변환을 추가함으로써 수학적 규칙을 깨뜨려(Algebraic Attack 방지), 암호를 훨씬 더 안전하게 만듭니다.

② Shift Row (행 이동)

그림 위치: Shift Row 박스와 그 옆에 선들이 엇갈리는 부분.
역할 (Diffusion): 행렬의 각 행(Row)을 옆으로 미는 단계입니다.

• 1번째 행: 이동 없음.
• 2번째 행: 왼쪽으로 1칸 이동.
• 3번째 행: 왼쪽으로 2칸 이동.
• 4번째 행: 왼쪽으로 3칸 이동.

효과: 바이트들의 위치를 섞어줍니다.

구조: 128비트 데이터는 $4 \times 4$ 행렬(State Matrix) 모양입니다.
동작 원리: 각 행(Row)을 왼쪽으로 회전(Cyclic Shift) 시킵니다.

Row 0 (맨 윗줄):
규칙: No shift (이동 없음).
결과: $B_0, B_4, 8, 12 \rightarrow$ 그대로 유지.

Row 1 (두 번째 줄):
규칙: 1 pos. left (왼쪽으로 1칸 이동).
결과: 맨 앞의 $B_1$이 맨 뒤로 가고, 나머지가 앞으로 당겨집니다.
($B_1, 5, 9, 13 \rightarrow 5, 9, 13, \mathbf{B_1}$)

③ Mix Column (열 섞기)

그림 위치: Mix col. 박스들. 4개의 바이트($B_0 \sim B_3$)가 한 묶음으로 들어가는 것 보이시죠?
역할 (Diffusion): 세로 방향(Column)으로 데이터를 섞습니다.
수학적 원리: 이전 시간에 배운 행렬 곱셈과 다항식 연산이 여기서 쓰입니다.
효과: 한 바이트의 변화가 전체 열(Column)에 영향을 미치게 하여 확산 효과를 극대화합니다.

1. 기본 개념: 열(Column) 단위 처리

• 입력: Shift Row 단계를 거친 데이터들($B_0, B_5, B_{10}, B_{15}$)이 들어옵니다.
• 참고: Shift Row 때문에 원래 같은 열에 없던 애들이 한 열로 모였습니다. 그래서 인덱스 번호가 뒤죽박죽인 것처럼 보이지만, 현재 상태 행렬에서는 하나의 세로줄(Column)입니다.
• 동작: 이 4개의 바이트를 통째로 가져와서, 특정한 행렬과 곱셈을 수행하여 새로운 값 $C_0, C_1, C_2, C_3$를 만들어냅니다.

2. 행렬 곱셈 (Matrix Multiplication)

• 고정 행렬: 가운데 있는 $4 \times 4$ 행렬은 AES 표준에 의해 정해진 상수 행렬입니다. 숫자가 $01, 02, 03$으로만 구성되어 있죠? 이 값들이 데이터를 섞는 '믹서기 날' 역할을 합니다.
• 순환 구조: 행렬을 잘 보면 첫 줄($02, 03, 01, 01$)이 오른쪽으로 한 칸씩 이동하며 다음 줄을 만드는 순환(Circulant) 구조를 가지고 있습니다.

3. 계산 방법

필기 아래쪽에 적힌 Remarks 부분을 자세히 보겠습니다. 행렬 곱셈 규칙에 따라 첫 번째 결과값 $C_0$는 다음과 같이 계산됩니다.

$C_0 = (\mathbf{02} \cdot B_0) + (\mathbf{03} \cdot B_5) + (\mathbf{01} \cdot B_{10}) + (\mathbf{01} \cdot B_{15})$

여기서 더하기($+$)와 곱하기($\cdot$)는 우리가 아는 사칙연산이 아닙니다! 유한체 $GF(2^8)$ 연산입니다.

• 덧셈 ($+$): XOR 연산입니다. (가장 쉽습니다.)
• 곱셈 ($\cdot$): 이게 핵심입니다.
  필기 맨 아래쪽을 보세요.

$01$: 다항식 $1$입니다. (그냥 자기 자신, 변화 없음)

$02$: 다항식 $x$입니다.
어떤 값에 $x$를 곱한다는 것은 비트를 왼쪽으로 1칸 미는 것(Shift Left)과 같습니다.
단, 8비트 범위를 넘어가면 기약 다항식으로 XOR 해줍니다 (Reduction).

$03$: 다항식 $x + 1$입니다.
$03 \cdot B = (02 \oplus 01) \cdot B = (\mathbf{02} \cdot B) \oplus (\mathbf{01} \cdot B)$
즉, ($x$를 곱한 값) XOR (자기 자신)으로 계산합니다.

④ Key Addition (AddRoundKey, 키 더하기)

그림 위치: 맨 아래 Key Add. 박스와 $\oplus$ 기호(XOR).
역할: 라운드 키(Subkey)와 데이터를 XOR 연산합니다.
특징:필기 그림을 보면 Ki,1, Ki,16처럼 키도 바이트 단위로 쪼개져서 각 데이터 바이트와 1:1로 XOR 됩니다.암호화 과정 중 유일하게 비밀 키(Key)가 직접 개입하는 단계입니다.

---

Key schedule

1. 전반적인 키 확장 구조 (Image 1 좌측)

AES-128은 128비트(16바이트)의 키를 사용하며, 내부 연산을 위해 이를 32비트 단위의 '워드(Word)'로 쪼갭니다.

• $1 \text{ word} = 32 \text{ bits}$ (4 bytes)
• 초기 128비트 마스터 키 $K$는 4개의 워드 $W[0], W[1], W[2], W[3]$으로 나뉩니다. 이것이 필기 상단의 $R_0$ (Round 0) 키가 됩니다.
• AES-128은 총 10번의 라운드를 거치므로, $R_{10}$까지 총 44개의 워드($W[0] \sim W[43]$)가 필요합니다.필기 하단에 적힌 두 개의 핵심 점화식은 새로운 라운드의 워드를 생성하는 규칙입니다.

① 라운드의 첫 번째 워드를 만들 때 (4의 배수 인덱스, $W[4i]$)

$W[4i] = W[4(i-1)] \oplus g(W[4i-1])$
새로운 라운드 $i$의 첫 워드(예: $W[4]$)를 만들 때는, 이전 라운드의 첫 워드($W[0]$)와 바로 직전 워드($W[3]$)를 $g$ 함수에 통과시킨 값을 XOR($\oplus$) 합니다. 필기에서 형광펜으로 칠해진 흐름이 바로 이 수식을 시각화한 것입니다.

② 나머지 세 개의 워드를 만들 때 ($W[4i+j]$, $j=1, 2, 3$)

$W[4i+j] = W[4i+j-1] \oplus W[4(i-1)+j]$
예를 들어 $W[5]$를 만들 때는 복잡한 함수 없이 직전 워드인 $W[4]$와 이전 라운드의 같은 위치 워드인 $W[1]$을 단순히 XOR만 합니다. 디지털 하드웨어로 설계할 때 이 부분은 추가적인 로직 게이트 없이 단순한 XOR 게이트만으로 빠르게 연산(0 delay에 가깝게) 처리할 수 있는 장점이 있습니다.

2. $g$ 함수의 동작 원리 (Image 1 우측 박스)

라운드 키에 비선형성(Non-linearity)을 부여하는 핵심 부분입니다. 32비트 워드 하나(4바이트: $V_0, V_1, V_2, V_3$)가 입력으로 들어오면 3단계를 거칩니다.

1. RotWord (순환 시프트):
   입력된 4바이트의 순서를 왼쪽으로 한 칸씩 밉니다.$[V_0, V_1, V_2, V_3] \rightarrow [V_1, V_2, V_3, V_0]$(하드웨어 관점에서는 단순히 와이어 라우팅 순서만 바꿔주면 되므로 자원 소모가 없습니다.)

2. SubBytes (S-box 치환):
   필기의 동그라미 'S'로 표현된 부분입니다. 위치가 바뀐 4개의 바이트를 각각 AES S-box 테이블에 넣어 새로운 값으로 치환합니다.

3. Round Constant (RC)와 XOR:
   마지막으로 첫 번째 바이트에 라운드 상수 $RC[i]$를 XOR 해줍니다. 나머지 3바이트는 그대로 내려옵니다.

3. Round Constant ($RC[i]$)와 $GF(2^8)$ 연산 (Image 2)

두 번째 필기는 $g$ 함수에서 더해지는 $RC[i]$ 값이 어떻게 도출되는지 보여줍니다. 이 값은 갈루아 필드 $GF(2^8)$ 위에서 $x^{i-1}$을 계산한 결과입니다.

• $RC[1] = x^0 = 00000001_2$
• $RC[2] = x^1 = 00000010_2$

필기 하단에서 가장 중요하게 강조하신 부분이 $RC[10] = x^9$의 계산입니다.
$x^9$을 단순히 비트로 표현하면 $100000000_2$이 되어 9비트가 됩니다. $GF(2^8)$ 환경에서는 8비트를 넘을 수 없으므로, AES의 기약 다항식(Irreducible Polynomial)인 $P(x) = x^8 + x^4 + x^3 + x + 1$ 로 모듈러(mod) 연산을 해주어야 합니다.

필기에 적힌 $(36)_{16}$이 도출되는 과정은 다음과 같습니다:
$x^8 \equiv x^4 + x^3 + x + 1 \pmod{P(x)}$
여기에 양변에 $x$를 곱하면,
$x^9 \equiv x^5 + x^4 + x^2 + x$
이를 8비트 이진수로 표현하면 $(x^7, x^6, x^5, x^4, x^3, x^2, x^1, x^0)$ 자리에서 $x^5, x^4, x^2, x^1$이 1이 되므로:
$0011 \ 0110_2$

이를 16진수로 변환하면 정확히 $0\text{x}36$이 됩니다. (필기의 $X$ 표시된 부분은 단순 비트 시프트만 하면 안 되고 모듈러 연산이 필수적이라는 것을 아주 잘 짚어낸 것입니다.)