[암호학] 공개 키 암호와 전자서명

1. 공개 키 암호의 개념

       -> 갑돌이가 갑순이에게 데이터를 보내고자 할 때 갑돌이는 보내고자 하는 데이터를 공개되어있는 
          갑순이의 공개키로 암호화 하여 전송하면 전송된 암호문을 받은 갑순이는 본인이 가지고 있는 
          개인키를 통해 복호화 함.


2. 공개 키 암호의 종류
       -> 소인수분해 : 어떠한 두 수를 곱해서 나오는 결과값을 아는데에는 매우짧은 시간이 걸리지만
                        (ex. 100 * 50 = n)
                       그 역으로, 나온 결과값을 어떠한 수로 곱해서 나오는 것인지 찾는 것은 매우 어려움.
                        (ex. 2345 = a * b....a, b ?)  
       -> 이산대수 : 로그함수만을 사용하면 계산이 어렵지 않지만
                      (ex. 5^k = 25)
                     나머지 연산을 같이 하면 문제가 어려워짐
                      (ex. 10^k mod 19 = 9) 


3. RSA암호
   1) 개인키 공개키 생성 과정
       ① 소수(1과 자신만으로 나누어 떨어지는 수) p, q선택
          (N = p * q 임의의 p = 11, q = 3 이라 할 때 N = 33)
       ② 오일러 함수 이용하여 R = (p - 1) * (q - 1) 과 서로소 R 계산
          (R = (11 - 1)(3 - 1) R-> 20) 
       ③ 유클리드 알고리즘 gcd(E, R) =1 계산하여 D얻음 
          ⓐ 1 < E < R. 즉 1 < E < 20 을 만족하는 수 중에 간단한 소수 선택
          ⓑ gcd(E,(p-1)) = 1 , gcd(E,(q-1) = 1을 만족하는 E찾음 -> E = 3
          ⓒ ED = 1(mod R) 즉 3D - 1 / 20 = 0을 만족 하는 수 D = 7
       ④ 공개키 (N, E) / 비밀키 (N, D) / p, q, R 제거
          (공개 키 (33,3) / 비밀키 (33,7)
      ※ 유클리드 알고리즘 : 두 수 사이의 최대공약수를 구하는 공식. gcd(m, n) 일 때 m을 n으로 나눈
         나머지를 r이라 하고 r이 0이면 n 이 최대공약수. 0이 아니라면 연산 반복하여 최대공약수를 구함
   2) RSA의 적용 – 전자서명
      -> 문서데이터의 Hash값을 비교해서 일치하는지 여부를 검증하는 방식. 전자서명 과정은 다음과 같음.
       ① 송신자는 문서의 데이터를 해쉬 함수를 통해 해쉬 값을 생성
       ② 생성된 해쉬 값을 비밀키로 암호화 한 값이 전자서명과 함께 데이터 전송
       ③ 수신자는 송신자에게 받은 데이터와 전자서명을 수신 
       ④ 공개 키를 이용하여 전자서명을 복호화하고 원본 데이터를 해쉬함수를 통해 해쉬값을 얻어냄
       ⑤ 일치하면 송신자가 작성한 문서, 아니면 송신자가 작성하지 않은 문서
      ※ Hash 함수 : 임의의 길이의 메시지를 일정 길이의 출력으로 변환하는 함수