(c) Byoungcheon Lee, Joongbu Univ.

Presentation on theme: "(c) Byoungcheon Lee, Joongbu Univ."— Presentation transcript:

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

2 (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.

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

4 (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.

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

6 일방향함수(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.

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

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

9 (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.

10 (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.

11 (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 mod n  M  (n)  t M mod n  (M t)  (n) M mod n  M mod n (c) Byoungcheon Lee, Joongbu Univ.

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

13 (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.

14 (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.

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

16 (c) Byoungcheon Lee, Joongbu Univ.
ElGamal 암호 방식 (계속) 이산대수 문제 예 Z23 51    19 mod 23 52    3 mod 23 53    15 mod 23 54    6 mod 23 55    7 mod 23 56    12 mod 23 57    14 mod 23 (c) Byoungcheon Lee, Joongbu Univ.

17 (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.

18 (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.

19 (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.

20 (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.