I부 암호

공개키 암호 4장

공개키 암호 두 개의 키 트랩도어 단방향 함수를 기반 송신자는 수령자의 공개키로 암호화 수신자는 자신의 개인키로 복호화 한 방향은 계산하기가 용이 다른 방향은 계산하기가 난해 “트랩”은 키를 생산하기 위해 사용 예제: 주어진 p와 q에서, N=pq 는 계산하기가 용이하나 주어진 N에서 p와 q를 찾기는 난해하다.

공개키 암호 암호화 전자서명 밥의 공개키로 M을 암호화 한다고 가정 밥의 개인키로만 M을 찾을 수 있도록 복호화 가능 개인키로 “암호화”함으로 서명 서명을 확인하기 위해서는 누구나 공개키로 “복호화” 개인키를 가진 자만이 서명이 가능 손으로 서명하는 것과 유사

배낭 문제 주어진 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인 부분집합을 찾으라 해답: 62+26+166+48=302 일반적인 배낭은 NP-complete

4장. 공개키 암호 배낭 암호

배낭 문제 일반 배낭은 풀기가 어렵다. 그러나 수퍼증가 배낭(SIK)은 쉬운 문제 SIK는 각 무게가 먼저 무게들의 합보다 큼 예제 무게들 (2,3,7,14,30,57,120,251) 문제: 무게 합이 S=186인 부분집합을 찾아라. 가장 큰 무게에서 가장 작은 무게로 시도 해답: 120+57+7+2=186

배낭 암호 1. 수퍼증가 배낭(SIK)을 생산 2. SIK를 일반 배낭(GK)로 변환 3. 공개키: GK

배낭 암호 (2,3,7,14,30,57,120,251)를 SIK라고 하자 서로소인 m=41, n=491그리고 n이 SIK 요소들의 합보다 큰 수를 선정 일반 배낭으로 변환 2  41 mod 491 = 82 3  41 mod 491 = 123 7  41 mod 491 = 287 14  41 mod 491 = 83 30  41 mod 491 = 248 57  41 mod 491 = 373 120  41 mod 491 = 10 251  41 mod 491 = 471 일반 배낭: (82,123,287,83,248,373,10,471)

배낭 예제 개인키: (2,3,7,14,30,57,120,251) m1 mod n = 411 mod 491 = 12 예제: 평문 10010110 암호화 82 + 83 + 373 + 10 = 548 복호화 548 · 12 = 193 mod 491 SIK (S=193) 문제를 풀어라. 평문 10010110을 찾을 수 있음

배낭 약점 트랩도어: SIK를 모듈로 연산을 사용하여 “일반 배낭”으로 변환 이 배낭 암호는 안전하지 못함. 1983년 Apple II 컴퓨터로 해독 공격은 격자줄이기(lattice reduction) 이용 “일반 배낭”은 충분히 일반적이지 못함! 이러한 특수한 배낭은 쉽게 풀릴 수 있음!

RSA 콕스(GCHQ)와 또 독립적으로 리베스트, 샤미르 그리고 애들맨(MIT)에 의해 발명 p와 q를 큰 소수라고 하자. N = pq 를 모듈로스라 하자 e를 (p-1)(q-1)에 서로 소로 선정 ed = 1 mod (p-1)(q-1)를 만족하는 d로 선정 공개키: (N,e) 개인키: d

4장. 공개키 암호 RSA

RSA 메시지 M을 암호화 암호문 C를 복호화 E와 N은 공개키임을 상기할 것 C = Me mod N 암호문 C를 복호화 M = Cd mod N E와 N은 공개키임을 상기할 것 ed = 1 mod (p1)(q1) 이므로, 만약 공격자가 N을 인수 분해할 수 있으면, e를 사용하여 쉽게 d를 찾을 수 있음. 모듈로의 인수분해는 RSA를 해독 인수분해만이 유일하게 RSA를 해독하는 방법인지는 알려지지 않았음

RSA가 동작이 되는가? 주어진 C = Me mod N 에서 다음을 보여야 한다 오일러 정리 이용 사실: M = Cd mod N = Med mod N 오일러 정리 이용 x가 n과 서로 소이면 x(n) = 1 mod n 사실: ed = 1 mod (p  1)(q  1) “mod”정의에 의해, ed = k(p  1)(q  1) + 1 (N) = (p  1)(q  1) Then 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

간단한 RSA 예제 RSA 예제 공개키: (N, e) = (33, 3) 개인키: d = 7 큰 소수 p = 11, q = 3를 선정 그러면 N = pq = 33 그리고 (p1)(q1) = 20 e = 3 선정(20과 서로 소) ed = 1 mod 20을 만족하는 d를 찾으면, d = 7 공개키: (N, e) = (33, 3) 개인키: d = 7

간단한 RSA 예제 공개키: (N, e) = (33, 3) 개인키: d = 7 메시지: M = 8 암호문 C C 복호화 C = Me mod N = 83 = 512 = 17 mod 33 C 복호화 M = Cd mod N = 177 = 410,338,673 = 12,434,505  33 + 8 = 8 mod 33

보다 효율적인 RSA (1) 모듈로 지수 예제 개선된 방법: 제곱의 반복 절대로 거대한 숫자를 다루지 말 것! 520 = 95367431640625 = 25 mod 35 개선된 방법: 제곱의 반복 20 = 10100 base 2 (1, 10, 101, 1010, 10100) = (1, 2, 5, 10, 20) 참고: 2 = 1 2, 5 = 2  2 + 1, 10 = 2  5, 20 = 2  10 51= 5 mod 35 52= (51)2 = 52 = 25 mod 35 55= (52)2  51 = 252  5 = 3125 = 10 mod 35 510 = (55)2 = 102 = 100 = 30 mod 35 520 = (510)2 = 302 = 900 = 25 mod 35 절대로 거대한 숫자를 다루지 말 것!

보다 효율적인 RSA (2) 모든 사용자가 e = 3을 사용 (그러나 동일한 N 이나 d를 사용하지 않음) 공개키 연산은 단지 두 번의 곱만이 필요 개인키 연산은 여전히 “고가” 만약 M < N1/3 이면, C = Me = M3 이 되어 세제곱근 공격이 가능 어떤 M 에 대해서도, 만약 C1, C2, C3 가 3 사용자에게 전송되면, 세제곱근 공격이 가능 (중국인 나머지 정리를 사용) 임의 비트를 메시지에 첨부함으로 세제곱근 공격을 방지 Note: e = 216 + 1 도 대중적으로 사용 (중국인 나머지 정리 공격 방지)

4장. 공개키 암호 디피-헬먼

디피-헬먼 윌리럼슨 (GCHQ), 그리고 독립적으로 디피와 헬먼(Stanford)에 의해 발명 “키 교환” 알고리즘 공유하는 대칭키를 설정하기 위해 사용 암호화나 서명을 위해 사용되지 않음 안전성은 이산 로그 문제에 기반 주어진 g, p, 그리고gk mod p 에서 k를 찾아라!

디피-헬먼 p 를 소수 g 를 생성자라고 하자. 앨리스가 비밀값 a 를 선정 밥이 비밀값 b 를 선정 어떤 x  {1,2,…,p-1} 대해서도 x = gn mod p 를 만족하는 n 이 존재 앨리스가 비밀값 a 를 선정 밥이 비밀값 b 를 선정 앨리스가 ga mod p 을 밥에게 전송 밥이 gb mod p 를 앨리스에서 전송 둘 모두 공유 비밀값 gab mod p 를 계산 공유 비밀값은 대칭키로 사용

디피-헬먼 밥과 앨리스가 gab mod p 를 대칭키로 사용한다고 가정 트루디는 ga mod p 와 gb mod p를 볼수 있음 참고: ga gb mod p = ga+b mod p  gab mod p 만약 트루디가 a 또는 b를 찾으면, 체계는 해독 만약 트루디가 이산로그 문제를 풀 수 있으면 a 또는 b 를 찾을 수 있음

디피-헬먼 공개: g 와 p 비밀: 앨리스의 지수 a, 밥의 지수 b ga mod p gb mod p 앨리스, a 밥, b 앨리스는 (gb)a = gba = gab mod p 를 계산 밥은 (ga)b = gab mod p 를 계산 K = gab mod p 는 대칭키로 사용 가능

디피-헬먼 중간자 공격 (MiM) 에 취약 ga mod p gt mod p gt mod p gb mod p 앨리스, a 트루디가 비밀값 gat mod p 를 앨리스와 공유 트루디가 비밀값 gbt mod p 를 밥과 공유 앨리스와 밥은 트루디의 존재를 알지 못함!

디피-헬먼 MiM 공격을 어떻게 방지할 수 있나? 디피-헬먼 에서는 MiM공격에 대해 잘 알고 있어야만 함. 대칭키로 DH 교환 값을 암호화 공개키로 DH 교환 값을 암호화 DH 교환 값을 개인키로 서명 또 다른 방법은? 디피-헬먼 에서는 MiM공격에 대해 잘 알고 있어야만 함.

4장. 공개키 암호 타원곡선 암호

타원곡선 암호 (ECC) “타원곡선”은 암호체계가 아니다. 타원곡선은 공개키 체계를 수학적으로 수행하는 한 가지 다른 방법 타원곡선에는 DH, RSA 버전 등이 있다 타원곡선은 다른 체계에 비해 효율적 일 수 있다 같은 비밀성을 위해 더 적은 비트를 사용 그러나 연산들은 더욱 복잡

타원곡선이란 무엇인가? 타원 곡선 E는 아래 방정식의 그래프 y2 = x3 + ax + b “무한대의 점”도 포함 타원곡선은 무엇처럼 보이는가? 다음 슬라이드를 보자!

타원곡선 그림 타원곡선 만약 P1 과 P2 가 E 상에 있으면, 그림에서 보는 바와 같이 다음을 정의할 수 있다. E: y2 = x3 - x + 1 만약 P1 과 P2 가 E 상에 있으면, 그림에서 보는 바와 같이 다음을 정의할 수 있다. P3 = P1 + P2 덧셈이 필요한 모든 것 P1 P2 P3 x y

타원곡선상의 점 y2 = x3 + 2x + 3 (mod 5) 을 고려해 보자 x = 0  y2 = 3  no solution (mod 5) x = 1  y2 = 6 = 1  y = 1,4 (mod 5) x = 2  y2 = 15 = 0  y = 0 (mod 5) x = 3  y2 = 36 = 1  y = 1,4 (mod 5) x = 4  y2 = 75 = 0  y = 0 (mod 5) 그러면 타원곡선 상의 점들은 (1,1) (1,4) (2,0) (3,1) (3,4) (4,0) 과 무한점: 

타원곡선 수학 덧셈: y2 = x3 + ax + b (mod p) P1=(x1,y1), P2=(x2,y2) P1 + P2 = P3 = (x3,y3) 여기서 x3 = m2 - x1 - x2 (mod p) y3 = m(x1 - x3) - y1 (mod p) 그리고 m = (y2-y1)(x2-x1)-1 mod p, if P1P2 m = (3x12+a)(2y1)-1 mod p, if P1 = P2 특수한 경우: 만약 m 이 무한대인 경우 P3 = , 그리고  + P = P 모든 P에 대해

타원곡선 덧셈 y2 = x3 + 2x + 3 (mod 5)를 생각해 보자. 곡선상의 점들은 (1,1) (1,4) (2,0) (3,1) (3,4) (4,0) 그리고  (1,4) + (3,1) = P3 = (x3,y3)? m = (1-4)(3-1)-1 = -32-1 = 2(3) = 6 = 1 (mod 5) x3 = 1 - 1 - 3 = 2 (mod 5) y3 = 1(1-2) - 4 = 0 (mod 5) 이 곡선상에서는, (1,4) + (3,1) = (2,0)

ECC 디피-헬먼 공개: 타원곡선과 곡선상의 점 (x,y) 비밀: 앨리스의 A 와 밥의 B 앨리스가 A(B(x,y))를 계산 A(x,y) B(x,y) 앨리스, A 밥, B 앨리스가 A(B(x,y))를 계산 밥이 B(A(x,y))를 계산 AB = BA 이므로 이들 값은 동일

ECC 디피-헬먼 공개: 곡선 y2 = x3 + 7x + b (mod 37) 과 점 (2,5)  b = 3 앨리스의 비밀: A = 4 밥의 비밀: B = 7 앨리스가 밥에게 전송: 4(2,5) = (7,32) 밥이 앨리스에게 전송: 7(2,5) = (18,35) 앨리스가 계산: 4(18,35) = (22,1) 밥이 계산: 7(7,32) = (22,1)

4장. 공개키 암호 공개키의 용도

공개키의 용도들 비밀성 인증 (나중에) 전자 서명은 무결성과 부인봉쇄를 제공 데이터를 안전하지 않은 채널로 전송 안전하지 않은 미디어에 안전하게 저장 인증 (나중에) 전자 서명은 무결성과 부인봉쇄를 제공 대칭키로 부인봉쇄는 불가

부인봉쇄-부정 앨리스는 밥으로 부터 100장의 주식을 주문 앨리스는 대칭키를 이용하여 MAC 을 계산 주식값 폭락, 앨리스는 주문하지 않았다고 주장 밥이 앨리스의 주문을 증명할 수 있는가? 할 수 없다! 밥도 역시 대칭키를 알고 있기 때문에 메시지를 속일 수가 있다 문제: 밥은 앨리스가 주문을 한 것을 알고 있지만 증명할 수가 없다.

부인 봉쇄 앨리스가 100장의 주식을 밥에게서 주문 앨리스는 그녀의 개인키로 주문을 서명 주식값 폭락, 앨리스는 주문하지 않았다고 주장 밥이 앨리스의 주문을 증명할 수 있는가? 할 수 있다! 앨리스의 개인키를 가진 사람만이 그 주문에 서명할 수 있다. 위의 경우 앨리스의 비빌키가 도난 당하지 않았다고 가정 (폐기 문제)

4장. 공개키 암호 선서명 후암호화 vs. 선암호화 후서명

공개키 표기법 서명: 앨리스의 개인키로 메시지 M 서명: [M]앨리스 그러면 {[M]앨리스}앨리스 = M [{M}앨리스]앨리스 = M

비밀성과 부인봉쇄 비밀성과 부인봉쇄 둘 다 원한다고 가정 공개키 암호로 두 가지 모두 가능한가? 앨리스가 밥에게 메시지 전송 선서명 후암호화 {[M]앨리스}밥 선암호화 후서명 [{M}밥]앨리스 순서가 의미가 있는 것인가?

Sign and Encrypt M = “나는 당신을 죽도록 사랑합니다.” 문제: 무엇이 문제인가? 앨리스 밥 챨리 문제: 무엇이 문제인가? 답: 챨리는 암호를 잘못 이해한다!

선암호 후서명 M = “이성과 열정은…” 찰리는 M을 복호화 할 수 없음에 유의 문제: 문제가 무엇인가? 앨리스 챨리 밥 찰리는 M을 복호화 할 수 없음에 유의 문제: 문제가 무엇인가? 답: 밥은 암호를 잘못 이해하고 있다!

4장. 공개키 암호 공개키 기반체계

공개키 인증서 사용자의 성명과 공개키를 포함(다른 정보도 포함 가능) 인증서는 이 증서를 보증할 발행자가 서명 (예: VeriSign 회사) 인증서의 서명은 서명자의 공개키로 확인

인증기관 인증기관은 인증서에 서명하고 그 인증서를 발행하는 제3의 신뢰성 있는 기관 서명을 확인하는 것은 해당되는 개인키의 소유자의 동일성 여부를 확인 서명을 확인하는 것이 인증서의 공급원을 확인하는 것이 아님! 인증서는 공개! 만약 CA가 잘못하면 큰 문제가 발생(예를 들면 CA가 다른 사람에게 마이크로 소프트의 인증을 발행!) 인증서의 일반 양식은 X.509

PKI 공개키 기반체계는 공개키 암호를 안전하게 사용하는데 필요한 모든 요소들로 구성 PKI 일반적인 표준을 없음 키 생산과 관리 인증 기관 인증 폐기 등 PKI 일반적인 표준을 없음 몇 가지 “신뢰 모텔들”을 검토

PKI 신뢰 모델 완전 독점 모텔 모든 분야의 신뢰 조직은 하나의 CA만을 사용 VeriSign을 가장 선호 (당연한 이유)

PKI 신뢰 모델 소수 독점 모델 다수의 신뢰받는 CA 이 접근 방법이 현재 브라우즈에서 사용 브라우저는 서명들을 확인하기 위해 80개 이상의 인증서를 보유! 사용자는 신뢰하는 CA를 결정할 수 있음

PKI 신뢰 모델 완전 자유 모델 많은 다른 PKI 신뢰 모델들 존재 모든 사람이 하나의 CA! 사용자가 어떤 “CAs”를 신뢰할 것인지 결정 이 접근 방법은 PGP (신뢰의 웹) 에서 사용 왜 이 방법을 “완전 자유” 모델이라고 부르는가? 인증서가 프랭크에 의해 서명되었고 A는 프랭크를 모른다고 가정. 그러나 A는 밥을 신뢰하고 밥은 앨리스를 신뢰하고 앨리스는 프랭크를 보증한다면, A는 프랭크를 신뢰해야 하는가? 많은 다른 PKI 신뢰 모델들 존재

4장. 공개키 암호 실세계에서 보안성

대칭키 대 공개키 대칭키 속도 공개키 기반체계(PKI) 불필요 공개키Public Key 서명 (부인봉쇄) 키 공유 불필요

표기법 재정리 공개키 암호 표기 개인키 암호 표기 앨리스의 개인키로 메시지 M 서명 앨리스의 공개키로 메시지 암호화 평문 P를 대칭키 K로 암호화 C = E(P,K) 암호문 C를 대칭키 K로 복호화 P = D(C,K)

실세계 보안성 혼합 암호체계 밥이 앨리스와 안전하게 대화할 수 있는가? 키 설정을 위한 공개키 암호 데이터 암호를 위한 대칭키 암호 다음의 경우 {K}밥 E(밥의 데이터, K) E(앨리스의 데이타, K) 앨리스 밥 밥이 앨리스와 안전하게 대화할 수 있는가?