Chap 4. 공개키 암호

목 차 1. 공개키 암호 시스템의 원리 2. RSA 알고리즘 3. 키 관리

1. 공개키 암호 시스템의 원리 관용 암호 방식의 문제점 키 분배의 문제 디지털 서명이 불가능  공개키 암호로 해결 (1976년 Diffe와 Hellman에 의해 제기)

1.1 공개키 암호 시스템 공개키 알고리즘 공개키 알고리즘의 특징 : 두 개의 다른 키 사용 공개키 : 모든 사람이 접근 가능한 키 (공개) 개인키 : 각 사용자 자신만이 소유 (비밀) (관용 암호에 사용되는 키는 비밀키라고 함) 공개키 알고리즘의 특징 암호 알고리즘과 암호키를 알아도 복호키 계산 불가능 두 개의 키 중 하나는 암호에 다른 하나는 복호에 사용

관용 암호와 공개키 암호 비교 관용 암호 공개키 암호 암호/복호에 동일한 키와 암호/복호에 각각 서로 다른 키 와 관용 암호 공개키 암호 암호/복호에 동일한 키와 암호/복호에 각각 서로 다른 키 와 동일한 알고리즘 사용 동일한 알고리즘 사용 수신자와 송신자는 키를 수신자와 송신자는 연관된 키쌍 중 교환해야 함 하나를 알아야 함 공유한 키(비밀키)는 비밀로 유지 키 쌍중 하나(개인키)를 비밀로 유지 키 분배의 어려움 공개키를 공개 디지털 서명 불가능 디지털 서명 가능 속도가 빠름 속도가 느림

공개키 암호의 단순 모델 : A가 B에게 암호화 메시지를 보내는 경우 1. 공개키와 개인키 생성 평문 암호문 평문 암호 알고리즘 복호 알고리즘 사용자 A 사용자 B 1. 공개키와 개인키 생성 2. 공개키는 공개하고 개인키는 개인이 소유 3. A는 B의 공개키로 메시지를 암호화 4. B는 자신의 개인키로 메시지 복호화 (B의 개인키를 모르는 제 3자는 메시지 복호 불가능)

공개키 암호 시스템 : 기밀성 : 공개키로 암호화함으로써 메시지 기밀성 제공 평문 암호문 평문 암호문과 공개키로부터 평문 획득 불가능 암호 해독자 평문 암호문 평문 암호화 복호화 사용자 A 사용자 B B의 개인키 B의 공개키 키 쌍 출처

공개키 암호 시스템 : 인증 : 개인키로 서명함으로써 송신자 인증 제공 평문 서명문 평문 개인키를 알 수 없음으로 위조된 서명문 작성 불가능 (평문은 알 수 있음) 암호 해독자 평문 서명문 평문 암호화 복호화 사용자 A 사용자 B A의 개인키 A의 공개키 키 쌍 출처

공개키 암호 시스템 : 기밀성과 인증 : 개인키로 서명하고 공개키로 암호화하여 기밀성과 인증 제공 평문 서명문 암호문 서명문 복호화 복호화 사용자 A 사용자 B B의 개인키 B의 공개키 키 쌍 출처 A의 개인키 A의 공개키 키 쌍 출처

1.2 공개키 암호 시스템의 응용 공개키 암호 시스템의 사용 공개키 암호 시스템의 응용 암호/복호 (수신자의 공개키로 메시지 암호) 디지털 서명 (송신자의 개인키로 메시지 서명) 키 교환 (세션키를 교환하기 위해 사용) 공개키 암호 시스템의 응용 알고리즘 암호/복호화 디지털 서명 키 교환 RSA 가능 가능 가능 LUC 가능 가능 가능 DSS 불가능 가능 불가능 Diffie-Hellman 불가능 불가능 가능

1.3 공개키 암호를 위한 요구 사항 공개키 알고리즘의 조건 (Diffie와 Hellman) 키 쌍(공개키 KU, 개인키 KR)의 생성이 쉽다. 다음 식과 같은 암호문의 생성이 쉽다. C = EKUb(M) 다음식과 같은 암호문의 복구화가 쉽다. M = DKRb(C) = DKRb[EKUb(M)] 공개키 KUb로부터 개인키 KRb를 결정하는 것은 어렵다. 공개키 KUb와 암호문 C로부터 메시지 M의 복구가 어렵다. 암호와 복호 기능이 다음과 같이 적용 가능하다. (추가 사항) M = EKUb[DKRb(M)]

1.4 공개키 암호 분석 공격 유형 전사적 공격에 취약  키의 크기를 크게 함으로써 방지 (상대적으로 속도가 느려짐) 공개키로부터 개인키를 계산하는 방법  수학적으로 계산이 불가능함을 증명하지 못함 가능한 메시지 공격 : 모든 가능한 메시지를 공개키로 암호화하여 암호문과 비교  메시지에 임의의 비트를 추가함으로써 방지

1.5 Knapsack 알고리즘 일반적인 개념 : 일정한 크기의 배낭에 어떤 물건을 넣어야 하는지에 관한 문제 정의 cargo 벡터 a = (a1, a2, … , an) ai :정수 평문 메시지 블록 x = (x1, x2, … , xn) xi :이진수 대응하는 암호문 S = a · x =  (ai  xi) 개념 공개키 : a xi = 1은 ai가 Knapsack에 포함된다는 의미 S와 a에 의해 x를 복구 n I=1

Knapsack의 조건 S의 값에 유일한 역이 존재 ex) 두 가지 역이 존재하는 예 a = (1, 3, 2, 5), S = 3 일 경우 x = 1010, x = 0100의 두가지 경우가 존재 일반적인 복호는 어려우나, 특별한 지식이 있을 경우 쉬움 초증가 벡터(superincreasing vector) 이용 초증가 벡터 : a의 각 원소가 선행하는 원소들의 합보다 큰 경우 ex) a’ = (171, 197, 459,1191, 2410) 일 경우 x5 = 1, x4 = 1, x3 = 0, x2 = 1, x1 = 0 임을 쉽게 알 수 있음

Knapsack 문제에 초증가 Knapsack 문제를 묶는 방법 a’을 임의로 선택 (a’ : 쉬운 초증가 Knapsack 벡터) m과 w를 선택 m : a’원소들의 합보다 큰 정수 w : m과 서로 소인 정수 a 생성 (a : 어려운 Knapsack 벡터) a = wa’ mod m 쉬운 Knapsack 벡터로의 변환 가능 w-1a = a’ mod m

Knapsack 알고리즘 사용 예 키 생성 a’ (쉬운 Knapsack) w = 467, m = 523, w-1 = 28 (mod 523) a (어려운 Knapsack) 공개키 : KU = a, 개인키 : KR = {w-1, m, a’) 암호화 평문 = 01001011 암호문 = 818 ( 0 467 + 1 355 + 0 131 + 0 318 + 1 113 + 0 21 + 1 135 + 1 215 = 818 ) 1 3 7 13 26 65 119 267 467 375 131 318 113 21 135 215

Knapsack 알고리즘 사용 예 (계속) 복호화 818 w-1 = 818 28 = 415 (mod 523) 415  267  x8 = 1 415 - 267 = 148  119  x7 = 1 148 - 119 = 29  65  x6 = 0 29  26  x5 = 0 29 - 26 = 3  13  x4 = 0 3  7  x3 = 0 3  3  x2 = 1 3 - 3 = 0  1  x1 = 0  평문 : x1x2x3x4x5x6x7x8 = 01001011

2. RSA 알고리즘 2.1 알고리즘 설명 RSA의 개발 알고리즘 : 1977년에 개발되어 1978년에 공포 (Rivest, Shamir, Adleman) 알고리즘 평문은 블록으로 암호화 암호화 C = Me mod n 복호화 M = Cd mod n = (Me)d mod n = Med mod n 공개키 : KU = {e, n}, 개인키 : KR = { d, n }

Med = M mod n의 증명 오일러 정리 p,q (솟수), n = qp, 정수 n, m (0mn), k (임의의 정수) 일 때 mk(n)+1 = mk(p-1)(q-1)+1 = m mod n (n) : n보다 적고 n과 서로소인 양의 정수가 되는 함수 ( p,q가 솟수일 경우, (pq) = (p-1)(q-1) ) ed = k(n) + 1 ed = 1 mod (n) e = d-1 mod (n)  e와 d는 mod (n)에 곱셈 역원 (e와 d가 (n)에 서로소인 경우에만 참)

RSA 알고리즘 정리 키 생성 p, q 선택 ( p, q는 솟수 ) n = p  q 계산 정수 d 선택 ( gcd((n),d) =1, 1<d< (n) ) e 계산 ( e = d-1 mod (n) ) 공개키 ( KU = {e, n} ) 개인키 ( KR = {d, n} ) 암호화 C = Me ( mod n ) 복호화 M = Cd ( mod n )

RSA 알고리즘 사용 예 공개키와 개인키 생성 1. 두 솟수 p = 7, q = 17 을 선택 2. n = pq = 7  17 = 119 계산 3. (n) = (p-1)(q-1) = 96 계산 4. (n) = 96과 서로소이고 (n)보다 작은 e 선택 ( e = 5 ) 5. de = 1 mod 96이고 d < 96 인 d를 결정 (d = 77)  공개키 KU = {5, 119}, 개인키 KR = {77, 119}

RSA 알고리즘 사용 예 (계속) 암호화와 복호화 : 평문 메시지 M = 19 일 경우 암호문 : 195 = 66 mod 119  66 복호문 : 6677 = 19 mod 119  19 암호화 복호화 암호문 66 2476099 20807 195 = = 119 나머지 : 66 1.27…10140 1.06 …10138 6677 = = 119 나머지 : 19 평문 19 평문 19 KU = 5, 119 KR = 77, 119

2.2 계산적인 측면 암호화와 복호화 계산량을 줄이는 방법 모듈러 연산의 특징 이용 효율적인 지수 승 [(a mod n)  (b mod n)] mod n = (a  b) mod n  중간 결과를 축소 효율적인 지수 승 직접적인 방법 (x16 일 경우) : x16 = xxxxxxxxxxxxxxxx  15번의 곱셈 효율적인 방법 : x2, x4, x8, x16  4번의 곱셈

키 생성 랜덤한 큰 솟수를 찾는 방법 (확률적 검사법) 1. 랜덤하게 홀수 n을 선택 2. 랜덤하게 a<n인 정수 a를 선택 3. 확률적 솟수 판정법 수행 (만약 n이 검사에서 실패하면 1단계로) 4. n이 충분한 횟수로 통과하면 n을 수용, 그렇지 않으면 2단계로 솟수 생성을 위한 검사 횟수 N에 가까운 솟수는 (ln N)에 대하여 평균 1회 생성 ex) 2200 범위의 솟수  ln(2200)/2 = 70 회 정도 시행

암호 해독의 고찰 암호 해독의 접근 방법 전사적 공격  큰 키를 사용하여 방지 인수 n를 두 소인수로 인수 분해  큰 값에 대한 두 솟수의 곱을 인수 분해하는 적당한 알고리즘이 없음 p와 q을 결정하지 않고 직접 (n)을 결정  인수 분해만큼 어려움 (n)을 결정하지 않고 직접 d를 결정

3. 키 관리 3.1 공개키의 분배 공개키의 공개 발표 자신의 공개키를 다른 사용자에게 전송 등의 방법으로 공개 문제점 어떤 사용자가 다른 사용자 A로 위장하여 공개키 공개 (A에 전송되는 암호화 메시지를 읽을 수 있게 됨) KUa KUb KUa KUb . . KUa KUb 사용자 A 사용자 B KUb KUa

공개적으로 사용 가능한 디렉토리 필요한 사항 기관은 각 가입자에 대한 {이름, 공개키}의 디렉토리 유지 각 가입자는 디렉토리 기관에 공개키 등록 가입자는 필요시 새로운 것으로 교체 가능 기관은 디렉토리를 공포 가입자는 전자적으로 디렉토리 접근 가능 문제점 디렉토리 정보를 수정 위조의 공개키로 임의의 가입자로 위장하여 도청

공개적으로 사용 가능한 디렉토리 (계속) 공개키 디렉토리 KUa KUb 사용자 A 사용자 B

공개키 기관 : 공개키 기관에서 공개키 분배 제어 공개키 기관 시행자 A 대응자 B (1) Request || Time1 (2) EKRau[KUb || Request || Time1] (5) EKRau[KUa || Request || Time2] (3) EKUb[IDA || N1] 시행자 A (6) EKUa[N1 || N2] 대응자 B (7) EKUb[N2]

공개키 기관 (계속) (1) 단계 B의 공개키에 대한 요구를 타임스템프와 함께 전송 (2) 단계 자신의 개인키로 암호화하여 전송 (3) 단계 B의 공개키를 저장하고, A의 식별자(IDA)와 임시비표(N1)을 B의 공개키로 암호화하여 전송

공개키 기관 (계속) (4), (5) 단계 B는 (1), (2) 단계와 같은 방법으로 A의 공개키 획득 (6) 단계 B는 임시비표 N1, N2를 A의 공개키로 암호화하여 전송 (7) 단계 A는 N2를 B의 공개키로 암호화하여 전송 문제점 공개키 디렉토리 수정에 취약

공개키 인증서 공개키 기관의 도움없이 인증서를 이용하여 키 교환 인증서 방식을 위한 요구 사항 임의의 가입자는 인증서의 내용(이름, 공개키) 확인 가능 임의의 가입자는 인증서의 정당성 확인 가능 인증 기관만이 인증서 생성과 갱신 가능 임의의 가입자는 인증서의 현행성 확인 가능

공개키 인증서 (계속) : 사용자는 공개키 인증서를 받은 후 인증서로 공개키 전송 공개키 기관 시행자 A 대응자 B KUa KUb CA = EKRau[ Time1, IDA, Kua ] CA = EKRau[ Time2, IDB, Kub ] (1) CA 시행자 A (2) CB 대응자 B : 사용자는 공개키 인증서를 받은 후 인증서로 공개키 전송

3.2 비밀키의 공개키 분배 공개키의 사용처 단순 비밀키 분배 (1) 단계 : 공개키는 느리기 때문에 관용 암호의 비밀키 분배에 많이 사용 단순 비밀키 분배 (1) Kua || IDA (2) EKUa[Ks] 사용자 A 사용자 B (1) 단계 A는 공개키 쌍 {KUa, KRa}을 생성하고, 식별자 IDA와 함께 공개키 전송 (2) 단계 B는 비밀키 Ks를 생성하고 A의 공개키로 암호화하여 전송

단순 비밀키 분배 (계속) 문제점 : 적극적인 공격에 약함 (1) A는 공개키 쌍 {KUa, KRa}을 생성하고, 공개키 전송 (2) E는 메시지를 가로채고, 자신의 공개키(KUe)를 전송 (3) B는 비밀키 Ks를 생성하고 E의 공개키로 암호화하여 전송 EKUe[Ks] (4) E는 메시지를 가로채어 Ks를 획득 (DKRe[EKUe[Ks]] = Ks (5) E는 A에게 EKUa[Ks] 전송  E는 A와 B가 모르게 비밀값 Ks 획득 (도청 공격)

기밀성과 인증을 가지는 비밀키 분배 : 적극적, 소극적 공격에 대한 해결 (1) EKUb [N1 || IDA] (2) EKUa [N1 || N2] (3) EKUb [ N2] 사용자 A 사용자 B (4) EKUb [EKRa [Ks]]

기밀성과 인증을 가지는 비밀키 분배 (계속) : 공개키를 교환했다고 가정 (1) 단계 (2) 단계 (3) 단계 (4) 단계 A의 식별자와 임시비표(N1)를 B의 공개키로 암호화하여 전송 (2) 단계 B는 새로운 임시비표(N2)와 N1을 A의 공개키로 암호화하여 전송 (3) 단계 A는 보증을 위해 B의 공개키로 암호화한 N2을 반환 (4) 단계 A는 비밀키 Ks를 선택하여 M=EKUb[EKRa[Ks]]를 B에게 전송

혼합 방식 키 분배 센터(KDC)의 사용을 유지 : 각 사용자에게 마스터키를 나누어주고, 마스터키로 암호화 된 비밀 세션키를 분배 공개키 방식은 마스터키를 분배하기 위해 사용