4. 공개키암호화방식 건국대학교
공개키암호방식 대칭키암호방식의문제점 키분배의문제 디지털서명이불가능 공개키암호로해결 (976 년 Diffe 와 Hellman 에의해제기 ) 건국대학교 2
공개키암호방식 공개키알고리즘 : 두개의다른키사용 공개키 : 모든사람이접근가능한키 ( 공개 ) 개인키 : 각사용자자신만이소유 ( 비밀 ) ( 관용암호에사용되는키는비밀키라고함 ) 공개키알고리즘의특징 암호알고리즘과암호키를알아도복호키계산불가능 두개의키중하나는암호에다른하나는복호에사용 건국대학교 3
공개키암호방식 대칭키암호와공개키암호비교 대칭키암호 암호 / 복호에동일한키와동일한알고리즘사용 수신자와송신자는키를교환해야함 공유한키 ( 비밀키 ) 는비밀로유지 키분배의어려움 디지털서명불가능 속도가빠름 공개키암호 암호 / 복호에각각서로다른키와동일한알고리즘사용 수신자와송신자는연관된키쌍중하나를알아야함 공개키쌍중하나 ( 개인키 ) 를비밀로유지 공개키를공개 디지털서명가능 속도가느림 건국대학교 4
공개키암호방식 공개키암호의단순모델 : A 가 B 에게암호화메시지를보내는경우 B 의공개키 B 의개인키 평문암호문평문암호알고리즘복호알고리즘 사용자 A 사용자 B. 공개키와개인키생성 2. 공개키는공개하고개인키는개인이소유 3. A 는 B 의공개키로메시지를암호화 4. B 는자신의개인키로메시지복호화 (B 의개인키를모르는제 3 자는메시지복호불가능 ) 건국대학교 5
공개키암호방식 공개키암호시스템 : 기밀성 : 공개키로암호화함으로써메시지기밀성제공 암호문과공개키로부터평문획득불가능 암호해독자 평문암호문평문암호화복호화 사용자 A 사용자 B B 의공개키 키쌍출처 B 의개인키 건국대학교 6
공개키암호방식 공개키암호시스템 : 인증 : 개인키로서명함으로써송신자인증제공 암호해독자 개인키를알수없음으로위조된서명문작성불가능 ( 평문은알수있음 ) 평문서명문평문암호화복호화 사용자 A 사용자 B A 의개인키 키쌍출처 A 의공개키 건국대학교 7
공개키암호방식 공개키암호시스템 : 기밀성과인증 : 개인키로서명하고공개키로암호화하여기밀성과인증제공 평문 암호화 서명문 암호화 암호문 복호화 서명문 복호화 평문 사용자 A 사용자 B B 의공개키 키쌍출처 B 의개인키 A 의개인키 키쌍출처 A 의공개키 건국대학교 8
공개키암호방식 공개키암호시스템의사용 암호 / 복호 ( 수신자의공개키로메시지암호 ) 디지털서명 ( 송신자의개인키로메시지서명 ) 키교환 ( 세션키를교환하기위해사용 ) 공개키암호시스템의응용 알고리즘 암호 / 복호화 디지털서명 키교환 RSA 가능 가능 가능 LUC 가능 가능 가능 DSS 불가능 가능 불가능 Diffie-Hellman 불가능 불가능 가능 건국대학교 9
공개키암호방식 공개키알고리즘의조건 (Diffie 와 Hellman) 키쌍 ( 공개키 KU, 개인키 KR) 의생성이쉽다. 다음식과같은암호문의생성이쉽다. C = E KUb (M) 다음식과같은암호문의복구화가쉽다. M = D KRb (C) = D KRb [E KUb (M)] 공개키 KUb 로부터개인키 KRb 를결정하는것은어렵다. 공개키 KUb 와암호문 C 로부터메시지 M 의복구가어렵다. 암호와복호기능이다음과같이적용가능하다. ( 추가사항 ) M = E KUb [D KRb (M)] 건국대학교 0
공개키암호방식 공격유형 전사적공격에취약 키의크기를크게함으로써방지 ( 상대적으로속도가느려짐 ) 공개키로부터개인키를계산하는방법 수학적으로계산이불가능함을증명하지못함 가능한메시지공격 : 모든가능한메시지를공개키로암호화하여암호문과비교 메시지에임의의비트를추가함으로써방지 건국대학교
2 Knapsack 일반적인개념 : 일정한크기의배낭에어떤물건을넣어야하는지에관한문제 물건의무게 * 배낭에들어있는물건의종류 = 배낭의무게 공개키 => 물건의무개 평문메시지 => 배낭에들어있는물건의종류 암호메세지 => 배낭의무게 건국대학교 2
2 Knapsack 수식화 정의 cargo 벡터 a = (a, a 2,, a n ) a i : 정수 평문메시지블록 x = (x, x 2,, x n ) x i : 이진수 n 대응하는암호문 S = a x = (a i x i ) 개념 공개키 : a x i = 은 a i 가 Knapsack에포함된다는의미 S와 a에의해 x를복구 I= 건국대학교 3
2 Knapsack Knapsack 의조건 S 의값에유일한역이존재 ex) 두가지역이존재하는예 a = (, 3, 2, 5), S = 3 일경우 x = 00, x = 000 의두가지경우가존재 일반적인복호는어려우나, 특별한지식이있을경우쉬움 초증가벡터 (superincreasing vector) 이용 초증가벡터 : a의각원소가선행하는원소들의합보다큰경우 ex) a = (7, 97, 459,9, 240) 일경우 s = a*x = 3798 =>240이반드시존재 3798-240 = 388 => 는 9이반드시존재 3798-240 - 9 = 97 => 97만존재 x 5 =, x 4 =, x 3 = 0, x 2 =, x = 0 임을쉽게알수있음 건국대학교 4
2 Knapsack Knapsack 문제에초증가 Knapsack 문제를묶는방법 a 을임의로선택 (a : 쉬운초증가 Knapsack 벡터 ) Knapsack 에서는초증가벡터라는사실을아는것이개인키임 그런데곡개키를 a 인체로공개하면개인키가노출되는것과같음 따라서초증가벡터라는사실을알수없는방법이필요함 m 과 w 를선택 m : a 원소들의합보다큰정수 w : m 과서로소인정수 a 생성 (a : 어려운 Knapsack 벡터 ) a = wa mod m 쉬운 Knapsack 벡터로의변환가능 w - a = a mod m 건국대학교 5
2 Knapsack 쉬운초증가 Knapsack 으로문제풀이 a, w -, m, a 를미리알고있을경우 s= a*x 에서 x 구하기 a = wa mod m 우선 s = w - s mod m 으로정의 s = w - s mod m = w - (a*x) mod m = w - (wa *x mod m) mod m = a *x mod m 따라서쉬운 s 와 a 로 x 를구할수있음 건국대학교 6
2 Knapsack Knapsack 알고리즘사용예 << 키생성 >> a ( 쉬운 Knapsack) m = 523, w = 467 = w* w- (mod 523) 467에서로소인수를곱하여찾아냄 w- = 28 (mod 523) a ( 어려운 Knapsack) 공개키 : KU = a, 개인키 : KR = {w-, m, a } 467 3 7 3 26 65 9 267 375 3 38 3 2 35 25 건국대학교 7
2 Knapsack 암호화 평문 = 0000 암호문 = 88 ( 0 467 + 355 + 0 3 + 0 38 + 3 + 0 2 + 35 + 25 = 88 ) 건국대학교 8
2 Knapsack Knapsack 알고리즘사용예 ( 계속 ) 복호화 88 w - = 88 28 = 45 (mod 523) 45 267 x 8 = 45-267 = 48 9 x 7 = 48-9 = 29 < 65 x 6 = 0 29 26 x 5 = 29-26 = 3 < 3 x 4 = 0 3 < 7 x 3 = 0 3 3 x 2 = 3-3 = 0 < x = 0 평문 : x x 2 x 3 x 4 x 5 x 6 x 7 x 8 = 0000 3 7 3 26 65 9 267 건국대학교 9
3 RSA RSA 의개발 : 977 년에개발되어 978 년에공포 (Rivest, Shamir, Adleman) 알고리즘 평문은블록으로암호화 암호화 C = M e mod n 복호화 M = C d mod n = (M e ) d mod n = M ed mod n 공개키 : KU = {e, n}, 개인키 : KR = { d, n } 건국대학교 20
3 RSA 공개키암호방식을만들기위한질문. 모든 M < n 에대하여 M ed = M mod n 을만족하는 e, d, n 값을 찾는것이가능한가? 2. M < n 인모든값에대하여 M e, C d 를계산하기쉬운가? 3. 주어진 e, n 에대하여 d 를결정하기어려운가? 건국대학교 2
3 RSA M ed = M mod n 의증명 ed = 인 e 와 d 를구하면됨 그런데, 오일러정리에의해 m kφ(n)+ = m mod n 가가능한 kφ(n) + = = ed 를알수있음 { p,q ( 솟수 ), n = qp, 정수 n, m (0<m<n), k ( 임의의정수 ) 일때 φ(pq) = (p-)(q-) φ(n) : n 보다적고 n 과서로소인양의정수가되는함수 m kφ(n)+ = m k(p-)(q-)+ = m mod n } 따라서오일러의정리에맞는 e 와 d 를구할수있다면 M ed = M mod n 는성립함 n = qp 인 p,q ( 솟수 ) 를선택,, 정수 n, m (0<m<n) ed = kφ(n) + ed = mod φ(n) e = d - mod φ(n) e 와 d 는 mod φ(n) 에곱셈역원 건국대학교 22
3 RSA RSA 알고리즘정리 키생성 p, q 선택 ( p, q 는솟수 ) n = p q 계산 정수 d 선택 ( gcd(φ(n),d) =, <d< φ(n) ) e 계산 ( e = d - mod φ(n) ) 공개키 ( KU = {e, n} ) 개인키 ( KR = {d, n} ) 암호화 C = M e ( mod n ) 복호화 M = C d ( mod n ) 건국대학교 23
3 RSA RSA 알고리즘사용예 공개키와개인키생성. 두솟수 p = 7, q = 7 을선택 2. n = pq = 7 7 = 9 계산 3. φ(n) = (p-)(q-) = 96 계산 4. φ(n) = 96 과서로소이고 φ(n) 보다작은 e 선택 ( e = 5 ) 5. de = mod 96 이고 d < 96 인 d 를결정 (d = 77) 공개키 KU = {5, 9}, 개인키 KR = {77, 9} 건국대학교 24
3 RSA RSA 알고리즘사용예 ( 계속 ) 암호화와복호화 : 평문메시지 M = 9 일경우 암호문 : 9 5 = 66 mod 9 66 복호문 : 66 77 = 9 mod 9 9 암호화 복호화 평문 9 2476099 20807 9 5 = = 9 나머지 : 66 암호문 66.27 0 40.06 0 38 66 77 = = 9 나머지 : 9 평문 9 KU = 5, 9 KR = 77, 9 건국대학교 25
4 공개키분배 공개키의공개발표 자신의공개키를다른사용자에게전송등의방법으로공개 문제점 어떤사용자가다른사용자 A 로위장하여공개키공개 (A 에전송되는암호화메시지를읽을수있게됨 ) KUa KUb 사용자 A KUa. KUa KUa KUb. KUb KUb 사용자 B 건국대학교 26
4 공개키분배 공개적으로사용가능한디렉토리 필요한사항 기관은각가입자에대한 { 이름, 공개키 } 의디렉토리유지 각가입자는디렉토리기관에공개키등록 가입자는필요시새로운것으로교체가능 기관은디렉토리를공포 가입자는전자적으로디렉토리접근가능 문제점 디렉토리정보를수정 위조의공개키로임의의가입자로위장하여도청 건국대학교 27
4 공개키분배 공개적으로사용가능한디렉토리 ( 계속 ) 공개키 디렉토리 KUa KUb 사용자 A 사용자 B 건국대학교 28
4 공개키분배 공개키기관 : 공개키기관에서공개키분배제어 공개키기관 () Request Time (4) Request Time 2 (2) E KRau [KU b Request Time ] (5) E KRau [KU a Request Time 2 ] (3) E KUb [ID A N ] 시행자 A (6) E KUa [N N 2 ] (7) E KUb [N 2 ] 대응자 B 건국대학교 29
4 공개키분배 공개키기관 ( 계속 ) () 단계 (2) 단계 (3) 단계 B 의공개키에대한요구를타임스템프와함께전송 공개키기관은 B 의공개키와 () 단계의메시지를 자신의개인키로암호화하여전송 B의공개키를저장하고, A의식별자 (ID A ) 와임시비표 (N ) 을 B의공개키로암호화하여전송 건국대학교 30
4 공개키분배 공개키기관 ( 계속 ) (4), (5) 단계 (6) 단계 (7) 단계 B 는 (), (2) 단계와같은방법으로 A 의공개키획득 B 는임시비표 N, N 2 를 A 의공개키로암호화하여전송 A 는 N 2 를 B 의공개키로암호화하여전송 문제점 공개키디렉토리수정에취약 타임스템프에의해서송신상대방의공개키유효기간을확인한것이므로필요시공개키기관으로부터공개키를다시갖고와야함 건국대학교 3
4 공개키분배 공개키인증서 공개키기관의도움없이인증서를이용하여키교환 인증서방식을위한요구사항 임의의가입자는인증서의내용 ( 이름, 공개키 ) 확인가능 임의의가입자는인증서의정당성확인가능 인증기관만이인증서생성과갱신가능 임의의가입자는인증서의현행성확인가능 건국대학교 32
4 공개키분배 공개키인증서분배방식 KU a 공개키기관 C A = E KRau [ Time, ID A, Ku a ] KU b C B = E KRau [ Time 2, ID B, Ku b ] 시행자 A () C A (2) C B 대응자 B : 사용자는공개키인증서를받은후인증서로공개키전송 건국대학교 33
4 비밀키의공개키분배 공개키의사용처 : 공개키는느리기때문에대칭키암호의비밀키분배에많이사용 단순비밀키분배 () Kua ID A 사용자 A (2) E KUa [Ks] 사용자 B () 단계 A는공개키쌍 {K Ua, K Ra } 을생성하고, 식별자 ID A 와함께개키전송 (2) 단계 B는비밀키 Ks를생성하고 A의공개키로암호화하여전송 공 건국대학교 34
4 비밀키의공개키분배 단순비밀키분배 ( 계속 ) 문제점 : 적극적인공격에약함 () A 는공개키쌍 {K Ua, K Ra } 을생성하고, 공개키전송 (2) E 는메시지를가로채고, 자신의공개키 (K Ue ) 를전송 (3) B는비밀키 Ks를생성하고 E의공개키로암호화하여전송 E KUe [Ks] (4) E는메시지를가로채어 Ks를획득 (D KRe [E KUe [Ks]] = Ks (5) E는 A에게 E KUa [Ks] 전송 E 는 A 와 B 가모르게비밀값 Ks 획득 ( 도청공격 ) 건국대학교 35
4 비밀키의공개키분배 (4)[Ks] 획득 (5)EKUa[Ks] 암호해독자 (3)EKUe[Ks] (2)Kua IDA (2)Kue IDA 사용자 A () Kua ID A (2) E KUa [Ks] 사용자 B 건국대학교 36
4 비밀키의공개키분배 기밀성과인증을가지는비밀키분배 : 적극적, 소극적공격에대한해결 () E KUb [N ID A ] (2) E KUa [N N 2 ] 사용자 A (3) E KUb [ N 2 ] (4) E KUb [E KRa [Ks]] 사용자 B 건국대학교 37
4 비밀키의공개키분배 기밀성과인증을가지는비밀키분배 ( 계속 ) : 공개키를교환했다고가정 () 단계 A의식별자와임시비표 (N ) 를 B의공개키로암호화하여전송 (2) 단계 B는새로운임시비표 (N 2 ) 와 N 을 A의공개키로암호화하여전송 (3) 단계 A는보증을위해 B의공개키로암호화한 N 2 을반환 (4) 단계 A는비밀키 Ks를선택하여 M=E KUb [E KRa [Ks]] 를 B에게전송 건국대학교 38
4 비밀키의공개키분배 혼합방식 키분배센터 (KDC) 의사용을유지 : 각사용자에게마스터키를나누어주고, 마스터키로암호화 된비밀세션키를분배 공개키방식은마스터키를분배하기위해사용 건국대학교 39
4 비밀키의공개키분배 () E KUkdc [Request N ID A ] 사용자 A (2) E KUa [Request N N 2 ] (3) E KUkdc [ N 2 ] (4) E KUb [E KRkdc [Ka]] 키분배센터 (KDC) 키분배센터 (KDC) () Request N (2) E Ka [K S Request N E Kb [K S,ID A ]] 발신자 A (3) E Kb [K S ID A ] (4) E KS [N 2 ] (5) E Ks [f(n 2 )] 응답자 B 건국대학교 40