AES(Advanced Encryption Standard) - 1

1. AES(Advanced Encryption Standard) 개요

• 블록 암호 알고리즘
• 대칭키 암호 알고리
• 기밀성을 위협하는 치명적인 취약점이 발견되지 않았음.

 

1-1. Round

AES는 128비트 평문을 128비트 암호문으로 출력하는 알고리즘

non-Feistel 알고리즘에 속한다.

10, 12, 14라운드를 사용하며, 각 라운드에 대응하는 키 길이는 128, 192, 256비트이다.

 

$N_r$은 라운드 수를 뜻한다.

키 길이에 따라서 AES의 세 가지 버전이 존재한다. (AES-128, AES-192, AES-256)

모든 경우에 대해 Key expansion 알고리즘으로부터 생성되는 라운드 키 길이는 평문과 암호문의 길이와 동일한 128비트이다.

 

 

 

Key expansion 알고리즘으로부터 생성된 라운드 키의 수는 총 라운드 수보다 하나 더 많다.

라운드 키의 수 = $N_r + 1$

 

 

1-2. 데이터 단위

AES는 bit, byte, word, block, state의 5가지 단위를 사용하여 계산한다.

bit는 더 이상 쪼개질 수 없는 atmoic data unit이다.

 

 

(1) Bit

Bit는 0 또는 1의 2진 데이터 값으로 다른 데이터를 이루는 가장 작은 요소이다.

 

(2) Byte

1Byte는 8개의 bit로 이루어지고 각 bit들을 원소로 하는 행/열 행렬로 표현할 수 있다.

 

(3) Word

1Word는 32bit, 즉 4Byte로 이어지고 각 byte를 원소로 하는 행/열 행렬로 표현할 수 있다.

 

(4) Block

AES의 한 Block은 128bit로 구성되고 16byte를 원소로 하는 1x16 행렬로 표현할 수 있다.

 

(5) State

AES는 여러 라운드를 사용하며, 각 라운드는 여러 단계로 구성된다.

데이터 블록은 단계마다 변형되는데, 이때 암호 알고리즘의 시작과 끝의 값을 Data Block 이라고 하며, 

각 단계 전후에 있는 데이터 블록을 State라고 정의한다.

 

각 단계의 State를 S라고 나타내고, 때때로 임시 상태를 T로 표현한다.

블록과 마찬가지로 State는 16개의 Byte로 구성되며 Byte를 성분으로 하는 4x4 행렬로 나타낸다.

 

각 원소는 $s_{r,c}$로 표현하며 r은 행이고, c는 열이다.

 

 

 

 

1-3. 라운드 함수 구조

각 라운드는 마지막 라운드를 제외하고 역연산이 가능한 4개의 transformation을 사용하고, 마지막 라운드에서는 3개의 transformation만 가진다.

 

각 transformation은 하나의 State를 입력으로 하여 다음의 transformation or round에 사용될 또 다른 상태를 생성한다.

첫 라운드가 시작되기 전에는 AddRoundKey만 사용하고, 마지막 라운드에서는 MixColumns를 제외한 3개의 transformation만 사용된다.

 

 

 

2. Transformation

 AES 알고리즘은 안정성을 제공하기 위해서 Substitution, Permutation, Mixing, Key-adding과 같은 4가지 형태의 Transformation을 사용한다.

 

2-1. Substitution

• Substitution은 각 바이트에 대해서 적용된다.
• 모든 바이트 변환을 위해서 하나의 테이블만이 사용된다 => 입력 값이 같으면 출력 값이 동일함
• Transforamtion은 $GF(2^8)$상의 수학적 연산으로 정의된다.

 

(1)  SubBytes

•  AES의 암호화 과정에서 사용되는 Substitution 함수
• 하나의 바이트를 대치하기 위해서 각 바이트를 4비트씩 2개의 16진수로 계산하여 왼쪽 4비트를 S-Box의 행으로, 오른쪽 4비트를 열로 Table을 읽는다.
• 즉 두 16진수의 행과 열이 교차하는 부분에서 바이트 값을 출력한다.

 

AES의 128비트 State를 한 바이트를 State로 가지는 (4X4) 행렬로 나타낸다.

각 바이트에 대해서 독립적으로 SubByte를 수행하고 계산 후에도 행렬에서 State들의 위치는 변하지 않는다.

이와 같이 바이트 별로 독립적인 16번의 변환 과정이 존재한다.

 

SubByte는 Confusion(혼돈)효과를 준다.

예를 들어, 5A와 5B는 한 비트만 다르지만 S-box에 의해서 BE와 39로 변환되어 4비트가 달라진다.

 

 

(2) InvSubBytes - SubByte의 역변환

 

2-2. Transformation over $GF(2^8)$

표처럼 각 바이트에 대해 대치될 값을 찾을 수도 있지만, AES는 Irreducible polynomial(기약 다항식) $x^8+x^4+x^3+x+1$을 가진 체 $GF(2^8)$를 이용해 대수적인 변환으로 S-box를 정의한다.

 

SubBytes는 subbyte로 불리는 루틴을 16번 반복하고, InvSubBytes는 invsubbyte로 불리는 루틴을 16번 반복한다.

그리고 각 루틴은 한 바이트씩 처리한다.

 

(1) subbyte

1. 입력 바이트에 대한 inverse(역원)을 구한다.

2. 그 값을 행렬 X와 XOR하고 열 행렬 y를 더한다.

 

(2) invsubbyte

1. 열 행렬 y를 빼고, 역행렬을 이용해 XOR 연산을 되돌린다.

2. GF(2⁸)에서 다시 inverse를 구해 원래 값으로 복구한다.

 

여기서 Square matric X와 column matrix y는 고정된 값이다.

비트 단위 곱셈과 덧셈은 $GF(2)$에서 수행된다.

 

 

 

더 자세한 수학적인 과정은 따로 글을 작성해 알아볼 예정이다.

 

2-3. Permutation

(1) ShiftRows

• 왼쪽으로 이동을 수행한다.
• 이때 이동하는 수는 상태 행렬의 행 번호(0~3)에 의존한다.
• 0번째 행에서는 이동하지 않고, 마지막 행에서는 3바이트만큼 순환 이동한다.
• ShiftRows 변환은 한번에 하나의 행을 변환한다.
  

  

(2) InvShiftRows

• 오른쪽으로 이동을 수행한다.
• 이동하는 수는 상태 행렬의 행 번호(0~3)에 의존한다.

 

 

2-4. Mixing

SubBytes의 경우 원래 값과 테이블의 성분을 기반으로해서 바이트 값을 바꾼다.

여기서 변환 과정에 이웃한 바이트들이 포함되지 않는다.

따라서 SubBytes는 하나의 바이트 안에서의 변환 Intrabyte transformation이다.

 

ShiftRows의 경우 바이트 안의 비트를 치환하지 않고 바이트를 교환하는 것이다.

따라서 ShiftRows는 바이트 단위로 교환하는 변환 Byte-exchange transformation이다.

 

인접한 바이트들 안에 있는 비트들에 기반하여 비트 값을 바꾸는 바이트 내부 변환이 필요하다.

즉, 비트 단위의 확산을 줄 수 있는 바이트 뒤섞음이 필요하다.

 

Mixing transforamtion은 한 번에 4개의 바이트를 가지고 각 바이트의 비트들을 바꾸어서 4개의 새로운 바이트를 생성한다.

4개의 입력 바이트들이 동일하더라도 각각의 새로운 바이트가 서로 다르게 하기 위해서, 먼저 각 바이트에 서로 다른 상수 값을 곱해서 그것들을 뒤섞는 과정을 수행한다.

 

뒤섞는 과정은 아래와 같이 행렬 곱 연산에 의해 수행된다.

 

(1) MixColumns

• 각 State의 열을 새로운 열 형태로 변환한다.
• State의 열 행렬의 고정된 특정한 Square Matrix를 곱하는 연산이다.

 

이 과정에 사용되는 상수 행렬은 다음과 같다.

 

(2) InvMixColumns

• 기본적으로 MixColumns와 동일함
• 두 개의 상수 행렬이 서로 역행렬이다.

 

2-6. Key-adding

가장 중요한 Transformation은 암호 키를 포함하는 부분이다.

이전의 모든 Transformation들은 역변환이 가능한 알려진 알고리즘을 사용한다.

만약 암호 키가 각 라운드의 State에 더해지지 않는다면, 공격자는 주어진 암호문으로부터 평문을 매우 쉽게 찾을 수 있게 된다.

 

AES는 키 확장 알고리즘을 사용한다.

이는 암호 키로부터 $N_r+1$개의 라운드 키를 생성하는 알고리즘이다.

각 라운드 키는 128비트이며, 이는 4개의 32비트 워드로 간주된다.

각 워드는 열 행렬로 간주한다.

 

(1) AddRoundKey

• 한 번에 한 열씩 수행한다 => MixColumns와 유사
• 각 State의 열 행렬에 라운드 키 워드를 더한다.
• MixColumns에서의 연산은 행렬 곱셈이고, AddRoundkey에서의 연산은 행렬 덧셈이다.