제9장 공개키 암호 (I) Public-key Cryptography 2007. 11.

목 차 9.1 공개키 암호시스템 원리 (Principles of Public-Key Cryptosystems) 9.2 RSA 알고리즘 (The RSA Algorithm) 9.3 ElGamal 암호알고리즘 (The ElGamal Algorithm) 9.4 Knapsack 암호 알고리즘 (The Knapsack Algorithm) 2

9.1 공개키 암호 시스템의 원리 9.1.1 공개키 암호 시스템 9.1.2 공개키 암호 시스템의 응용 9.1.3 공개키 암호를 위한 요구사항 9.1.4 공개키 암호 분석 3

9.1 공개키 암호 시스템의 원리 암호학 역사에서 최대의 혁명적 발견 대칭키 암호 방식의 문제점 공개키 암호 방식 1976년 Diffie 와 Hellman 에 의해 제기 대칭키 암호 방식의 문제점 치환과 순열기법을 기본방법으로 사용 키 분배의 어려움과 디지털 서명이 불가능 공개키 암호 방식 정수론의 소인수 분해와 이산대수 어려움 근거 키 분배문제 해결 디지털서명 용이: 문서 서명효과, 발신처 인증, 부인봉쇄 4

9.1 공개키 암호 시스템의 원리 공개키 암호방식에 대한 오해 관용(대칭키) 암호방식보다 안전 안전성은 키 길이와 암호해독 계산시간의 문제 관용(대칭키) 암호를 무력화시킬 범용 기술 키 관리와 서명에 효과적 응용 관용(대칭키) 방식보다는 계산 부하가 큼 키 분배 문제 해결 간단하거나 효율적이라고 단정 불가 별도의 관리 프로토콜 필요 5

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

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

9.1.1 공개키 암호 시스템(cont’) 8

9.1.1 공개키 암호 시스템(cont’) 9

9.1.1 공개키 암호 시스템(cont’) 관용 암호화 공개키 암호 비교 관용(대칭키) 암호 공개키 암호 관용(대칭키) 암호 공개키 암호 암호/복호에 동일키와 동일 알고리즘을 사용 수신자와 송신자간의 키 교환이 필요 비밀키는 비밀로 유지하여야 함 키 분배의 어려움과 디지털 서명이 불가능함 계산 속도가 빠름 암호/복호에 서로 다른 키를, 알고리즘은 동일 사용 수신자와 송신자는 연관된 키 쌍 중 하나를 알아야 함 키 쌍 중 개인키는 비밀로 유지하여야 함 디지털 서명 가능 계산 속도가 느림 10

9.1.1 공개키 암호 시스템(cont’) 공개키 암호 시스템의 보안 서비스 기밀성 : 그림 9.2 수신자의 공개키를 이용하여 암호화 인증 : 그림 9.3 (기밀성은 보장되지 않음) 송신자의 비밀키를 이용하여 암호화 기밀성과 인증 : 그림 9.4 송신자의 비밀키를 이용하여 암호화한 후 수신자의 비밀키를 이용하여 암호화 11

9.1.1 공개키 암호 시스템(cont’) 공개키 암호 시스템 : 기밀성 수신자의 공개키로 암호화함으로써 메시지 기밀성 제공 12

9.1.1 공개키 암호 시스템(cont’) 공개키 암호 시스템 : 인증 송신자의 개인키로 서명함으로써 송신자 인증 제공 13

9.1.1 공개키 암호 시스템(cont’) 공개키 암호 시스템 : 기밀성과 인증 송신자의 개인키로 서명, 수신자의 공개키로 암호화하여 기밀성과 인증 제공 14

9.1.2 공개키 암호 시스템 응용 A: C = EKUb[P] B: P = DKPb[C] 공개키 암호 시스템의 사용 분야 암호/ 복호 (수신자의 공개키로 메시지 암호) A: C = EKUb[P] B: P = DKPb[C] 디지털 서명 (송신자의 개인키로 메시지 서명) A: C = EKPa[P] B: P = DKUa[C] 키 교환 (세션키를 교환하기 위해 사용) 공개키 암호 알고리즘의 응용 15

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

9.1.4 공개키 암호 분석 전사적 공격에 취약 공개 키로부터 개인 키를 계산하는 방법 키의 크기를 크게 함으로써 방지 상대적으로 속도가 느려지므로 실제 사용을 위하여는 적절히 작아야 함 ⇒ 현재 응용이 서명과 키 관리로 한정되는 이유임 공개 키로부터 개인 키를 계산하는 방법 수학적으로 계산이 상대적으로 어렵거나 불가능 해야 함 가능한 메시지 추측 공격(메시지 길이가 작을 때) 17

9.2 RSA 알고리즘 9.2.1 알고리즘의 설명 9.2.2 계산적 측면 9.2.3 RSA의 안전성 18

9.2 RSA 알고리즘 특징 미국 MIT의 Ron Rivest, Adi Shamir과 Leonard Adleman가 공동 개발 공개키 암호방식의 요구사항을 만족하는 최초방식 1978년에 공포된 블록 암호 방식 평문과 암호문은 어떤 정수 n에 대하여 0 ~ (n-1) 사이의 정수임 평문 블록은 키 길이보다 작아야 함 비밀키 암호방식(DES)보다 계산이 늦음 소인수 분해의 어려움에 근거 19

9.2.1 알고리즘의 설명 RSA 암복호화 방식 각 블록은 어떤 수 n보다 작은 이진 값을 가짐 블록 사이즈는 log2(n)과 같거나 작음 실제 블록 사이즈 : 2k 비트임(2k < n ≤ 2k+1) 공개키 : KU = {e, n}, 개인키 : KR = { d, n } 암호화와 복호화 C = Me mod n M = Cd mod n = (Me)d mod n = Med mod n 알고리즘의 조건 ∀ M<n, M = Med mod n를 만족하는 e, d, n을 찾는 것이 가능 ∀ M<n, Cd 와 Me의 계산이 용이 주어진 e와 n에 대하여 d를 찾기 어려움 20

9.2.1 알고리즘의 설명(cont’) 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과 서로소인 양의 정수가 되는 오일러 totient 함수 ( p,q가 솟수일 경우, ф(pq) = (p-1)(q-1) ) ed = k ф(n) + 1 ed = 1 mod ф(n) d = e-1 mod ф(n) ⇒ e와 d는 mod ф(n)에 곱셈 역원 (e와 d가 ф(n)에 서로소인 경우에만 참) 21

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

9.2.1 알고리즘의 설명(cont’) RSA 알고리즘의 동작 예 공개키와 개인키 생성 두 솟수 p = 7, q = 17 을 선택 n = pq = 7 Í 17 = 119 계산 ф(n) = (p-1)(q-1) = 96 계산 ф(n) = 96’과 서로 소이고 ф(n)보다 작은 e 선택 ( e = 5 ) de ≡1 (mod 96) 이고 d < 96 인 d를 결정 (d = 77) ⇒ 공개키 KU = {5, 119}, 개인키 KR = {77, 119} 23

9.2.1 알고리즘의 설명(cont’) 2) 암호화와 복호화 평문 메시지 M = 19 일 경우 암호문 : 195 = 2476099 = 66 mod 119  66 복호문 : 6677 = 19 mod 119  19 24

9.2.2 계산적인 측면 계산량을 줄이는 방법 모듈러 연산의 특징 이용 1) 암호화와 복호화 계산량을 줄이는 방법 모듈러 연산의 특징 이용 [(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번의 곱셈 ab mod n 계산 알고리즘 : 그림 9.7 25

9.2.2 계산적인 측면(cont’) 2) 키 생성 키 생성시 소요 작업 충분히 큰 두 소수 p와 q의 결정 e와 d 중 하나를 선택하고 나머지 하나를 계산 랜덤한 큰 솟수를 찾는 방법 (확률적 검사법) 1. 랜덤하게 홀수 n을 선택 2. 랜덤하게 a<n인 정수 a를 선택 3. Miller-Rabin과 같은 확률적 소수 판정법을 수행 4. n이 충분한 횟수의 검사에 통과하면 n을 수용, 소수 생성을 위한 검사 횟수 N에 가까운 소수는 (ln N)에 대하여 평균 1회 나타남 예 : 2200 범위의 소수  ln(2200)/2 = 70 회 정도 검사를 시행 26

9.2.3 RSA의 안전성 전사적 공격 큰 키를 사용하여 방지 인수 n를 두 소인수로 인수 분해 큰 값에 대한 두 소수의 곱을 인수 분해하는 적당한 알고리즘이 없음 p와 q을 결정하지 않고 직접 ф(n)을 추측하여 결정 인수 분해만큼 어려움 ф(n)을 결정하지 않고 직접 e, d를 추측하여 결정 27

9.2.3 RSA의 안전성(cont’) 인수분해 시간 제안 사항(인수 분해를 어렵게) n = 10150 ~ 10200 p, q = 1075 ~ 10100 (p-1), (q-1) 은 큰 솟수 gcd(p-1,q-1)은 작아야 e <n 이고 d<n1/4 일 때 d 는 쉽게 결정되므로 유의 필요 28

9.3 ElGamal 암호 방식 이산대수 문제 이용 y  gx mod p g : 원시원소 p : 소수 29

9.3 ElGamal 암호 방식 (계속) 이산대수 문제 예 Z23 51  5 58  16 515  19 mod 23 30

9.3 ElGamal 암호 방식 (계속) 암호화 k  RZp (p : 소수) K  yBk (yB  g XB mod p) C1  g k mod p C2  KM mod p (M : 평문) C = C1 || C2 31

9.3 ElGamal 암호 방식 (계속) 복호화 K  (g k) XB mod p  C1 XB mod p M  C2 / K mod p 32

9.3 ElGamal 암호 방식 (계속) C ElGamal 암호 방식의 구성 가입자 A 공개정보 g , p, yA, yB yA  gXA mod p k  R Zp – 1 K  yBk mod p C1  gk mod p C2  KM mod p C = C1 || C2 yB  gXB mod p K  C1XB mod p M  C2 /K mod p C 33

9.3 ElGamal 암호 방식 예 C = (21, 18) 송신자 A 공개정보 p = 23, g = 7 , yA = 17, yB = 15 수신자 B XA = 5 yA  gXA = 75  17 mod 23 r = 3  R Z22 K  yBr = 153  17 mod 23 C1  gr = 73  21 mod 23 M = 20 C2  KM = 17  20  18 mod 23 C = (C1 , C2) = (21, 18) XB = 9 yB  gXB = 79  15 mod 23 C1 = 21 C2 = 18 K  C1XB  219  17 mod 23 M  C2 /K = C2 K –1  18  19  20 mod 23 C = (21, 18) 34

9.3 ElGamal 암호 방식 예 35

9.4 Knapsack 암호 Markle과 Hellman에 의해 최초로 공개키 암호기법 적용 S=a1x1+a2x2+…+anxn 에서 X=(x1,x2,…,xn)값을 구하기. Positive integer a=(a1,a2, …,an) &Positive integer S, 즉 S가 a의 어떤 원소들의 합이 S가 되는가의 문제이다. 예 1) 3x1+5x2+9x3+19x4+37x5=45 X=(1,1,0,0,1)  해가 1개 존재. 2) 5x1+14x2+15x3+27x4+11x5=23       해가 없음. 3) 3x1+5x2+8x3+13x4+21x5=34       X=(0,0,0,1,1) ,  (0,1,1,0,1) 해가 2개 존재. n=5정도는 쉽게 풀 수 있다. n=100정도라면 결코 쉬운 문제 아니다. 36

9.4 Knapsack 암호 (계속) 1. 2x1+5x2+9x3+19x4+37x5=45 예를 들어 3<5 3+5<9 3+5+9<19 3+5+9+19<37 이런관계가 되는 것을 ‘a가 초증가한다' 라고 한다.   즉 a1+…+ai-1< aj ,where 2≤j≤7 이다. 37

9.4 Knapsack 암호 (계속) knapsack 벡터가 초증가하는 성질을 가졌을때의 해 xn= 1, if s≥an     0, if otherwise xj= 1, if s – (aj+1xj+1+…+anxn) >=aj     0, otherwise 38

9.4 Knapsack 암호 (계속) 예) 3x1+5x2+9x3+19x4+37x5=45 ①초증가 성질을 지니는가를 확인! ②3+5+9+19<=37<45 (yes) → x5=1     3+5+9+19<=45-37=8 (no)→ x4= 0     3+5+9<=8 (no) → x3= 0     3+5<=8 (yes) → x2= 1     3<=8-5=3 (yes) → x1= 1     3-3=0    ∴x=(1,1,0,0,1) 39

9.4 Knapsack 암호 (계속) Knapsack 문제 1cm 47cm 2cm 2  47  36cm 4cm 14cm A B B  A  47 mod 58 1cm 47cm 1 1 2cm 2  47  36cm 2 2 4cm 14cm 3 3 8cm 28cm 4 4 16cm 56cm 5 5 32cm 54cm 6 6 40

9.4 Knapsack 암호 (계속) A B Knapsack 문제(계속) 4+16+32=52cm 14+56+54=124cm 3 5 6 B 3 5 6 14+56+54=124cm 41

9.4 Knapsack 암호 (계속) Knapsack 암호의 구성 공개 암호화 키 비밀 복호화 키 B  A  K mod Q gcd(K, Q) = 1 공개 암호화 키 B 비밀 복호화 키 K, Q 42

9.4 Knapsack 암호 (계속) 암호화 47cm 36cm 14cm 28cm 56cm 54cm 1 M B C = 47 + 14 + 56 + 54 = 171 47cm 36cm 14cm 28cm 56cm 54cm 43

9.4 Knapsack 암호 (계속) 복호화 Y  C  K–1 mod Q (K K–1 1 (mod 58)이 되는 K–1 는 21이다.)  171  21 mod 58  (58 2+55)  21 mod 58  53 mod 58 초증가 수열의 막대 합 53-32  1 21-16  1 5- 8  0 5- 4  1 1- 2  0 1- 1  1 ∴M = 101011 (반대로 내려오면서 쓴다. 즉 53를 이진수로 표현) 44

관용 암호방식과 공개키 암호방식의 비교 관용 암호방식 공개키 암호방식 암호키 관계 암호화키 = 복호화키 암호화키  복호화키 암호화 키 비밀 공개 복호화 키 암호 알고리즘 비밀/공개 비밀키 수 nC2 2n 안전한 인증 곤란 용이 암호화 속도 고속 저속 45