(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. 공개키 암호 방식 평문 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 암호 방식 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 암호 방식 (계속) 증명 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. 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.