[Cryptography] AES(Advanced Encryption Standard)

[Cryptography] AES(Advanced Encryption Standard)

AES

배경

- DES가 tehoretical attack과 exhaustive key search attack에 취약하기 때문에 대체를 위해 출현

- AES 공모에서 Rijndael 선정

특징

- TDES보다 빠르고 강력함

- symmetric block cipher

- Block Size : 128 bit

- Key Size : 128/192/256 bit

- Round : 10/12/14 (key size에 따라)

- Round Key size : 128 bit

- DES와 달리 Feistel 구조가 아닌 SPN구조(Iterative)

Encryption

ex) AES Encryption

- irreducible polynomials : x^8+x^4+x^3+x+1 -> 쉽게 MOD 라고 생각하면 됨

- Plaintext : 00 10 20 30 40 50 60 70 80 90 A0 B0 C0 D0 E0 F0

- Key : 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

- Data는 위와 같이 저장

1. S-Box 생성

- 0x00~0xFF까지를 해당 값의 역원을 구해 b7~b0 배치

- 해당 값을 행렬 연산을 통해 구함(carry는 생각하지 말고 그냥 단순히 and 연산을 하고 1의 갯수가 홀수면 1, 짝수면 0으로 계산)

ex) b7-b0 : 10110000 -> 10001111 & 10110000 = 10000000, 1의 갯수 : 홀수 -> b`0 = 1

- b`7 ~ b`0 까지 구한 후 S-box에 넣어줌

- AES 복호화 과정에서 사용되는 Inverse S-box도 동시에 만들어줌

-> S-Box (1,E) = 0x72,  Inverse S-Box (7,2) = 0x1E

- 역원은 Extended Euclidean Algorithm을 사용하여 계산(곱셈은 irreducible polynomial을 이용하여 MOD 해줘야함 - x^8을 넘는 경우가 생기기 때문)

2. Key Expansion

- Key를 이용하여 Round 0~ Round 10에 사용될 round key를 생성

- 각 열이 w가 되고 각 라운드는 이전 라운드 key를 사용하여 생성됨

- XOR과 R Function 두개를 이용하여 생성

1) R Function

- 앞서 구했던 S-Box를 이용하여 R function을 거침

- Rc는 index를 round로 하고 round 1은 1로 두고 2씩 곱해서 생성

- irreducible polynomial를 이용하여 mod

3. Substitute bytes 

- S-Box(16*16)를 이용하여 Substitution 

-> ex) 00 -> S-Box[0][0], F0 -> S-Box[15][0]

4. Shift Rows

- Substitute bytes를 거친 결과를 Input으로 사용

- 4*4 배열에서 1행은 왼쪽으로 0번 shift, 2행은 왼쪽으로 1번 shift, 3행은 왼쪽으로 2번 shift, 4행은 왼쪽으로 3번 shift

5. Mix Columns

- 이전 과정까지 거친 평문을 input으로 하여 행렬 연산 수행

6. Add Round key

- 앞서 Key Expansion을 통해 생성했던 round key와 앞 과정을 모두 수행한 평문을 XOR

Decryption

1. Add round key

- Encryption과 같은 방식

2. Inverse shift rows

- 4*4 배열에서 1행은 오른쪽으로 0번 shift, 2행은 오른쪽으로 1번 shift, 3행은 오른쪽으로 2번 shift, 4행은 오른쪽으로 3번 shift

3. Inverse Substitue Bytes

- Inverse S-Box(16*16)를 이용하여 Substitution 

-> ex) 00 -> Inverse-S-Box[0][0], F0 -> Inverse-S-Box[15][0]

4. Inverse Mix columns

- 이전 과정까지 거친 것을 input으로 하여 행렬 연산 수행