RSA 암호시스템: 개요와 동작원리

RSA 암호화 시스템에 대해서 자세히 알아보려고 합니다. 간단한 내용을 원하시는 분들께서는 아래의 포스팅을 참고해주시기 바랍니다.

2018/01/18 - [IT 지식정리/기타] - 대칭키 암호화와 공개키 암호화 요약

2018/01/18 - [IT 지식정리/기타] - RSA 암호화 방식 요약

RSA (Rivest–Shamir–Adleman)는 초기에 소개된 공개키 암호화(public-key cryptosystems) 기술 중 하나로 암호화된 데이타 전송에 널리 사용되고 있습니다. 

공개키 암호화시스템에서 암호화키(encryption key)는 공개(공개키)되어 사용되고, 복호화키(decryption key)는 반대로 비공개(개인키)로 된 시스템입니다.

RSA에서는 2개의 큰 소수를 이용한 인수분해의 원리를 이용해서 암호화를 합니다. 

1978년에 이 알고리즘을 처음으로 개발한 3 사람의 이름의 앞 글자를 따서 RSA (Ron Rivest, Adi Shamir, Leonard Adleman)로 이름을 지었습니다.

1973년에 영국의 국가정보기관(GCHQ)에서 근무했던 수학자 Clifford Cocks가 동일한 방식의 암호시스템을 개발하였던 사실이 1997년에 공개되었습니다.

RSA유저들은 2개의 큰 소수를 사용해서 공개키를 만들고 공유하게 됩니다. 이 2개의 소수들은 비밀유지가 되어야 합니다. 누구든지 공개키를 사용해서 암호화가 가능하고, (공개키의 크기가 충분히 크다면 ) 2개의 소수를 알고 있어야만 복호화를 할 수 있습니다. RSA 암호화에도 암호를 풀 수 있는 문제점이 존재하고 있습니다.

RSA는 비교적 느린 속도 때문에 데이타를 직접적으로 암호화 할 때에는 잘 사용되지 않습니다. 속도가 빠른 대칭키 암화화 기술을 사용 할 때, 암호화키(shared key)를 암호화하여 전달 할 때 주로 사용됩니다.

RSA 암호시스템의 동작

RSA 알고리즘은 키 생성 - 키 분배 - 암호화 - 복호화 이렇게 4가지 단계가 있습니다. 

RSA의 기본적인 원리는 3개의 큰 정수 e,d,n 과 (0 ≤ m < n일 경우의) 아래를 충족시키는 m이 있을 경우, e와 n을 알더라도(심지어 m을 알더라도) d를 찾기가 굉장히 힘든 데에서 착안하였습니다.

간혹 아래와 같이 바꾸어서 사용하기도 합니다.

공개키 암호화기술인 RSA는 공개키와 개인키가 있습니다. 공개키는 누구에게든 알려져도 되고, 메세지를 암호화 할 때 사용됩니다.  공개키로 암호화가 된 메세지는 개인키를 사용해서만 복호화가 가능하고, 복호화는 어느정도의 시간이 걸리게 됩니다. 위의 수식에서 정수 n과 e는 공개키를 뜻하고, 정수 d는 개인키를 뜻합니다 (n 역시 복호화 과정에 사용되기 때문에 개인키에 포함할 수 있습니다). m은 메세지가 됩니다.

키생성(Key generation)

RSA알고리즘의 키생성은 아래와 같은 과정을 거치게 됩니다.

1. 2개의 각기 다른 소수 p와 q를 선택합니다.

보안을 위해서 p와 q는 랜덤으로 선택이 되어야 하고, 인수분해가 어려워지기 위해서 크기는 비슷하고, 길이는 조금 달라야 합니다.

2. n 값을 구합니다. n=pq.

n은 공개키와 개인키에서 계수로 사용됩니다. n의 길이(bit로)가 key length 값 입니다.

3. λ(n) = lcm(λ(p), λ(q)) = lcm(p − 1, q − 1) 값을 계산합니다. λ는 카마이클의 피함수(Carmichael's totient function) 이고, 이 값은 개인키에 사용됩니다.

4. 1 < e < λ(n)이며, gcd(e, λ(n)) = 1인 정수 e를 선택합니다. (e와 λ(n)는 서로소)

5. d값을 구한다. d ≡ e−1 (mod λ(n))

e는 공개키의 지수이고, d는 개인키의 지수가 됩니다.

공개키는 계수 n과 공개키 지수 e로 구성이 됩니다. 개인키는 지수 n과 개인키 지수 d로 구성이 됩니다. d는 반드시 비밀유지가 되어야 하며, d를 구할 수 있는 p와 q, λ(n) 도 비밀유지가 되어야 합니다.

때로는 오일러의 피함수 φ(n) = (p − 1)(q − 1)가 λ(n) 대신 사용되기도 했지만, 가끔 d가 필요이상으로 커져버리는 경우가 발생합니다. 예: d > λ(n). 

대부분의 RSA는 두가지 방식을 모두 지원하지만, FIPS 184-4 와 같은 표준들은 d < λ(n) 의 조건이 필요합니다.

키분배(Key distribution)

A가 B에서 정보를 보낸다고 가정을 해봅니다. RSA를 사용하게 되면, A는 B의 공개키(public key)를 알아야 메시지를 암호화 할 수 있습니다. B는 반드시 자신의 개인키(Private key)를 사용해서 메시지를 복호화하여야 합니다. 

A가 암호화된 메시지를 보내기 위해서는 B가 먼저 자신의 공개키 (n,e)를 신뢰성이 있는 경로를 통해서 A에게 보내어야 합니다. B의 개인키 (d)는 절대로 전달 되어서는 안 됩니다.

암호화(Encryption)

A는 B의 공개키를 획득한 뒤에, M이라는 메세지를 B에게 보낼 수 있게 됩니다. 

M을 변환하여 m을 만듭니다. 이 때는 변환법(padding scheme)을 사용합니다. 그런 뒤에 아래와 같이 B의 공개키 e를 사용하여 암호화 된 c를 계산합니다.

복호화(Decryption)

B는 개인키 d를 이용해서, 암호화 된 c를 m으로 복호할 수 있습니다.

그리고 m은 변환법(padding scheme)에 따라서 M으로 변환 할 수 있습니다.

RSA 알고리즘 툴: http://logos.cs.uic.edu/340%20Notes/rsa.html

참고문서: https://en.wikipedia.org/wiki/RSA_(cryptosystem)