AES 암호 알고리즘

AES 암호 알고리즘 (Advanced Encryption Standard)

 

AES 선정 과정

- 1997년 NIST에서 DES를 대체하기 위한 암호 알고리즘을 공모

- NIST 제시 조건

   - 128 비트 블록

   - 128, 192, 256 비트를 지원하는 암호화 키 사이즈

   - Worldwide-royalty free

   - 트리플 DES보다 안전하고 효율적인 알고리즘

- AES1: 15개 알고리즘이 후보로 선정

- AES2: 최종 후보로 5개 알고리즘 선정 (AES finalist)

- AES3: 2000년 10월 2일, Rijndael 최종 선정

 

 

 

 

 

Rijndael

- 블록암호

- 벨기에 암호학자에 의해 개발 (Daemen, Rijmen)

- 가능한 키 사이즈

   - 128 비트부터 256 비트까지 32 비트 단위로 선택 가능

   - AES 규격 상으로 128, 192, 256 3종류 사용

   - SPN (Substitution-Permutation Network) 구조를 사용

 

 

 

 

 

SPN (Substitution-Permutation Network) 구조

- Shannon이 제안한 Substitution Permutation 패러다임을 직접적으로 구현

- 암호화의 기본 모듈(라운드)을 여러 번 반복해서 수행

- 64 비트 블록, 8 비트 S-box 가정

- 64 비트 입력과 64 비트 라운드 키 XOR

- Substitution: 8 비트씩 나누어 S-box 통과 (비선형)

- Permutation: 64 비트 중간값에 대해 Mixing Permutation (P-box) 적용

 

 

 

 

 

SPN 특징

- 각 라운드별로 역방향 연산이 가능 (invertible)

   - 라운드 키를 아는 경우 라운드 키 XOR 역연산

      - y = x ⊕ k ⇒ y ⊕ k = (x ⊕ k) ⊕ k = x

   - S-box & P-box

      - 일대일 함수로서 역연산 가능

- Feistel 구조와의 차이점

   - 단점: Feistel과 다르게 별도의 복호화 알고리즘 구현이 필요함 (역방향 연산 가능이 필요함)

   - 장점: 입력을 쪼갠 상태에서 동시에 라운드 진행 가능 (Feistel 구조는 병렬연산을 지원하지 않음)

 

 

 

 

 

AES 암호 알고리즘

- 128 비트 블록 암호

- 키 사이즈 128, 192, 256 비트

- 여러 개의 SPN 라운드를 반복 (반복횟수는 키 사이즈에 따라 다름)

표기	키 사이즈	라운드 수
AES-128	128 비트	10 라운드
AES-192	192 비트	12 라운드
AES-256	256 비트	14 라운드

- 마지막을 제외한 각 라운드: 4개의 세부 변환으로 구성

   - SubBytes, ShiftRow, MixColumns, AddRoundKey

- 마지막 라운드: 3개의 세부 변환으로 구성

   - SubBytes, ShiftRow, AddRoundKey

 

 

 

 

 

바이트

- Byte: 8 비트로 구성된 비트열 (10진수 0~255)

- Byte와 16진수: 주로 4 비트씩 끊어서 16진수로 씀

- 4 비트 숫자는 10진수로 0~15

- 16진수로 썼다는 것을 표시하기 위해 비트열 앞쪽에 0X를 붙임 (자명한 경우는 생략)

 

 

 

 

 

State & Word

- State: AES의 내부 데이터를 표시한 행렬

   - 128 비트 블록 → 16 바이트 블록 → 4 * 4 행렬 (행렬의 각 성분이 1 바이트)

   - 4 * 4 크기의 2차원 character형 배열

- 16 바이트 숫자의 state 변환

   - 앞에서부터 열을 먼저 채워 나감 (1행 1열 - 1행 2열 - ... - 4행 4열)

- Word: 4 바이트 숫자 (32 비트)를 word로 정의

   - AES state에서 각 열벡터에서 word가 됨

 

 

 

 

 

AES-128 전체 구조

- AddRoundKey: 128 비트 라운드 키 XOR

- SubBytes: S-box, 비선형성 제공

- ShiftRows, MixColumns: Diffusion을 위한 permutation

 

 

 

 

 

SubBytes

- State의 각 바이트를 S-box에 따라 다른 바이트로 substitution

- 2^8가지의 입력값이 존재하여 2^8가지의 출력값이 존재

- 비선형성을 제공 → 차분 공격, 선형 공격에 저항성을 가짐

- S-box: 빠른 연산을 위해 코드에 Table을 기록 → Table Look-up을 통해 substitution

- Table 읽기

   - 바이트의 앞쪽 4비트 → 행

   - 바이트의 뒤쪽 4비트 → 열

   - 해당 행 & 열의 값으로 바꿈

 

 

 

 

 

S-box 구성의 수학적 원리

- 8 비트 숫자를 Field라고 부르는 수학적 집합과 대응 (대수적 구조)

- Field (체): 덧셈, 뺄셈, 곱셈, 나눗셈 (정확히는 곱셈에 대한 역원) 연산이 자유로운 수학적 구조 (유리수, 실수)

- S-box가 사용하는 field는 다항식으로 정의되는 finite field (유한체, GF(2^8))

- S-box는 역원을 구하는 과정

   - 각 바이트를 다항식으로 대응

   - S-box는 주어진 다항식에 대한 GF(2^8)에서 곱셈에 대한 역원이 기록되어 있음

   - 역원 변환 함수는 비선형 함수 (비선형성이 상당히 높은 것으로 분석됨)

   - S-box 구성의 투명성을 제공하기 위해 이러한 방식을 사용

      - DES의 경우는 random substitution 중에서 선택 → backdoor 의혹이 제기된 원인

 

 

 

 

 

ShiftRows

- State의 각 행에 대한 permutation

   - 정해진 숫자만큼 왼쪽으로 순환 이동

   - 1행: 그대로, 2행: 1칸, 3행: 2칸, 4행: 3칸

- 선형 변환이며 확산 효과를 제공

 

 

 

 

 

MixColumns

- State의 각 열에 대한 permutation

- 선형 변환이며 확산 효과를 제공

- 행렬 곱으로 구성

   - 입력 행렬 A, 출력 행렬 B → 특정 행렬 C에 대해 B = C *F A

   - *F: field GF(2^8)에서 곱셈 연산

- 행렬 곱: 곱하기 1, 곱하기 2, 곱하기 3 경우만 존재

- 더하기의 경우 F = GF(2^8)에서는 XOR 연산

- 곱하기 연산

   - 곱하기 1은 자기 자신

   - 곱하기 3은 GF(2^8)에서는 "곱하기 1 + 곱하기 2"와 같음

      - 곱하기 1 + 곱하기 1은 곱하기 2와 같지는 않음

   - 곱하기 2만 계산할 수 있으면 됨

- 실제로는 8 비트 숫자 전체에 대해 곱하기 2(또는 3)을 구한 것을 table로 구성

- 암호화 시에는 table look-up 연산을 간단하게 처리

 - 곱하기 2 계산

- x를 비트열로 표시 후 1칸씩 왼쪽으로 이동

   - 정수에서 2배 연산과 동일 (2x)

- x의 최상위 비트 (MSB)가 0인 경우 그대로 return

- x의 최상위 비트 (MSB)가 1인 경우 1B를 XOR한 값을 return

 

 

 

 

 

AddRoundKey

- 128 비트 state와 128 비트 라운드 키를 XOR

   - fk(x) = x ⊕ k

- 두 입력의 XOR 차이를 그대로 유지

   - 128 비트열: x, y

   - fk(x) ⊕ fk(y) = x ⊕ y

 

 

 

 

 

복호화

- AddRoundKey: 해당 라운드 키를 다시 XOR 하면 됨

   - (x ⊕ k) ⊕ k = x

- InvSubBytes: AES에서 S-box는 8 비트 숫자들 간에 일대일 대응 함수

   - 역으로 변환하는 함수를 Inverse S-box table 생성가능

- InvShiftRows: ShiftRows에서 왼쪽으로 순환 이동한 만큼 오른쪽으로 순환 이동

- InvMixColumns: MixColumns에서 곱하기 행렬 C^-1의 역행렬을 곱하면 됨

 

 

 

 

 

AES-128 라운드 키 스케줄 (Key Expansion)

 

 

 

 

 

AES 디자인에 고려된 사항

- 병렬처리 가능

- 빠른 확산 (Diffusion)

   - 2개 라운드만 거쳐도 128 비트가 잘 확산됨

   - 2개 라우드를 통과하여 얻은 state의 각 비트가 입력 state 128 비트에 모두 의존하여 계산됨

- 대수적 구조를 가진 S-box

   - 강한 비선형성

   - DES와 달리 투명성

- 라운드 키 스케줄에 S-box 적용

   - 두 개의 비슷한 AES 키를 입력으로 받더라도, S-box의 비선형성으로 라운드 키가 많이 달라짐

- AES-128이 10 라운드인 까닭

   - 6 라운드까지로 구성하는 경우 키 전수조사보다 빠른 공격이 존재

   - 10 라운드가 되면 어떠한 알려진 공격도 키 전수조사보다 빠르지 않음