[정보보호] AES 알고리즘

AES 애니메이션을 보셨나요 ?

AES 는 128bit 블록을 128bit, 192bit, 256bit 의 키로 암호화를 수행할 수 있습니다.

AES 애니메이션에서 보여지는 것은 128bit (16byte) 키로 암호화를 수행하는 과정입니다.

AES 애니메이션을 기준으로 알고리즘을 설명하도록 하겠습니다.

(제가 자료실에 올려놓은 AES 알고리즘 문서는 더욱 상세한 수학적 내용이 있습니다.

AES 애니메이션이 이 문서에 알고리즘을 굉장히 알기 쉽도록 잘 구성되어 있으므로

무엇으로 구현을 해도 똑같습니다. 애니메이션을 다 이해하신 후 문서를 보시면 더 잘

이해될 겁니다.)

먼저 아래 그림을 보세요.

[그림 1] Encryption Process

위의 [그림 1]을 보시면 암호화 과정이 매우 간단한 것처럼 보입니다.

일단 키스케줄은 나중에 살펴보기로 합시다.(키 스케줄링은 이미 수행되었다고 가정)

State 가 입력으로 들어오고 있는데요(128bit) 이 부분이 암호화할 평문 블록입니다.

맨먼저 State 와 최초 입력한 Cipher Key 를 XOR 연산을 수행합니다. 이 과정을 AddRoundKey 과정이라고 합니다.

여기서 나온 결과를 가지고 SubBytes, ShiftRows, MixColumns, AddRoundKey 과정을 10번 반복합니다.

주의할 점은 그림에도 나와 있는 것처럼 마지막 10번째 Round 과정에서는 MixColumns 과정을 수행하지 않도록 합니다.

이렇게 하면 Encryption 된 블록이 출력됩니다. 이 과정만 원활히 수행이 되면 AES 알고리즘의 암호화 과정이 끝나게 됩니다.SubBytes, ShiftRows, MixColumns, AddRoundKey 과정과 키 스케줄 과정만 알면 AES 를 구현할 수 있을 것입니다. ^^; ( 흐 ~~ 말처럼 쉽게 되면 얼마나 좋겠습니까? )

먼저 SubBytes 를 살펴보도록 하겠습니다.

[SubBytes]

이 과정은 우리가 DES 알고리즘을 구현할 때 나왔던 치환(Substitution)의 개념과 똑같습니다.

특정 규칙에 의해 치환을 수행하면 됩니다.

[그림 2] S-Box (in hexadecimal format)

[그림 2] 는 치환을 수행할 수 있는 S-Box 를 보여줍니다.

[그림 3] 치환 과정

위의 [그림 3] 에서는 치환의 과정을 보여줍니다.

만약, S(0,0) 이 0x19 라고 하면 S-Box 표에서 x 는 1, y 는 9 를 선택합니다. 그러면 0xd4 가 선택됩니다.

S"(0,0) 는 0xd4 의 값을 가지게 됩니다.

이런 식으로 쭈욱~~~ 변환을 수행하면 됩니다.

그런데 알고리즘 문서를 보시면 ... 아핀 변환이라는 말이 나옵니다.

실제로 S-Box 는 아핀 변환의 결과집합입니다.

아핀 변환에 대해서는 알고리즘 문서를 보시면서 한번 공부해 보세요.^^;

부족하다 싶으면 수학책이나 기타 검색자료를 보시고 공부를 하실 필요도 있을겁니다.

(이럴때는 수학과 나온 사람들이 부럽지 않나요 ??? ~~~ )

그런데 구현하는 입장에서 봤을 때는 결과 집합인 S-Box 만 알아도 구현에는

문제가 없습니다. ~~~~~~

이제 다음과정인 ShiftRows 과정을 살펴봅시다.

[ShiftRows]

흐 ... 사실 이 과정은 매우 쉽습니다. 다행스럽게도 .....

아마 애니메이션 보실 때도 쉽다고 느끼셨을것 같은데요 ....

[그림 4] ShiftRows 과정

[그림 4]를 보시거나 애니메이션을 아시겠지만, S 에서 S" 로 변환을 할 때

1번째 row 는 아무것도 수행하지 않고, 2번째 row 는 1byte 쉬프트 (순환), 3번째 row 는 2byte 쉬프트(순환), 4번째 row 는 3byte 쉬프트(순환) 를 수행합니다.

위의 그림이 잘 이해가 되지 않으면 애니메이션을 보세요.^^;

자 이렇게 하면 ShiftRows 과정은 끝이 납니다.

흠 ... 다음은 조금 어려운 MixColumns 과정입니다.

[MixColumns]

이번 과정은 .... 수학적인 배경지식이 필요합니다.

하지만, 수학적인 내용을 다 적기에는 무리가 있는 것 같아 ....

구현 코드를 직접 보여드리도록 하겠습니다.

알고리즘 문서와 wikipedia .... 또는 수학책을 보시면서 ...

직접 공부해 보시기 바랍니다. ^^; ( 흐 ~~~ )

[그림 5] MixColumns 과정 : Multiplication

즉, [그림 5]에서 보여주는 product 연산을 수행할 수 있어야 합니다.

수식을 좀 더 상세하게 살펴보겠습니다.

[그림 6] MixColumns 과정 도식화

[그림 7] MixColumns 과정 : 실제 계산 수행할 Matrix (Nb = 4)

[그림 8] Maxtrix (그림 7) 연산 수행 과정

이제 최종적으로 [그림 8] 의 과정을 계산하여야 합니다.

위에서 언급하였던 것처럼 실제 계산 과정은 각자 공부를 해보시도록 하구요 ...

위의 연산을 수행하는 함수를 직접 기술하도록 하겠습니다.

[소스 1] multiplication 수행 함수 (C 언어)

위의 [소스 1]을 보시면 fw_mul 함수와 fw_MixColumns 함수 이렇게 2개의 함수를 보여주고 있습니다.

[그림 5], [그림 7], [그림 8] 의 과정을 수행하는 핵심함수는 fw_mul 이고, fw_mul 을 이용해서 MixColumns 를 수행하는 함수는 fw_MixColumns 입니다.

즉, 여러분이 나중에 AES 알고리즘을 직접 구현할 때는 fw_mul 함수를 만드는 부분에서 어려움을 겪을 것이라 예상됩니다. 물론 수학과를 나오신 분이나 수학에 조예가 있으신 분들은 직접 만드실 수 있을테구요 ....

그렇지 않을 경우엔 위의 소스를 그대로 가져다 쓰시거나 ... 좀 더 효율적으로 만들어진 함수를 구해서 쓰셔도 됩니다.

우리는 알고리즘을 이해하는 것이 목적이고 실제 AES 를 구현해보는 것이 목적이지만, 완벽하게 수학적인 지식을 습득할 필요는 없습니다. 공부를 위해서는 알 필요가 있겠지만요.

[AddRoundKey]

흠 ... AddRoundKey 과정도 별로 어렵지 않습니다.

즉, State 값과 .... RoundKey 값을 XOR 연산을 수행하면 됩니다.

[그림 9] AddRoundKey 과정

위의 [그림 9] 를 보시면 ... 애니메이션 과정중에 나오는 것인데요 ...

XOR 연산을 수행하면 됩니다.

자 이렇게 해서 ... Encryption 과정은 끝이 났구요 ......

키스케줄 과정을 계속 살펴보도록 하겠습니다.

[키 스케줄]

키 스케줄 과정은 여러분들도 잘 아시다시피 ... 입력받은 키를 이용하여 라운드 함수를 수행할 때 사용할 서브키를 뽑아내는 과정입니다. 라운드를 10번 수행해야 하므로(128bit 키일 경우) 10번의 서브키가 출력될 것입니다.

[그림 10] 키 스케줄(키 익스펜션) 과정 : 1번째 컬럼 워드값 연산

애니메이션을 보셨으면 아마 지금 제가 설명하는 과정보다 더 이해하기가 쉬우실 것입니다.

일단, 애니메이션을 보셨으리라 생각하고 설명드리도록 하겠습니다.

AES 알고리즘에서는 키 스케줄 과정을 키 확장(expansion) 과정이라고 말합니다. 뭐 그냥 용어 정의이므로 그냥 참고하시면 됩니다.

파란색 부분은 입력된 Key 이구요 ...노란색은 Rcon 인데 Round Constant(라운드 상수값) 이라고 부릅니다.

이 값은 .. 물론 알고리즘에서 정해진 값이구요 ... 제가 자료실에 올려놓은 AES 알고리즘 문서에서는 Appendix A 부분을 보시면 128bit, 192bit, 256bit 키를 가질 각각의 경우에 대해서 Rcon 값이 나와 있습니다. 흐 ... 못찾으실까봐요 .... ^^;

주황색 부분은 W_i-1 부분을 로테이션 시켜서 치환한 값입니다. ( 이 부분은 확실히 애니메이션이 쉽습니다. 참고하세요)

즉, 이 3가지 word 값을 XOR 연산을 수행하면 됩니다.

이것이 1번째 컬럼 워드값을 계산하는 과정이구요 .....

2번째 컬럼 워드값은 1번째 컬럼 워드값과 원본 키 블록의 2번째 컬럼 워드값을 XOR 연산 수행하면 됩니다.

3번째, 4번째 컬럼 워드값도 마찬가지로 계산됩니다.

아래 그림을 참고하세요.

[그림 11] 키확장 과정 : 2번째 컬럼 워드값 연산 (3번째, 4번째도 똑같이 적용)

자 이렇게 해서 ..... AES 알고리즘을 끝마쳤네요 ....

복호화 과정과 키가 192bit, 256bit 일 경우의 예는 직접 한번 해 보실 수 있도록 숙제로 남겨드리도록 하겠습니다.

참고자료에 제가 구현한 AES 알고리즘 (C언어) 소스를 올려놓도록 하겠습니다.

더 빠르고 더 좋은 소스를 구하기는 그리 어렵지 않을 것인데요 ....

제가 만든걸 굳이 올리는 이유는 ..... 알아보기 쉽게 ... 만들었기 때문입니다.

직접 구현하고자 하시는 분들이 막힐 경우엔 한번 참고해 보세요.

물론... 이 소스를 너무 크리티컬한 곳에는 사용하지 마시기 바랍니다.(뭐 쓸일도 없겠지만요..)

제가 다 검증한게 아니기 때문에 ... 구현시... 막힐 때 참고하시면 됩니다.

만약 AES 소스가 정말 업무에 필요하다면 .... openssl 소스나 기타 .... linux 소스 등등에서 구해서 사용하시기 바랍니다. 에궁 소스를 직접 쓸 일이 있을지는 모르겠네요.