현대 암호학: Advanced Encryption Standard

Finite Field Arithmetic
AES Structure
AES Transformation Functions
AES Key Expansion
An AES Example
AES Implementation
Polynomials with Coefficients in 𝐺𝐹(2^8)

---

AES

 

고급 암호화 표준 (Advanced Encryption Standard, AES)

 

2001년에 미국 국립표준기술연구소(National Institute of Standards and Technology, NIST)에 의해 발표되었다.
- 광범위한 애플리케이션에서 승인된 표준으로서 DES를 대체하기 위해 개발된 대칭키 블록 암호다.
- 소프트웨어 및 하드웨어 최적화 (SW and HW optimization)
Intel은 암호화 및 복호화 속도를 향상시키기 위해 x86 명령어 집합의 하드웨어 확장으로 고급 암호화 표준 새로운 명령어(Advanced Encryption Standard New Instructions, AES-NI)를 도입했다 (2008년).
AES-NI 명령어는 x86 프로세서가 AES-GCM(12장에서 설명)으로 알려진 인증된 암호화 모드에 대해 바이트당 0.64 사이클의 성능을 달성할 수 있도록 한다.
Intel은 고성능 프로세서를 위해 기존 AES-NI에 VAES*라고 불리는 벡터화된 명령어를 추가했다 (2018년).
이 명령어들은 AES 소프트웨어의 성능을 더욱 향상시켜 이론적으로 바이트당 0.16 사이클의 처리량을 목표로 한다.

---

유한체 연산 (Finite Field Arithmetic)

- 고급 암호화 표준(AES)에서 모든 연산은 8비트 바이트 단위로 수행된다.
덧셈, 곱셈, 나눗셈과 같은 산술 연산은 유한체 GF(2^8 ) 위에서 수행된다.
- 체(Field)는 집합 내에서 덧셈, 뺄셈, 곱셈, 나눗셈을 자유롭게 수행해도 그 결과를 집합 밖으로 벗어나지 않는 집합이다.
나눗셈은 다음 규칙에 따라 정의된다:
a/b=a×b^−1
- 유한체(유한한 개수의 원소를 갖는 체)의 예시로는 Z p 집합이 있다.
Z p 는 0부터 p−1까지의 모든 정수로 구성되며, 여기서 p는 소수이고 산술 연산은 p를 법(modulo)으로 하여 수행된다.

- 알고리즘에 사용되는 연산 중 나눗셈이 있다면, 체(field) 위에서 정의된 산술 연산을 사용해야 gks다.
   = 나눗셈은 모든 0이 아닌 원소가 곱셈 역원을 가져야 한다.
- 편의성과 구현 효율성을 위해 낭비되는 비트 패턴 없이 주어진 비트 수에 정확히 들어맞는 정수를 사용하고 싶다.
0부터 2 n −1 범위의 정수는 n비트 워드에 들어맞는다.
모듈러 연산을 사용하는 이러한 정수의 집합 Z 2 n 은 체가 아니다.

- 2^n을 포함하는 유한체는 GF(2^n)으로 표현할 수 있다.

---

AES 구조 (AES Structure)

AES 암호화 과정 (AES Encryption Process)

평문 (Plaintext) - 16 바이트 (128 비트): 암호화할 16바이트(128비트)의 평문 블록이 입력된다.

AES는 128비트의 고정된 블록 크기를 가지며, 키 길이에 따라 10, 12, 또는 14라운드를 수행한다.

키 (Key) - M 바이트: 암호화에 사용될 키가 입력된다.

키 길이는 16바이트(128비트), 24바이트(192비트), 또는 32바이트(256비트)가 될 수 있으며, 이는 라운드 수(Nr)에 영향을 미친다. (표 참조)

키 확장 (Key Expansion): 입력된 키를 사용하여 각 라운드에 사용될 라운드 키를 생성한다.

초기 키를 확장하여 (Nr + 1)개의 라운드 키를 생성하며, 각 라운드 키는 16바이트(128비트) 크기다.

초기 라운드 키 덧셈 (Initial Round Key Addition): 평문 블록(Initial state)과 0번째 라운드 키(Round 0 key)를 비트별 XOR 연산합한다.

라운드 (Round 1 ~ Round N-1): 초기 라운드 키 덧셈 결과를 N-1번의 라운드를 거쳐 처리한다. 

각 라운드는 4가지 변환(transformation)으로 구성된다.

SubBytes: S-box라는 치환 테이블을 사용하여 상태(state)의 각 바이트를 다른 바이트로 치환한다. 이는 비선형성을 제공한다.
ShiftRows: 상태의 각 행을 왼쪽으로 순환 이동(cyclic shift)한다. 각 행마다 이동하는 칸 수는 다르다.
MixColumns: 상태의 각 열을 특정 행렬과 곱셈하여 열 내부의 바이트들을 섞는다. 이는 확산(diffusion)을 제공한다.
AddRoundKey: 현재 라운드의 라운드 키와 상태를 비트별 XOR 연산한다.

 

최종 라운드 (Round N): 마지막 라운드는 이전 라운드와 유사하지만, MixColumns 변환이 생략된다.
SubBytes
ShiftRows
AddRoundKey (Round N key)

 

최종 상태 (Final state) - 16 바이트: 최종 라운드의 결과를 최종 암호문으로 출력하기 전에 16바이트의 최종 상태로 나타낸다.

암호문 (Ciphertext) - 16 바이트 (128 비트): 최종 상태를 16바이트(128비트)의 암호문 블록으로 출력한다.

라운드 수 및 키 길이 (No. of rounds & Key Length): AES의 라운드 수는 키 길이에 따라 달라진다.

키 길이 128비트 (16 바이트): 10 라운드 (Nr = 10)
키 길이 192비트 (24 바이트): 12 라운드 (Nr = 12)
키 길이 256비트 (32 바이트): 14 라운드 (Nr = 14)

---

AES 구조 (AES Structure)

• AES 암호화 및 복호화 (AES Encryption and Decryption)

(a) 암호화 (Encryption)

1. 평문 (Plaintext) - 16 바이트: 암호화할 16바이트의 평문 블록이 입력됩니다.
2. 키 (Key) - 16 바이트: 암호화에 사용될 16바이트의 키가 입력됩니다. (여기서는 128비트 키를 기준으로 설명합니다. 키 길이에 따라 라운드 수가 달라질 수 있습니다.)
3. 키 확장 (Expand key): 입력된 16바이트 키를 사용하여 각 라운드에 사용될 라운드 키들을 생성합니다. 총 11개의 16바이트 라운드 키 (w[0...3]부터 w[40...43])가 생성됩니다.
4. 초기 라운드 키 덧셈 (Add round key): 평문과 첫 번째 라운드 키 (w[0...3])를 비트별 XOR 연산합니다.
5. 라운드 1 ~ 9 (Round 1 ~ Round 9): 9번의 라운드를 반복합니다. 각 라운드는 다음 4가지 변환으로 구성됩니다.
   • Substitute bytes: S-box를 사용하여 상태의 각 바이트를 치환합니다.
   • Shift rows: 상태의 각 행을 왼쪽으로 순환 이동합니다.
   • Mix columns: 상태의 각 열을 특정 행렬과 곱셈하여 섞습니다.
   • Add round key: 해당 라운드의 라운드 키 (w[4...7]부터 w[36...39])와 상태를 비트별 XOR 연산합니다.
6. 라운드 10 (Round 10): 마지막 라운드는 Mix columns 단계를 제외한 3가지 변환으로 구성됩니다.
   • Substitute bytes
   • Shift rows
   • Add round key: 마지막 라운드 키 (w[40...43])와 상태를 비트별 XOR 연산합니다.
7. 암호문 (Ciphertext) - 16 바이트: 최종 라운드의 결과로 16바이트의 암호문이 출력됩니다.

(b) 복호화 (Decryption)

1. 암호문 (Ciphertext) - 16 바이트: 복호화할 16바이트의 암호문 블록이 입력됩니다.
2. 키 (Key) - 16 바이트: 암호화에 사용된 동일한 16바이트의 키가 입력됩니다.
3. 키 확장 (Expand key): 암호화와 동일한 방식으로 키를 확장하여 11개의 라운드 키를 생성합니다. 복호화 시에는 라운드 키를 역순으로 사용하고, Mix columns 변환의 역연산에 사용되는 키는 약간 다릅니다.
4. 초기 라운드 키 덧셈 (Add round key): 암호문과 마지막 라운드 키 (w[40...43])를 비트별 XOR 연산합니다.
5. 라운드 1 ~ 9 (Round 1 ~ Round 9): 9번의 역 라운드를 반복합니다. 각 역 라운드는 다음 4가지 역변환으로 구성됩니다.
   • Inverse shift rows: Shift rows의 역연산으로, 상태의 각 행을 오른쪽으로 순환 이동합니다.
   • Inverse sub bytes: Substitute bytes의 역연산으로, 역 S-box를 사용하여 바이트를 치환합니다.
   • Add round key: 해당 라운드의 역순 라운드 키 (w[36...39]부터 w[4...7])와 상태를 비트별 XOR 연산합니다.
   • Inverse mix cols: Mix columns의 역연산으로, 상태의 각 열을 특정 역행렬과 곱셈하여 원래대로 되돌립니다.
6. 라운드 10 (Round 10): 첫 번째 역 라운드는 Inverse mix cols 단계를 제외한 3가지 역변환으로 구성됩니다.
   • Inverse shift rows
   • Inverse sub bytes
   • Add round key: 첫 번째 라운드 키 (w[0...3])와 상태를 비트별 XOR 연산합니다.
7. 평문 (Plaintext) - 16 바이트: 최종 역 라운드의 결과로 16바이트의 평문이 출력됩니다.

---

 

상세 구조 (Detailed Structure)

• 각 라운드 동안 전체 데이터 블록을 치환(substitutions)과 순열(permutation)을 사용하여 단일 행렬로 처리합니다.
• 입력으로 제공된 키는 44개의 32비트 워드 배열 w[i]로 확장됩니다.
• 네 가지 다른 단계가 사용됩니다:
  • Substitute bytes (바이트 치환): 블록의 각 바이트를 S-box를 사용하여 바이트 단위로 치환합니다.
  • ShiftRows (행 이동): 간단한 순열입니다.
  • MixColumns (열 섞기): GF(28) 위에서의 산술 연산을 사용하는 치환입니다.
  • AddRoundKey (라운드 키 더하기): 현재 블록과 확장된 키의 일부를 간단한 비트별 XOR 연산합니다.

 

• 암호화는 AddRoundKey 단계로 시작하고 끝납니다.
• 암호화 과정을 블록에 대한 XOR 암호화(AddRoundKey)와, 그 뒤에 블록을 뒤섞는 연산(나머지 세 단계), 다시 XOR 암호화 등이 번갈아 수행되는 것으로 볼 수 있습니다.
• 각 단계는 쉽게 되돌릴 수 있습니다.
• 복호화 알고리즘은 확장된 키를 역순으로 사용합니다.
  • 하지만 복호화 알고리즘은 암호화 알고리즘과 동일하지 않습니다.
• 암호화와 복호화 모두에서 상태(state)는 동일한 방식으로 표현됩니다.
• 암호화와 복호화의 마지막 라운드는 세 단계로만 구성됩니다.

 

---

AES Transformation Functions

 

S-Box 근거 (S-Box Rationale)

• S-box는 알려진 암호 분석 공격에 대해 저항력을 갖도록 설계되었습니다.
• Rijndael 개발자들은 입력 비트와 출력 비트 간의 상관관계가 낮고, 출력이 입력의 선형 수학 함수가 아닌 속성을 갖는 설계를 추구했습니다.
• 비선형성은 곱셈 역원의 사용으로 인해 발생합니다.

ShiftRows 근거 (ShiftRows Rationale)

• 처음 보이는 것보다 더 중요합니다.
• 상태(State)는 물론 암호의 입력과 출력 모두 4바이트 열의 배열로 처리됩니다.
• 암호화 시 평문의 처음 4바이트는 상태의 첫 번째 열에 복사되고, 그 다음 4바이트는 두 번째 열에 복사되는 방식입니다.
• 라운드 키는 상태 열 단위로 적용됩니다.
• 따라서 행 이동은 개별 바이트를 한 열에서 다른 열로 이동시키며, 이는 4바이트의 배수만큼 선형 거리를 이동시키는 것입니다.
• 이 변환은 한 열의 4바이트가 네 개의 서로 다른 열로 분산되도록 보장합니다.

MixColumns 연산 근거 (MixColumns Operation Rationale)

• 코드워드 간의 최대 거리(maximal distance)를 갖는 선형 코드(linear code)에 기반한 행렬의 계수는 각 열의 바이트 간에 좋은 혼합(mixing)을 보장합니다.
• MixColumns 변환은 ShiftRows 변환과 결합하여 몇 라운드 후에는 모든 출력 비트가 모든 입력 비트에 의존하도록 보장합니다.

AES의 MixColumns 연산은 각 열의 바이트들을 효과적으로 섞는 역할을 합니다.

이는 선형 코드 이론에 기반한 특정 행렬과의 곱셈 연산을 통해 이루어지며, 이 설계는 각 열 내부의 정보가 잘 혼합되도록 보장합니다.

더욱 중요한 점은 MixColumns 변환이 이전 단계인 ShiftRows 변환과 함께 작용하여, 암호화가 진행될수록 정보가 데이터 블록 전체로 빠르게 확산되도록 한다는 것입니다.

즉, 몇 번의 라운드만 거치면 암호문의 어떤 비트라도 평문의 모든 비트와 키의 모든 비트에 영향을 받게 됩니다. 이는 암호의 안전성을 높이는 핵심적인 요소 중 하나입니다.

 

AddRoundKey 변환 (AddRoundKey Transformation)

• 상태(State)의 128비트는 라운드 키의 128비트와 비트별 XOR 연산을 수행합니다.
• 이 연산은 상태 열의 4바이트와 라운드 키의 1 워드 간의 열 단위 연산으로 볼 수 있습니다.
  • 바이트 수준 연산으로도 볼 수 있습니다.

---

AES 구현 (AES Implementation)*

• 구현 측면 1 (Implementation Aspects 1)
  • AES는 8비트 프로세서에서 매우 효율적으로 구현될 수 있습니다.
    • AddRoundKey는 바이트 단위 XOR 연산입니다.
    • ShiftRows는 간단한 바이트 이동 연산입니다.
    • SubBytes는 바이트 수준에서 작동하며 256바이트 크기의 테이블만 필요합니다.
    • MixColumns는 유한체 GF(28)에서의 행렬 곱셈을 필요로 하지만, 이는 모든 연산이 바이트 단위로 수행됨을 의미합니다.
• 구현 측면 2 (Implementation Aspects 2)
  • 32비트 프로세서에서도 효율적으로 구현될 수 있습니다.
    • 32비트 워드를 사용하도록 단계를 재정의할 수 있습니다.
    • 256-워드 크기의 4개의 테이블을 미리 계산해 둘 수 있습니다.
      • 1 워드는 4 바이트이므로, 256 x 4 x 4 = 4KB입니다.
      • 테이블 저장에 4KB의 비용이 듭니다.
    • 그러면 각 라운드의 각 열은 4번의 테이블 조회와 4번의 XOR 연산을 사용하여 계산할 수 있습니다.
  • 설계자들은 이러한 매우 효율적인 구현이 AES 암호로 선정된 주요 요인이라고 믿습니다.