고급 암호화 표준

가정용 네오지오 기판에 대해서는 네오지오 문서를 참조하십시오.

1 개요

Advanced Encryption Standard, 줄여서 AES라고 흔히 불린다. 벨기에의 2명의 암호학자, 존 대먼과, 빈센트 라이먼이 만든 암호화 알고리즘이다. NIST가 제정한 알고리즘이며 미국 정부가 채택한 후, 높은 안전성과 속도로 인해 인기를 얻어 전세계적으로 많이 사용되고 있다. ^[1]

2 역사

NIST(National Institute for Standards and Testing)가 기밀문서를 안전하게 암호화 시켜서 보호하기 위해 DES 암호화 알고리즘을 대체할 새로운 암호화 알고리즘을 찾기 시작했다 ^[2]. 그러다 AES라는 암호화 알고리즘이 나온 것이다.
NIST는 1998년 8월 20일에 First AES Candidate를 개최하였고^[3], 1999년 3월에 Second ARS Candidate Conference를 개최하였고, 1999년 8월에 5개의 암호화 알고리즘이 후보로 추가되었다 ^[4]. 결국, AES를 위한 암호화 알고리즘은 레인달이 뽑혔다^[5]. 이후 2001년 2월 28일, 기밀문서를 암호화 할 때, DES를 대체하여 많이 사용되기 시작되었다.

3 알고리즘

AES암호화에 사용되는 단계들이다.

이 밑에 있는 것들이 알고리즘 이름들이다.

S-Box
ShiftRows
MixColumns
AddRoundKey

키 스케쥴다음, 가장 처음에 AddRoundKey로 CipherText를 암호화 시킨다. 그 다음, 위에 4 알고리즘을 CipherText에 적용한다. 비트크기에 따라 반복하는 수가 다르다. AES-128같은 경우는 9번, AES-192는 11번, 그리고 AES-256은 13번 반복한다.

4 알고리즘을 적용후, 마지막으로 S-Box, ShiftRows, 그리고 AddRoundKey를 적용한다.

3.1 레인달 알고리즘

3.1.1 SubBytes

바이트들을 S-Box (Substitution Box)에 있는 바이트들과 바꾸는 부분이다.

그 S-Box는 이렇게 생겼다.

---	00	01	02	03	04	05	06	07	08	09	0A	0B	0C	0D	0E	0F
00	0x63	0x7C	0x77	0x7B	0xF2	0x6B	0x6F	0xC5	0x30	0x01	0x67	0x2B	0xFE	0xD7	0xAB	0x76
10	0xCA	0x82	0xC9	0x7D	0xFA	0x59	0x47	0xF0	0xAD	0xD4	0xA2	0xAF	0x9C	0xA4	0x72	0xC0
20	0xB7	0xFD	0x93	0x26	0x36	0x3F	0xF7	0xCC	0x34	0xA5	0xE5	0xF1	0x71	0xD8	0x31	0x15
30	0x04	0xC7	0x23	0xC3	0x18	0x96	0x05	0x9A	0x07	0x12	0x80	0xE2	0xEB	0x27	0xB2	0x75
40	0x09	0x83	0x2C	0x1A	0x1B	0x6E	0x5A	0xA0	0x52	0x3B	0xD6	0xB3	0x29	0xE3	0x2F	0x84
50	0x53	0xD1	0x00	0xED	0x20	0xFC	0xB1	0x5B	0x6A	0xCB	0xBE	0x39	0x4A	0x4C	0x58	0xCF
60	0xD0	0xEF	0xAA	0xFB	0x43	0x4D	0x33	0x85	0x45	0xF9	0x02	0x7F	0x50	0x3C	0x9F	0xA8
70	0x51	0xA3	0x40	0x8F	0x92	0x9D	0x38	0xF5	0xBC	0xB6	0xDA	0x21	0x10	0xFF	0xF3	0xD2
80	0xCD	0x0C	0x13	0xEC	0x5F	0x97	0x44	0x17	0xC4	0xA7	0x7E	0x3D	0x64	0x5D	0x19	0x73
90	0x60	0x81	0x4F	0xDC	0x22	0x2A	0x90	0x88	0x46	0xEE	0xB8	0x14	0xDE	0x5E	0x0B	0xDB
A0	0xE0	0x32	0x3A	0x0A	0x49	0x06	0x24	0x5C	0xC2	0xd3	0xAC	0x62	0x91	0x95	0xE4	0x79
B0	0xE7	0xC8	0x37	0x6D	0x8D	0xD5	0x4E	0xA9	0x6C	0x56	0xF4	0xEA	0x65	0x7A	0xAE	0x08
C0	0xBA	0x78	0x25	0x2E	0x1C	0xA6	0xB4	0xC6	0xE8	0xdD	0x74	0x1F	0x4B	0xBD	0x8B	0x8A
D0	0x70	0x3E	0xB5	0x66	0x48	0x03	0xF6	0x0E	0x61	0x35	0x57	0xB9	0x86	0xC1	0x1D	0x9E
E0	0xE1	0xF8	0x98	0x11	0x69	0xD9	0x8E	0x94	0x9B	0x1E	0x87	0xE9	0xCE	0x55	0x28	0xDF
F0	0x8C	0xA1	0x89	0x0D	0xBF	0xE6	0x42	0x68	0x41	0x99	0x2D	0x0F	0xB0	0x54	0xBB	0x16

맨 윗쪽 행과, 첫번재 열은 단순히 쉽게 읽게 하기 위해 있는 숫자들이므로, 햇갈리지 말자.

예를 들어, 0x4C를 S-Box에서 바꾸면, 0x29가 되겠다.

3.1.2 InvSubBytes

이 부분은, 위에 SubBytes 와 같지만, 이 알고리즘은 복호화를 할때 사용된다.

Inv S-Box는 이렇게 생겼다.

---	00	01	02	03	04	05	06	07	08	09	0A	0B	0C	0D	0E	0F
00	0x52	0x09	0x6A	0xD5	0x30	0x36	0xA5	0x38	0xBF	0x40	0xA3	0x9E	0x81	0xF3	0xD7	0xFB
10	0x7C	0xE3	0x39	0x82	0x9B	0x2F	0xFF	0x87	0x34	0x8E	0x43	0x44	0xC4	0xDE	0xE9	0xCB
20	0x54	0x7B	0x94	0x32	0xA6	0xC2	0x23	0x3D	0xEE	0x4C	0x95	0x0B	0x42	0xFA	0xC3	0x4E
30	0x08	0x2E	0xA1	0x66	0x28	0xD9	0x24	0xB2	0x76	0x5B	0xA2	0x49	0x6D	0x8B	0xD1	0x25
40	0x72	0xF8	0xF6	0x64	0x86	0x68	0x98	0x16	0xD4	0xA4	0x5C	0xCC	0x5D	0x65	0xB6	0x92
50	0x6C	0x70	0x48	0x50	0xFD	0xED	0xB9	0xDA	0x5E	0x15	0x46	0x57	0xA7	0x8D	0x9D	0x84
60	0x90	0xD8	0xAB	0x00	0x8C	0xBC	0xD3	0x0A	0xF7	0xE4	0x58	0x05	0xB8	0xB3	0x45	0x06
70	0xD0	0x2C	0x1E	0x8F	0xCA	0x3F	0x0F	0x02	0xC1	0xAF	0xBD	0x03	0x01	0x13	0x8A	0x6B
80	0x3A	0x91	0x11	0x41	0x4F	0x67	0xDC	0xEA	0x97	0xF2	0xCF	0xCE	0xF0	0xB4	0xE6	0x73
90	0x96	0xAC	0x74	0x22	0xE7	0xAD	0x35	0x85	0xE2	0xF9	0x37	0xE8	0x1C	0x75	0xDF	0x6E
A0	0x47	0xF1	0x1A	0x71	0x1D	0x29	0xC5	0x89	0x6F	0xB7	0x62	0x0E	0xAA	0x18	0xBE	0x1B
B0	0xFC	0x56	0x3E	0x4B	0xC6	0xD2	0x79	0x20	0x9A	0xDB	0xC0	0xFE	0x78	0xCD	0x5A	0xF4
C0	0x1F	0xDD	0xA8	0x33	0x88	0x07	0xC7	0x31	0xB1	0x12	0x10	0x59	0x27	0x80	0xEC	0x5F
D0	0x60	0x51	0x7F	0xA9	0x19	0xB5	0x4A	0x0D	0x2D	0xE5	0x7A	0x9F	0x93	0xC9	0x9C	0xEF
E0	0xA0	0xE0	0x3B	0x4D	0xAE	0x2A	0xF5	0xB0	0xC8	0xEB	0xBB	0x3C	0x83	0x53	0x99	0x61
F0	0x17	0x2B	0x04	0x7E	0xBA	0x77	0xD6	0x26	0xE1	0x69	0x14	0x63	0x55	0x21	0x0C	0x7D

맨 윗쪽 행과, 첫번재 열은 단순히 쉽게 읽게 하기 위해 있는 숫자들이므로, 햇갈리지 말자.

반대로, 0x29를 복호화 하면, 0x4C가 나온다.

3.1.3 ShiftRows

바이트의 행을 뒤집는 부분이다.

0x00	0x01	0x02	0x03
0x04	0x05	0x06	0x07
0x08	0x09	0x0A	0x0B
0x0C	0x0D	0x0E	0x0F

이런 식으로, 바이트가 있다면,

0x00	0x01	0x02	0x03
0x05	0x06	0x07	0x04
0x0A	0x0B	0x08	0x09
0x0F	0x0C	0x0D	0x0E

이런 식으로 바뀐다.
먼저, 첫번째 줄은 아무런 변화가 없다.
두번째줄에서는, 왼쪽으로 한칸이 밀렸다.
세번째줄은 왼쪽으로 두칸이 밀렸다.
네번째줄은 왼쪽으로 세칸이 밀렸다.

여기서, 조심할것이 있다. 128비트, 192 비트, 또는 256 비트에 따라 열의 숫자가 달라진다.

3.1.4 InvShiftRows

Inverse Shift Rows. 이 스테이지도 복호화 할때 사용된다.

0x00	0x01	0x02	0x03
0x05	0x06	0x07	0x04
0x0A	0x0B	0x08	0x09
0x0F	0x0C	0x0D	0x0E

이런식의 바이트들을

0x00	0x01	0x02	0x03
0x04	0x05	0x06	0x07
0x08	0x09	0x0A	0x0B
0x0C	0x0D	0x0E	0x0F

이런식으로 다시 돌려두는것이다.

첫번째줄은 ShiftRows 스테이지에서 그런것 처럼 아무런 변화가 없다.
두번째줄은 왼쪽으로 3번 민다.
세번째줄은 왼쪽으로 2번 밀렸다.
네번째줄은 왼쪽으로 1번 밀면 된다.

3.1.5 MixColumns

이 단계에서는, 특수한 공식이 사용된다.

a0 * [2 3 1 1] = r0
a1 * [1 2 3 1] = r1
a2 * [1 1 2 3] = r2
a3 * [3 1 1 2] = r3

여기서 r값들을 구하려면, 이런 식으로 해야한다.

r0 = (a0 * 2) + (a1 * 3) + (a2 * 1) + (a3 * 1).
r1 = (a0 * 1) + (a1 * 2) + (a2 * 3) + (a3 * 1).
r2 = (a0 * 1) + (a1 * 1) + (a2 * 2) + (a3 * 3).
r3 = (a0 * 3) + (a1 * 1) + (a2 * 1) + (a3 * 2).

근데, 여기서 곱하기는 절대로 초등학교 수학에서나 나오던 곱하기가 아니다. Exclusive-OR(XOR)을 특별하게 사용해야 한다.

C언어로 표현하면 이렇게 된다.

<syntaxhighlight lang="cpp" line="1">
typedef unsigned char byte;
void rijndael_mixcolumn (byte * data, size_t data_len) {
if ((data_len % 4) != 0)
return;

for (size_t i = 0 ; i < data_len ; i += 4) {
byte copy_arr [4], res [4];

memcpy (copy_arr, data + i, 4);

res [0] = (data [0 + i] << 1) ^ (0x1B & ((byte) ((signed char) data [0 + i] >> 7)));
res [1] = (data [1 + i] << 1) ^ (0x1B & ((byte) ((signed char) data [1 + i] >> 7)));
res [2] = (data [2 + i] << 1) ^ (0x1B & ((byte) ((signed char) data [2 + i] >> 7)));
res [3] = (data [3 + i] << 1) ^ (0x1B & ((byte) ((signed char) data [3 + i] >> 7)));

data [0 + i] = res [0] ^ copy_arr [3] ^ copy_arr [2] ^ res [1] ^ copy_arr [1];
data [1 + i] = res [1] ^ copy_arr [0] ^ copy_arr [3] ^ res [2] ^ copy_arr [2];
data [2 + i] = res [2] ^ copy_arr [1] ^ copy_arr [0] ^ res [3] ^ copy_arr [3];
data [3 + i] = res [3] ^ copy_arr [2] ^ copy_arr [1] ^ res [0] ^ copy_arr [0];
}
}
</syntaxhighlight>

이 과정을 미리 계산해서 Table-lookup에 저장해 놓고 계산하는 방법도 있으며, 모든 AES 최적화에는 이러한 Table-lookup방식을 적용한다.^[6]

3.1.6 InvMixColumns

Inverse Mix Columns. 이 부분은, MixColumns와 흡사하나, InvMixColumns는 Inverse Substitution Box와 마찬가지로, 복호화 할때 사용된다.

공식:
a0 * [14 11 14 9] = r0
a1 * [9 14 11 13] = r1
a2 * [13 9 14 11] = r2
a3 * [11 13 9 14] = r3

3.1.7 AddRoundKey

이 단계는 다른 단계와는 비해 간단하다. 비트 연산자인, XOR연산자를 사용하면된다. ^[7]
예를 들어, 0x0A ⊕ 0x03 같은 경우에는, 0x09다.

먼저, 0x0A, 즉 10을 이진수로 바꾸면 1010이고, 0x03를 이진수로 바꾸면 0011 이다.
이 두 숫자에 XOR에 적용할때, 서로 다른 값일경우 1이되고, 같은 값이면 0이 된다.
먼저, 10의 이진수의 첫번째 숫자는 1이고, 0x03의 첫번째 숫자는 0이다. 이 둘을 XOR으로 처리하면 1이 나온다.
0x0A의 두번째 숫자는 0, 0x03의 두번째 숫자는 0이다. 서로 같기때문에 0 이다.
0x0A의 세번째 숫자는 1, 0x03의 세번째는 1이다. 즉, 0이 된다.

그렇게 계산을 하면 1001이 나온다. 이것을 16진수로 바꾸면 0x09가 나온다.

복호화에서도 똑같이 XOR을 사용한다. 기본적으로, XOR만으로도 암호화가 가능하다. 하지만, 쉽게 뚫리기에 XOR만 가지고는 안하고 이렇게 다른 알고리즘과 섞어서 사용한다.

3.2 그외 필요한 스테이지

3.2.1 BASE64

BASE64와 AES간에는 하등의 관계가 없다.
BASE64는 인코딩하는 방식의 하나일뿐 AES는 어떤 인코딩이든 암호화 할 수 있다.
~~암호화후, 복호화전에 BASE64로 엔코딩과 디코딩을 해야하는듯 하다.~~
~~BASE64는 Rijndael Cipher와 관련이 없다..~~

3.2.2 PKCS7 / PKCS5 Padding

이 스테이지는 암호화 전, 그리고 복호화 후에 사용한다.
좀더 정확히는 BASE64 엔코딩후, 디코딩 전에 한다. ^[8]
이 스테이지도 Rijndael Cipher와 관련이 없다.

PKCS7같은 경우는, BASE64로 엔코딩 후, 또는 디코딩 전에 처리한다.

01 02 03 04 05 06 07 08	01 02 03 04 05

같은 바이트가 있다. 이 바이트 들을

01 02 03 04 05 06 07 08	01 02 03 04 05 03 03 03

같이 수정한다.

위와 같이 블록 크기가 8인 데이터들이 있다.
마지막에는 데이터가 5 밖에 없다. 거기에다가 블록 크기가 8이기에, 뒤에 3바이트가 더 있어야 한다.
PKCS7 패딩은 뒤에 필요한 바이트 만큼의 크기의 바이트들을 넣는것이다.

4 특징

128-bit, 192-bit, 그리고 256-bit 키 길이로 처리한다.

128 비트일경우, 10 번 (마지막 라운드 함수를 포함하여) 라운드를 돌려 암호화 하고, 192 비트는 12번을 돌고, 256 비트 일경우, 14 번을 돈다.

S-Box를 간단히 설명하자면 입력 데이터를 지정된 숫자로 바꿔서 암호를 깨기 어렵게 만드는 기법이다. AES는 이걸 창조롭게 재발명하여 암호화 속도를 높이고 싶으면 S-Box를 메모리에 박아놓고, 프로그램 메모리 양을 줄이려면 실행시 S-Box를 연산으로 구해내는 기법을 사용했다. 입맛에 따라 고를 수 있게. (..)

4.1 프로그래밍 언어 API

자바 API에 java.security 패키지와, javax.crypto 패키지를 사용하여 AES 암호화를 사용할 수 있다 ~~뭐, 자바는 API자체 크기가 크고 아름다우니.~~ ^[9]. 여기를 참고하면 될 듯하다.

C/C++ 같은 경우는, 기본 라이브러리에는 없는 듯 하다 ^[10]. 3rd Party Software나, 다른 API는 구글에 검색만 해도 다 나오니 필요하면 검색해 보자.

PHP 언어도 지원하는 듯 하다. 자바와 마찬가지로, 여기를 참고하면 될 듯하다.

C#은 지원한다. System.Security.Cryptography 네임스페이스와 System.Security.Cryptography.Aes 클래스를 사용하면 된다. 설명은 이곳을 참고하면 된다.

Python은 외부 라이브러리를 통해 지원한다. Crypto 모듈에서 지원한다. 이 곳을 참고하자.

Go 언어는 지원한다. "crypto/aes" 패키지를 이용하면 된다.

Assembly언어는 딱히 라이브러리나, API가 있는것이 아니고, CPU가 인식 할 수 있는 명령어인 기계어를 특정 규칙에 따라서 1:1로 매칭시킨 것이기에 없다.
단, 예외로 Intel x86 계열 CPU 의 경우 데스크탑 제품군은 샌디브릿지부터 AES-NI 라는 확장 명령어셋을 지원한다. AES 연산을 하드웨어 가속시킨 것이다.

4.2 안전성

미국 정부가 채택하여 기밀문서를 암호화를 했다. 즉, 정부가 믿을 정도라는 것이다. 그러나, 몇번은 공격을 받은듯 하다. 솔직히 AES의 알고리즘은 은근히 간단한 수학 공식이다. 암호화하는 게 쉽다고 깨는게 쉬운 건 아니지만 말이다. 물론 절대로 프로그램이나, 암호화를 공격하여 해킹을 막는 방법은 절대로 존재하지 않았고, 존재하지 않고, 앞으로도 존재할수가 없다. 다만, 공격을 하는 시간을 늘리고, 더 까다롭게 하는 것 밖에 못한다. 그러나 아직은 AES가 최강의 암호화 이고, 당장은 키없이 해독하는것을 거의 불가능하다고 믿어지고 있다. 심지어, 다른 최신 cipher 와 마찬가지로, known-plaintext 해킹기술로도 해독이 불가능 하다고 한다. ~~물론 NSA가 깼는지 여부는 알 수 없고 한 15년쯤 지나면 밝혀지겠지~~

5 기타

Rijndael은 AES를 만든 암호학자 이름에서 따온 것이라고 한다.

AES의 과정을 쉽게 설명하고 보여주는 동영상.

AES에 대해 설명해주는 만화. ~~물론 영어다.~~

↑ 아직까지 보안적 안전성의 기준은 DES를 3번 사용하는 TDES가 그 기준이지만(112비트), AES가 너무 잘만들어져서 사실상 128비트로 굳어버렸을 정도이다.
↑ DES는 몇몇 수퍼 컴퓨터에 의하여 더이상 안전하지 않다는 결과가 나왔다. 거의 하루 정도의 시간을 소모하여 DES로 암호화 된 데이터를 얻었고, 이제는 DES암호화를 해킹하는 칩도 나왔다. 물론, 비싸다(...)
↑ 이 행사때 후보에 들어간 암호화 알고리즘은 15개가 된다.
↑ 암호화 알고리즘들은 MARS, RC6, Rijndael(레인달), Serpent, Twofish 였다.
↑ 암호화 알고리즘 후보는 보안성이 좋아야 했었고, 비용도 적게 들고, 유연하면서 간단해야 했다. Rijndael이 뽑힌 이유는 다른 암호화 알고리즘이 안 좋아서가 아니다. 다른 알고리즘도 좋기는 하나, 레인달이 유난히 더 좋아서라고 카더라.
↑ 이는 당연히 소프트웨어적인 최적화로, 하드웨어에서의 최적화 방식과는 다르다. 대부분의 암호 알고리즘의 최적화에서 입력값에 따라 출력값의 연산을 수행하는 것이 아니라, 테이블에서 불러오는 방식으로 적용가능하다.
↑ XOR은 CPU가 지원하는 명령어다.
↑ 어떤 Cipher를 사용하느냐에 따라 다를수 있다.
↑ JSP는 웹서버 스크립트가 자바이기 때문에 당연히 지원한다.
↑ C/C++ 언어의 기본 라이브러리는 기초적인 것만 있다. 절대 그 이상이 있는 건 존재하지 않는다.

[1] 아직까지 보안적 안전성의 기준은 DES를 3번 사용하는 TDES가 그 기준이지만(112비트), AES가 너무 잘만들어져서 사실상 128비트로 굳어버렸을 정도이다.

[2] DES는 몇몇 수퍼 컴퓨터에 의하여 더이상 안전하지 않다는 결과가 나왔다. 거의 하루 정도의 시간을 소모하여 DES로 암호화 된 데이터를 얻었고, 이제는 DES암호화를 해킹하는 칩도 나왔다. 물론, 비싸다(...)

[3] 이 행사때 후보에 들어간 암호화 알고리즘은 15개가 된다.

[4] 암호화 알고리즘들은 MARS, RC6, Rijndael(레인달), Serpent, Twofish 였다.

[5] 암호화 알고리즘 후보는 보안성이 좋아야 했었고, 비용도 적게 들고, 유연하면서 간단해야 했다. Rijndael이 뽑힌 이유는 다른 암호화 알고리즘이 안 좋아서가 아니다. 다른 알고리즘도 좋기는 하나, 레인달이 유난히 더 좋아서라고 카더라.

[6] 이는 당연히 소프트웨어적인 최적화로, 하드웨어에서의 최적화 방식과는 다르다. 대부분의 암호 알고리즘의 최적화에서 입력값에 따라 출력값의 연산을 수행하는 것이 아니라, 테이블에서 불러오는 방식으로 적용가능하다.

[7] XOR은 CPU가 지원하는 명령어다.

[8] 어떤 Cipher를 사용하느냐에 따라 다를수 있다.

[9] JSP는 웹서버 스크립트가 자바이기 때문에 당연히 지원한다.

[10] C/C++ 언어의 기본 라이브러리는 기초적인 것만 있다. 절대 그 이상이 있는 건 존재하지 않는다.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]