Chapter 4 공개키 암호 Knapsack RSA Diffie-Hellman 키 교환 방식 Elliptic Curve Cryptography 공개키 방식의 활용

공개키(PKC) 암호 또 다른 이름 공개키 암호는 비교적 새로운 개념이다. 비대칭 암호(asymmetric cryptography) 대칭키 암호에 대응해서 비대칭 암호라고도 함 두 개의 키를 사용 공개키 암호는 비교적 새로운 개념이다. 1960년대 후반 영국의 GCHQ(Government Communication Headquaters)에 의해 소개됨 이와도 별도로 1970년도 초반 대학의 연구자들에 의해서도 소개되었다. GCHQ; British intelligence agency responsible for providing signals intelligence (SIGINT) and information assurance to government and armed forces as required under the guidance of the Joint Intelligence Committee. Chapter 4 -- Public Key Cryptography

PKC에 대한 오해 PKC는 대칭키 암호보다 더 안전하다. PKC는 대칭키 암호를 쓸모없는 것으로 만들었다. 두 방식 모두 암호의 안전성은 이것을 깨기 위한 계산의 양에 달려 있다. PKC는 대칭키 암호를 쓸모없는 것으로 만들었다. PKC가 요구하는 계산의 양은 대칭키 보다 훨씬 많기 때문에 PKC를 사용하는데 있어서 장애물이 되고 있다. PKC의 키 분배는 사소한 일이다. PKC의 절차는 대칭키 암호 보다 더 간단하거나 효율적이지 않다. PKC의 키 분배를 위해서 공개키 구조(PKI)가 필요하다. Chapter 4 -- Public Key Cryptography

PKC의 키 메시지는 공개키(public key)로 암호화하고 개인키(private key)로 복호화한다. 키 생성 트랩 도어 단방향 함수(trap door one way function)에 기반을 둔다. Trap door 한 방향으로의 계산은 쉬우나 다른 방향으로의 계산은 힘들다. 예: p와 q가 주어졌을 때, N=pq의 계산은 용이하다. 하지만 N이 주어졌을 때 p와 q를 찾는 것은 쉽지 않다. 메시지는 공개키(public key)로 암호화하고 개인키(private key)로 복호화한다. Chapter 4 -- Public Key Cryptography

PKC를 이용한 메시지 암호화 메시지 M은 Alice의 공개키로 암호화한다. 공개키를 가질 수 있다. M 하지만 Alice의 개인키는 Alice만 갖고 있다. M Chapter 4 -- Public Key Cryptography

이 책에서 PKC와 관련하여 다룰 주제 Knanpsack RSA Diffie-Hellman Key Exchange 안전하지는 않다(insecure) RSA PKC의 대명사처럼 사용됨 Diffie-Hellman Key Exchange 키 교환(key exchange) 알고리즘 ECC(Elliptic Curve Cryptography) Chapter 4 -- Public Key Cryptography

배낭(Knapsack) Chapter 4 -- Public Key Cryptography

Knapsack 문제 (기술적으로, 이것은 “subset sum” 문제이다.) 예 N개의 가중치의 집합 W0,W1,...,Wn-1과 합계 S가 주어졌을 때, 다음의 식을 만족하는 ai  {0,1}를 찾을 수 있는가? S = a0W0+a1W1 +...+ an-1Wn-1 (기술적으로, 이것은 “subset sum” 문제이다.) 예 가중치 (62,93,26,52,166,48,91,141) 문제: 합계 S=302이 되는 subset을 찾으라. 답: 62+26+166+48=302 (general) knapsack (GK)문제는 NP-complete In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC, NP standing for Nondeterministic Polynomial time) is a class of problems having two properties: 1. Any given solution to the problem can be verified quickly (in polynomial time); the set of problems with this property is called NP. 2. If the problem can be solved quickly (in polynomial time), then so can every problem in NP. Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly is one of the principal unsolved problems in computer science today. While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. An expert programmer should be able to recognize an NP-complete problem so that he or she does not unknowingly waste time trying to solve a problem which so far has eluded generations of computer scientists. Instead, NP-complete problems are often addressed by using approximation algorithms in practice. Chapter 4 -- Public Key Cryptography

Knapsack 문제 일반적인 Knapsack(GK) 문제는 풀기 힘들다. 하지만 superincreasing knapsack (SIK) 문제는 풀기 쉽다. SIK: 가중치는 모든 이전의 가중치의 합 보다 크다. 예 가중치 (2,3,7,14,30,57,120,251) 문제: 합이 S=186이 되는 subset을 찾으라. 가장 큰 가중치부터 가장 작은 가중치로 순서대로 비교해 나간다. 답: 120+57+7+2=186 Chapter 4 -- Public Key Cryptography

Knapsack 암호 체계 1. superincreasing knapsack (SIK)을 생성한다. 2. SIK을 “general” knapsack (GK)으로 변환한다. 공개키: GK 개인키: SIK와 conversion factors GK로 암호화한다(용이) 개인키로 복호화하는 것은 용이하다. (암호문을 SIK로 변환한다.) 개인키가 없다면, GK를 풀어야 한다(???) Chapter 4 -- Public Key Cryptography

Knapsack 암호체계 1. SIK: (2,3,7,14,30,57,120,251) m = 41, n = 491 n은 SIK 원소들의 합 보다 크다. 그러면 GK는 다음과 같이 계산할 수 있다; 2 x 41 mod 491 = 82 3 x 41 mod 491 = 123 7 x41 mod 491 = 287 14 x 41 mod 491 = 83 30 x 41 mod 491 = 248 57 x 41 mod 491 = 373 120 x 41 mod 491 = 10 251 x 41 mod 491 = 471 3. GK : (82,123,287,83,248,373,10,471)

Knapsack 암호화 예 개인키: (2,3,7,14,30,57,120,251) m=41, n=491, m1 mod n = 411 mod 491 = 12 공개키: (82,123,287,83,248,373,10,471) 예: 평문 10010110 을 암호화 82 + 83 + 373 + 10 = 548 복호화 S’ · m1 = 548 · 12 = 193 mod 491 = S S = 193인 SIK를 구한다.(쉽다) 120+57+14+2 = 193 평문 10010110 Chapter 4 -- Public Key Cryptography

Knapsack 약점 Trapdoor: modular arithmetic을 사용하여 SIK를 “general” knapsack(GK)으로 변환한다. 단방향: GK로 암호화하기는 쉽지만 반대로 푸는 것은 힘들다; SIK로 푸는 것은 쉽다. knapsack cryptosystem은 안전하지 않다. 1983년에 Apple II 컴퓨터로 해독되었다. 공격은 lattice reduction을 사용하였다. SIK로부터 유도해 내는 “General knapsack”은 충분히 “general”하다고 말 할 수 없다. 이러한 특별한 knapsack은 풀기가 쉽다. Chapter 4 -- Public Key Cryptography

Ron Rivest It’s me!!! RSA Chapter 4 -- Public Key Cryptography

RSA 가장 어려운 계산은? 덧셈 곱셈 소인수분해 Easy Difficult 123 + 654 -------- 777 x 654 --------- 492 615 738 ----------- 80442 소인수분해 221 = ?x? 221/2 = 221/3 = 221/5 = 221/7 = 221/11 = 221/13 = 221 = 13 x 17 Easy Difficult Chapter 4 -- Public Key Cryptography

RSA GCHQ의 Cocks에 의해 만들어졌으며, 이와는 독립적으로 MIT의 Rivest, Shamir, Adleman에 의해서도 만들어졌다. p와 q: 두 개의 큰 소수(prime numbers) N = pq : modulus로 사용 (p-1)(q-1)와 “서로 소수”인 e를 선택한다. ed = 1 mod (p-1)(q-1)인 d를 찾는다. 공개키 : (N,e) 개인키 : d Chapter 4 -- Public Key Cryptography

RSA e 와 N은 공개되어있다. 메시지 M의 암호화 암호문 C의 복호화 C = Me mod N 암호문 C의 복호화 M = Cd mod N e 와 N은 공개되어있다. 만약 N을 소인수 분해(factoring)할 수 있다면, 공격자는 ed = 1 mod (p1)(q1)이므로 e를 사용하여 d를 찾아낼 수 있다. N을 소인수 분해할 수 있다면 RSA를 깰 수 있다. 소인수 분해 이외에 RSA를 깨는 방법이 존재하는지는 아직 알려져 있지 않다. Chapter 4 -- Public Key Cryptography

Does RSA Really Work? 오일러 정리(Euler’s Theorem) 그렇다면 다음이 성립한다: C = Me mod N이 주어질 때, 다음과 같이 되는 것을 보여야 한다. M = Cd mod N = Med mod N where M < N 오일러 정리(Euler’s Theorem) 만약 M과 N이 “서로 소”라면, M(N) = 1 mod N 그렇다면 다음이 성립한다: ed = 1 mod (p  1)(q  1) “mod”의 정의에 의해서 ed = k(p  1)(q  1) + 1 (N) = (p  1)(q  1) 그러면 ed  1 = k(p  1)(q  1) = k(N) Med = M(ed  1) + 1 = MMed  1 = MMk(N) = M(M(N))k mod N = M1k mod N = M mod N Chapter 4 -- Public Key Cryptography

간단한 RSA 사용 예(1) 큰 소수 선택: p = 11, q = 3 그러면 N = pq = 33, (p1)(q1) = 20 e = 3 (20과 서로 소수) 선택 ed = 1 mod 20 가 되는 d = 7를 찾음 공개키: (N, e) = (33, 3) 개인키: d = 7 Chapter 4 -- Public Key Cryptography

간단한 RSA 사용 예(2) 공개키: (N, e) = (33, 3) 개인키: d = 7 메시지 M = 8을 암호화하자. 암호문 C는 다음과 같이 계산된다. C = Me mod N = 83 = 512 = 17 mod 33 암호문 C를 다음과 같이 복호화하여 메시지 M을 구한다. M = Cd mod N = 177 = 410,338,673 = 12,434,505  33 + 8 = 8 mod 33 Chapter 4 -- Public Key Cryptography

Diffie-Hellman Chapter 4 -- Public Key Cryptography

Diffie-Hellman 이것의 안전성은 discrete log problem에 달려있다. GCHQ의 Williamson이 만들었고, 또한 독자적으로 Stanford의 Diffie와 Hellman도 만들었다. “키 교환(key exchange)” 알고리즘 대칭키를 공유하는데 사용한다. 암호화나 서명을 위한 것은 아니다. 이것의 안전성은 discrete log problem에 달려있다. given g, p, and gk mod p → find k Chapter 4 -- Public Key Cryptography

Discrete Logarithm Problem 공개된 값: 큰 소수 p, generator g gk mod p = x Discrete logarithm problem: x, g, p가 주어졌을 때 k를 구하라. Table g=2, p=11 k 1 2 3 4 5 6 7 8 9 10 gk nth element 1st element Cyclic Group G Generator α α1 α2 α3 … αx = β

Diffie-Hellman P는 소수, g는 발생기(generator)라고 하자. Alice는 비밀 값 a를 선택한다. 어떤 x  {1,2,…,p-1}에 대해서 x = gn mod p인 n이 존재한다. Alice는 비밀 값 a를 선택한다. Bob는 비밀 값 b를 선택한다. Alice는 Bob에게 ga mod p를 보낸다. Bob은 Alice에게 gb mod p를 보낸다. 둘 다 비밀 값 gab mod p을 계산하다. 이 비밀 값을 대칭 키(symmetric key)로 사용한다. Chapter 4 -- Public Key Cryptography

Diffie-Hellman Bob과 Alice가 gab mod p을 대칭키로 사용할 때, Trudy는 ga mod p와 gb mod p를 알고 있다. 주의: ga gb mod p = ga+b mod p  gab mod p 만약Trudy가 a와 b를 찾아낼 수 있으면 시스템은 깨진다. 만약 Trudy가 discrete log 문제를 풀 수 있으면, 그는 a 혹은 b를 찾아낼 수 있다. Chapter 4 -- Public Key Cryptography

Diffie-Hellman 공개: g와 p 비밀: Alice의 a, Bob의 b ga mod p gb mod p Alice, a Bob, b Alice의 계산: (gb)a = gba = gab mod p Bob의 계산: (ga)b = gab mod p 비밀키 K: K = gab mod p Chapter 4 -- Public Key Cryptography

man-in-the-middle (MiM) 공격 Diffie-Hellman은 MiM 공격의 위험에 놓인다. ga mod p gt mod p gt mod p gb mod p Alice, a Trudy, t Bob, b Trudy는 Alice와 비밀키를 공유: gat mod p Trudy는 Bob과 비밀키를 공유: gbt mod p Alice와 Bob은 Trudy의 존재를 모른다! Chapter 4 -- Public Key Cryptography

man-in-the-middle (MiM) 공격 해법 교환하는 값(ga mod p, gb mod p)을 대칭키로 암호화하여 보낸다. 교환하는 값을 공개키로 암호화하여 보낸다. 교환하는 값을 개인키로 서명한다. 다른 방법은? Diffie-Hellman에서는 MiM 공격이 가능하다는 것을 명심해야 한다. Chapter 4 -- Public Key Cryptography

공개키 암호의 적용 Chapter 4 -- Public Key Cryptography

PKC의 활용(1): 메시지 암호화 메시지 M은 Alice의 공개키로 암호화한다. 공개키를 가질 수 있다. M 하지만 Alice의 개인키는 Alice만 갖고 있다. M Chapter 4 -- Public Key Cryptography 30

PKC의 활용(2): 전자 서명 전자 서명(Digital Signature) Alice는 자신의 개인키로 암호화하여 서명한다 (Sign). 손으로 서명하는 것과 같다. Bob은 Alice의 공개키로 복호화하여 Alice의 서명을 증명한다. Alice의 개인키는 Alice만 갖고 있으므로 Alice 이외에는 서명을 할 수 없다. Chapter 4 -- Public Key Cryptography 31

PKC가 해결하는 문제들 기밀성 안전하지 않은 채널로 데이터를 전송할 때 안전하지 않은 미디어를 안전한 저장소에 보관할 때 전자서명(Digital signature)은 무결성과 인증과 부인 봉쇄(non-repudiation)를 제공한다. 대칭키로는 부인 봉쇄가 가능하지 않다. 비밀키로 서명한 사람은 나중에 자신이 서명한 것을 부인할 수 없다. 무결성과 인증은 왜 가능한가? Chapter 4 -- Public Key Cryptography

부인 봉쇄(non-repudiation) Alice는 Bob으로부터 주식 100주를 주문했다. Alice는 대칭키로 MAC을 계산했다. 그런데 주식값이 떨어지자, Alice는 자신이 주문한 것을 부인했다. Bob은 Alice가 주문했다는 사실을 증명할 수 있을까? No! Bob역시 대칭키를 알고 있기 때문에 주문을 조작할 수 있다. 문제: Bob은 Alice가 주문한 것을 알고 있다. 하지만 그것을 증명할 수 없다. Chapter 4 -- Public Key Cryptography

부인 봉쇄(Non-repudiation) Alice는 Bob으로부터 주식 100주를 주문했다. Alice는 자신의 개인키로 주문에 서명을 했다. 그런데 주식값이 떨어지자, Alice는 자신이 주문한 것을 부인했다. Bob은 Alice가 주문한 것을 증명할 수 있을까? Yes! Alice의 개인키를 갖고 있는 사람 만이 주문에 서명을 할 수 있다. 물론 Alice의 개인키가 도난당하지 않았다는 가정을 해야 한다.(키 폐기 문제) Chapter 4 -- Public Key Cryptography

서명하고 암호화 vs 암호화하고 서명 Chapter 4 -- Public Key Cryptography

공개키 표기법 메시지 M을 Alice의 개인키로 서명(Sign) Alice’s private key: [M]Alice 메시지 M을 Alice의 공개키로 암호화 Alice’s public key: {M}Alice 그러면 {[M]Alice}Alice = M [{M}Alice]Alice = M Chapter 4 -- Public Key Cryptography

기밀성과 부인 봉쇄 기밀성과 부인 봉쇄를 동시에 하고 싶다고 하자. 공개키 암호는 이 두 가지 목표를 이룰 수 있을까? Alice는 Bob에게 다음의 메시지를 보낸다. 서명하고 임호화 {[M]Alice}Bob 암호화하고 서명 [{M}Bob]Alice 어떤 순서로 하는가에 따라서 달라질까? Chapter 4 -- Public Key Cryptography

서명하고 암호화 M = “I love you” Q: 무엇이 문제인가? A: Charlie는 암호를 오해한다! {[M]Alice}Bob {[M]Alice}Charlie Alice Bob Charlie Q: 무엇이 문제인가? A: Charlie는 암호를 오해한다! Chapter 4 -- Public Key Cryptography

암호화하고 서명 M = “My theory, which is mine….” Charlie는 M을 복호화할 수 없다. [{M}Bob]Alice [{M}Bob]Charlie Alice Charlie Bob Charlie는 M을 복호화할 수 없다. Q: 무엇이 문제인가? A: Bob은 암호를 오해한다! Chapter 4 -- Public Key Cryptography

공개키 구조(PKI) Chapter 4 -- Public Key Cryptography 40

공개키 인증서(Certificate) Bob은 어떻게 Alice의 공개키를 알 수 있는가? Alice는 자신이 개인키와 공개키를 만들어서 Bob에게 이것이 나의 공개키라고 알려 주는가? 그러면 Bob은 그것이 Alice의 공개키라고 신뢰할 수 있을까? 인증서에는 Alice의 이름과 Alice의 공개키(그리고 다른 정보)를 포함하고 있다. 인증서를 제공하는 발행자(Certificate Authority)가 이것을 보증하기 위해서 인증서에 서명을 한다.(예를 들면 VeriSign) Bob은 발행자의 공개키를 사용하여 인증서의 서명을 증명할 수 있다. Chapter 4 -- Public Key Cryptography 41

인증 기관(Certificate Authority) 인증기관 (CA)은 신뢰할 수 있는 제3자(TTP)로 인증서를 발행하고 서명한다. 인증서의 서명을 증명하는 것은 이에 대응하는 개인키 소유자의 존재를 증명하는 것이다. 인증서는 공개되어 있다! CA가 실수를 한다면 큰 문제이다.(CA는 이전에 Microsoft 인증서를 다른 사람에게 발행한 적이 있다!) 인증서의 형식은 X.509으로 정해져 있다. Chapter 4 -- Public Key Cryptography 42

X.509 인증서 예(1) 다음 그림은 www.freesoft.org의 공개키를 인증하는 인증서이다. 인증 기관은 Thwate Thwate는 인증서를 인증하기 위해서 인증서의 마지막 부분에 자신의 개인키로 서명을 하였다(signature). 이 인증서를 받는 사람은 Thwate의 공개키로 인증서의 마지막 부분의 signature를 확인할 수 있다.

X.509 인증서 예(2) 그러면, 사용자는 Thwate의 공개키를 어떻게 알 수 있는가?

X.509 인증서 예(3) 그러면 이 인증서를 받은 사용자는 Thwate가 신뢰할 수 있는 인증 기관인지 어떻게 확신할 수 있는가? 신뢰할 수 있는 기관의 Root certificate는 브라우저에 사전에 설치되어 있다. 이러한 인증 기관들은 브라우저에 사전에 설치될 수 있는 특권을 사게 된다.

PKI 공개키 구조 (PKI)는 공개키 암호 방식을 안전하게 사용하기 위해 필요한 모든 요소로 구성된다. 키 생성과 관리 인증 기관(CA) 인증 폐기 (CRLs), 등등 PKI에 대한 일반적인 표준은 없다. 몇가지 “신뢰 모델(trust model)”을 검토해 보자. Chapter 4 -- Public Key Cryptography

PKI 신뢰 모델 완전 독점 모델(Monopoly model) 하나의 보편적인 신뢰 기관이 CA로서 모든 것을 관장한다. 당연히 VeriSign 같은 기관을 가장 선호할 것이다. 만약 CA가 손상되면 큰 문제 만약 이 CA를 신뢰하지 못하면 큰 문제! Chapter 4 -- Public Key Cryptography

PKI 신뢰 모델 소수 독점 모델(Oligarchy) 다수의 신뢰할 수 있는 CA들이 존재 오늘날 브라우저에서 사용하는 접근 방법 브라우저는 단순히 서명을 증명하기 위해서 80개 이상의 인증서를 가질 수 있다! 사용자는 어떤 CA들을 신뢰할 수 있는지 결정해야 한다. Chapter 4 -- Public Key Cryptography

PKI 신뢰 모델 완전 자유 모델(Anarchy model) 이외에 많은 다른 신뢰 모델에 존재할 수 있다. 모두가 CA가 될 수 있다! 사용자는 어떤 “CA들”을 신뢰할 수 있는지 결정해야 한다. 이 방법은 PGP에서 사용되고 있다.(Web of trust) 왜 이것을 “무정부(anarchy)”라고 부르는가? Frank가 어떤 인증서를 서명했는데 나는 Frank를 모른다. 하지만 나는 Bob을 신뢰하고 Bob은 Alice를 믿을 수 있다고 하고 Alice는 Frank를 보증한다. 나는 Frank를 신뢰해야 하는가? 이외에 많은 다른 신뢰 모델에 존재할 수 있다. Chapter 4 -- Public Key Cryptography

현실 세계에서의 암호화(기밀성) Chapter 4 -- Public Key Cryptography

대칭키 vs 공개키 대칭키의 장점 공개키의 장점 속도 공개키 구조 (PKI)가 필요없다. 서명 (부인 봉쇄) 공유된 비밀키가 필요없다. Chapter 4 -- Public Key Cryptography

대칭키 vs 공개키 암호화 비교 공개키 암호 대칭키 암호 믿을 수 있는(authentic) 공개키 필요 공유하는 비밀키가 필요 고도의 안전을 위해서 2048 bit key (RSA) 필요 (2010년) ~100 signatures/s ~1000 verify/s (RSA) on 1GHz processor ~10x speedup in HW 대칭키 암호 공유하는 비밀키가 필요 고도의 안전을 위해서 80 bit key 필요 (2010년) ~1,000,000 ops/s on 1GHz processor >100x speedup in HW

RSA로 큰 파일을 암호화한다면? 1024-bit RSA 암호화할 때 시간 1024-bit RSA 복호화할 때 시간 ~1 ms on 1 GHz Pentium 1024-bit RSA 복호화할 때 시간 ~10 ms on 1 GHz Pentium 1 Mbyte file을 암호화하는 시간은? 1024 bits / RSA operation = 128 bytes = 27 1 Mbyte = 220 시간: 220 / 27 * 1ms = 213 ms = 8 초! 더 빠른 방법은? First, pick random key, encrypt key with RSA, then encrypt file with block cipher.

결론은? 공개키 방식으로 암호화는 비효율적이다. 대칭키 방식의 암호화는 공개키 방식에 비해서 빠르게 이루어진다. 암호화 시간이 너무 많이 걸린다. 대칭키 방식의 암호화는 공개키 방식에 비해서 빠르게 이루어진다. 하지만, 대칭키 방식은 대칭키를 어떻게 설정(분배)하는가의 문제가 있다. 그러면 어떻게 할 것인가? Chapter 4 -- Public Key Cryptography

현실 세계에서의 암호화(기밀성) 혼합된 암호 체계 Bob은 Alice와 말하고 있다고 확신할 수 있는가? {K}Bob 공개키는 키를 설정(교환)하기 위해서 사용한다. 대칭키는 데이터를 암호화하는데 사용한다. {K}Bob [{K}Bob]Bob E(Bob’s data, K) E(Alice’s data, K) Alice Bob Bob은 Alice와 말하고 있다고 확신할 수 있는가? Chapter 4 -- Public Key Cryptography

대칭키의 교환(분배) 대칭키를 배울 때 마지막에 대칭키의 분배 문제는 나중에 얘기하겠다고 했다. 이제까지 배운 것을 갖고 어떻게 대칭키을 분배할 수 있는지 정리해 보자. 직접 교환(분배): 송수신자가 직접 교환 혹은 미리 설정(분배)해 놓는다. 공개키로 암호화하여 전달한다. Diffie-Hellman에 의해 키 교환