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

강의목차 공개키 알고리즘의 수학적 배경 RSA 암호알고리즘 전자서명 과 은닉서명 HASH 함수 2 2

공개키 알고리즘의 수학적 배경 소수(Prime Number) 비대칭 키 암호에서 소수가 상당히 많이 사용된다. 소수는 오직 1이나 자신으로만 나누어 떨어진다 가장 작은 소수는 2이다. 소수 판정법  그리스 수학자 에라토스테네스가 소수 찾는 방법을 고안했다  주어진 수 n 이 소수인지 아닌지 판단은 그 수의 보다 작은 모든 소수를 구한다 .  보다 작은 모든 소수가 n을 나누지 못한다면 n 은 소수이다.  어느 한 개의 소수라도 n을 나눈다면 n은 소수가 아니다. 3

에라토스테네스의 체 (Sieve of Eratosthenes) 공개키 알고리즘의 수학적 배경 에라토스테네스의 체 (Sieve of Eratosthenes) 아래는 100 보다 작은 모든 소수를 찾는 표이다 100보다 작은 숫자에 100 보다 작은 소수인 2,3,5,7 로 나누어 지는지 표시한다.(2,3,5,7 숫자는 남겨둔다) √ 4

공개키 알고리즘의 수학적 배경 상대적 소수(Relative Prime) 최대공약수 두 정수 a, b 의 최대 공약수가 1 일 경우, 두 개의 정수를 상대적 소수(Relatively Prime)라 한다.  (a, b) = 1일 때 a 와 b 는 상대적 소수이다.  (25, 42) = 1 최대공약수 0 이 아닌 2 개의 정수 a, b 를 동시에 나눌 수 있는 가장 큰 공약수이다.  gcd (a, b) 또는 (a,b) 표현한다.  (24, 84) = 12 , (0,44) = 44 5

공개키 알고리즘의 수학적 배경 유클리드 알고리즘 2개의 정수 a, b 의 최대공약수(gcd)는 division algorithm 을 계속 적용 하여 맨 마지막 0 이 아닌 나머지가 최대 공약수이다. 2개의 정수 a, b (a  b ) 경우 최대공약수를 구해보자.  b = a  q 1 + r1 0 < r1 < a a = r1  q2 + r 2 0 < r2 < r 1 r1 = r2  q3 + r3 ……. 0 < r3 < r 2 r n-3 = r n-2  q n-1 + r n-1 0 < r n-1 < r n-2 r n-2 = r n-1  q n + rn 0 < r n < r n-1 r n-1 = r n  q n+1 + 0  (a, b) = r n 6

공개키 알고리즘의 수학적 배경 유클리드 알고리즘 유클리드 알고리즘으로 (252, 198)의 최대공약수를 구해보자.  252 = 1981 + 54 198 = 543 + 36 54 = 361 + 18 36 = 182 (252, 198) = 18 이 최대공약수이다. 7

공개키 알고리즘의 수학적 배경 확장형 유클리드 알고리즘 c 가 2 개의 정수 a, b 의 최대 공약수 이면, c 를 a 와 b의 선형결합 (liner combination)으로 나타낼 수 있다.  (a, b) = c 이면 c = s  a + t  b 이다 (s, t 정수) (252, 198) =18 인 경우, 18 = 252  s + 198  t 로 표현되고, s 와 t 를 구할 수 있다.  s 와 t 는 유클리드 알고리즘에 의해 구한다. 18 = (252, 198), 18 = 252  s + 198  t 에서 s 와 t 를 구해보자  18 = 54 – 1  36 (유클리드 알고리즘에 의해 54 = 1  36 + 18 ) = 54 – 1  (198 – 3  54)  (198 = 3  54 + 36) 8

공개키 알고리즘의 수학적 배경 확장형 유클리드 알고리즘  18 = 54 – 1  36 (유클리드 알고리즘에 의해 54 = 1  36 + 18 ) = 54 – 1  (198 – 3  54)  (198 = 3  54 + 36) = 4 54 – 1  198 = 4 (252 – 198) – 198  (252= 198  1 + 54 ) = 4  252 – 5 198 = 252  4 + 198  ( – 5) 따라서, s = 4, t = – 5 ∴ 18 = 252  4 + 198  (– 5) 9

공개키 알고리즘의 수학적 배경 합동식(Congruence) 합동  a 와 b 의 차가 m 의 배수일 때, a 와 b 는 법(modulus) m에 대하여 합동이라 하고, a  b (mod m) 으로 표현한다.  a – b = k · m 이면 a = k · m + b 가 되고 이를 a  b (mod m) 로 정의한다 (k : 양 또는 음의 상수) 10

공개키 알고리즘의 수학적 배경 합동식(Congruence) 동치  a 와 b를 m 으로 각각 나눈 나머지 같으면 a  b (mod m) 으로 나타내고, a 와 b는 법 m 에 대하여 동치라 한다.  1, 3, 5, 7, 9.. 는 2로 나누었을 때 나머지가 같으므로 이들은 동치이다.  1  3 mod 2  5 mod 2  7 mod 2  9 mod 2  11 mod 2 …  나머지가 같은 수들을 같은 수로 취급하자는 개념 11

공개키 알고리즘의 수학적 배경 합동식(Congruence) 문제 2 50 을 7 로 나누었을 때 나머지를 구해보자. 문제 2 50 을 7 로 나누었을 때 나머지를 구해보자.  250 = 7 · k + b 에서 b 를 구하면 된다. 250 – b = 7 · k 가 되고 합동식 정의에 의해 250  b mod 7 가 된다  23 = 8 = (7 · 1) + 1 이므로 23  1 mod 7 이 된다.  250  ( 23 )16 · 22 mod 7  ( 1 ) · 22 mod 7  4 mod 7  나머지는 4 이다 12

공개키 알고리즘의 수학적 배경 합동식(Congruence) 합동식이 X · 5  1 mod 23 일 때 X 값을 구해보자  합동식 정의에 의해 a – b = m · k 일 때 a  b mod m 표현할 수 있다.  X · 5  1 mod 23 를 X · 5 = k · 23 + 1 로 표현 할 수 있고 이 식을 1 = X · 5 – k · 23 이라 표현할 수 있다.  앞에서 공부한 확장형 유클리드 알고리즘을 이용하여 X 값을 구할 수 있다.  (a, b) = c 일 때, c = s · a + t · b 로 나타낼 수 있다 13

공개키 알고리즘의 수학적 배경 합동식(Congruence) 합동식이 X · 5  1 mod 23 일 때 X 값은 ?  (23, 5) = 1 이므로 1 = s · 23 + t · 5 로 표현할 수 있다.  23 = 5 · 4 + 3 ☞ 유클리드 알고리즘 5 = 3 · 1 + 2 3 = 2 · 1 + 1 2 = 12 + 0  따라서 1 = 3 – 2 · 1 = 3 – (5 – 3 · 1) ☞ (5 = 3 · 1 + 2) 14

공개키 알고리즘의 수학적 배경 합동식(Congruence) 합동식이 X · 5  1 mod 23 일 때 X 값은 ?  1 = 3 – (5 – 3 · 1) = 2 · 3 – 5 = 2 · (23 – 5 · 4) – 5  (23 = 5  4 + 3 ) = 2 · 23 – 9  5  1 = 2  23 – 9  5 ; – 9 · 5 = (– 2) · 23 + 1 이고 – 9  5  1 mod 23 로 표현할 수 있다. 따라서 X = – 9 이다  – 9 를 양수로 바꾸려면 – 9 = 23  (– 1) + 14 = 14 가 된다 따라서 – 9  14 mod 23 으로 나타낼 수 있다 15

공개키 알고리즘의 수학적 배경 합동식(Congruence) 유클리드 알고리즘과 확장형 유클리드 알고리즘에 의해 합동식이 유클리드 알고리즘과 확장형 유클리드 알고리즘에 의해 합동식이 14 · 5  1 mod 23 임을 알아냈다. 14  5  1 mod 23 라는 것은 14와 5는 mod 23 에 대해 역원 관계에 있다는 의미이다. RSA 알고리즘에서 공개 키(e)와 개인 키(d)는 e · d  1 mod (n) 관계에 있어 공개 키와 개인 키는 서로 역원관계이다. 16

공개키 알고리즘의 수학적 배경 오일러 Ø(n) 함수 n 보다 작으면서 n과 서로 소, 즉 (a, n) = 1 인 정수의 개수를 나타낸다. Z*n 은 n 보다 작으면서 n과 서로 소인 정수들의 집합이다.  Ø(n) = |Z*n| Ø(1) = 0 p 는 소수일 때, Ø(p) = p – 1 이다  Ø (13) 을 구해보면, 13은 소수이므로 Ø(13) = 13 – 1 = 12 m과 n은 서로 소일 때, Ø(m × n ) = Ø(m) × Ø(n) 로 쓸 수 있다  Ø(10) = Ø (2 × 5) = Ø(2) × Ø(5) =1 × 4 = 4 (2와 5는 서로 소) p는 소수일 때, Ø(pe ) = pe - pe-1 관계가 성립한다  Ø (240) = Ø(24 × 31 × 51 )= Ø(24 ) Ø(31 ) Ø(51) = (24 - 23)(31 - 30)(51 - 50 ) = 64 17

공개키 알고리즘의 수학적 배경 오일러 정리(Euler’s Theorem) 제 1정리  a와 n이 서로 소이면, 즉 (a, n) =1 이면 aØ(n) ≡ 1 (mod n) 성질을 만족 한다.  624 mod 35 를 구해보면, (6, 35) = 1 이므로 624 mod 35 = 6 Ø(35) mod 35 ≡ 1 (mod 35) 이 된다. 제 2 정리  a와 n이 서로 소라는 조건이 필요 없이 n = p × q 이고 a < n 이고 k 가 정수이면 a k · Ø(n) +1 ≡ a (mod n) 성질을 만족한다  2062 mod77 를 구해보면, Ø(77) = Ø(7 × 11) = 6 × 10 =60 이므로 20 Ø(77) +1 = 20 61 ≡ 20 (mod 77) 이다. 따라서 2062 mod77 ≡ 20 × 20(mod 77) = 15 이다 18

공개키 알고리즘의 수학적 배경 오일러 정리(Euler’s Theorem) 오일러 정리의 제 1 정리를 이용하여 곱셈의 역원을 구해보자  aØ(n) ≡ 1 (mod n) 이므로 aØ(n) - 1 ≡ a - 1 (mod n) 가 된다. 이 식을 이용 하여 곱셈의 역원을 구한다.  8-1mod77 을 구해보자  (8, 77) = 1 이므로 8Ø(77) ≡ 1 (mod 77) 이고, Ø(77) = Ø(7 × 11) = 60  860 ≡ 1 (mod 77)이다. 8-1mod77= 1 × 8-1mod77 = 860 × 8-1mod 77 = 859(mod 77) 를 구하면 된다.  81 ≡ 8 (mod 77), 82 ≡ 64, 83 ≡ 50, 84 ≡ 15, 85 ≡ 43, 86 ≡ 36, 87 ≡ 57 88 ≡ 71, 89 ≡ 29, 810 ≡ 1, 859(mod 77) = (810)5 × 89(mod 77)=29(mod77) 19

RSA 암호 20

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

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

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

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

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) 이므로 25

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

RSA 암호 알고리즘 27

전자서명 28

전자서명 전자서명 Alice와 Bob이 전자문서를 주고 받고자 할 때 문서 작성자의 신원 확인을 확인할 필요가 있다. 전자서명은 문서 작성자의 신원확인과 문서의 무결성을 검증하는 기능 그리고 부인방지 기능을 한다. 서명자는 자신의 개인 키로 서명을 하고, 검증자는 서명자의 공개 키로 서명을 검증한다 29

전자서명 전자서명 공개 키 암호시스템이 암호화 용도로 사용되는 경우에는 수신자의 개인 키와 공개 키가 활용되지만, 전자서명 용도로 사용되는 경우에는 송신자의 개인 키와 공개 키가 사용된다. 공개 키 암호시스템은 길이가 긴 메시지를 처리하는데 효율성이 떨어 진다. 이에 길이가 짧은 메시지 다이제스트에 서명하는 것이 더 효율적 이다. 30

전자서명 부인방지 기능 Alice가 메시지의 서명한 사실을 나중에 부인할 경우 Bob은 Alice가 문서의 전자서명 당사자임을 증명할 수 있어야 한다. 이를 위해 신뢰받는 제 3자를 이용하여 부인방지기능을 구현한다. Alice 는 메시지, 전자서명, Alice의 ID, Bob의 ID 를 신뢰 센터로 보낸다. 31

전자서명 부인방지 기능 센터에서 Alice의 공개키로 Alice의 전자서명을 검증한 후, 메시지의 복사본, Alice의 ID, Bob의 ID, Time-Stamp를 첨부하여 보관한다. 센터는 센터의 개인 키로 Alice의 메시지에 전자서명을 한 후, Alice의 메시지와 함께 Bob에게 보낸다. Bob은 센터의 공개 키로 Alice의 메시지를 검증한다. 32

전자서명 부인방지 기능 Alice 와 Bob이 메시지를 보낸 사실 또는 받은 사실을 나중에 부인할 경우 제 3의 기관인 센터에 저장된 메시지 사본으로 확인할 수 있다. 33

전자서명 RSA 전자서명 RSA 암호 시스템의 키를 생성하는 것과 동일한 절차로 전자서명 키를 생성한다. Alice는 메시지 M 과 메시지 다이제스트 D=H(M) 그리고 전자서명 S= Dd mod n 를 만들어 Bob에게 보낸다. Bob 은 이를 검증한다. 34

전자서명 은닉서명 개요 전자문서 내용을 보여주지 않고 전자문서에 서명을 받아야 할 경우 사용하는 전자서명이다 Bob이란 과학자가 중요한 이론을 발견하였고 이를 공증기관인 Alice 에게 공증을 받고 싶어하지만 발견한 이론의 내용을 Alice가 보여지기 않기를 바란다고 가정해 보자. David Chaum이 이런 경우에 사용할 수 있는 Blind(은닉) 전자서명을 개발하였다. 35 35

전자서명 은닉서명 개념도 Bob Alice Put it into an envelope, and seal. 과학이론 논문 Bank seal 과학이론 논문 전자서명 전자서명 Alice 과학이론 논문 전자서명 36 36

전자서명 은닉서명 처리절차 Bob은 임의의 은닉인자 b 를 선택한다. Bob 은 메시지 M 과 은닉인자 b, Alice의 공개키 e 를 이용하여 아래와 같이 암호화 하여 Alice 에게 보내어 전자서명을 요청한다. • M × be mod n Alice 는 블라인드 된 메시지 M × be mod n 를 수신하여 Alice 의 개인키로 전자서명하여 Bob 에게 보낸다. • (M × be )d mod n Bob은 수신한 은닉인자 b 의 역원을 곱하여 전자서명을 얻는다. 37 37

메시지 인증 변경감지코드(MDC : Modification Detection Code) 메시지 다이제스트는 메시지 무결성만 확인하는 변경감지코드이다. 메시지 다이제스트만으로는 메시지 전송자의 신원확인을 할 수 없다. Alice는 메시지 M과 메시지 다이제스트 MDC 를 Bob에게 전송한다. Bob은 수신한 메시지 M으로부터 메시지 다이제스트 MDC를 생성하 여 두 메시지 다이제스트 값을 비교하여 무결성 여부를 판단한다. 38

메시지 인증 메시지인증코드(MAC : message authentication code) 메시지 인증코드는 메시지 무결성과 데이터 출원지를 인증해 준다. 데이터 출원지 인증이란 메시지 전송자가 해당 메시지를 실제 전송한 사람임을 증명하는 것이다. MDC 와의 차이점은 MAC 에는 Alice 와 Bob 사이의 비밀 값이 포함 되어 있는 것이다. 39

메시지 인증 메시지인증코드(MAC: message authentication code) Alice는 비밀 값 (예 , K: 키)와 메시지를 이어 붙인 K|M 을 해쉬함수에 적용하여 MAC인 h(K|M)을 생성하여 Bob에게 전송한다. Bob은 수신한 메시지 M와 가지고 있는 K를 K|M을 만든 후 새로운 MAC 값을 생성하여 수신한 h(K|M)과 비교하여 일치 여부를 확인하여 수신한 메시지가 Alice로 부터 온 것임을 확신할 수 있다. 공격자인 Eve는 Alice와 Bob이 공유하는 키 K를 가지고 있지 않기 때문에 Alice와 동일한 MAC값을 생성할 수 없다. 40

HASH 함수 41

해시함수와 메시지 무결성 개요 메세지 무결성이란 메시지의 위,변조 없이 전송되는 것을 의미한다. 무결성 검증은 해당 메시지의 핑거프린트(fingerprint)에 해당되는 메시지 다이제스트에 의해 이루어진다. 메시지의 수신자가 해쉬함수를 이용하여 새롭게 생성한 메시지 다이제 스트와 송신자가 보낸 메시지 다이제스트를 비교하여 무결성을 검증 한다. 42

해시함수 개요 다양한 길이의 메시지를 고정된 짧은 길이의 메시지 다이제스트 (message digest : 축약문)으로 변환 하는 기능을 한다. Y = H(M) • H : 해쉬함수 • M : 가변길이의 메시지(평문) • Y : 해쉬함수 H 를 통하여 생성된 고정된 길이의 메시지 다이제스트 메시지의 무결성 검증에 사용된다. 43

해시함수 해쉬함수의 3가지 조건 프리이미지 저항성(preimage resistance) 제 2 프리이미지 저항성(second preimage resistance) 충돌 저항성(collision resistance) 44

해시함수 조건 프리이미지 저항성(preimage resistance) 메시지 다이제스트 값 y (y=h(M)) 만 주어진 경우에, Eve 가 y=h(M΄) 을 만족하는 다른 메시지 M΄ 을 찾아내는 것이 매우 어렵게 하는 성질이다. ☜ 매우 어렵게 하는 성질 45

해시함수 조건 제2프리이미지 저항성(Second Preimage Resistance) 메시지와 메시지 다이제스트 값이 주어진 경우, 동일한 메시지 다이제 스트 값을 갖는 다른 메시지(M΄)를 찾는 것을 불가능하게 하는 성질이다 Eve가 메시지 M 과 다이제스트 값 h(M)을 가로챈 후, h(M)=h(M΄)을 만족하는 다른 메시지 M΄을 만들어 Bob에게 보낼 수 있다(메시지 위조) 46

해시함수 조건 충돌저항성(Collision Resistance) 동일한 메시지 다이제스트 값을 갖는 서로 다른 2개의 메시지를 만들지 못하도록 하는 성질이다. 충돌저항성이 없는 경우엔 메시지 전송자인 Alice의 메세지 위조를 막 지 못한다. 47

해시함수 조건 충돌저항성 조건이 없을 경우 사례 Alice와 Bob은 결혼할 때, 둘이 이혼할 경우에 Bob은 재산의 50%를 다이제스트를 변호사에게 보관하기로 하였다. Alice는 Bob에게 50%를 준다는 내용의 결혼서약서(M )와 전혀 다른 내용의 서약서(M΄)를 만든 후, 메시지 다이제스트가 일치하는 H(M) = H(M΄) 것을 선택한 후, 해당 메시지 다이제스트를 변호사에게 보관케 한다. 메시지 다이제스트가 일치하는 서로 다른 메시지 M과 M΄ 을 찾는 것 자체를 불가능하게 하는 조건이 강한 충돌방지 조건이다. 48

해시함수 조건 49

Thanks Chul Ho Rhee richman3@naver.com