배우면서 쓰는 암호학
사실 AES라는 말은 정보 분야를 전공으로 하고 있다면 평상시에도 가끔씩 들어보았을 만한 말이다.
하지만 들어보기만 했지, 정보 보안 분야에서 쓰이는 말인줄도 최근에 처음 알게 되었다.
AES에 대해서 알아보도록 하자.
- AES -
사실 AES의 설계 원리를 정확히 이해하기 위해서는
- 갈루아 필드 (Galois Field)
- 체 이론 (Field Thereom)
- 군 이론 (Group Thereom)
이 3가지 이론들을 전제로 알고 있어야 한다.
하지만 3개의 이론들 각각이 양이 어마어마하게 많다.. 따라서 이 부분은 빠르게 스킵하고,
AES를 간략하게 알아보도록 하자.
>> SPN
AES 암호 체계는 SPN (Substitution Permutation Network) 이라는 암호 구조를 기반으로 작동한다.
SPN은 아래의 2가지 동작을 반복하는 암호 체계라고 말할 수 있다.
- 치환 (Substitution) - using S-BOX
- 순열 (Permutation) - using P-BOX
>> before AES
AES 과정을 본격적으로 설명하기에 앞서, AES 는 Block Cipher 방식이라고 이야기했었다. 그렇다면 블럭을 만들어서 각각을 암호화해야 한다는 것인데, 어떻게 Block 을 나누게 될까??
AES는 이런 4x4 행렬을 만들어서 하나의 Block로 간주하게 된다.
예를 들어서 '00041214120414000C00131108171919' 라는 문자열을 AES 방식을 통해서 암호화한다고 가정하면, 다음과 같이 나타낼 수 있게 된다.
따라서 결론적으로 하나의 block은 16 * 8byte 인 128byte를 크기로 가지게 된다.
이를 맞춰주기 위해서 AES 암호화 방식의 키는 128byte, 192byte, 256byte 크기를 가지는 행렬로 정의하게 된다.
그리고 이 행렬의 크기에 따라서 라운드의 수, 블럭의 크기 등 여러 요소가 바뀌게 되지만, 이번 포스팅에서는 AES 암호화 방식을 손쉽게 설명하기 위해 128byte 키를 가지는 AES-128 방식을 디폴트로 두고 설명해보도록 하겠다.
>> AES 구조
먼저, AES의 전체적인 그림을 나타내어보면 다음과 같다.
평문을 AddRoundKey, SubBytes, ShiftRows, MixColumns 등의 함수들을 이용해서 암호화하게 되는데,
위 그림에서 보다시피
- SubBytes → ShiftRows → MixColumns → AddRoundKey
과정이 계속 반복된다. 이 과정이 반복되는 횟수는 키가 몇 바이트인지에 따라서 달라지는데, 현재는 128을 기준으로 설명하고 있으니 총 대략 10번 진행된다고 보면 되겠다.
>> AES functions
자 그럼 본격적으로 AES가 어떤 과정들을 거치는지, 함수들이 어떤 과정을 의미하는지를 하나하나 뜯어보자!
- SubBytes function
SubBytes function은 전에 말했던 S-Box를 이용해서 치환하는 함수이다. 바로 감이 오겠지만, 고전 암호인 다중 문자 치환 암호와 비슷한 표를 토대로 각 원소들을 치환한다.
이렇게 원래 4x4 행렬 속의 원소들을 표를 토대로 바꾸게 되는데, 상위 4바이트가 행, 그리고 하위 4바이트가 열을 담당한다. 예를 들어서 D4 라는 원소가 존재한다면, 위의 표에서 D,4에 해당하는 값을 찾아보면 7A가 되는 것을 알 수 있다. 이렇게 각 원소들을 모두 치환해주는 것이 SubBytes 함수이다.
- ShiftRows function
ShiftRows function은 말 그대로 Row를 Shift하는 함수이다. 암호학에서의 '전치'와 같은 역할을 한다고 생각하면 쉽게 이해할 수 있을 것이다. 각각의 원소에 대해서는 치환 과정을 거치지 않고 그냥 원소끼리의 위치만 바꿔주는 함수이다.
그렇다면 어떤 방식으로 전치가 이루어지는지를 살펴보자.
사실 그림 한장이면 충분하다. n 번째 행은 n칸 Left Shift 되는 것이라고 생각하면 편하다.
- MixColumns function
MixColumns function은 행렬의 연산을 통해서 원소들을 치환하는 함수이다.
다음과 같은 방법으로 4x4행렬의 하나의 열을 바꾸게 되는데, 사실 이 연산은 단순 행렬곱이 아니라 갈루아 필드 내에서 이루어지는 행렬곱이다. 나도 갈루아 필드라는 개념은 잘 알지 못하지만, 아마 단순 곱 계산이 아니라 binary의 형태로 바꾸어서 이를 XOR 해주는 연산자라고 예상된다.
- AddRoundKey function
위의 사진처럼, 원래의 4x4 행렬에다가 key 행렬의 같은 위치에 있는 원소를 XOR 연산을 통해서 새로운 행렬로 바꾸어주게 된다. 그런데 이때, Key 행렬은 어떻게 정의할 수 있을까?? 각각 라운드가 진행되면서 AddAround 함수가 대략 11번 진행되는데, 이때마다 같은 행렬을 써야 할까??
결론부터 말하자면 아니다.
암호화에 필요한 key 행렬들은 일련의 과정을 통해서 새롭게 생성된다. 이제부터 이 key가 어떻게 생성되는지를 알아보도록 하자.
>> Key Schedule
앞서 말했던 key 행렬이 생성되는 방식을 Key Schedule 이라고 한다. 어떻게 Key가 생성될까??
먼저, AES 암호화를 위해서 필요한 키는 1개의 4x4 행렬이다. 이 키를 이용해서 나머지 키들을 만들게 되는데, 이를 살펴보도록 하자.
앞서 소개했던 AES 방식과 유사하게, Key Schedule에서는 3가지 함수를 쓴다.
- RotWord → SubWord → Rcon
이렇게 총 3개의 함수를 쓰게 되는데, 각각 어떤 함수인지 알아보도록 하자.
- RotWord function
사실 따로 나누어서 설명해야 하나 싶을 정도로 간단하다.
이 사진 하나면 설명이 따로 필요 없을 정도이다.
그냥 하나의 열을 위로 shift 해준다고 생각하면 될 것 같다.
- SubWord function
마찬가지로, 너무 간단하다. AES functions 들 중에서 SubBytes 의 function 과 암호화 과정이 동일하다.
주어진 S-Box 를 토대로 새로운 행렬을 만들어주면 된다.
여기서 중요한 점은 SubBytes function에서 쓰인 S-Box가 동일하다는 점이다.
- Rcon function
위의 두 함수들과 다르게 이 함수는 살짝 복잡하다. 잘 살펴보자.
먼저, Rcon 함수를 실행하기 위해서는 새로운 배열이 필요하다.
바로 Rcon 이라는 4x1 행렬의 배열이다.
사실 KeyShedule은 열을 기준으로 암호화가 이루어진다. 무슨 뜻이냐면, Key가 4x4 행렬이라고 할 떄, 이는 4개의 열이 합쳐진 것으로 판단해 따로따로 암호화한다는 것이다.
따라서 처음 키에서는 W0, W1, W2, W3 을 쓰게 되고, 두번째 열은 W4, W5, W6, W7 의 행렬들을 쓰게 된다.
(각각의 W 행렬들은 4x1 행렬, 이 행렬 4개가 모여 원래의 키 4x4 행렬을 생성하게 된다.)
이 표가 Rcon 표이다.
Rcon 표를 이용해서 어떤 W(i) 에 대해서, W(i+4) 를 만드는 과정을 하다 보면, 자연스럽게 여러 Key들이 완성되게 된다.
Rcon function은
1. W(i) 에 대해서 , Rcon[(i/4)-1] 행렬과 위의 두 함수를 거쳐 온 행렬 D(i)를 XOR 하게 된다.
2. 이렇게 XOR 한 행렬을 또 다시 W(i) 와 XOR 하면 새로운 행렬 W(i+4)가 생성된다.
이 두 과정을 거쳐서 반복된다.
RotWord, SubWord, Rcon을 반복하여 W43 까지 행렬을 생성하게 되고, 이를 4열씩 각 라운드에 사용한다. W0, W1, W2, W3 은 암호화를 시작할 때 사용하게 되고, 따라서 1라운드에서는 W4, W5, W6, W7이 사용된다.
>> code?
아무래도 처음 포스팅이라 설명이 난잡하다고 느껴진다...
이해를 돕기 위해서 지금까지 설명한 AES의 암호화 과정을 그림으로 한눈으로 보면 다음과 같다.
다음 포스팅에서는 DES에 관해서 알아보도록 하자...
