전자상거래 보안 (암호학과 네트워크보안) 207.4.12 Chul Ho Rhee richman3@naver.com

AES (Advanced Encryption Standard) 2

AES 암호 알고리즘 AES의 개요 AES 는 2001년 미국 국립기술 표준원(NIST) 에서 공표한 대칭 키 암호 알고리즘이다. AES는 128 비트 평문을 128 비트 암호문으로 만드는 알고리즘이다. AES는 128, 192, 256 비트의 암호 키를 사용하고 키 크기에 따라 각각 10, 12, 14 라운드를 갖는 3 가지 버전이 있다. 암호 키의 크기가 달라도 라운드 키는 모두 128 비트이다. 라운드 키 수는 라운드 수보다 하나 더 많다.  라운드 키의 수 = Nr + 1 ( Nr : 라운드 수) 3

AES 암호 알고리즘 AES의 개념도 4

AES 암호 알고리즘 라운드 함수 AES는 마지막 라운드를 제외한 각 라운드에서 4개의 변환을 사용한다  SubBytes  ShiftRows  MixColumns  AddRoundKey 라운드 함수에 적용되기 전에 AddRoundKey 변환을 적용한다 마지막 라운드에서는 3개의 변환만 사용한다(MixColumns 제외) 5

AES 암호 알고리즘 라운드 함수 AES 라운드의 각 변환은 하나의 스테이트를 입력 으로 받아서 다른 스테이트 를 생성한다 6

AES 암호 알고리즘 데이터 단위 바이트(Byte) 워드(Word)  4 바이트 블록(Block)  16 바이트  16 바이트 스테이트(State)  16 바이트  4 × 4 행렬  Src (r: 행, c: 열) 7

AES 암호 알고리즘 라운드 함수 8

AES 암호 라운드의 변환 바이트 치환 변환(Substitute Bytes Trans.) SubBytes는 AES의 암호화 과정에서 사용되는 치환함수이다. 각 바이트를 4 비트씩 2개의 16진수로 계산하여 왼쪽 4비트를 S-박스 의 행을, 오른쪽 4비트를 열을 지정하여 테이블을 읽는다. 16번의 변환이 일어난다 9

AES 암호 라운드의 변환 바이트 치환 변환(SubBytes) 두 개의 바이트 (5A)16 과 (5B)16은 1개 비트만 다르지만, SubBytes 변환으로 (BE)16 과 (39)16 으로 변환되어 4개 비트가 달라진다 10

AES 암호 라운드의 변환 바이트 치환 변환(SubBytes) 평문의 입력 블럭을 SubBytes 변환으로 처리한 후, InvSubBytes 를 통해서 원래의 값으로 복원할 수 있다. 17 F0 11

AES 암호 라운드의 변환 열 혼합변환(MixColumns) 열 단위로 4개 바이트에 대하여 상수 정방행렬과 연산하여 각 바이트내의 비트들을 서로 섞어 새로운 바이트를 생성한다. 상수행렬 12

AES 암호 라운드의 변환 열 혼합변환(MixColumns) 다음은 열 단위로 4개 바이트에 대하여 16진수 상수 정방행렬과 연산하는 방법이다  16진수 곱셈을 의미한다 13

AES 암호 라운드의 변환 다항식 표현 8-비트 10011001 값을 다항식으로 다음과 같이 표현할 수 있다 14

AES 암호 라운드의 변환 다항식 표현 다항식 x + x + x 을 8-비트 워드로 만들어 보자 8-비트 워드로 표현되는 다항식의 최고 차수는 7 이고, 생략된 항들을 채워 넣는다. 이것은 8-bit 워드인 0010 0110 를 나타내는 다항식이 된다 5 2 15

AES 암호 라운드의 변환 다항식 덧셈 AES 에서의 산술연산은 갈로아체 GF(2)와 GF(2 ) 상에서 이루어 진다  즉, mod 2 연산으로 수행된다. 다항식의 지수들간의 연산은 GF(2 ) 상에서 이루어진다  GF(2 ) 상에서 다항식은 다음과 같이 나타낸다.  GF(2 ) 상에서 (x + x + x + x + 1) 를 기약다항식으로 사용한다. AES 에서 다항식간의 곱셈연산에서 차수가 8 차 이상이 나오면 기약다항식으로 나눈 후, 그 나머지를 사용한다 8 n 8 8 8 4 3 16

AES 암호 라운드의 변환 다항식 덧셈 GF(2), GF(2 ) 상에서 (x + x + x) ⊕ (x + x + 1) 를 계산해보자. 여기서 사용한 연산 기호 ⊕ 는 다항식의 덧셈을 의미한다. 덧셈은 exclusive-or (XOR)으로 연산한다. 계수에 대한 연산 결과는 유한체 GF(2) 의 원소 집합 {0,1} 중의 하나가 된다. ☞ mod 2 연산이 수행된다. 8 5 2 3 2 17

AES 암호 라운드의 변환 다항식 곱셈 기약다항식 (x + x + x + x + 1) 을 갖는 GF(2 ) 에서 (x + x + x) ⊗ (x + x + x + x + x) 를 계산해 보자. 여기서 사용한 연산기호 ⊗ 은 두 다항식의 곱셈을 의미한다. 다항식의 곱셈은 첫째 다항식의 각 항과 두 번째 각 항의 곱셈의 합이다 같은 차수의 항은 삭제한다 ☞ 덧셈은 exclusive-or (XOR) 연산결과가 8차식 이상인 경우 기약다항식으로 나누어 나머지를 결과 값으로 한다 8 4 3 8 5 2 7 4 3 2 18

AES 암호 라운드의 변환 다항식 곱셈 곱셈결과를 기약다항식으로 나누는 과정은 일반 나눗셈과 같지만 뺄셈을 할 때 덧셈으로 처리한다.  계수에 대한 연산 결과는 유한체 GF(2) 의 원소 집합 {0,1} 중의 하나가 되어야 하므로, 계수의 연산결과를 mod 2 연산으로 처리 함  GF(2) 상에서 덧셈과 뺄셈은 동일하다.  1 + 1= 1−1 = 0; 1 + 0 = 1−0 = 1 19

AES 암호 라운드의 변환 다항식 곱셈 (x + x + x) ⊗ (x + x + x + x + x) 의 계산을 컴퓨터로 구현할 때는 x ⊗ P2 연산을 (x ⊗ (x ⊗ P2 ) 와 같이 나누어 연산하는 게 효율적이다. x, x 은 곱셈 연산한 후 기약다항식으로 나누어 나머지만 취한다. 5 2 7 4 3 2 2 1 7 20

AES 암호 라운드의 변환 열 혼합변환 연산처리법 r0 =(02 • d4) + (03 • bf) + (01 • 5d) + (01 • 30) 02=0010 , d4=11010100 이므로 02 = x 이고 d4 = x + x + x + x (02 • d4) = ( x ⊗ (x + x + x + x ) = x + x + x + x (03 • bf) = (x + 1) ⊗ (x + x + x + x + x + x +1 ) = x + x + x + x + x + x + x + x + x + x + x + x + x + 1= x + x +x + 1 (02 • d4) + (03 • bf) = x + x + x + 1 7 6 4 2 8 5 3 21

AES 암호 라운드의 변환 열 혼합변환 연산처리법 (02•d4)+(03•bf) = x + x + x + 1 r0 =(02•d4)+(03•bf) + (01•5d)+(01•30) (02•d4)+(03•bf) = x + x + x + 1 (01•5d)+(01•30)= x + x + x + x + 1 + x + x = x + x + x + x +1 r0 = x ☞ 0000 0100 r0 = 04 (16진수) 6 5 3 6 4 3 2 5 4 6 5 3 2 2 22

AES 암호 라운드의 변환 라운드 키 더하기 변환(AddRoundKey) 각 스테이트 열 행렬에 라운드 키의 대응하는 워드를 논리합 연산(⊕) 을 한다. ⊕ 23

AES 암호 라운드의 변환 라운드 키 더하기 변환(AddRoundKey) 각 스테이트 열 행렬에 라운드 키의 대응하는 워드를 논리합 연산(⊕) 을 한다. 47 40 A3 4C 37 D4 70 9F 94 E4 3A 42 ED A5 A6 BC AC 19 28 57 77 FA D1 5C 66 DC 29 00 F3 21 41 6A EB 59 8B 1B 40 2E A1 C3 F2 38 13 42 1E 84 E7 D6 ⊕ = State Round Key Add Round Key 결과 24

AES 암호의 키 확장(Expansion) 25

AES 암호의 키 확장 AES-128의 키 확장 암호 키는 k0 ~ k15 까지 구성된다. 처음 W0, W1, W2, W3 등 4 개의 워드는 암호 키로부터 생성된다 W0 는 k0 에서 k3 까지 구성되고, W1 은 그 다음 4 바이트로 구성된다. 나머지 워드(Wi , 4 ≦Wi ≦ 43) 들은 다음과 같이 계산한다.  i mod 4 ≠ 0 일 경우, W i = W i-1 ⊕ W i-4 로 계산한다  i mod 4 = 0 일 경우, W i = t i ⊕ W i -4 로 계산한다  t i = SubWord( RotWord (W i-1 )) ⊕ Rcon i/4 26

AES 암호의 키 확장 27

AES 암호의 키 확장 AES-128의 키 확장 t i = SubWord( RotWord (W i-1 )) ⊕ Rcon i/4  4개의 바이트를 한 바이트씩 왼쪽으로 이동시킨다 SubWord  SubBytes 와 유사하게 S-박스 이용하여 치환한다 Rcon(라운드 상수)  각 라운드 상수 RCon은 4 바이트이다 28

AES 암호의 키 확장 AES-128의 키 확장 라운드 상수 Rcon (4바이트)  오른쪽 3 바이트는 모두 0 이다 29

AES 암호의 키 확장 AES-128의 키 확장 16 바이트 암호키(24 75 A2 B3 34 75 56 88 31 E2 12 00 13 AA 54 87)16 를 이용하여 t4 의 값을 구해보자 t i = SubWord( RotWord (W i-1 )) ⊕ Rcon i/4 RotWord(13 AA 54 87) = AA 54 87 13 ☞ SubWord(AA 54 87 13) = AC 20 17 7D ☞ t4 = AC20177D ⊕ RCon 1 = AC20177D⊕(01000000)16 = AD20177D k0 k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12 k13 k14 k15 2 4 7 5 A 2 B 3 3 4 7 5 5 6 8 8 3 1 E 2 1 2 1 3 A 5 4 8 7 w0 w1 w2 w3 1 바이트 이동 S-Box 처리결과 1 1 1 1 ⊕ 1 1 0 1 0 1 1 0 1 30

AES 암호의 키 확장 AES-128의 키 확장 31

AES 의 암호 및 복호 암호 및 복호 처리 32

블록암호 운용모드 33

강의목차 블록암호 운영모드(긴 메시지 암호기법) ECB(Electronic Code Book) CBC(Cipher Block Chaining) CFB(Cipher Feedback) OFB(Ouput Feedback) CTR(Counter) 스트림 암호 RC4 34 34

블록암호 운영모드 현대 블록암호의 사용 현대 블록암호인 DES와 AES는 고정길이(8바이트, 16바이트) 의 평문 블록을 암호 및 복호 한다. 그러나 실제 운용환경에서는 평문의 길이가 무척 길고 가변적이다. 이에 임의의 길이의 평문을 암호화하는 방법인 운영모드가 필요하다 35

블록암호 운영모드 ECB(Electronic Codebook) 방식 운영 모드 중에서 가장 간단한 모드이다. 평문 크기가 블록 크기의 배수가 아니면 마지막 블록에 패딩을 한다 긴 평문을 64비트씩 n개의 블록(m1, m2, m3,…, mn)으로 나눈다 . 각 블록별로 동일한 키에 의해 독립적으로 암호화가 이루어진다 • 암호화 : C = E K (m i ) i = 1, 2, 3, …. n • 복호화 : m = D K (c i ) i = 1, 2, 3,…. n 동일한 평문 블록은 동일한 암호문으로 암호된다. 36

블록암호 운영모드 ECB 방식의 처리구조도 37

블록암호 운영모드 ECB 방식의 안전성 각 블록이 독립적으로 암호 및 복호가 이루어지므로 암호 및 복호 처리시간이 빠르다 • 병렬처리가 가능 블록간의 독립성으로 블록단위의 패턴이 유지된다. 평문에서 같은 값을 갖는 블록은 대응하는 암호문 블록도 동일하다 •암호문에서 1, 5, 10번째 블록 값이 동일하다면, 평문의 1, 5, 10 번째 블록도 같다. 38

블록암호 운영모드 ECB 방식의 안전성 블록간의 독립성으로 Eve(해커)는 키를 알지 못하더라도 특정암호 블록을 변조할 수 있다. • Eve가 평문에서 8번 째 블록에 항상 특정 정보(예, 급여정보)를 포함 하고 있다는 사실을 안다면, 이전에 가로챈 암호문의 8번째 블록으로 이 블록을 대체할 수 있다. 임의의 한 블록에 에러가 발생하는 경우 다른 블록으로 에러파급 (Error Propagation)이 일어 나지 않는다. 39

블록암호 운영모드 ECB 방식의 응용 데이터 베이스의 레코드를 암호하거나 복호하는 분야에 유용하다 레코드를 암호하고 복호하는데 다른 레코드와 처리순서에 관계없이 독립적으로 처리할 수 있기 때문 40

CBC(Cipher Block Chaining) 방식 블록암호 운영모드 CBC(Cipher Block Chaining) 방식 CBC 모드에서 각각의 평문 블록은 암호화되기 전에 이전 블록의 암호문과 XOR된다. 암호화된 블록은 전송된 후, 다음 블록의 암호화에 사용되기 위해서 메모리에 저장되어야 한다. 첫 번째 블록을 암호화하기 위해 초기벡터(IV) 값이 필요하다. 초기벡터(IV) 값은 송신자와 수신자가 사전에 공유한다. • 암호화 : C i = E k (m i ⊕ C i -1), i = 1, 2, 3, 4,… n • 복호화 : m i = D k (c i ) ⊕ C i -1 ; IV (= C0 ) 41

블록암호 운영모드 CBC 방식의 처리구조도 42

블록암호 운영모드 CBC 방식의 안전성 평문의 동일한 블록들은 암호문에서 서로 다른 블록으로 암호화 된다 ☞ 암호 시 전 단계의 암호블록을 이용하기 때문 CBC 모드에서 암호문 블록 C j 가 전송도중 한 비트가 오류가 발생하면 복호시 어떤 영향을 미칠까? • 복호 과정에서 평문 블록 P j 의 대부분 블록에서 오류가 발생한다. • 평문 블록 Pj+1 에서는 C j 블록의 같은 위치에서 한 비트 오류가 발생 한다 • Pj+2 부터 PN 까지의 평문 블록은 에러에 아무런 영향을 받지 않는다. 43

블록암호 운영모드 CBC 방식의 응용 암호화는 직렬처리만 가능하고, 복호화는 병렬처리가 가능하다. 44

Thanks Chul Ho Rhee richman3@naver.com 45