SeoulTech UCS Lab 2013-2 st 암호이론및정보보호실무 제 9 장공개키암호 2013. 10. 14 강원민 Email: wkaqhsk0@seoultech.ac.kr
목차 1. 공개키암호시스템의원리 2. RSA 알고리즘 3. Diffie-Hellman 알고리즘 2
공개키암호시스템의원리 공개키암호시스템의원리 1. 암호화 / 복호화에사용되는키가서로다르다 ( 기밀성, 키배송, 인증에서중요 ) 2. 주어진암호알고리즘과암호키를알고있더라도복호키를결정하는것은계산적으로실행불가능 3
대칭암호의가장어려운점 키배송문제 (key distribution problem) 대칭암호를사용하려면송신자와수신자가대칭키를사전에공유해야하는문제 대칭키를보내지않으면밥은복호화할수없다 해결책은? (14장) 4
키배송문제를해결하기위한방법 (14 장에서논의 ) 키의사전공유에의한해결 키배포센터에의한해결 Diffie-Hellman 키교환 공개키암호에의한해결 5
키의사전공유에의한키배송문제의해결 키사전공유 안전한방법으로키를사전에건네주는 것 직접전달은안전 이메일 / 일반메일등은위험 인원이많아지면관리해야할키수증가 6
키배포센터에의한키배송문제의해결 키배포센터 (key distribution center; KDC) 암호통신때마다통신용의키를키배포센터에의뢰해서개인과키배포센터사이에서만키를사전에공유 키배포센터의역할을하는컴퓨터를지정 구성원전원의키를보존 7
공개키암호란? 공개키암호 (public-key cryptography) 암호화키 와 복호화키 가분리 송신자는 암호화키 를써서메시지를암호화하고, 수신자는 복호화키 를써서암호문을복호화 송신자가필요한것은 암호화키 수신자가필요한것은 복호화키 도청자에게알려지면안되는것은 복호화키 - Why? 8
공개키암호구조의구성요소 평문 (P): 읽을수있는평문메시지또는데이터 암호화알고리즘 (E): 평문에대하여다양한변형을수행 공개키와개인키 : 하나는암호화를위하여사용되고다른하나는복호화를위하여사용되도록선택된키의쌍 암호문 (C): 출력으로써변형된메시지, 평문과키에의존적이며주어진하나의메시지에대하여 2 개의다른키는 2 개의다른암호문을생성 복호화알고리즘 (D): 암호문과대응하는키를받아서본래의평문을생성 9
공개키의의미 공개키 (public key) 암호화키 는일반에게공개해도무방 Public Key can open anywhere why? 10
개인키의의미 개인키 (private key) 복호화키 는미공개 이키는본인만사용 개인키는다른사람에게보이거나, 건네주거나해서는안됨 개인키는자신의통신상대에게도보여서는안됨 11
공개키 - 개인키쌍 키쌍 (key pair) 공개키와개인키는둘이한쌍 공개키로암호화한암호문은그공개키와쌍이되는개인키가아니면복호화할수없다 수학적인관계 키쌍을이루고있는 2 개의키는서로밀접한관계 공개키와개인키쌍은별개로만들수없음 12
공개키를사용한통신의흐름 앨리스가밥에게메시지보내기 (1) 밥은공개키 / 개인키로이루어진한쌍의키 (K B(pub) /K B(pri) ) 생성 (2) 밥은자신의공개키 (K B(pub) ) 를앨리스에게전송 (3) 앨리스는밥의공개키를써서메시지 (P) 를암호화 (C=E(K B(pub),P)) (4) 앨리스는암호문 (C) 을밥에게전송 (5) 밥은자신의개인키 (K B(pri) ) 를써서암호문을복호화 (P=D(K B(pri),C)) 13
공개키를사용한메시지전송 14
공개키를사용한메시지전송 (Eng Ver.) Bob 15 Alice
공개키암호시스템 : 기밀성 16
개인키를사용한메시지전송 ( 인증 ) Bob Alice 17
공개키암호시스템 : 인증 18
관용암호와공개키암호의비교 19
공개키암호로도해결할수없는문제 공개키의인증에관한문제 입수한공개키의진위를판단할필요 중간자공격 (man-in-the-middle attack) 공개키암호의속도 대칭암호에비해처리속도가몇백배나늦음 20
RSA 란무엇인가? RSA 는공개키암호알고리즘의하나 RSA 이름 개발자 3 명의이름 Ron Rivest, Adi Shamir, Leonard Adleman 의이니셜 (Rivest-Shamir-Adleman) 응용 공개키암호 디지털서명 키교환 21
RSA 암호화알고리즘 암호키의안전한분배및관리를해결하기위해이용 두수의차가큰서로다른두소수를이용 일반적으로두수의곱은구하기쉽지만, 인수분해가어렵다는점을이용 인수분해문제와이산대수문제를이용한알고리즘 22
RSA 알고리즘의기본형태 알고리즘의기본형태 송신자와수신자는 n 값을알아야한다. 송신자는 e 값을알고, 수신자만 d 의값을안다. 1. 모든 M < n에대하여 = M mod n을만족하는 e, d, n 값을 찾는것이가능하다. 2.M < n 인모든값에대하여, 를계산하기쉽다. 3. 주어진 e 와 n에대하여 d를결정하기어렵다. 23
4.2 RSA 에의한암호화 RSA 에서평문도키도암호문도숫자로변환한뒤실행 RSA 의암호화는다음식으로표현 암호문 (C) = ( 평문 (M)) E mod N (RSA 에의한암호화 ) 24
E 와 N 은무엇일까? (E, N): 공개키 E와 N이라는한쌍의수를알면누구라도암호화를행할수있다 E와 N이 RSA 암호화에사용되는키 E와 N은면밀한계산을통해생성 25
4.3 RSA 에의한복호화 복호화도간단하다 평문 (P) = ( 암호문 (C)) D mod N (RSA 의복호화 ) 26
D 와 N 은무엇일까? (D, N): 개인키 D와 N이라는한쌍의수를알면누구라도복호화를행할수있다 D와 N이 RSA 복호화에사용되는키 D와 N도면밀한계산을통해생성 E와 D는밀접한연관관계 27
RSA 의암호화와복호화 28
키쌍의생성 1. N을구한다 2. L을구한다 (L은키쌍을생성할때만등장하는수이다 ) 3. E를구한다 4. D를구한다 29
N 구하기 큰소수를 2 개준비 (p 와 q) N = p q (p, q 는소수 ) 30
L 구하기 L 은 RSA의암호화나복호화에사용안함 키쌍을만들때임시로사용 L = lcm(p-1, q-1) (L은 p-1 과 q-1의최소공배수 ) 31
E 구하기 다음두식을만족하는수 E 를하나찾아낸다 1 < E < L gcd(e, L) = 1 (E 와 L 은서로소 ) 32
D 구하기 다음두식을만족하는수 E 를하나찾아낸다 1 < D < L E D mod L = 1 33
RSA 키쌍생성 (1) N을구한다의사난수생성기로 p와 q를구한다 p와 q는소수 N = p q (2) L을구한다 L = lcm(p-1, q-1) L은 p-1과 q-1의최소공배수 (3) E를구한다 1<E<L gcd(e, L) = 1 E와 L과의최대공약수는 1(E와 L은서로소 ) (4) D를구한다 1<D<L E D mod L = 1 34
RSA 키쌍 35
RSA 예 p 와 q 선택하기 2 개의소수 p=17, q=19 선택 N 구하기 N = p q = 17 19 = 323 L 구하기 L = lcm(p-1, q-1) = lcm(16, 18) = 144 (16 과 18 의최소공배수 ) E 구하기 ( 선택하기 ) gcd(e, L) = 1 이되는수 E 를선택하자. E 가될수있는수는다음과같은수이다. 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 우리는 E=5 를선택 ( 다른수를선택해도무방 ) D 구하기 E D mod L = 5 29 mod 144 = 145 mod 144 = 1 이므로 D=29 36
RSA 예 공개키 : (E, N) = (5, 323) 개인키 : (D, N) = (29, 323) 37
암호화와복호화 평문은 N=323 보다작은수 예로평문 =123 이라하고암호화를해보자 평문 E mod N = 123 5 mod 323 = 225 암호문 D mod N = 225 29 mod 323 = 123 38
RSA 의안전성 39
중간자공격 중간자 (man-in-the-middle) 공격 RSA를해독하는게아니다 기밀성을침해하는공격 공격자맬로리가송신자와수신자사이에서송신자에대해서는수신자처럼, 수신자에대해서는송신자처럼행세하는공격 40
중간자공격절차 (1/3) 1) 앨리스는밥의공개키요청 2) 맬로리는, 앨리스의요청을도청 3) 밥은자신의공개키 (KB(pub)) 를앨리스에게전송 4) 맬로리는밥의이메일이앨리스에게도달하지못하도록하고, 밥의공개키를보존 5) 맬로리는자신의공개키 (KM(pub)) 를밥의공개키라고속여서앨리스에게전송 41
중간자공격절차 (2/3) 6) 앨리스는자신의메시지 (P) 를밥의공개키 ( 실은맬로리의공개키 ) 로암호화 ( C=E(K M(pub), P) ) 7) 앨리스는암호화한메시지 (C) 를밥에게전송 8) 맬리로는앨리스의암호메일을갈취해서자신의개인키 (KM(pri)) 로복호화 ( P=D(KM(pri),C) ) 하고평문 (P) 을확보 42
중간자공격절차 (3/3) 9) 맬로리는앨리스행세를하며위조메일 ( P ) 을만들고위의단계 (4) 에서보존해둔밥의공개키 (K B(pub) ) 를써서이위조메일을암호화 (C = E(K B(pub, P ) ) 하여밥에게전송 10) 밥은받은암호메일 (C ) 을자신의개인키로복호화화하고메일 ( P ) 을읽게된다 43
맬로리에의한중간자공격 44
10 장다른공개키암호시스템 Diffie-Hellman 키교환 - 키의안전한교환 - 이산대수문제를이용 45
이산대수 이산대수 임의의소수 P 에대해서근의멱승이 1 부터 p-1 까지의모든정수를생성하는원시근을 α 라고함 α 의멱승에대한 mod p 의계산결과 (α mod p, α 2 mod p,, α p-1 mod p) 가 { 1, 2, 3,, p-1} 까지의각각다른정수를생성 소수 p=7, 원시근 α =3 일때 b= α i mod p 에서 3 1 mod 7 = 3, 3 2 mod 7 = 2, 3 3 mod 7 = 6 3 4 mod 7 = 4, 3 5 mod 7 = 5, 3 6 mod 7 = 1 계산결과 b 는 1 부터 6 까지의각각다른정수를구성 b= α i mod p 지수 i 는밑수 a 에대한 b 의이산대수이다. 나머지수를알아도 i 를구하는것은어렵다. 46
키교환알고리즘 전체공개요소 - q ( 소수 ), α ( 0<q 그리고 q 의원시근 ) 사용자 A 의키생성 - 개인키 X A 선택 (X A < q) - 공개키 Y A 계산 (Y A = α XA mod q) 사용자 B 의키생성 - 개인키 X B 선택 (X B < q) - 공개키 Y B 계산 (Y B = α XB mod q) 사용자 A 에의한비밀키계산 - K = (Y B ) XA mod q 사용자 B 에의한비밀키계산 - K = (Y A ) XB mod q 큰소수에대한계산은전사공격으로매우오랜시간이걸린다. 알아내는것이매우힘들다. 47
Q & A 48
Thank You! 49