1. AES 개요
1.1 AES와 Rijndael
AES는 Vincent Rijmen과 Joan Daemen이 개발한 Rijndael 알고리즘을 바탕으로 NIST가 2001년 선정한 블록암호 표준이다.
| 항목 | AES-128 | AES-192 | AES-256 |
|---|---|---|---|
| 평문 및 암호문 블록 | 128비트 | 128비트 | 128비트 |
| 비밀키 길이 | 128비트 | 192비트 | 256비트 |
| 라운드 수 | 10 | 12 | 14 |
| 내부 구조 | SPN | SPN | SPN |
DES의 Feistel 구조와 달리 AES의 기본 구조는 **Substitution-Permutation Network(SPN)**다. 블록 크기와 키 크기는 별개다. AES에서 블록은 항상 128비트이며, 키에 따라 라운드 수가 달라진다.
1.2 16진수 표현과 State
한 바이트는 8비트이고, 4비트 값 하나를 16진수 한 자릿수(0~9,A~F)로 표기한다. AES에서는 128비트 입력을 16바이트, 곧 4행 4열 State 행렬로 구성한다. State 예시:
일반적인 AES 상태 배열은 열 단위로 채워지는 4x4 바이트 행렬이다. 다음 행렬 연산은 평문과 키의 바이트 순서를 명확히 지정해야 정확히 계산된다.
1.3 암복호화 순서와 마지막 라운드
암호화 전 단계에서 AddRoundKey가 먼저 적용된다. AES-128의 일반 라운드 1~9는
순서로 수행한다. 마지막 라운드에는 MixColumns가 없다. 복호화는 각 변환의 역을 사용하며 라운드키도 역순이다.

2. AES의 유한체
2.1 Field와
체(Field)는 덧셈, 뺄셈, 곱셈, 0이 아닌 원소에 대한 나눗셈이 가능하고 결합법칙, 교환법칙, 분배법칙을 만족하는 집합이다. 실수와 복소수는 체이나 정수 는 이 정수가 아니므로 체가 아니다. 는 p가 소수인 경우 체가 된다. 은 원소가 개인 유한체다. 일반적으로 를 차수 n의 기약다항식으로 나눈 나머지 동치류를 이용해 구성한다. 합동산술에서 나눗셈은 역원 곱셈이다. 합성수를 법으로 삼으면 0이 아닌 어떤 원소에는 역원이 존재하지 않으므로 체가 되지 않는다.
2.2 AES의 기약다항식
AES 바이트 연산은 계수 다항식의 몫체를 이용한다.
바이트 비트열 는 다음 다항식과 대응한다.
예를 들어 는 이다.
2.3 덧셈은 XOR
계산 예시는
그러면 같은 항끼리 덧셈하면 계수가 0이 되어
바이트로 표현하면
2.4 곱셈과 reduction
곱셈은 다항식 곱셈 결과를 구한 후 차수 8 이상의 항을 로 나눈 나머지로 환원한다.
예를 들어 이므로 가장 높은 차수항을 이 관계로 줄일 수 있다. 모든 덧셈은 에서 XOR다.
핵심: AES에서 곱하기 02는 1비트 왼쪽 이동을 기초로 구현하고, 최고 비트가 1이면 환원 다항식에 따른 XOR을 추가한다. 이 설명은 이후 MixColumns의 02, 03 계수와 연결된다.
3. 다항식 Euclidean Algorithm과 역원
3.1 Bézout 항등식
체 의 다항식 에 대해 유클리드 알고리즘과 확장 유클리드 알고리즘은
를 만족하는 를 구한다. 가 기약이고 이면 gcd가 1이므로
3.2 일반 나눗셈 절차
나머지가 0이 될 때까지 반복한다. 마지막 0이 아닌 나머지가 gcd다. 연산은 에서 수행되므로 빼기 역시 덧셈과 같다.
3.3 역원 계산
첫 두 나눗셈은 다음과 같다.
두 번째 식에서
이고 첫 번째 식의 나머지를 대입하면
에서 이므로
따라서
검산: 이라는 Bézout 식을 직접 펼쳐 확인한다.
3.4 Extended Euclidean Algorithm의 상태 갱신
초기 계수는
이다. 몫 를 사용하여
로 갱신한다. 에서는 빼기가 XOR와 동일하다. 각 단계마다 불변식을 유지한다. 이 불변식은 수학적 귀납법으로 증명할 수 있다.
4. SubBytes 및 AES S-box
4.1 SubBytes
State의 각 바이트를 독립적으로 8비트 S-box에 넣는다. 위치를 바꾸는 ShiftRows와 달리 바이트 값 자체를 비선형으로 변환한다. 예시는:
4.2 S-box의 수학적 구성
입력 에 대하여 먼저 곱셈 역원 을 구한다. 단 은 별도로 0에 대응한다. 그다음 비트벡터에 고정된 affine transformation을 적용한다.
이 변환에서 는 아래의 8×8 이진 행렬이다.

예시:
-
-
-
(역원이 04이고 affine transformation을 적용)
단순히 256개 값을 암기하는 대신 유한체 역원 계산과 affine map의 두 단계가 핵심이다.
4.3 S-box와 Inverse S-box
S-box는 바이트의 상위 16진수 한 자리를 행, 하위 한 자리를 열로 읽는다. 예를 들어 입력 EA는 E행 A열의 87로 치환된다. 역 S-box는 이 대응을 반대로 되돌린다.


5. ShiftRows
State의 네 행을 각각 왼쪽으로 0, 1, 2, 3바이트씩 순환 이동한다. 역변환은 오른쪽 순환 이동이다. 예시:
첫 행은 바뀌지 않는다는 점과, 같은 바이트라도 행에 따라 이동량이 다르다는 점을 확인한다.
6. MixColumns
6.1 행렬 연산
한 열의 네 바이트를 의 원소로 보고 고정된 4x4 행렬을 곱한다. 네 출력 바이트가 각 열의 모든 입력 바이트에 의존하도록 **확산(diffusion)**한다.
행렬 곱셈은 보통 정수 연산이 아니라 에서 수행한다. 역 MixColumns는 위 행렬의 역행렬을 이용한다.
6.2 예제의 첫 번째 열
입력의 첫 열은 이고, 출력은 이다.
다항식으로 같은 계산을 전개하면,
같은 방식으로 다른 열도 계산한다. 전체 예시 출력:
7. AddRoundKey
현재 State의 128비트와 같은 크기의 round key를 비트별 XOR한다.
XOR을 두 번 하면 제자리로 돌아오므로 역연산 또한 같은 키로 XOR하는 것이다. 첫 바이트 예시:
전체 연산:
AES의 라운드 변환 중 비밀키에서 유도한 라운드 키를 직접 사용하는 단계는 AddRoundKey다.
8. AES-128 Key Expansion
8.1 4바이트 Word
AES-128 비밀키 128비트는 네 개의 4바이트 word로 시작한다.
다음 word는 앞선 4칸의 word와 바로 직전 word를 조합한다.
8.2 변환의 단계
-
RotWord: word를 왼쪽으로 한 바이트 회전
-
SubWord: 회전 결과의 네 바이트에 AES S-box 적용
-
Rcon: 맨 앞 바이트에 라운드 상수 를 XOR
라운드 상수의 첫 바이트는 에서 을 계산해 구하고, 나머지 세 바이트는 0으로 둔다. 부터 까지 만들어 최초 키 포함 총 11개 라운드 키를 사용한다. 네 word마다 특수한 가 개입한다는 점, Shift/Rotate와 S-box, Rcon이 서로 다른 단계임을 구별해야 한다.

9. AES 안전성과 블록 암호 비교
AES-128의 전수 탐색 공간은 . 2011년에는 Bogdanov, Khovratovich, Rechberger가 Biclique 공격을 제시했다.
| AES 버전 | Biclique 공격의 계산복잡도 |
|---|---|
| AES-128 | 약 |
| AES-192 | 약 |
| AES-256 | 약 |
이는 이론적인 공격 복잡도로, 곧바로 실용적인 암호 해독 가능성을 뜻하지 않는다.
| 항목 | DES | Triple DES | AES |
|---|---|---|---|
| 블록 크기 | 64비트 | 64비트 | 128비트 |
| 키 크기 | 56비트 | 112 또는 168비트 | 128/192/256비트 |
| 라운드 | 16 | DES 연산 3회 | 10/12/14 |
| 구조 | Feistel | Feistel 기반 EDE | SPN |
Comments