[Cryptography] stage3_블록암호: AES

AES는 전세계에서 암호 알고리즘을 공모받고, 심사를 거쳐 개중 가장 뛰어난 것이 선정된 결과이며, Rijndael구조가 채택되었고, 표준으로 선정된 이후부터 지금까지 기밀성을 위협하는 치명적인 취약점이 발견되지 않았다.

 

CPU제조사들이 AES연산을 위한 명령어를 따로 정의해 줘서 암/복호화 성능도 뛰어나다. -> 현대에는 대칭키 암호 알고리즘을 사용할 때 일반적으로 AES가 사용됨.

 

 

*SPN

AES는 SPN(Substitution Permutation Network)라는 암호 구조를 사용한다. SPN은 곱 암호의 일종인데, S-Box를 사용하는 치환(Substitution)과, P-Box를 사용하는 순열(Permutation)을 여러 라운드에 걸쳐 반복한다.

 

페이스텔 구조(DES)와 달리 SPN구조의 경우 라운드마다 입력 전체에 라운드 함수를 적용하므로, 같은 수의 라운드를 사용할 때 SPN이 페이스텔 구조에 비해 암호학적으로 두 배의 안전성을 갖는다.

 

 

*AES구조

AES는 라운드마다 128비트 크기의 블록을 암호화하는 블록 암호이다. 키의 길이는 128, 192, 256비트 중 하나로 선택할 수 있고, 라운드 수는 키 길이에 따라 10, 12, 14로 결정된다. 키의 길이에 따라 AES-<키 길이> 라고 부른다.

 

AES는 암호화 시, 각 블록을 4행 4열의 상태 배열로 재구성한다. state의 각 칸에는 8비트 == 1바이트가 저장된다. (16 * 8 == 총 128비트)

 

입력 1F3CF203B211C5AA6EB27A45E4D98130의 경우 

 

1F 3C F2 03

B2 11 C5 AA

6E B2 7A 45

E4 D9 81 30

 

위와 같은 stage로 재구성 -> 재구성된 입력에 대해 AddRoundKey함수 적용 -> 매 라운드마다 SubBytes, ShiftRows, MixColumns, AddRoundKey 4개 함수 돌아가면서 반복 적용 -> 마지막 라운드에서는 MixColumns제외 나머지 함수 3개만 적용

 

위 입력의 경우 128비트 -> 10라운드이므로, 

 

Encryption:

plain -> AddRoundKey -> [SubBytes -> ShiftRows -> MixColumns -> AddRoundKey] * 9rounds -> [SubBytes -> ShiftRows -> AddRoundKey] -> ciphertext

 

Decryption:

ciphertext -> [InvShiftRows, InvSubBytes, AddRoundKey, InvMixColumns] * 9rounds -> [InvShiftRows -> InvSubBytes -> AddRoundKey] -> plain

 

AES의 라운드 함수들은 역함수가 존재 -> 그걸 이용해서 AES복호화가 이루어짐.

 

 

*AES라운드 함수

 

SubBytes: state의 각 바이트를 S-Box를 참조해 치환하는 함수이다. -> 바이트의 상위 4비트가 행, 하위 4비트가 열을 결정한다. -> 어떤 바이트가 2A이면 그 바이트는 S-Box의 2행 A열을 참조해 E5로 치환한다. 

 

S-Box

 

ShiftRows: state의 각 행을 구성하는 바이트들을 쉬프트하는 함수. (순열 역할) 

 

AE 72 3C 7E                                      AE 72 3C 7E ​

​83 1A 32 D3      -> ShifRows ->   1A 32 D3 83 ​

97 18 6A C1                     ​                  6A C1 97 18 

56 0C 29 86                                       86 56 0C 29

 

2행은 왼쪽으로 1칸, 3행은 왼쪽으로 2칸, 4행은 왼쪽으로 3칸을 민다.

 

 

MixColumns: 열 단위로 치환을 수행하는 함수. 갈루아 필드 내에서의 행렬 연산으로 구해진다.

 

 

DB F2 D4 2D                                        8E 9F D5 4D

13 0A D4 26    -> MixColumns ->  4D DC D5 7E

53 22 D4 31                                          A1 58 D7 BD

45 5C D4 4C                                         BC 9D D6 F8

 

 

AddRoundKey: 키 생성 함수(Key Schedule)로 생성된 라운드 키의 state를 각 바이트별로 XOR한다. (복호화 시 동일한 키를 한번 더 XOR하면 됨)

                  63 A9 24 0D                    21 3C C5 71                                            42 95 E1 7C

state =   5C 2A 74 B6       key =  CC 6A 82 C1  -> AddRoundKey -> 90 80 F6 77             

                  A3 30 5D 11                     75 20 53 9C                                           D6 10 0E 8D             

                  C5 2C 34 7C                    15 7C 63 1E                                           D0 50 57 62  

 

 

Key Schedule: 키 생성 함수. 각 라운드에 쓰일 라운드 키를 생성한다. 

 

AES-128알고리즘,

 

              2B 28 AB 09

key =  7E AE F7 CF

             15 D2 15 4F

             16 A6 88 3C

 

라고 하자. AES는 암/복호화 시작 시, 그리고 매 라운드마다 AddRoundKey를 적용한다. -> AES-128에서는 라운드 키가 11개 필요하다. (시작 + 10라운드)

 

각 라운드 키는 4행 4열의 행렬이므로, 4행 44열의 키 행렬을 하나 만든 뒤 4열씩 나누어 매 AddRoundKey마다 사용하면 된다. 이 키 행렬의 각 열을 W0 ~ W43이라고 하자.

 

첫 번째 AddRoundKey에서는 입력된 키를 그대로 사용하므로 W0 ~ W3은 입력된 키의 각 열들과 같다.

 

i >= 4에서, Wi는 Wi-1에 RotWord, SubWord, Rcon을 적용하고, 이를 Wi-4과 XOR하여 생성한다.

 

->RotWord: 열을 위로 한 번 회전시킨다.

 

09                               CF

CF -> RotWord -> 4F

4F                               3C

3C                               09

 

->SubWord: SubBytes에서 사용한 것과 동일한 S-Box를 시용해 각 바이트를 치환한다.

  

CF                                8A

4F -> SubWord -> 84

3C                                EB

09                                 01

 

->Rcon: R = [01, 02, 04, 08, 10, 20, 40, 80, 1B, 36] 인 R에 대해 Wi의 최상위 바이트를 R[i/4 - 1]과 XOR한다. 

 

i = 4인 경우이므로, 

8A                                    8B

84 -> Rcon(i == 4) -> 84

EB                                   EB

01                                     01

 

->Rcon의 출력과 Wi-4를 XOR하면 최종적으로 Wi가 생성된다.

 

           8B                   2B                            A0

W4 = 84        W0 = 7E         -> XOR -> FA

           EB                   15                             FE

            01                   16                             17

 

 

위 과정을 반복하여 W43까지 생성한 뒤, 이를 4열씩 잘라 각 라운드에 사용한다. W0 ~ W3의 경우 암호화 시작 시 사용했으므로, 1라운드에서는 W4 ~ W7부터 이용한다. 

 

Rcon과 열 XOR과정은 키 길이에 따라 약간의 차이가 있다.