제 6 장대칭암호알고리즘 : AES 6.1 AES 6.1.1 AES 개요 1977년도에미국표준으로제정된 DES는지금까지큰허점이발견되지않았지만키길이가 56비트밖에되지않아현재의컴퓨팅기술로는쉽게전사공격을하여암호해독을할수있다. 따라서 1997년에새표준에대한작업을시작하여 2000년 10월에 AES(Advanced Encryption Standard) 라는새표준을채택하였다. 1997년새표준에대한제안에의하면새암호알고리즘의블록크기는 128비트이어야하며, 알고리즘에대한변경없이 128비트, 196비트, 256비트길이의키를지원해야한다. 1998년도에제출된여러제안중에 15개를일차적으로선정하였고, 1999년에이중에다섯개를최종후보로선정하였다. 이중에벨기에암호학자인 Daemen과 Rijmen이제안한 Rijndael 암호알고리즘이 AES로채택되었다. 채택된 Rijndael 알고리즘은기존표준인 DES와달리 Feistel 구조가아니었으며, 제안에서요구한사항뿐만아니라블록크기를 192비트, 256비트로확장할수있도록되어있었다. 하지만제안에서요구한 128비트블록크기버전만표준으로채택되었다. Rijndael 암호알고리즘의라운드수는블록크기와키길이에의해다음과같이결정된다. 가암호블록의크기에대한 32비트워드의수이고, 가암호키길이에대한 32비트워드의수이면라운드의수 이다. 표준으로채택된블록의길이는 128비트이므로 이며, 128비트, 192비트, 256비트세가지종류의키길이를지원하므로 이다. 따라서블록크기가 128비트이고, 키길이가 128비트이면 이된다. 이때암호키는 4행 2차원바이트배열로구성된것으로간주한다. 이암호키는 개의 32비트워드로확장되어사용된다. 즉, 블록크기와키길이가모두 128비트이면 128비트암호키는총 44개의 32비트워드로확장되며, 각라운드마다이중 4개의워드가사용된다. 각라운드는그림 6.1처럼하나의자리바꿈연산과세개의치환연산으로구성되어있다. 그림에서알수있듯이 AES의라운드는매우단순하다. S-박스 : 을이용한치환연산 행이동 (shift row): 단순자리바꿈 열섞음 (mix column): 을이용한치환연산 라운드키적용 (add roundkey): XOR 연산을이용 여기서 을이용한계산이란기약다항식 을사용하는다항식체를말한다. 위네가지세부연산은모두역이가능하다. 따라서라운드키를적용하는부분을제외하고는그자체만으로는어떤안전성도제공하지못한다. 다른대부분의알고리즘과마찬가지로복호화는키를역순으로사용하며, 전체알고리즘은그림 6.2와같다.
< 그림 6.1> AES 의한라운드구성도 < 그림 6.2> AES 알고리즘 그림 6.2에서알수있듯이복호화에서사용되는연산은암호화에서사용된연산의역연산이다. 앞서언급한바와같이각라운드에서사용되는모든연산은역이가능하다. 따라서그역을이용하여복호화가이루어진다.
6.1.2 상태 AES의모든연산들은상태 (state) 라고하는 2차원바이트배열에수행된다. 이상태는항상 4행으로구성되며, 각행은 바이트로구성된다. 하지만표준에서 이므로표준에서사용하는상태는항상 바이트행이된다. 128비트입력을상태로전환하는방법은그림 6.3과같다. < 그림 6.3> AES 에서입력을상태로변환하는방법 예를들어 128 비트입력이 EA835CF00445332D655D98AD8596B0C5와같으면이것의상태는그림 6.4와같다. EA 04 65 85 83 45 5D 96 5C 33 98 B0 F0 2D AD C5 < 그림 6.4> AES 의상태의예 6.1.3 S-Box 치환 암호화과정의각라운드에서가장먼저수행되는연산은 s-box 치환연산이다. 이연산은상태를구성하는각바이트를 s-box을이용하여치환한다. 두개의 s-box가있으며, 하나를전방향 s-box라하고, 다른하나를역방향 s-box라한다. 두개의 s-box은각각그림 6.5 와 6.6에기술되어있다. 두 s-box는서로역관계에있다. 즉, 특정바이트값을전방향 s-box으로치환한후에그결과를다시역방향 s-box로치환하면원래값을얻게된다. 따라서전방향 s-box는암호화할때사용되고, 역방향 s-box는복호화할때사용된다. AES에사용되는전방향 s-box는다음과같은원리에의해구성되었다. 단계 1. s-box를 00, 01,..., FF 순으로초기화한다. 단계 2. 이값들을 에서곱셈에대한역원으로매핑한다. 단, 곱셈에대한역원이없는 00은 00으로매핑한다. 단계 3. 한항의값이 이면다음과같이변형한다. 여기서주의해야할것은행렬곱셈이나덧셈모두 XOR 연산이수행된다.
예6.1) 95에해당되는 s-box의값은? 95의곱셈에대한역원은 8A이다. 그러면 은다음과같이계산된다. (10001111 01010001) 1 = (1 1 0 1 1 1 1 1 0) 1 = 1 1 = 0 이와같이계산하면결과는 01010100 = 2A가된다. S-box 는알려진공격에안전하도록설계되었으며, 가되는경우또는 가없도록설계되었다. 또한그역을취할수있도록만들었다, 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76 1 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0 2 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15 3 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75 4 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84 5 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF 6 D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8 7 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2 8 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73 9 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB A E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79 B E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08 C BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A D 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E E E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF F 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16 < 그림 6.6> AES 의전방향 s-box
0 1 2 3 4 5 6 7 8 9 A B C D E F 0 52 09 6A D5 30 36 A5 38 BF 40 A3 9E 81 F3 D7 FB 1 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CB 2 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E 3 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 25 4 72 F8 F6 64 86 68 98 16 D4 A4 5C CC 5D 65 B6 92 5 6C 70 48 50 FD ED B9 DA 5E 15 46 57 A7 8D 9D 84 6 90 D8 AB 00 8C BC D3 0A F7 E4 58 05 B8 B3 45 06 7 D0 2C 1E 8F CA 3F 0F 02 C1 AF BD 03 01 13 8A 6B 8 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 73 9 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6E A 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1B B FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4 C 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5F D 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EF E A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61 F 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7D < 그림 6.7> AES 의역방향 s-box 6.1.4 행이동자리바꿈 AES의각라운드에사용되는 4개의기본연산중나머지세연산은치환이고, 이연산만자리바꿈이다. 이연산은그림 6.8과같이이루어지며, 복호화할때에는그림 6.8과정반대로이루어진다. 이연산은자리바꿈을통해암호화과정이평문에모든비트에고루영향을주도록하기위함이다. 더욱이평문비트들이상태로전환되어열단위로연산을적용받기때문에이와같은이동이영향을분산시키는효과는매우크다. < 그림 6.8> AES 의행이동자리바꿈연산 6.1.5 열섞음치환 이연산은상태행렬을다음행렬에곱하여값을치환하게되며, 이때곱셈연산은 에서계산된다. 이계산은두가지형태로계산될수있다. 첫째는실제행렬곱셈을다음과같이하는것
이다. 이경우이와같은계산을총 16번해야한다. 둘째는입력상태의열을다음과같은 3차다항식으로생각하고 법 에서 에곱하는것이다. 이렇게하여얻어진 3차다항식의각계수는출력상태의열이된다. 예 6.2) 다음은주어진입력상태를열섞음연산에적용하였을때그결과를보여주고있다. 이예에서 이 47이되는과정을살펴보면다음과같다. 02와 87를다항식으로표현하면각각 와 와같다. 두값을법 에서곱하면그결과는 이된다. 따라서이것을다시비트로표현하면 0001 0101이된다. 그러면왜두가지방식의계산이동일한결과를얻는지살펴보면다음과같다. 계수가 인두개의 4 차다항식을법 에서곱한결과는다음과같다., 이다항식을 로나누었을때나머지를구하면다음과같다.
따라서계수가 인두개의 4차다항식을법 에서곱한결과는다음과같은행렬식으로표현이가능하다. 따라서 이면행렬식은다음과같이된다. 이과정을역하기위해서는사용된곱셈행렬의역행렬만있으면된다. 따라서복호화할때에는다음과같은행렬을사용한다. 6.1.6 AES 키스케줄링 < 그림 6.10> AED 키스케줄링알고리즘 AES는사용되는암호키의길이가 128비트이면총 44개의 32비트워드로확장되어각라운드마다 4개의 32비트워드를라운드키로사용한다. AES의키스케줄링알고리즘은그림
6.10 과같으며다음과같이진행된다. 단계 1. 128비트키를그림 4.7에기술된것처럼 4개의 32비트워드로바꾼다. 이 3개의값이첫 4개의 32비트워드가된다. 단계 2. 첫 4개의워드중마지막워드는 1 바이트왼쪽순환이동된뒤에전방향 s-box 를이용하여치환된다. 그다음에라운드상수와 XOR된다. 결과값은첫워드와 XOR되어다음 4개워드의첫워드가만들어진다. 단계 3. 이렇게만들어진첫워드와기존 4개의워드중두번째워드가 XOR되어두번째워드가만들어지고, 이결과와세번째워드가 XOR되어세번째워드가만들어지며, 마지막으로이결과와네번째워드가 XOR되어마지막워드가만들어진다. 단계 4. 단계 2부터 3을 9번수행하여각라운드키를생성한다. 참고문헌 [1] Advanced Encryption Standard (AES), Federal Information Processing Standards Publication 197, Nov. 2001.