전자상거래 보안 (암호학과 네트워크보안) 2017.5.17 Chul Ho Rhee richman3@naver.com

강의목차 공개키 알고리즘 개념 RSA 암호알고리즘 공개키 알고리즘의 수학적 배경 ElGamal 암호알고리즘 2 2

공개키 알고리즘 개요 암호용 키 및 복호용 키가 다르다 비밀키 알고리즘에 비하려 속도가 느리다(1,000배) 긴 문서의 암호보다 비밀키 알고리즘의 비밀키 암호에 사용 • C =E(k pub-R (P)) , P =D(k priv-R (C)) P : 비밀키 값 3

공개키 알고리즘 개요 전자서명 생성 및 검증에 사용 • C = E(k priv-S(P)), P= D(k pub-S (C)) P : 해쉬함수 값(축약문) • k priv-S 는 전송자의 개인키이다 4

공개키 알고리즘 암호 및 복호 표현방법 C =E(k pub-R (P)) = Pe mod n ☞ e 공개 키 P =D(k priv-R (C)) = Cd mod n ☞ d 개인 키 5

공개키 알고리즘 개요 키 관리와 키 분배가 용이하다 키 관리  A, B, C 사람과 공개키 암호통신을 할 경우 각자의 공개 키 및 개인 키를 생성하여, 공개키는 공개하고 자신의 개인키만 관리한다. ☞ (k pub(A), k priv(A), k pub(B), k priv(B), k pub(C), k priv(C) )  n 사람이 암호화 통신할 경우 2· n 개 의 키가 필요하다. 키 분배  공개 키에 의한 암호화 통신을 할 경우 각자의 공개 키를 공개하여 필요할 때 상대방이 이용할 수 있도록 한다. (디렉토리 서버에 저장) 6

공개키 알고리즘 공개키 알고리즘의 적용사례(전자서명/비밀키 암호) 7

암호화와 전자서명 암호화 및 전자서명 처리과정 송신자는 메시지(평문)을 해쉬함수를 이용하여 축약문(message digest) 값을 생성한다. 송신자는 자신의 서명용 개인키로 축약문을 암호하여 전자서명을 생성한다. 송신자는 비밀키 알고리즘을 이용하여 비밀 키로 메시지를 암호 한다. 메시지의 암호화에 사용된 비밀 키를 수신자의 키 교환용 공개키로 암호화 하여 전자봉투를 만든다. • 송신자는 사전에 수신자의 키 교환용 공개키가 있는 인증서를 획득 하여야 한다. 8

암호화와 전자서명 암호화 및 전자서명 처리과정 송신자는 암호화된 메시지와 전자봉투를 수신자에게 전송한다. 수신자는 암호화된 메시지와 전자봉투를 받은 후, 자신의 키 교환용 개인키로 전자봉투를 복호하여 비밀 키를 얻는다. 수신자는 획득한 비밀 키로 암호화된 메시지를 복호하여 메시지 내용을 파악한다. 수신자는 송신자의 전자서명용 공개키가 들어있는 인증서를 획득한다. 수신자는 인증서에서 전자서명용 공개 키를 추출하여 송신자의 전자 서명을 복호하여 축약문을 생성한다. 9

암호화와 전자서명 암호화 및 전자서명 처리과정 수신자는 송신자의 메시지를 동일한 해쉬함수로 처리하여 축약문를 생성한다. 전자서명을 복호하여 얻은 축약문과 메시지로부터 구한 축약문을 서로 비교하여 메시지의 무결성과 메시지 송신자의 신원확인을 한다. 10

RSA 암호 11

RSA 암호 알고리즘 공개키 및 개인키 생성과정 두 개의 큰 소수 p, q 를 선정하여 n = p · q 를 계산한다 (n) 과 서로 소인 공개키 e ((e , (n)) = 1) 를 임의로 선택한다. 확장형 유클리드 알고리즘으로 e · d  1 mod (n)을 만족하는 개인 키 d 를 구한다.  개인 키 e 와 공개 키 d 는 서로 역원관계이다 {n, e}는 공개 키로 공개하고, { d }는 개인 키로 개인이 보관한다. 12

RSA 암호 알고리즘 키 생성 알고리즘 13

RSA 암호 알고리즘 암호 및 복호 과정 개념도 14

RSA 암호 알고리즘 RSA 암호해독 Alice와 Bob이 RSA 암호화 통신 내용을 공격자인 Eve가 암호해독을 어렵다. 15

RSA 암호 알고리즘 RSA 암호의 수학적 증명 RSA 암호의 암호화 및 복호화 과정을 오일러의 제 2 정리를 이용하여 수학적으로 증명할 수 있다. 오일러의 제2정리에 의해 다음과 같이 생각할 수 있다. Bob이 복호화 평문을 P1 이라 하고 이것이 Alice가 작성한 평문 P와 같다는 것을 증명해 보자 ☞ ed  1(mod Ø(n) 이므로 16

RSA 암호 알고리즘 간단한 예제 수신자인 Bob은 p 와 q 를 7 과 11로 선택해서 n = 77을 계산한다. Ø(77) =Ø(7 × 11) = (7 − 1) × (11 − 1) = 60 이 된다. Bob 은 Z60∗ 안에서 e · d mod 60 = 1 관계에 있는 두 개의 지수 e 와 d 를 선정한다. 만약 e 를 13으로 선택한다면, d 는 37 이 된다. e와 d는 서로 역원관계이다. 전송자인 Alice 는 평문 5 를 Bob에게 보내려고 한다. Alice는 bob의 공개된 키 값 13을 이용해서 5를 암호화 한다. Bob은 암호문 26 을 수신하고 자신의 개인 키 37을 이용하여 복호 한다. ☞ e · d  1(mod Ø(n) 이므로 17

RSA 암호 알고리즘 간단한 실제 적용사례 제니퍼는 자신의 키 쌍을 만들기 위해 p = 397, q = 401을 사용하여 n = 159197을 계산한다. Ø(159197) = 158400을 계산한 후, e = 343 and d = 12007을 선택했다. 테드가 e 와 n을 알면 메시지 ‘no’를 제니퍼에게 보내는 과정이다. ‘no’는 숫자코드로 바꾸면 1314이고, (1314)343=33677(mod159197)이 된다. 18

RSA 암호 알고리즘 19

Thanks Chul Ho Rhee richman3@naver.com