[암호학 이론] AES 암호화 알고리즘

 

 

 

 

 

 

2023.10.31 - [crypto] - [암호학 이론] DES 암호화 알고리즘

[암호학 이론] DES 암호화 알고리즘

 

이번 게시물은 DES에서 발전된 알고리즘인 만큼 서로 유사한 부분들이 있습니다. 또한 이번 AES에서 쓰이는 쉬프트 연산, S-box에 대해 이전 게시물인 DES에서 이미 설명을 했기 때문에 별다른 설명을 하지 않습니다. DES 암호화 알고리즘에 대해 모르시는 분들은 먼저 읽고 이해하고 오시는 것을 추천드립니다.

 

 

 

 

 

- AES(Advanced Encryption Standard)

 

AES algorithm (1)

 

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

 

 

 

AES algorithm (2)

 

위의 그림은 라운드 함수의 과정까지 나타낸 AES 알고리즘의 과정의 그림입니다. 두 그림을 보면 AES 알고리즘과 라운드 함수의 과정을 다음과 같이 알 수 있습니다. (위의 두 그림과 앞으로 이어질 설명들은 키의 길이가 128비트를 기준으로 합니다.)

 

 

 

- AES algorithm process

1. Pre-round transformation (AddRoundKey)

2. 1~9 Round

3. Last Round

 

- Round function process

2.1. SubBytes

2.2. ShiftRows

2.3. MixColumns (1 ~ 9 Round)

2.4. AddRoundKey

2.4.1. Key Schedule

 

 

 

1. Pre-round transformation (AddRoundKey)

모든 과정에 앞서서 일단 입력 받은 128비트를 4행 4열 배열(State) 형태로 재구성을 해줍니다. 또한 한 칸(State)에는 8비트가 담겨집니다.

 

4행 4열로 재배열

 

입력 받은 평문의 값이 1F3CF203B211C5AA6EB27A45E4D98130 라고 할 때 위의 그림과 같이 재배열을 해줍니다.

 

AddRoundKey

 

재배열을 한 평문을 키와 xor 연산을 해줍니다. 라운드 함수 안에 AddRoundKey 과정이 포함되어 있지만 라운드 함수를 거치기전 미리 한번 xor 연산을 해주는 과정입니다. 1 ~ 9까지 라운드 함수와 마지막 10라운드 함수의 차이는 MixColumns라는 과정의 포함 유무이므로 라운드 함수에 대해 바로 알아봅니다.

 

 

 

- Round function process

2.1. SubBytes

2.2. ShiftRows

2.3. MixColumns (1 ~ 9 Round)

2.4. AddRoundKey

2.4.1. Key Schedule

 

 

 

2.1. SubBytes

 

SubBytes

 

입력 받은 4행 4열의 State들을 S-box를 참조하여 치환하는 것입니다. DES에서의 S-box 참조 기준과 달리 한 State의 크기인 8비트 기준으로 상위 4비트가 행, 하위 4비트가 열의 수가 됩니다. 예를 들어 위의 그림에서 첫번째 State인 D7을 기준으로 하면, 상위 4비트인 'D'가 행의 숫자가 되고 하위 4비트인 '7'이 열의 숫자가 됩니다. 따라서 밑에 있는 S-box table 그림을 참고로 하면 값이 0E라는 8비트 값을 얻을 수 있습니다.

 

S-box

 

위의 그림은 실제 SubBytes 계산에서 참조하는 S-box table 입니다.

 

 

 

2.2. ShiftRows

 

ShiftRows

 

ShiftRows (Encryption)

 

ShiftRows는 위의 그림과 같이 1행은 0비트, 2행은 1비트, 3행은 2비트, 4행은 3비트씩 왼쪽으로 쉬프트 연산을 해줍니다. 이때 DES와 마찬가지로 데이터의 손실이 일어나면 안되므로 순환 쉬프트 연산(Circular Shift)을 해주고 있습니다.

 

InvShiftRows (Decryption)

 

암호화 때는 ShiftRows시 왼쪽으로 해주던 쉬프트 연산을 복호화 때는 반대방향인 오른쪽으로 각 행마다 암호화 때와 같은 비트수로 쉬프트 연산을 해주면 됩니다.

 

 

 

2.3. MixColumns (1 ~ 9 Round)

 

MixColumns process

 

MixColumns는 입력값을 다음 그림의 중간에 보이는 행렬과 Matrix multiplication을 하고 출력하는 과정입니다. 굉장히 간단해 보이지만 일반적인 Matrix multiplication과 분명한 차이가 있기 때문에 AES 알고리즘 과정에서 가장 복잡하며 수학적 배경지식을 요구하는 과정입니다. 

 

MixColumns Encryption and Decryption

 

AES 알고리즘으로 복호화할 때는 암호화 MixColumns에서 사용했던 행렬의 역행렬의 값을 Matrix multiplication에 이용합니다. 위의 그림을 참고하시면 행렬 값들을 알 수 있습니다. AES에서 자세한 MixColumns 과정이 궁금하신 분들은 밑의 게시물을 참고하시기 바랍니다.

 

2023.11.08 - [crypto] - [암호학 이론] AES MixColumns 과정에 대한 이해

[암호학 이론] AES MixColumns 과정에 대한 이해

 

 

 

2.4. AddRoundKey

 

AddRoundKey

 

앞에 했던 Pre-round transformation와 마찬가지로 입력 값을 각 라운드의 키와 xor 연산을 해서 출력하는 과정입니다.

 

 

 

2.4.1. Key Schedule

 

Key Schedule

 

이제 Key scheduling 과정에 대해 알아보겠습니다. 다음의 그림은 AES-128, 192, 256 모든 경우를 고려한 수식이지만 우리는 현재 AES-128를 가정해서 알아보고 있으므로 AES-128에 맞춰서 보겠습니다.

 

• 먼저 W, Word는 4행 4열 State 상태의 키 값에서 한 열(column)을 나타냅니다.
• N은 처음 주어지는 키에서 W의 갯수를 말합니다. (따라서 AES-128은 4, 196은 6, 256은 8입니다.)
• R은 필요한 라운드의 키 갯수입니다. 128비트 기준으로 처음 Pre-round transformation 에서 사용되는 키 1개와 10라운드 동안 사용되는 키 10개 합치면 총 11개입니다. ( AES-196 : 13, AES-196 : 15 )
• 128비트 기준으로 총 11개의 키가 필요하므로 W는 0 ~ 43까지 입니다. ( 0 ~ 4R-1 )
• K0, K1, ... , K N-1은 처음 주어지는 키의 W를 말합니다. 따라서 W0 = K0 입니다.
• RotWord

RotWord (1)

 

RotWord는 선택한 W(열)을 위로 한번 올려준다고 생각해주면 됩니다.

 

RotWord (2)

 

이렇게 잠시 열을 행으로 두고 왼쪽으로 1비트 만큼 순환 쉬프트 연산(Circular shift)을 해준다고 볼 수도 있습니다.

(헷갈리시면 이건 무시하고 위에껄로 이해하시면 됩니다. )

 

• SubWord

SubWord

 

Word 안의 State들을 SubBytes와 같은 방식으로 S-box table에서 값을 참조하여 치환해주면 됩니다.

 

 

 

Key Schedule

 

이제 다시 Key Scheduling 과정을 수식으로 표현한 그림을 보겠습니다. 처음에 키 값도 4열 4행의 State 상태로 주어지므로 W0, ... , W3까지는 K0, ... , K3과 값이 같습니다. 수식 중간에 있는 mod 연산은 나머지 연산입니다. i를 N으로 나눴을때 나머지와 0이 같을 때를 두번째 수식 조건이 나타내고 있습니다. 즉 i가 4의 배수일 때를 의미합니다. W4를 구할 때 두번째 수식을 따라야 합니다. RotWord(W3)의 결과 값을 SubWord 계산을 해주고 그 값을 W0와 xor 해주고 rcon0과 xor을 해주면 W4의 값이 생성됩니다.

 

rcon

 

다음과 같은 rcon이라는 고유의 값들이 있다고 생각하고 보고 계산하시는게 닛다고 생각합니다. rcon 생성과정은 DES 알고리즘과 큰 연관도 없을 뿐더러 상당히 복잡합니다. 키 생성과정을 이정도로 다루는 사이트도 거의 없었기 때문에 넘어갑니다.

 

i가 4의 배수가 아닐 때는 4번째 수식에 해당합니다. 따라서 Wi = W i-N xor W i-1 입니다. 세번째 수식은 AES-256 의 경우만 특별히 해당하는 부분이므로 무시해도 됩니다.

 

https://en.wikipedia.org/wiki/AES_key_schedule

AES key schedule - Wikipedia

 

Key Scheduling 과정을 자세히 다루는 사이트들도 없고 찾아도 i 기준이 서로 틀려서 위키피디아가 가장 도움이 됐던 것 같습니다. rcon 생성과정도 언급해놔서 궁금하신 분들은 참고하셔도 좋을듯 합니다.

 

rcon constant

 

AES-196, AES-256 일때 rcon 값이 필요하신 분들은 위의 그림에 있는 값들을 참고하셔도 좋을 듯 합니다.