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

암호용어와 개념 암호용어 암호 알고리즘 설계기준 •암호 해독비용이 암호화된 정보의 가치 초과 •암호 해독시간이 정보의 유효 기간 초과 커코프(Kerckhoff) 의 원리 •암호문의 안전성은 암호 및 복호 알고리즘의 비공개에 달려 있는 것 이 아니라, 키의 비밀성에 달려있어야 한다 •키를 추측하는 것이 거의 불가능토록 하여 암호 및 복호 알고리즘을 비공개로 할 필요가 없어야 한다. 2

단일문자 암호 곱셈암호 P C 곱셈암호의 암호화는 평문에 키를 곱하고, 복호화는 암호문에 키의 곱셈에 대한 역원을 곱한다 곱셈암호의 암호화는 평문에 키를 곱하고, 복호화는 암호문에 키의 곱셈에 대한 역원을 곱한다 곱셈 암호에서 평문과 암호문은 Z26 의 원소이고, 키는 Z26 의 원소 이다 * P C 3 3

단일문자 암호 곱셈의 역원 a, b ∈ Zn 인 두 수 a, b는 다음을 만족하면 서로 곱셈에 대한 역원 관계에 있다고 한다. • a × b ≡ 1 mod n (a × b 값을 모듈로 n으로 나눌 때 나머지 1) • 모듈로 10 즉, mod 10 에서 3 의 곱셈 역원은 7 이다 즉 , 3 × 7 ≡ 1 mod10 관계이기 때문에 서로 역원관계이다. • a 가 Zn 에서 곱셈에 대한 역원을 갖기 위한 조건은 gcd (n, a) = 1 이다. 즉, a 와 n 은 서로소 이어야 한다. Z10 에서 곱셈에 대한 모든 역원을 구해보자 • Z10 에서 곱셈의 역원을 가질 수 있는 원소는 { 1, 3, 7, 9} 이다. • (1, 1), (3, 7), (9,9) 의 역원 쌍이 존재한다. 4 4

단일문자 암호 Z26 의미 Zn 의 원소중에서 곱셈에 대한 역원을 가진 원소의 집합이다 Zn 과 Zn* 에 대한 예 * 5 5

단일문자 암호 곱셈암호의 암호 곱셈암호에서 사용되는 키는 Z26 에 속한 원소이어야 한다 메시지 “hello”를 암호 키가 7 인 곱셈 암호의 사례이다 암호 키 7 에 대한 역원인 복호 키는 15 이다. * * 6

다중문자 암호 개념 다중문자 치환암호에서 키를 다중문자(예 , PASCAL)를 사용한다. • 평문에서 같은 문자일지라도 암호문에서 다른 문자로 치환된다. • 평문 문자와 암호문 문자사이의 관계는 일대다 대응이 된다. 다중문자 암호는 암호문에서 문자의 출현빈도를 감추는 장점이 있다. 따라서 공격자는 암호문을 해독하기 위하여 문자의 통계적 특성에 따른 분석방법을 사용할 수 없다. 7

다중문자 암호 Vigenere 암호 “PASCAL”이란 6 문자의 키를 사용하여 “She is listening”이라는 평문을 암호해 보자 키 수열은 (15, 00, 18, 02, 00, 11) 이고, 키 수열은 평문의 길이 만큼 반복 사용된다 8

다중문자 암호 Vigenere 암호 옆 표의 첫째 행은 평문 문자를 나타내고, 첫째 열은 키에 사용되는 문자를 나타낸다 평문 문자와 키 문자의 교차점 이 암호문자가 된다 9

다중문자 암호 Playfair 암호 1차 세계대전 때 영국군이 사용 55 행렬로 구성 Secret Key 테이블은 오른쪽 모서리부터 대각선 방향으로 알파벳을 배치한다 평문을 두 문자씩 나누어 암호한다. 10

다중문자 암호 Playfair 암호방법 평문의 두 문자가 playfair 암호 키 테이블의 같은 행에 위치할 경우, 암호문자는 같은 행의 오른쪽 인접하는 문자이다 평문 두 문자가 행의 마지막 문자이면 그 행을 시작하는 문자이다 평문 두 문자가 같은 열에 위치할 경우, 암호문자는 같은 열의 그 아래에 위치한 문자이다 두 문자가 같은 행, 같은 열이 아닌 경우, 암호문자는 같은 행의 다른 문자와 같은 열에 위치한 문자이다 11

다중문자 암호 Playfair 암호 평문 “hello”를 playfair 암호방식으로 암호해 보자 평문을 두 문자씩 묶는데, 두문자가 같으면 둘을 분리하기 위해 가짜 문자(a bogus letter) x 를 삽입한다 평문 문자가 홀수이면 맨 끝에 가짜 문자 x를 삽입한다 평문 hello 를 he lx lo 로 나눈다 12

다중문자 암호 ROTOR 암호 에니그마 암호 독일이 2차 세계 대전 때 군사용으로 사용 평문 “bee”는 “BAA”로 암호된다 13

전치암호 암호방법 정해진 크기(예, 5 문자)로 평문을 나눈 뒤, 키를 사용하여 문자 위치를 바꾼다 Alice 는 “Enemy attacks tonight”이라는 메시지를 Bob 에게 전달 하고자 한다 각 블록이 같은 크기가 되도록 마지막에 가짜 문자를 삽입한다 Alice 와 Bob 은 아래의 치환 키를 사용하기로 약속한다 15

전치암호 암호방법 행 순서로 읽기 열 순서로 읽기 16

스트림 암호 개념 암호 및 복호시 한번에 한 문자씩 암호 알고리즘에 입력되고 암호문도 한 문자씩 생성된다 덧셈암호와 Vigenere 암호는 스트림 암호이다 17

블록 암호 개념 m(m> 1)개의 평문 문자가 함께 암호화 되어, m개의 암호문이 생성된다 18

현대 대칭키 암호 19

강의목차 고전 대칭키 암호와 현대 대칭키 암호 차이점 현대 블록 암호 소개 및 특성 현대 블록 암호의 구성요소 현대 블록 암호 용어 현대 대칭 키 암호공격(차분공격) 20 20

현대 대칭키 암호 개요 고전 대칭키 암호와의 차이점 고전 대칭키 암호 • 문자기반(Character-oriented)의 암호이다 현대 대칭키 암호 • 비트기반(Bit-oriented)의 암호이다 • 암호대상이 텍스트에서 그래픽, 오디오, 비디오 등으로 확대 • 이들 데이터를 비트 스트림으로 변환하고 암호하여 전송한다 21 21

단일문자 암호(고전 암호) 덧셈암호(문자기반) 키가 15인 덧셈암호를 이용하여 메시지 “hello”를 암호하여라 • 암호문 : WTAAD 평문과 암호문을 구성하는 문자를 Z26의 원소로 표현 22 22

현대 대칭키 암호 개요 특징 현대 대칭키 블록암호는 n 비트 평문 블록을 암호하고, n 비트 암호 및 복호 알고리즘은 k 비트 키를 사용한다. 암호 알고리즘과 복호 알고리즘은 서로 역함수 관계이고, 동일한 비밀키 를 사용한다 메시지 길이가 n비트 보다 작을 경우 패딩 (padding)을 한다 23 23

현대 대칭키 암호 개요 암호 설계방식 치환암호 방식 • 평문의 비트값 0과 1을 다른 비트값 1과 0으로 치환한다 • 평문의 0 또는 1의 개수는 암호문의 0 또는 1의 개수와 다르다 • 0의 개수가 12개, 1의 개수가 52개인 64비트 평문 블록이 0의 개수가 34개, 1의 개수가 30개인 암호블록으로 암호 될 수 있다 전치암호 방식 • 평문 비트의 순서를 재배열하여 암호 한다 • 평문의 0 또는 1의 개수는 암호문의 0 또는 1의 개수와 같다 • 전수조사(Exhaustive search)공격에 취약하다 24

현대 대칭키 암호 개요 치환암호 및 전치암호 비교 공격자가 64비트 블록 암호문(1 비트 개수가 10)을 가로챈 후, 공격자가 64비트 블록 암호문(1 비트 개수가 10)을 가로챈 후, 암호를 분석한다고 가정해 보자 치환방식으로 암호가 된 경우 • 공격자는 이 암호문에 해당하는 평문에 1 비트가 몇 개 있는지 알 수 없다 • 암호를 분석하기 위해 64 비트 블록에 대하여 2 번의 시행착오 (Trial-and-test)가 필요하다 • 암호분석 하는데 무척 긴 시간이 걸린다 64 25

현대 대칭키 암호 개요 모든 키 탐색에 필요한 시간 전사적 공격은 가능한 모든 키를 암호문에 적용하여 평문을 찾아 내는 공격법이다 평균적으로 가능한 모든 키의 절반이 시도하면 평문을 찾아낼 수 있다. 키 크기 가능한 키의 수 복호 시간 ( 1µs 당 1 복호) 복호 시간( 1µs 당 10 6 복호) 32 비트 232 = 4.3 × 109 231 µs = 35.8 분 2.15 ms 56 비트 256 = 7.2 × 1016 255 µs = 1142 년 10.01 hours 128 비트 2128 = 3.4 × 1038 2127 µs = 5.4 × 1024 년 5.4 × 1018 년 168 비트 2168 = 3.7  1050 2167 µs = 5.9 × 1036 년 5.9 × 1030 년 26 문자 26 ! = 4 × 1026 2×1026 µs = 6.4× 1012 년 6.4 × 106 년 모든 키 탐색을 위해 요구되는 평균시간 26

현대 대칭키 암호 개요 치환암호 및 전치암호 비교 전치방식으로 암호가 된 경우 • 암호문에 평문의 1 비트와 0 비트의 개수가 그대로 나타난다 • 평문의 1의 개수가 10개이다 • 공격자는 64비트 평문 블록 가운데 1비트 개수가 10개인 평문만 조사하면 된다 • 64！/[(10！)(54！)] 조사하면 된다 ☞ 3 분만에 해독가능 27

현대 블록암호의 구성요소 P-박스 단순 P-박스 평문 비트를 전치시키는(위치를 바꾼다) 기능을 한다 단순 P-박스, 확장 P-박스, 축소 P-박스 등 3가지 종류가 있다 단순 P-박스 n 비트를 입력받아 n 비트를 출력한다 55 단순 P-박스 28 28

현대 블록암호의 구성요소 33 단순 P-박스의 모든 경우 3 × 3 P-박스의 6가지 가능한 모든 경우이다 29 29

현대 블록암호의 구성요소 확장 P-박스 확장 P-박스는 n 비트를 입력 받아 m 비트를 출력한다(n< m) 입력비트 중 특정 비트를 한 번 이상 출력한다 35 확장 P-박스 30 30

현대 블록암호의 구성요소 축소 P-박스 축소 P-박스는 n 비트를 입력 받아 m 비트를 출력한다.(n>m) 입력 비트 중 특정 비트를 소실되어 출력되지 않는다 53 축소 P-박스 31 31

현대 블록암호의 구성요소 S-박스 평문 비트를 치환시키는 (다른 문자로 바꾼다) 기능을 한다 3 비트의 입력 값 왼쪽 최상위 비트는 행을 정의하고, 입력 값의 오른쪽 하위 2 비트는 열을 정의한다. 출력 두 비트는 선택된 열과 행이 교차되는 성분의 값이다 입력이 이면 11이 출력된다. 입력이 출력10을 낸다 1 1 1 32 S-박스 32 32

현대 블록암호의 구성요소 순환이동(Circular Shift) 연산 왼쪽 순환이동, 오른쪽 순환이동 연산이 있다. 평문 비트를 서로 섞는 역할을 한다 왼쪽 순환이동 연산은 평문 n 비트를 왼쪽으로 k 비트만큼 순환한다. 왼쪽 순환이동 오른쪽 순환이동 33 33

현대 블록암호의 구성요소 스왑(Swap) 연산 평문 입력비트의 절반이 오른쪽 왼쪽으로 바뀌는 연산이다 평문비트가 짝수인 경우에만 연산이 이루어 진다 34 34

현대 블록암호의 구성요소 배타적 논리합(Exclusive -OR) 연산 평문과 키가 배타적 논리합 연산을 한다 35 35

현대 블록암호 용어 확산(Diffusion) 혼돈(Confusion) 암호문과 평문 사이의 관계를 숨기는 기능을 한다 확산기능을 통해 공격자가 언어의 출현빈도(언어의 통계적 특성)에 의한 암호문 해독을 불가능하게 한다 혼돈(Confusion) 암호문과 키 사이의 관계를 숨기는 기능을 한다 공격자가 암호문을 이용하여 키를 찾는 것을 불가능하게 한다 36 36

현대 블록암호 용어 합성 암호(Product Cipher) 라운드(Round) 전치(P-박스), 치환(S-박스), 기타 다른 구성 요소들이 결합된 복합 암호이다. 합성 암호의 반복적인 사용으로 확산과 혼돈을 얻을 수 있다. 라운드(Round) 합성 암호의 반복적 사용을 라운드라 칭한다 각 라운드에서 암호가 이루어지기 때문에 N 라운드의 암호에서는 N 번 암호가 이루어진다 37 37

현대 블록암호 2개 라운드 처리과정 8 비트 평문이 라운드 키와 배타적 논리합 연산으로 서로 섞인다 2 비트씩 분할되어 4 개의 S-박스로 입력된다 S-박스의 출력 값은 P-박스 를 통해 전치된 후, 다음 라운드의 입력 값이 된다 2개의 라운드로 구성된 합성함수 38 38

IP : Initial Permutation DES 암호 개념도 PC : Permuted Choice IP : Initial Permutation IP L i-1 R i-1 L i = R i-1 R i = L i-1  f (R i-1, K i ) L i R i -1 PC-2 PC-1 C i-1 D i-1 Left-Shift C i D i K i 64비트 평문 64비트 암호문 64비트 암호키(56비트) 16 회 반복 i = 1,2,… 16 L16 R16 39

DES 암호 개념도 2개의 전치박스(P-박스)와 16개의 라운드로 구성 전치작업 전치 작업 40

현대 블록암호 확산과정 평문의 8 번째 비트는 라운드 키 k1 에 대응되는 비트와 배타적 논리합 연산을 거친 후, S-박스 7 번과 8 번 비트로 통과한다 S-박스 7번 비트는 P-박스를 거친 후 2 번 비트가 되고, 8번 비트는 4 번 비트가 된다 1 라운드에서 평문의 8번째 비트는 암호문의 2번, 4번 비트에 영향을 주게 된다 2 라운드에서 2번째 입력 비트는 라운드 키 k2 에 대응되는 비트와 배타적 논리합 연산을 거친 후, S-박스 1번과 2번 비트로 통과한다 1번 비트는 P-박스를 거친 후 6번 비트가 되고, 2번 비트는 1번 비트 가 된다 41 41

현대 블록암호 확산과정 평문 JESTER 을 오른쪽 표에 의해 암호화 하면 • J E S T E R 24 15 43 44 15 42 (암호문) • 2자리 숫자를 수직방향으로 각각의 숫자로 분리하여 행으로 두 자리 씩 읽으면 21 44 14 45 34 52 가 된다. • E(15)의 첫째 숫자인 “1” 이 J(24)의 첫째 숫자인 “2”와 결합되는 등 암호화시 평문의 각 문자들이 다른 문자들로 확산되는 결과를 얻는다 2 1 4 4 1 4 4 5 3 4 5 2 42 42

현대 블록암호 확산과정 확산을 통해 아래 표의 평문 E(15)를 암호문에서 분산시키는 결과를 얻게 된다 전치와 치환 방법으로 암호화시 평문의 각 문자를 다른 문자들로 확산시키는 결과를 얻을 수 있다 암호문에 나타나는 평문의 언어적 통계특성을 숨길 수 있다 43 43

현대 블록암호 혼돈과정 암호문 중 1,3,6,7 번 비트는 라운드 키의 3개의 비트에 의해 영향을 받는다 k1의 8번 비트 44 44

현대 블록암호 실제 암호 확산과 혼돈 성질이 많을 수록 좋은 암호가 된다. 확산과 혼돈 성질을 향상시키기 위해 좀 더 큰 평문 블록, 많은 S- 박스, 많은 라운드를 사용한다 더 많은 라운드를 사용할수록 평문과 암호문과의 관계 더욱 숨기게 되고(확산), 라운드 키 k i 개수의 증가로 암호문과 키와의 관계도 숨기는 효과를 얻게 된다 45 45

현대 블록암호 공격 블록암호 공격 현대 블록암호는 암호 키 길이(사이즈)가 크기 때문에 암호 키의 전수조사 공격(Brute force attack)은 거의 불가능 하다 현대 블록암호의 대한 새로운 공격법에는 차분 암호분석(differential cryptanalysis)과 선형 암호분석(liner cryptanalysis)방법이 있다 46 46

현대 블록암호 차분공격 암호 알고리즘이 단지 배타적 논리합 연산으로만 구성된다고 하자. 암호 키 값을 알지 못하더라도, 평문의 차분을 P1 P2 로 정의하고, 암호문의 차분을 C1 C2 로 정의하면, 공격자는 평문차분과 암호문 차분 사이의 관계(C1 C2 = P1 P2 )를 쉽게 발견할 수 있다. P1과 P2의 차분과 C1과 C2의 차분 (C1 C2 = P1 P2 ) 을 이용하면 암호 키의 효과를 없게 할 수 있다. 47 47

현대 블록암호 차분공격 배타적 논리합 연산에 S-박스를 추가한 암호 알고리즘을 가정하자. S-박스를 추가하면, 평문인 P1과 P2의 차분과 암호문 C1와 C2 관계 를 찾는 것을 힘들게 한다. 그러나, 공격자는 평문 차분에 대하여 암호문 차분이 얼마나 발생 하는지 차분표 를 만든다 48 48

현대 블록암호 차분공격 암호 키 길이가 3비트이므로 입력차분은 총 8가지 경우가 생긴다 S-박스 표에 의해 입력차분이 (100)2 이면 출력차분은 (00)2인 경우 2가지, 출력차분이 (01)2 인 경우 2가지, 출력차분이 (10)2 인 경우 4가지 이다 49 49

현대 블록암호 차분공격 공격자는 확률적 정보를 제공하는 차분분포표를 만들 수 있다. 표의 성분은 입력차분에 대하여 출력차분이 발생할 확률을 나타낸다 0 확률은 결코 발생할 수 없는 경우이다 50 50

현대 블록암호 차분공격 공격자는 0.5(50%)의 확률로 P1 P2 = 001이면, C1 C2 = 11 을 만족함을 알 수 있다. 공격자는 암호문 C1 = 00 에 대한 평문 P1 = 010과 암호문 C2 = 11 에 대한 평문 P2 = 011 을 가지고 있다고 하자 첫 번째 쌍 P1 과 C1 을 이용하여 역으로 분석을 시도한다. 두 번째 쌍 P2 과 C2을 이용하여 역으로 분석을 시도한다. 51 51

현대 블록암호 차분공격 위 두 개의 분석을 통하여 키가 K = 011 이거나 K =101임을 확인할 수 있다. 공격자는 정확한 키는 확신할 수 없지만 오른쪽 최상위비트가 1 임을 확신할 수 있다 52 52

Thanks Chul Ho Rhee richman3@naver.com