(c) Byoungcheon Lee, Joongbu Univ. 공개키 암호 중부대학교 정보보호학과 이병천 교수 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 공개키 암호의 도입 “New directions in cryptography” ; Diffie, Hellman 공개키 암호 방식 이론 발표, 1976년 RSA 공개키 암호 방식 ; Rivest, Shamir, Adleman 소인수분해 문제 이용, 1978년 MH 공개키 암호 방식 ; Merkle, Hellman Knapsack 문제 이용 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 대칭키 암호와 공개키 암호 대칭키 암호 공개키 암호 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 공개키 암호 방식 평문 M E 암호화 암호문 C D 복호화 평문 M 가입자 A 가입자 B KeB KdB 공개목록 KeB 키생성 공중통신망 seed (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 공개키 암호를 이용한 키관리 공중 통신망 가입자A 가입자C 가입자B 가입자D KAB KAC KAD KBA KBC KBD KCA KCB KCD KDA KDB KDC KAB : AB 간의 키 관용 암호 방식 KdA KeA KeB KeC KeD KdC Ke : 공개키 Kd : 비밀키 공개키 암호 방식 KdB (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 대칭키 암호방식과 공개키 암호방식의 비교 대칭키 암호 방식 공개키 암호방식 암호키 관계 암호화키 = 복호화키 암호화키  복호화키 암호화 키 비밀 공개 복호화 키 암호 알고리즘 비밀/공개 비밀키 수 nC2 2n 안전한 인증 곤란 용이 암호화 속도 고속 저속 (c) Byoungcheon Lee, Joongbu Univ.

일방향함수(One Way Function) x f(x)= y f easy x= f-1 (y) y f-1 difficult 비밀문 일방향 함수(trapdoor one way function) x= f-1 (y) y f-1 easy trapdoor (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 어려운 수학적 문제 쉬운 문제: 다항식 문제 (P 문제) 어려운 문제: 지수식 문제 (NP 문제) 소인수분해 문제 n = p  q p, q : 소수 이산대수 문제 y  g x mod p Knapsack 문제 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 소인수분해 문제 소인수분해 문제(factorization problem) 큰 두 소수의 곱을 구하기는 쉽지만, 큰 두 소수의 곱인 합성수의 소인수 분해가 어려운 점을 이용하는 이론 예 : RSA, Rabin, LUC 등 135979 115979 135979x115979=15770708441 f : 135979 x 115979 easy ? 15770708441 f -1 difficult (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 이산대수문제 이산대수 문제(discrete logarithm problem) 큰 수 n을 법으로 하는 지수승 y kx mod n은 계산하기 쉽지만, 주어진 y와 k에 대하여 식 y kx mod n을 만족하는 x를 구하기 어려운 점을 이용하는 이론 Diffie- Hellman, ElGamal, Massey-Omura, ECC 10 f(10)  1010 9 mod19 f (x)  10xmod19 easy Ind109=x 10 x9 mod19 f -1 difficult (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. RSA 공개키 암호 1977년 MIT의 Ron Rivest, Adi Shamir, Leonard Adleman에 의해 처음으로 제안된 공개키 암호 알고리즘 아직도 안전하다고 인정되고 널리 사용됨 키 길이 : 1024비트, 2048비트 Shamir Rivest Adleman (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. RSA 암호 방식 RSA 암호 방식 구성 소인수분해 문제의 어려움 이용 n = p  q 계산 p, q : 소수  (n) = (p – 1) (q – 1) 계산 : 오일러 함수 gcd (Ke,  (n)) = 1 를 만족하는 Ke 선택 Ke  Kd  1 mod  (n) 인 Kd 를 계산 (Ke, n) : 공개 암호화 키 Kd : 비밀 복호화 키 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. RSA 암호 방식 (계속) 암호화 C  M Ke mod n 복호화 M  CKd mod n 복호화 증명 Ke  Kd =  (n)  t + 1 M  MKeKd mod n  M  (n)  t + 1 mod n  M  (n)  t M mod n  (M t)  (n) M mod n  M mod n (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. RSA 암호 방식 (계속) 암호화 및 복호화 가입자 A 공개 정보 KeA, nA , KeB, nB 가입자 B nA = pA  qA KeA, KdA 계산 암호화 C  M KeB mod nB nB = pB  qB KeB, KdB 계산 복호화 M  C KdB mod nB C (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. RSA 암호 방식의 예 예 p = 3, q = 11 n = 33,  (33) = (3 – 1) (11 – 1) = 20 gcd (Ke =3,  (33)) = 1 Ke  (Kd = 7)  1 mod  (33) M = 5 C  M Ke mod n  53 mod 33  26 M  C Kd mod n  267 mod 33  5 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 공개키 암호의 해독 RSA-200 해독 2005. 5. 9. F. Bahr, M. Boehm, J. Franke, and T. Kleinjung Date: Mon, 9 May 2005 18:05:10 +0200 (CEST) From: Thorsten Kleinjung Subject: rsa200 We have factored RSA200 by GNFS. The factors are RSA-200 = 2799783391122132787082946763872260162107044678695542853756000992932612840010 7609345671052955360856061822351910951365788637105954482006576775098580557613 579098734950144178863178946295187237869221823983 = 3532461934402770121272604978198464368671197400197625023649303468776121253679 423200058547956528088349 × 7925869954478333033347085841480059687737975857364219960734330341455767872818 152135381409304740185467 병렬컴퓨터 이용 2.2GHz Opteron 컴퓨터의 75년 계산량 사용 http://www.loria.fr/~zimmerma/records/rsa200 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ElGamal 암호 방식 이산대수 문제의 어려움 이용 y  gx mod p g : 원시원소 p : 소수 y 가 주어졌을 때 x를 구하는 문제 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ElGamal 암호 방식 (계속) 이산대수 문제 예 Z23 51  5 58  16 515  19 mod 23 52  2 59  11 516  3 mod 23 53  10 510  9 517  15 mod 23 54  4 511  22 518  6 mod 23 55  20 512  18 519  7 mod 23 56  8 513  21 520  12 mod 23 57  17 514  13 521  14 mod 23 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ^ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ElGamal 암호 방식 (계속) 암호화 k  RZp (p : 소수) K  yBk (yB  g XB mod p) C1  g k mod p C2  KM mod p (M : 평문) C = (C1,C2 ) 복호화 K  (g k) XB mod p  C1 XB mod p M  C2 / K mod p (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ElGamal 암호 방식 (계속) ElGamal 암호 방식의 구성 가입자 A 공개정보 g , p, yA, yB 가입자 B 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 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ElGamal 암호 방식 ElGamal 암호 방식 예 송신자 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) (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 전자서명 전자서명의 기능 사용자 인증 메시지 인증 서명 종이문서  인장, 수기서명 전자문서  전자서명 전자서명의 종류 RSA, GQ, DSA, ElGamal, Schnorr, KCDSA (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 전자서명의 요구조건 위조불가 (unforgeable) 서명자 인증 (user authentication) 부인불가 (nonrepudiation) 변경불가 (unalterable) 재사용 불가 (not reusable) (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 수기서명과 전자서명의 비교 항목 수기서명 디지털 서명 서명 결과 고정 변화 디지털 복제 어려움 쉬움 서명 과정 간단 수학적 연산 법적 효력 있음 위조 가능 불가능 서명 도구 필기구 컴퓨터 보조 수단 불필요 필요 (해쉬함수) (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 해쉬함수 Message M 해쉬함수란? 임의의 길이의 입력메시지에 대해 고정된 길이의 해쉬값(특징값, 지문)을 출력하는 함수 키를 사용하지 않는 공개된 함수 일방향함수: 출력 해쉬값으로부터 입력메시지를 찾아내기 어렵다. 충돌회피성: 같은 해쉬값을 가지는 메시지쌍을 찾는 것이 어려워야 함 MD5, SHA1, SHA2, HAS160 등 해쉬함수의 응용 전자서명 메시지인증코드 (공유키 사용) H Message Digest D = H(M) (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 공개키 암호를 이용하는 전자서명 송신자(Client) 전자서명 생성 수신자(Server) 전자서명 검증 송신자인증서 해쉬값 전자서명값 비교 개인키 공개키 원문 ※ 본인 인증 송신자는 자신만이 가지고 있는 개인키와 인증기관에서 인증 받은 공개키, 즉 인증서를 통해 본인 임을 입증 ※ 무결성 보장 원문의 해쉬값과 전자서명값을 복호화한 해쉬값을 비교함으로서 위.변조 여부를 판단 ※ 부인 봉쇄 개인키를 이용하여 전자서명을 하였으므로 문서를 전송하지 않았다고 부인 불가 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. RSA 전자서명 서명자 A 공개 정보 KeA, nA, KeB, nB 검증자 B KeA, KdA , nA M : 서명문 h(M) = H S  HKdA mod nA KeB, KdB, nB H  SKeA mod nA 확인 S, M (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. RSA 전자서명 RSA 전자서명의 예 서명자 A KdA = 23 공개 정보 KeA = 7, nA = 55 검증자 B 서명문 M = 5 서명 S  MKdA mod nA = 523 mod 55  15 mod 55 M = 5 M  SKeA mod nA = 157 mod 55  5 mod 55 M = M 확인 M = 5, S = 15 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ElGamal 전자서명 서명자 A 공개 정보 yA, p, g 검증자 B yA  gXA mod p M : 서명문 k R Z p – 1 R  gk mod p H = h(M) S  (H– XAR )k – 1mod p – 1 yAR RS  gH mod p 확인 M, S, R (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ElGamal 전자서명 ElGamal 디지털 서명 예 서명자 A 공개 정보 yA, p=23, g=5 검증자 B xA = 9 yA  59  11 mod 23 k = 7 R Z 22 k – 1  19 mod 22 R  57  17 mod 23 M = 10 S  (10 – 9 × 17) × 19  11 mod 22 yAR RS  gM mod p 1117 × 1711  510 mod 23 확인 M = 10, S = 11, R = 17 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. Schnorr 서명 키생성 비밀키 xA 공개키 yA 서명 생성 는 m에 대한 서명 서명 검증 해쉬함수의 사용 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 전자서명 표준 DSS : Digital Signature Standard DSA : Digital Signature Algorithm FIPS – 186 등록, 1994년 NIST (c) Byoungcheon Lee, Joongbu Univ.