084. AES SPN 구조

⚠️ 이 문서는 현존 최고의 암호인 AES가 데이터를 섞을 때 사용하는 핵심 아키텍처인 'SPN(대치-치환 네트워크) 구조'와, 그 내부를 구성하는 4가지 치명적인 마법의 단계(SubBytes, ShiftRows, MixColumns, AddRoundKey)를 기술적으로 해부합니다.

핵심 인사이트 (3줄 요약)

  1. 본질: SPN(Substitution-Permutation Network) 구조는 데이터를 반으로 쪼개서 섞던 과거의 파이스텔(Feistel) 구조와 달리, 128비트 평문 전체를 한 번에 대치(S-Box)하고 치환(자리바꿈)하여 수학적으로 병렬 처리하는 압도적 속도의 블록 암호 아키텍처다.
  2. 가치: 클로드 섀넌이 주창한 암호의 두 가지 절대 조건인 **'혼돈(Confusion: 모양 바꾸기)'**과 **'확산(Diffusion: 널리 퍼뜨리기)'**을 4가지 함수를 통해 완벽하게 수학적(갈루아 체)으로 구현해 냈다.
  3. 융합: 이 4개의 단계는 1바이트의 변화가 1라운드 만에 전체 데이터에 눈사태처럼 퍼지는 '눈사태 효과(Avalanche Effect)'를 만들어 내며, 하드웨어 칩 내부의 논리 회로(XOR, Shift)로 굽기 쉬워 압도적인 암호화 속도를 달성한다.

Ⅰ. 개요 및 파이스텔(Feistel) 구조와의 결별

과거 DES 암호가 썼던 파이스텔 구조는 데이터를 반(Left/Right)으로 자른 뒤, 오른쪽 데이터를 함수에 돌려서 왼쪽과 섞고, 위치를 바꾸는 짓을 반복했다. 이는 "암호화 함수와 복호화 함수가 똑같이 생겼다"는 장점이 있었지만, 한 번에 데이터의 절반만 섞이기 때문에 암호화 속도가 느리고 효율이 떨어졌다.

AES를 만든 천재들은 이를 버리고 SPN 구조를 채택했다. 128비트(16바이트)의 평문 전체를 4x4 행렬(State)로 네모나게 눕혀놓고, 한 번에 전체 바이트를 동시에 다른 글자로 바꿔치기(Substitution)하고, 위치를 섞어버리는(Permutation) 방식이다. 한 방에 전체를 버무리니 속도가 2배 빠르고 병렬 처리에 기가 막히게 적합하다.

📢 섹션 요약 비유: 파이스텔 구조가 밀가루 반죽을 반으로 나눠서 한쪽만 양념을 묻히고 꼬기를 16번 반복하는 방식이라면, SPN 구조는 도마 위에 반죽 전체를 넓게 펴놓고 양념 치기, 접기, 밀대로 밀기를 한 방에 동시다발적으로 하는 초고속 제빵 기술입니다.

Ⅱ. AES의 4단계 믹서기: 마법의 State 행렬

AES는 16바이트(128비트)의 데이터를 4x4 크기의 2차원 배열로 만든다. 이를 State(상태) 행렬이라고 부른다. 매 라운드마다 이 행렬을 다음 4가지 순서대로 무자비하게 섞는다.

1. SubBytes (대치 - 혼돈 창출)

  • 원리: 16개의 바이트를 하나하나 꺼내어, 미리 정해진 마법의 사전인 **'S-Box (Substitution Box)'**를 보고 전혀 다른 글자로 1:1 교환한다.
  • 역할: 고전 암호의 '단일 치환 암호'와 같다. 평문의 글자 모양 자체를 비선형적으로 비틀어버려, 암호문과 평문 사이의 관계를 미궁 속에 빠뜨리는 **혼돈(Confusion)**을 담당한다.

2. ShiftRows (행 이동 - 확산 창출 1)

  • 원리: 4x4 행렬의 가로줄(행)을 돌린다.
    • 1번째 줄: 그대로 둠 (0칸 이동)
    • 2번째 줄: 왼쪽으로 1칸 밈
    • 3번째 줄: 왼쪽으로 2칸 밈
    • 4번째 줄: 왼쪽으로 3칸 밈
  • 역할: 각 세로줄에 나란히 있던 바이트들이 뿔뿔이 다른 세로줄로 흩어진다. 고전 암호의 '전치 암호'와 같으며, 데이터의 자리를 섞는 **확산(Diffusion)**을 담당한다.

3. MixColumns (열 섞기 - 확산 창출 2)

  • 원리: 4x4 행렬의 세로줄(열) 4바이트를 통째로 집어넣어, 갈루아 체($GF(2^8)$)라는 복잡한 다항식 행렬 곱셈을 수행하여 완전히 새로운 4바이트의 세로줄을 뽑아낸다.
  • 역할: AES의 꽃이다. 단 1비트만 달라도 세로줄 전체의 값이 폭풍처럼 변하게 만드는 **눈사태 효과(Avalanche Effect)**의 핵심 코어다. ShiftRows가 가로로 흩뿌렸다면, MixColumns는 세로로 으깨버린다. (※ 마지막 라운드에서는 연산 속도와 복호화 대칭을 위해 이 단계를 생략한다.)

4. AddRoundKey (라운드 키 더하기 - 락온)

  • 원리: 위에서 엉망진창으로 섞인 128비트 행렬 데이터에, 사용자의 비밀키에서 뽑아낸 128비트 '라운드 키(Round Key)'를 나란히 놓고 XOR ($\oplus$) 연산으로 더해버린다.
  • 역할: 아무리 SubBytes와 ShiftRows로 데이터를 섞어도, 해커가 그 알고리즘(순서)을 역으로 돌리면 평문이 나와버린다(케르크호프스 원리). 이를 막기 위해 나만 아는 '비밀키'를 발라버려 자물쇠를 딸깍 채우는 최종 잠금 단계다.
┌─────────────────────────────────────────────────────────────────┐
│           AES SPN 구조의 1라운드 (4단계) 연산 시각화 도해도     │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  [ 입력: 4x4 State 행렬 ]                                       │
│    A1 A2 A3 A4                                                  │
│    B1 B2 B3 B4                                                  │
│    C1 C2 C3 C4                                                  │
│    D1 D2 D3 D4                                                  │
│                                                                 │
│  1. SubBytes (사전 보고 글자 바꾸기)                            │
│    -> S-Box를 거쳐 A1은 X9로, B2는 Y1로 아예 다른 색깔로 변신!  │
│                                                                 │
│  2. ShiftRows (가로로 밀어서 흩뿌리기)                          │
│    A1 A2 A3 A4  (0칸)       A1 A2 A3 A4                         │
│    B1 B2 B3 B4  (1칸)  =>   B2 B3 B4 B1                         │
│    C1 C2 C3 C4  (2칸)  =>   C3 C4 C1 C2                         │
│    D1 D2 D3 D4  (3칸)       D4 D1 D2 D3                         │
│                                                                 │
│  3. MixColumns (세로로 갈아서 으깨기)                           │
│    -> 세로줄 (A1, B2, C3, D4)를 특수 수학 공식으로 갈아 마심!   │
│    -> 결과: 전혀 예측 불가능한 새로운 4개의 바이트 탄생         │
│                                                                 │
│  4. AddRoundKey (비밀키 뿌리기)                                 │
│    -> 으깨진 결과물 ⊕ [이번 라운드의 128비트 비밀키]            │
│                                                                 │
│  ★ 이 짓을 AES-128은 10바퀴, AES-256은 14바퀴 반복함!           │
└─────────────────────────────────────────────────────────────────┘

[다이어그램 해설] AES가 완벽한 이유는 ShiftRows와 MixColumns의 완벽한 콤비네이션 때문이다. 첫 바퀴에서 MixColumns가 세로줄 4바이트를 버무린다. 두 번째 바퀴에서 ShiftRows가 그 버무려진 바이트들을 다른 세로줄 4곳으로 흩뿌려준다. 세 번째 바퀴에서 MixColumns가 또 버무린다. 단 2바퀴만 돌아도 최초 평문의 1바이트가 16바이트 전체에 완벽하게 바이러스처럼 퍼져버린다 (완전한 확산).

  • 📢 섹션 요약 비유: 찰흙으로 도자기를 빚을 때, 파란색과 빨간색 물감을 톡 떨구고(평문), 손가락으로 꾹 눌러 모양을 바꾸고(SubBytes), 가로로 길게 밀고(ShiftRows), 세로로 비틀어 꼬아버린 뒤(MixColumns), 나만의 비밀 도장(AddRoundKey)을 찍는 과정을 10번 반복하면, 절대 원래의 빨강/파랑 점을 찾아낼 수 없는 완벽한 보라색 도자기가 완성됩니다.

Ⅲ. SPN 구조의 장단점 및 실무적 의미

  1. 병렬 처리 (속도의 극대화)
    • 파이스텔(DES)은 1라운드가 끝나야 2라운드의 왼쪽, 오른쪽을 계산할 수 있는 직렬 구조였다.
    • SPN(AES)은 SubBytes를 할 때 16바이트를 각각 독립적으로 S-Box 테이블에서 찾으면 되므로, GPU나 멀티코어 CPU에서 16개를 한 방에(병렬로) 치환해 버릴 수 있다. 이 때문에 AES는 기가비트급 암호화 속도를 가볍게 뽑아낸다.
  2. 복호화 회로의 추가 필요성 (비용)
    • 파이스텔은 암호화 함수를 그대로 복호화에 쓸 수 있어 칩을 작게 만들 수 있다.
    • SPN 구조는 암호화를 풀려면 모든 함수를 거꾸로 돌려야 한다 (Inverse SubBytes, Inverse ShiftRows 등). 따라서 암호화 회로와 복호화 회로를 하드웨어 칩에 따로 그려야 해서 칩의 면적이 약간 커진다. (하지만 현대 반도체 기술에서는 이 정도 면적은 아무런 문제가 되지 않는다.)

Ⅳ. 결론

"AES의 4단계는 완벽하게 짜인 수학적 교향곡이다." SubBytes가 해커의 눈을 가리고(혼돈), ShiftRows와 MixColumns가 평문의 흔적을 갈기갈기 찢어 흩날리며(확산), AddRoundKey가 나만의 비밀 자물쇠를 채운다. 이 4개의 톱니바퀴가 10번 맞물려 돌아가는 SPN 구조는 현존하는 암호학의 가장 아름답고 견고한 아키텍처이며, 전 세계의 수억 대의 스마트폰이 매일 1초에도 수백 번씩 이 수학 공식을 묵묵히 수행하고 있다.

📌 관련 개념 맵

  • 전체 알고리즘: AES (Advanced Encryption Standard)
  • 대비되는 아키텍처: Feistel 구조 (DES, SEED에서 사용)
  • 보안 핵심 원리: 눈사태 효과 (Avalanche Effect), 혼돈 (Confusion), 확산 (Diffusion)
  • 암호학 수학: 갈루아 체 (Galois Field $GF(2^8)$)

👶 어린이를 위한 3줄 비유 설명

  1. AES라는 마법의 믹서기 안에는 4개의 특별한 칼날이 층층이 들어있어요.
  2. 1번 칼날은 글자 모양을 완전히 다른 글자로 바꿔치기하고, 2번과 3번 칼날은 가로세로로 마구 섞어버리고, 마지막 4번 칼날은 주인의 '비밀 열쇠'를 발라서 자물쇠를 채워요.
  3. 이 4개의 칼날을 통과하는 짓을 무려 10번이나 반복하니까, 원래 어떤 글자가 들어왔는지 슈퍼컴퓨터 할아버지가 와도 절대 알아맞힐 수가 없답니다!