[정수론](12)[RSA 암호]

암호학 둘러보기 9 참고
(여기서 더 정수론 내용이 들어갔다.)

• 과정
  메세지 보내는 A, 메세지 받는 B이고 공개된 파라미터 e가 있다.
  B의 공개키(N): N = p*q (p, q는 매우 큰 소수)
  B의 개인키([d]): [d]*e = 1 (mod[p-1]*[q-1]) (모듈러 역원 구하기. 만족하는 정수 d는 1개밖에 없으니 안심)
  A가 보낼 메세지 암호화(C): C = M^e (mod N)
  B는 자신의 개인키로 복호화(M): M = C^[d] (mod N)

내가 암호학 둘러보기에선 이렇게 써놨다.
이처럼 RSA는 상대의 공개키로 보낼 메세지를 암호화한다.

이제 정수론적으로 다시 봐보자.

• 과정
  매우 큰 소수 p, q를 선택하고 m = pq라고 두자
  p, q는 소수이므로 ϕ(m) = (p-1)(q-1)
  이후 ϕ(m)와 서로소인 k를 선택한다.
  공개키 = m, k / 비공개키 = p, q, ϕ(m) (ϕ(m)도 털리면 p, q 알기 쉬우니 공개 안됨)
  • 암호화
    상대는 공개키 m, k로 보낼 메세지 a를 다음의 방식으로 암호화한다
    c ≡ a^k (mod m)
    <- 연속제곱법으로 계산하면 빠르게 계산 가능
  • 복호화
    이후 암호화된 메세지 c를 받으면 p, q를 이용해 복호화한다
    x^k ≡ c (mod m) 을 풀면 되는데 ϕ(m)를 아니까
    ku-ϕ(m)v = 1에서 u를 구할 수 있고,
    x ≡ c^u ≡ a (mod m) 로 복호화할 수 있다.
• 예) m = 7081, k = 1789로 암호화된 5192라는 암호문 c가 있다. 이걸 복호화하시오
  일단 m을 인수분해하면 m = 73*97
  ϕ(m) = (73-1)(97-1) = 6912
  이후 선형방정식 ku - ϕ(m)v = 1인 u를 유클리드 호제법으로 찾으면
  u = 85
  따라서 c^u ≡ a (mod m) 이므로 5192^85 (mod 7081) 만 계산하면 된다.
  연속제곱법을 통해 계산하면 a = 1615가 나온다.
  (만약 m이 이것보다 더 큰 두 소수의 곱이였다면 인수분해부터 막히므로 복호화할 수 없으나,
  m이 그나마 작으므로 복호화할 수 있다.)

실제 구현은 여기 <- RSA의 암호화, 복호화