1. AES의 역사

(Advanced Encryption Standard)
DES를 대체하기 위해 NIST에서 공모를 통해 선정한 현대 암호의 표준입니다.

• 선정: 2000년, 벨기에의 Joan Daemen과 Vincent Rijmen이 설계한 Rijndael(레인달) 알고리즘이 최종 AES로 채택되었습니다.
• 위상: 현재 전 세계에서 가장 중요한 대칭키 알고리즘입니다.
• AES is by now the important symm key algorithm in the world
• NSA allows AES for classified data up to Top Secret w/192 or 256 bits key

AES 알고리즘(Advanced Encryption Standard)은 128비트를 블록 단위로 암호화하는 블록 암호 알고리즘입니다. 키의 사이즈는 128, 192, 256비트 중 하나로 선택이 가능하며 키의 길이에 따라 각각 10, 12, 14로 라운드 수가 달라집니다.

2. Structre of AES

Recall:
Fiestel Net <-> DES
AES is not a Fiestel Cipher, it based on Finite Fields

3. Galois Field (GF)

GF(Galois Field)
암호학에서는 보안을 위해 데이터의 범위를 제한하는 '유한한 집합'이 필요합니다.

• G(Group): 덧셈, 뺄셈만 가능, 집합내의 두 원소를 더했을때 다시 그 집합 안에 있어야 함.
• R(Ring): 덧셈, 뺄셈, 곱셈 가능. 정수집합(Z). 나누기는 아직 보장 X
• F(Field): 덧셈, 뺄셈, 곱셈, 나눗셈 가능, 0을 제외한 모든 원소가 곱했을때 1이되는 곱셈 역원'($x^{-1}$)을 가집니다. 암호학에서 말하는 GF(Galois Field, 유한체)가 바로 이 단계입니다.

유한체의 존재 조건

유한체는 원소의 개수가 $p^m$개일 때만 존재합니다. ($p$: 소수, $m$: 양의 정수)
존재함: $GF(11)$, $GF(81)$ ($3^4$), $GF(256)$ ($2^8$)
존재하지 않음: $GF(12)$ ($4 \times 3$ 이며 $p^m$ 형태가 아님)
p: prime number, m: positive integer

결론적으로, 이 그림은 "우리가 안전한 암호(AES 등)를 만들기 위해서는 모든 연산과 역원이 완벽하게 보장되는 가장 안쪽의 'F(Field)'라는 수학적 운동장이 필요하다"는 것을 설명하고 있습니다.

GF(P)

• prime field
• (mod p)

$GF(p^m)$

• extension field
• $GF(2^m)$: 컴퓨터는 0과 1 로 작동
  $GF(2^m)$을 사용하면 $m$비트 데이터를 하나의 수학적 원소로 다룰 수 있습니다.
  예시: AES 암호 알고리즘은 $GF(2^8)$을 사용하여 8비트(1바이트) 데이터를 처리합니다.

4. Prime field Arithmetic GF(p)

midterm 시험에 나옴!
$0$부터 $p-1$까지인 집합입니다

GF(p) = {0,1,2,..., p-1}

4.1 덧셈, 뺄셈, 곱셈:

일반 연산 후 $\pmod p$를 취합니다.
a + b = c mod p
a - b = d mod p
a x b = e mod p

4.2 Divide -> inverse

암호학에서 아래는 같은 말
$b$로 나눈다 = $b$의 역원($b^{-1}$)을 곱한다
조건: $GF(p)$에 속하는 어떤 수 $a$의 역원 $a^{-1}$은 반드시 다음 식을 만족해야 합니다.
$a \cdot a^{-1} \equiv 1 \pmod p$

즉, "곱해서 나머지가 1이 되는 수"가 바로 역원입니다.

찾는법: Exhaustive search (전수조사)
ex) 4의 inverse = 3

5. Extension Field GF(2^m) Arithmetic

AES는 8비트(1바이트) 연산을 위해 $GF(2^8)$을 주로 사용합니다.

(1) Polynomial Representation

원소를 다항식으로 간주하여 처리합니다.
예시: $GF(2^3) = GF(8)$의 원소는 $A(x) = a_2x^2 + a_1x^1 + a_0$로 표현됩니다.
공식: $a_{m-1}x^{m-1} + a_{m-2}x^{m-2} + \dots + a_1x^1 + a_0$

EX) GF(2power3) = GF(8) = {0,1,2,3,4,5,6,7}
A(x) = a2x + a1xpower1 + a0, (a2, a1, 10)
차수: $x$의 가장 높은 차수는 $m-1$

예시 $GF(2^3)$
$a_{m-1}x^{m-1} + a_{m-2}x^{m-2} + \dots + a_1x^1 + a_0$
$GF(2^3) = GF(8)$
원소의 개수: $2^3 = 8$개집합: $\{0, 1, 2, 3, 4, 5, 6, 7\}$
다항식 형태: $A(x) = a_2x^2 + a_1x^1 + a_0$

변환 테이블

(2) Addition & Subtraction

핵심: $GF(2^m)$에서 덧셈과 뺄셈은 완전히 똑같습니다. 둘 다 XOR 연산입니다.
이유: 계수들의 계산이 $\pmod 2$로 이루어지기 때문입니다.

• $1 + 1 = 2 \equiv 0 \pmod 2$$
• 1 - 1 = 0 \pmod 2$
• 즉, 더하나 빼나 결과가 $0$으로 같아집니다.

식: $A(x) = x^2 + x + 1$ 과 $B(x) = x^2 + 1$ 을 더하시오.

계산 과정:
$(x^2 + x + 1) + (x^2 + 1)$
$= (1+1)x^2 + (1+0)x + (1+1)$

모듈로 2 적용: $(1+1)$은 $2$가 아니라 $0$이 됩니다.
$= 0x^2 + x + 0$

컴퓨터 식 계산 (XOR):
$A(x) \rightarrow 111$ (2진수)
$B(x) \rightarrow 101$ (2진수)
$111 \oplus 101 = 010$ (2진수) $\rightarrow$ $x$ (다항식)

(3) Irreducible Polynomials

상황: $GF(2^3)$에서 두 다항식을 곱했습니다.
$A(x) = x^2 + x + 1$$B(x) = x^2 + 1$
일반 곱셈 결과:$x^4 + x^3 + x + 1$ (필기에 노란색으로 칠해진 부분)

문제점:$GF(2^3)$은 최대 차수가 2차($x^2$)여야 하는데, 결과값이 4차($x^4$)가 되어버렸습니다.
"NOT in the field!"라는 빨간 글씨는 "결과값이 $GF(2^3)$ 집합 범위를 벗어났다"는 뜻입니다. 이를 해결하려면 나눗셈(Reduction)이 필요합니다.

$GF(2^3)$
Irreducible Polynomials: $x^3+x+1$

방법: 계산 결과($x^4...$)를 미리 정해둔 기약 다항식 $P(x)$로 나누고, 그 나머지를 취하면 됩니다.

기약 다항식(Irreducible Polynomial)이란?더 이상 인수분해 되지 않는 다항식으로, 정수에서의 소수(Prime Number)와 같은 역할을 합니다.

유일하지 않음 (NOT unique?):
필기에 적힌 대로, $GF(2^3)$을 만들 수 있는 기약 다항식은 $x^3+x+1$ 하나만 있는 게 아닙니다. $x^3+x^2+1$도 가능합니다. 하지만 AES 같은 표준에서는 약속된 하나($x^8 + x^4 + x^3 + x + 1$)만 사용합니다.

---

아래 사진은 앞서 곱셈 결과로 나온 $x^4 + x^3 + x + 1$이라는 식을 기약 다항식 $P(x) = x^3 + x + 1$로 나누어 나머지를 구하는 과정

필기 아래쪽에 파란색으로 $P(x) = x^3+x^2+1$이라고 적고 "?" 표시와 함께 결과가 달라질 수 있음을 적어두셨죠?
이는 "어떤 기약 다항식을 선택하느냐에 따라 나머지(결과값)가 완전히 달라진다"는 중요한 사실을 의미합니다.

AES에서는 대체 뭘 쓰기로 약속했느냐를 보여줍니다.
AES의 기준: $GF(2^8)$ (8비트 처리)
사용하는 기약 다항식 (I.P.):$P(x) = x^8 + x^4 + x^3 + x + 1$
의미:
AES 알고리즘 내부에서 곱셈을 할 때마다 결과가 8차($x^8$) 이상으로 넘어가면, 무조건 이 식을 사용해서 나눗셈을 수행합니다.
이 다항식은 전 세계 표준이므로 절대 바뀌지 않습니다.