4. AES

DES vs Advanced Encryption Standard(AES)

AES Requirements

Symmetric block cipher, 128-bit data, 128/192/256-bit keys
Stronger & faster than Triple-DES
모든 디자인, 설계를 public하게 공개
Feistel network를 사용하지 않음(SPN Network)

SPN Network

Substitution-permutation network이다.
DES와 다른점은 invertible. Encryption할때 했으면 Decryption할 때 모두 거꾸로 적용을 해서 원래 평문을 얻어낸다.

AES External Format

Key의 Size가 커져도 사실상 Round의 수만 많아진다. Expanded Key Size는 128bit(4word)기준 10라운드로 40word지만 +1(Pre Round)를 추가하여 44word가 된다. 동일하게 192bit(6word)의 경우 12round + 1 (pre round)를 해서 52word가 된다.

128bit block을 byte로 나누면 16개 byte 생기고 4개로 나눠서 4개의 word를 만들고 각 word는 그림에서 보이는 순서대로 b0,b1,b2,b3가 1word, b4,b5,b6,b7이 1word 이런식으로 이루어진다.
state: 그냥 block이다 word 4개로 보여주는거

Group

집합이 있고 연산자(binary operation)가 주어졌을 때, 연산에 대해서 "닫혀있고, 결합법칙, 항등원, 역원이 있을 때" 그것을 Group이라 부름
+ 교환법칙 까지 성립하면 그것을 Commutative group(or abelian group)이라 부름
Ex) G = <Zn,+>인 경우 Abelian(commutative) group이다.
Ex)

Closure: 모든 원소에 대해 . operator연산을 했는데 모든 abcd나옴으로 닫힘.
Associativity: a.(a.b) == (a.a).b 이므로 성립.
Existence of identity: 모든 경우 자신이 나오므로 항등원 존재.
Existence of inverse: a를 기준으로 d의 역원은 b, c의 역원은 c, b의 역원은 d, a의 역원은 a. 역원 모두 성립.
Commutativity: a.b == b.a 같음으로 성립.

Cyclic Group

포함된 모든 원소가 하나의 원소(generator)의 지수 형태 표현으로 대치가 가능한 경우 Cyclic group이라 한다.
Group에서 지수 연산은 우리가 아는 그 지수가 아니라 그룹 연산자를 반복한 횟수이다.
e = a^0이다.(항등원)

1,5에서 Z6의 모든 원소를 만들어 낼 수 있으므로 Generator은 1과 5이며 하나의 원소의 지수 형태로 표현가능함으로 G는 Cyclic Group이다.
H2 = <{0,2,4}, +>: generator 2를 갖는 Cyclic group이다.

Z10 = {0,1,...,9}인데 Z10*는 거기서 10이랑 서로소인 원소들만 즉 {1,3,7,9}. 3,7이 Generator이고 G는 Cylic Group이다.

Order

Group G 원소의 개수
그룹 원소의 개수 만큼 지수승을 하면 항등원이다.
g^n = e

1. G = <Z6, +> 원소를 n번 더했을 때 결과가 0이 되는 최소 n.
ord(0) = 0 mod 6 = 0 (1번째 바로 0 나옴)
ord(1) = 1+1+1+1+1+1 mod 6 = 0 (6번째 나옴)
ord(2) = 2+2+2 mod 6 = 0 (3번째 나옴)
...
2. G = <Z10^*, x> 원소를 n번 곱했을 떄 결과가 1이 되는 최소 n.
ord(1) = 1 mod 10 = 1 (1번째)
ord(3) = 3 x 3 x 3 x 3 mod10 = 1 (4번째)
ord(7) = 7 x 7 x 7 x 7 mod10 = 1 (4번째)

Ring

Group에 연산자 2개가 필요함.
<R,+,x>

Field

<F,+,x>
각각의 연산자에 대해 모두 Abelian group이다.
0에 대해서는 역원이 존재하지 않아도 된다.

Finite Field

유한개의 원소를 갖는 Field
Finite Field == Galois Field
반드시 소수의 지수승에 원소를 갖는다. P^n 개수의 원소를 갖는다.
If n = 1, GF(p) = <Zp,+,x>
-> GF(p)는 p의개 원소를 가진다.(p는 소수)
-> Zp가 {0,1,..,p-1}개로 p개이다.
-> +,x 에 대해서 결합,교환,닫힘,역원,항등 모두 가능 (Abelian group). 단, 0에 대해서는 x이 역원이 존재하지 않는다.

정리:
GF(2) = 원소의 개수가 2개고, 원소에 대해서 연산자 2개가 있는데 연산자가 각각 +,x 이고 각각의 연산에 대해 Abelian group. + 연산에 대해서는 역원이 존재하지만, x 연산에 0에 대해서는 역원이 존재하지 않는다.
위 그림에서 보면 + 연산은 XOR 연산이고, x 연산은 AND 연산이다.

GF(2^8)
8bit 즉, 0000 0000 ~ 1111 1111 까지 값들을 GF(2^8)원소가 뭔지는 모르지만 1:1 매핑이 가능하다. 8개의 비트로 나타낼 수 있는 모든 연산을 GF에 있는 모든 원소에 대한 연산으로 매핑 시킬 수 있다. 왜? GF 내에는 어떤 연산자 2개가 정의 되어있고 그 연산자에 대해 Abelian group.
So, Bit를 연산을 취할 수 있음.

GF(2^n)을 polynomials로 나타내면 _ _ _ _ _ _ _ _ n개 이며 가장 첫 번째는 x^0 = 1 이고 가장 나중은 x^(n-1)이다.
그럴때 Addition(+)는 GF(2)에서의 addition으로 나타낸다. 즉, XOR
multiplication 역시 GF(2)에서의 multiplication으로 나타냄. 즉, AND
곱셈에 경우 캐리가 발생해 irreducible polynomial or prime polynomials이 필요하다.

irreducible polynomial이란 n보다 작은 polynomial로 나누어 떨어지지 않을 경우 즉, 인수분해가 불가능한 경우

x^(n-1)승을 넘어가는 경우에는 정의된 irreducible polynomial로 나눗셈을 해줘야된다.

ex) GF(2^3)일때
(x^2 + 1) + (x^2 + x + 1) = 101 XOR 111 = 010,
(x + 1) x (x^2 + 1) = x(x^2 + 1) + 1(x^2 + 1)이고 이건
011 x 101 인데 사실상 x^3 + x = 1010으로 x만큼의 곱하기 연산은 left shift연산과 같다. 즉, 1010 XOR 101 = 1111이고 irreducible polynomial이 x^3 + x + 1이면 1111 mod 1011 = 1111 XOR 1011 = 100이다.
그러니, x^2연산은 shif left 2회, x^3은 shift left 3회이다.

AES

SubBytes

Byte 단위로 Substitution한다. (비선형적인 특성을 부여 = output을 알아도 input을 쉽게 알지 못함)

16x16 S-box를 사용해 모두 1:1 매핑(permutation)
ex) {95}의 경우 row가 9, col이 5이다.

invertiable하다.
여기서 x가 input으로 16진수 8bit 즉, {95}와 같은 값이 주어진다.
x^-1:
input을 GF(2^8)에서의 polynomial로 매핑을 시키고 irreducible polynomial이 주어졌을때 그때의 역원을 구하면 됨.
Affine Transformation:
그냥 y = ax + b형식의 식으로만 알자
A: matrix로 주어짐
b: column vector로 주어짐

y = Ax^-1 + b
-> y - b = Ax^-1 -> y + b = Ax^-1 ->A^-1(y+b) = x^-1 -> (A^-1(y+b))^-1 = x -> (A^-1y + A^-1b)^-1

ShiftRows

Rows를 섞음으로써 mixcolumn할때 col단위로 섞기에 shiftrows를 하지 않으면 col끼리 섞이게 됨. 하지만 shiftrow를 하게 된다면 조금 더 잘 섞을 수 있음. (permutation. 평문이랑 암호문이랑 다르게 만드는거)

MixColumns

col에서 col 사이에 값을 섞어준다. matrix과 col을 곱함으로써 원래 기존의 Old col에 있는 x y z t의 값이 ax x by x cz x dt 의 계산 값으로 새롭게 됨.
즉 Old matrix(col)에 있는 값을 separately. (provide diffusion)

AddRoundKey

128bit key를 key expansion 과정을 걸치고 나온 값들을 XOR하면 됨.
Decription할때는 key 순서를 반대로 하면 됨.

한칸이 1byte, 칸 4개가 4byte. 전체가 4word, 16byte, 128bit

AES Key Scheduling

128bit 기준 10round. 40word + pre = 44word
4개중에 3개는 XOR
4개 중에 첫번째는 rotate + S-box + XOR round constant.

W0~w3까지는 기존 128bit key를 pre-roundkey로 사용됨.
그리고 w4부터는 앞에 있는 w0~w3까지의 조합으로 이루어짐.
w5,w6,w7는 이전의 값과 wi-4와 단순 XOR를 하면 되지만
w4는 RotWord -> SubWord -> round constant XOR을 한 값과 w0를 XOR해서 구함.
1. RotWord = left shift
ex) RotWord[b0,b1,b2,b3] = [b1,b2,b3,b0]
2. SubWord = 동일하게 SubByte table 사용
ex) [23,24,25,26] 이면 23에 맞는 row 2, col 3의 값을 사용
3. round constant와 XOR

다음과 같이 round constant는 정해짐. Round마다 x2를 하면 됨. 4word = 16byte크기.

Wi-1를 우선 Shift left -> Subbyte XOR Round Constant = ti -> ti XOR w[i-4] = wi

AES Decryption

이것이 성립하기에
다음과 같이 변형이 가능하고
결과적으로 Encryption과 Decryption을 동일하게 보이도록 만들수있다. 동일한 구조로 만들 수 있다. 다만 Decryption할땐 Encryption 할 때 사용한 component를 inverse해서 사용해야됨.
Key 순서를 inverse하게 사용하되, Mix col된 상태로 넣어줘야 함. 첫번째 키랑 마지막 키는 mix col과 연관이 없음으로 그냥 넣어줘도 됨.