본문으로 건너뛰기

6장. AES (Advanced Encryption Standard)

AES는 2001년 NIST가 DES를 대체하기 위해 채택한 대칭 블록 암호이다. 벨기에 암호학자들이 설계한 Rijndael 알고리즘이 선정되었다. AES는 GF(28)\text{GF}(2^8) 유한체 산술에 기반하며, Feistel 구조가 아닌 SPN(Substitution–Permutation Network) 구조를 사용한다.

학습 목표

  • AES의 전체 구조를 개관한다.
  • 4가지 변환 함수(SubBytes, ShiftRows, MixColumns, AddRoundKey)를 이해한다.
  • AES 키 확장 알고리즘을 설명한다.
  • GF(28)\text{GF}(2^8) 계수를 가진 다항식 산술의 사용을 이해한다.

6.1 유한체 산술 요약​

AES의 모든 연산은 8비트 바이트 단위로 수행된다.

연산정의
덧셈비트별 XOR
곱셈GF(28)\text{GF}(2^8)에서의 곱셈, 기약 다항식 m(x)=x8+x4+x3+x+1m(x) = x^8 + x^4 + x^3 + x + 1

{02}\{02\}와의 곱셈 (xtime):

  • b7=0b_7 = 0이면: 1비트 좌측 시프트
  • b7=1b_7 = 1이면: 1비트 좌측 시프트 후 {1B}\{1B\}와 XOR

6.2 AES 구조​

AES 파라미터​

파라미터AES-128AES-192AES-256
키 길이 (바이트/비트)16 / 12824 / 19232 / 256
평문 블록 크기16 / 12816 / 12816 / 128
라운드 수101214
확장 키 크기 (워드)445260

State 배열​

128비트 입력을 4×44 \times 4 바이트 행렬로 배치한다. 바이트 순서는 **열 우선(column-major)**이다.

암호화 과정​

  1. 초기 변환: AddRoundKey (라운드 0 키)
  2. 라운드 1 ~ N−1: SubBytes → ShiftRows → MixColumns → AddRoundKey
  3. 최종 라운드 N: SubBytes → ShiftRows → AddRoundKey (MixColumns 없음)

구조적 특징​

  • Feistel 구조가 아님: 전체 데이터 블록을 매 라운드마다 하나의 행렬로 처리
  • AddRoundKey만 키를 사용하므로 암호화의 시작과 끝에 배치
  • 최종 라운드에 MixColumns가 없는 이유는 암호의 가역성 보장을 위함
  • 복호화: 역변환을 역순으로 적용하되, 서브키도 역순 사용

6.3 AES 변환 함수​

SubBytes​

16×1616 \times 16 S-box 테이블을 이용한 바이트 단위 치환이다.

S-box 구성 과정:

  1. 바이트 값 {yx}\{yx\}를 GF(28)\text{GF}(2^8)에서의 곱셈 역원으로 매핑 ({00}→{00}\{00\} \to \{00\})
  2. 다음 아핀 변환(affine transformation) 적용:

bi′=bi⊕b(i+4) mod 8⊕b(i+5) mod 8⊕b(i+6) mod 8⊕b(i+7) mod 8⊕cib_i' = b_i \oplus b_{(i+4)\bmod 8} \oplus b_{(i+5)\bmod 8} \oplus b_{(i+6)\bmod 8} \oplus b_{(i+7)\bmod 8} \oplus c_i

여기서 c={63}=01100011c = \{63\} = 01100011

예시: {95}→역원{8A}→아핀{2A}\{95\} \xrightarrow{\text{역원}} \{8A\} \xrightarrow{\text{아핀}} \{2A\}

설계 근거: 곱셈 역원에 의한 비선형성으로 알려진 암호 분석에 저항. 고정점(S(a)=aS(a) = a)과 반고정점(S(a)=aˉS(a) = \bar{a})이 없음.

역변환 (InvSubBytes): 역 S-box 테이블 사용

ShiftRows​

State 행렬의 각 행을 좌측으로 순환 시프트한다.

행시프트량
0행시프트 없음
1행1바이트 좌측
2행2바이트 좌측
3행3바이트 좌측

설계 근거: 한 열의 4바이트가 4개의 다른 열로 분산되어 확산(diffusion) 효과를 제공한다.

역변환 (InvShiftRows): 반대 방향(우측)으로 순환 시프트

MixColumns​

각 열을 GF(28)\text{GF}(2^8) 위의 행렬 곱셈으로 변환한다.

(s0,j′s1,j′s2,j′s3,j′)=(02030101010203010101020303010102)(s0,js1,js2,js3,j)\begin{pmatrix} s'_{0,j} \\ s'_{1,j} \\ s'_{2,j} \\ s'_{3,j} \end{pmatrix} = \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix} \begin{pmatrix} s_{0,j} \\ s_{1,j} \\ s_{2,j} \\ s_{3,j} \end{pmatrix}

계수 {01}\{01\}, {02}\{02\}, {03}\{03\}만 사용하므로 시프트와 XOR만으로 구현 가능하다.

동치 다항식 표현: 각 열을 GF(28)\text{GF}(2^8) 계수의 다항식으로 보고 a(x)={03}x3+{01}x2+{01}x+{02}a(x) = \{03\}x^3 + \{01\}x^2 + \{01\}x + \{02\}를  mod (x4+1)\bmod (x^4 + 1)로 곱한다.

역변환 (InvMixColumns):

역행렬=(0E0B0D09090E0B0D0D090E0B0B0D090E)\text{역행렬} = \begin{pmatrix} 0E & 0B & 0D & 09 \\ 09 & 0E & 0B & 0D \\ 0D & 09 & 0E & 0B \\ 0B & 0D & 09 & 0E \end{pmatrix}

AddRoundKey​

128비트 State와 128비트 라운드 키를 비트별 XOR한다.

역변환: XOR의 자기 역원 성질에 의해 동일한 연산

6.4 AES 키 확장​

키 확장 알고리즘 (AES-128)​

16바이트 키를 44워드(176바이트)로 확장한다.

알고리즘:

w[0..3] ← 원래 키의 4워드
for i = 4 to 43:
    temp = w[i-1]
    if i mod 4 == 0:
        temp = SubWord(RotWord(temp)) ⊕ Rcon[i/4]
    w[i] = w[i-4] ⊕ temp

보조 함수:

함수설명
RotWord워드를 1바이트 좌측 순환 시프트: [B0,B1,B2,B3]→[B1,B2,B3,B0][B_0, B_1, B_2, B_3] \to [B_1, B_2, B_3, B_0]
SubWord워드의 각 바이트에 S-box 적용
Rcon[j]라운드 상수 (RC[j],0,0,0)(RC[j], 0, 0, 0), RC[1]=1RC[1]=1, RC[j]=2⋅RC[j−1]RC[j] = 2 \cdot RC[j-1] in GF(28)\text{GF}(2^8)

라운드 상수 RC[j]:

j12345678910
RC[j]01020408102040801B36

설계 근거​

  • 라운드 상수로 라운드 간 대칭성 제거
  • 키 일부로부터 나머지 추론 어려움
  • 키 비트 차이가 라운드 키 전체로 확산

6.5 AES 예제​

예제 데이터​

항목16진수 값
평문0123456789abcdeffedcba9876543210
키0f1571c947d9e8590cb7add6af7f6798
암호문ff0b844a0853bf7c6934ab4364148fb9

눈사태 효과 (Avalanche Effect)​

평문 1비트 변경 시:

  • 1라운드 후: 20비트 차이
  • 2라운드 후: 58비트 차이
  • 최종 암호문: 58비트 차이 (128비트 중 약 절반)

키 1비트 변경 시:

  • 2라운드 후: 58비트 차이
  • 최종 암호문: 53비트 차이

DES보다 강한 눈사태 효과를 보인다 (DES는 3라운드 후 약 절반 도달).

6.6 AES 구현​

동치 역암호 (Equivalent Inverse Cipher)​

AES의 복호화는 암호화와 변환 순서가 다르다. 동일한 구조로 만들기 위해 두 가지 교환이 필요하다.

1. InvShiftRows ↔ InvSubBytes 교환

  • InvShiftRows는 바이트 순서만 변경, InvSubBytes는 바이트 값만 변경 → 교환 가능

2. AddRoundKey ↔ InvMixColumns 교환

  • 두 연산이 열 단위로 선형이므로 라운드 키에 InvMixColumns를 미리 적용하면 교환 가능:

InvMixColumns(Si⊕wj)=InvMixColumns(Si)⊕InvMixColumns(wj)\text{InvMixColumns}(S_i \oplus w_j) = \text{InvMixColumns}(S_i) \oplus \text{InvMixColumns}(w_j)

구현 최적화​

8비트 프로세서:

  • SubBytes: 256바이트 룩업 테이블
  • MixColumns: {02}\{02\} 곱셈 테이블(X2, 256바이트)로 시프트/조건부 XOR 제거

32비트 프로세서:

  • 4개의 256워드 룩업 테이블 T0,T1,T2,T3T_0, T_1, T_2, T_3 (총 4KB) 정의
  • 한 라운드의 한 열 처리: 4회 테이블 참조 + 4회 XOR

(s0,j′s1,j′s2,j′s3,j′)=T0[s0,j]⊕T1[s1,j−1]⊕T2[s2,j−2]⊕T3[s3,j−3]⊕(k0,jk1,jk2,jk3,j)\begin{pmatrix} s'_{0,j} \\ s'_{1,j} \\ s'_{2,j} \\ s'_{3,j} \end{pmatrix} = T_0[s_{0,j}] \oplus T_1[s_{1,j-1}] \oplus T_2[s_{2,j-2}] \oplus T_3[s_{3,j-3}] \oplus \begin{pmatrix} k_{0,j} \\ k_{1,j} \\ k_{2,j} \\ k_{3,j} \end{pmatrix}

주요 용어​

한국어영어설명
AESAdvanced Encryption StandardDES를 대체한 대칭 블록 암호 표준
RijndaelRijndaelAES로 선정된 원래 알고리즘 이름
S-boxSubstitution Box바이트 단위 비선형 치환 테이블
StateState ArrayAES 처리 중 4×44 \times 4 바이트 행렬
SubBytesSubBytesS-box 기반 바이트 치환
ShiftRowsShiftRows행 단위 순환 시프트
MixColumnsMixColumns열 단위 GF(282^8) 행렬 곱셈
AddRoundKeyAddRoundKey라운드 키와 XOR
키 확장Key Expansion암호키를 라운드 키 배열로 확장
라운드 상수Round Constant (Rcon)키 확장 시 대칭성 제거용 상수
눈사태 효과Avalanche Effect입력 1비트 변화 → 출력 다수 비트 변화
동치 역암호Equivalent Inverse Cipher암호화와 동일 구조의 복호화