RSA 알고리즘

“누워서 읽는 알고리즘” 책에서 RSA 알고리즘을 소개하고 있어 정리하고자 합니다.

여기서 RSA 알고리즘을 증명하고자 하는 것이 아니며, 알고리즘 기본 정보만 소개합니다.

RSA란?

공개키 암호시스템의 하나로 1978년 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)의 이름 앞글자를 따 RSA라고 명명하였습니다. 공개키와 개인키로 이뤄진 이 알고리즘은 큰 숫자에 대해 소인수 분해가 어렵다는 것에 기반을 두고 있습니다. 즉, 소인수 분해가 가능해지면 알고리즘이 무용지물이 될 수도 있습니다.

위키백과(https://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8)에서 아래와 같이 언급하기도 하였습니다.

1993년피터 쇼어는 쇼어 알고리즘을 발표하여, 양자 컴퓨터를 이용하여 임의의 정수를 다항 시간 안에 소인수 분해하는 방법을 발표하였다. 따라서 양자 컴퓨터가 본격적으로 실용화되면 RSA 알고리즘은 무용지물이 될 것이다. 그러나 양자 컴퓨터가 이 정도 수준으로 실용화되려면 아직 여러 해가 더 필요할 것으로 보인다.

아마도 양자 컴퓨팅이 실현되면 다른 알고리즘이 필요할지도 모르겠습니다.

RSA 알고리즘

개요

RSA는 두 개의 키 즉, 공개키와 개인키로 이루어져 있는 알고리즘이라고 소개했습니다. 공개키는 암호화할 때, 개인키는 복호화할 때 사용합니다. 소인수 분해의 난해함으로 인해 공개키를 통해 쉽게 개인키를 유추할 수 없도록 설계되었습니다.

키 생성

1. p와 q가 소수라고 했을 때 n=pq를 계산합니다.

2. 이제 p와 q에서 각각 1을 빼서 곱합니다. 그것을 φ(파이)라고 합니다.

    φ = (p-1)(q-1)

3. 다음 조건을 만족하는 e를 찾습니다.

    1<e<φ, gcd(e, φ) = 1

    여기서 gcd는 두 수의 최대 공약수를 의미합니다.

4. 다음 조건을 만족하는 d를 찾습니다.

    1<d<φ, ed = 1 (mod φ)

5. (n, e)는 공개키이고, (n, d)는 개인키입니다.

    p, q, φ와 같은 값은 공개되지 않도록 합니다.

암호화

(n, e) 공개키를 이용하여 m이라는 메시지를 암호화 하는 방식입니다. c는 암호화된 문서를 의미하며 이를 전달하면 됩니다.

복호화

암호화된 메시지 c를 (n, d) 개인키를 이용하여 복호화 하는 방식입니다.

요약

책 P.178 ~ P.184에 RSA 알고리즘을 이용하여 메시지를 전달하는 예제에 대해서 설명하고 있습니다.

요약해 보면 히딩크 감동이 코엘료 감독에게 월드컵 비법을 전달하면서 RSA로 암호화해서 전달하고 있습니다. 이를 계산하는 방법을 확인해 보면 RSA 알고리즘을 이해하는데 도움이 될 것 같습니다.

---

참고

• https://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8