[암호학] RSA 알고리즘이란? RSA 알고리즘의 개요 및 종류

RSA 알고리즘이란?

공개키 알고리즘은 대칭키 알고리즘과 달리 두 개의 서로 다른 키를 사용하여 암호화와 복호화를 하는 방식입니다. 이 알고리즘은 정보통신 분야에서 보안 기술을 구현하는 데 사용되며, 대표적인 공개키 알고리즘으로 RSA 알고리즘이 있습니다.

 

RSA 알고리즘은 1977년에 Ron Rivest, Adi Shamir, Leonard Adleman이 개발한 알고리즘으로, 이름은 개발자들의 이니셜을 따서 지어졌습니다. RSA 알고리즘은 모듈러 연산, 오일러-파일 함수, 소수 판별 등의 수학적 개념을 기반으로 하고 있습니다.

 

RSA 알고리즘의 설명

RSA 알고리즘에서는 먼저, 암호화하려는 데이터를 숫자 형태로 바꾸어 처리합니다. 이때, 데이터의 크기가 크면 처리 시간이 오래 걸리므로 데이터의 크기를 줄이는 방법을 사용합니다. 예를 들어, 데이터를 작은 블록으로 나누어 처리하거나, 해시 함수를 사용하여 데이터의 압축된 버전을 생성하는 방법 등이 있습니다.

 

다음으로, RSA 알고리즘에서는 두 개의 서로 다른 소수 p와 q를 선택하고, 이를 곱한 값을 n으로 정의합니다. n을 모듈러 연산에 이용하며, 이때 n을 알고 있어야만 복호화를 할 수 있습니다. 또한, 오일러-파일 함수를 이용하여 n과 서로소인 값을 구하고, 이를 phi(n)으로 정의합니다.

 

그 다음으로, 공개키 e와 개인키 d를 생성합니다. 이때 e는 phi(n)과 서로소인 값을 선택하며, d는 e의 역원을 구하여 정의합니다. e와 n은 공개키로, d와 n은 개인키로 사용됩니다.

 

암호화를 수행할 때는 공개키 e를 이용하여 데이터를 암호화하고, 복호화를 수행할 때는 개인키 d를 이용하여 데이터를 복호화합니다. 암호화된 데이터를 누구나 복호화할 수 없으며, 오직 개인키를 가지고 있는 사람만이 복호화할 수 있습니다.

 

RSA 알고리즘은 대칭키 알고리즘보다 보안성이 높으며, 대용량 데이터의 암호화나 복호화도 가능합니다. 또한, RSA 알고리즘은 SSL/TLS, 전자 서명, 디지털 인증서 등 많은 분야에서 사용됩니다.

 

하지만, RSA 알고리즘도 완벽한 보안성을 보장하지는 않습니다. RSA 알고리즘의 보안성은 크게 두 가지 방법으로 침해될 수 있습니다. 첫 번째는 수학적 알고리즘을 사용하여 개인키를 찾아내는 것이고, 두 번째는 공격자가 RSA 알고리즘이 사용되는 컴퓨터 시스템을 해킹하여 개인키를 탈취하는 것입니다.

 

따라서, RSA 알고리즘에서는 키의 비밀성이 매우 중요합니다. 개인키는 반드시 안전한 장소에 보관해야 하며, 공개키는 모든 사용자가 사용할 수 있도록 공개되어야 합니다. 또한, RSA 알고리즘을 적용할 때는 키 크기를 적절하게 설정해야 합니다. 키 크기가 작으면 보안성이 떨어지며, 큰 키를 사용하면 처리 시간이 오래 걸리는 단점이 있습니다.

 

RSA 알고리즘 외에도, 다양한 공개키 알고리즘이 개발되어 있습니다. 대표적인 예로는 Diffie-Hellman 알고리즘이 있습니다. Diffie-Hellman 알고리즘은 공유 비밀키를 생성하는 알고리즘이며, SSL/TLS 프로토콜에서 암호화 키를 생성하는 데 사용됩니다.

 

 

 

RSA의 원리

 

RSA는 두 개의 키를 사용하는 암호화 방식입니다. 여기서 키란 메시지를 열고 잠그는 상수(변하지 않는 수)를 의미합니다. 일반적으로 많은 공개키 알고리즘의 공개키(public key 또는 pub key)는 모두에게 알려져 있으며 메시지를 암호화(encrypt)하는데 쓰이며, 암호화된 메시지는 개인키(private key 또는 pri key)를 가진 자만이 복호화(decrypt)하여 열어볼 수 있습니다.

공개키 알고리즘은 누구나 어떤 메시지를 암호화할 수 있지만, 그것을 해독하여 열람할 수 있는 사람은 개인키를 지닌 단 한 사람만이 존재한다는 점에서 대칭키 알고리즘과 차이를 가집니다.

RSA는 소인수 분해의 난해함에 기반하여, 공개키만을 가지고는 개인키의 안전한 암호화 시스템을 보장합니다.

이해하기 쉬운 예를 들자면, A라는 사람에게 B라는 사람이 메시지를 전하고자 할 때 B는 A의 열린 자물쇠를 들고 와 그의 메시지를 봉인(공개키 암호화 과정에 해당)하고, 그런 다음 A에게 전해 주면, 자물쇠의 열쇠(개인키에 해당)를 가지고 있는 A가 그 메시지를 열어보는(개인키 복호화 과정에 해당) 식이 됩니다. 중간에 그 메시지를 가로채는 사람은 그 열쇠를 가지고 있지 않으므로 메시지를 열람할 수 없습니다. (여기서의 조건은 A 의 열쇠가 안전하다는 조건이 있습니다.)

하지만 실제 사용에서는 메시지와 공개키 모두를 알 수 있다면 변조된 메시지를 보낼 수 있기 때문에, 실제로는 수신측의 공개키만을 사용하여 암호화하는 경우가 대부분입니다. 따라서 송신자는 수신자의 공개키를 이용해 메시지를 암호화하고, 수신자는 자신의 개인키를 이용해 메시지를 복호화합니다.

위의 구성된 방식이 일반적으로 사용되고 있습니다. RSA의 개인키는 자물쇠의 형태(공개키에 해당)만 보고서는 쉽게 제작할 수 없게 되어 있습니다.

 

RSA 키의 생성 원리

 

A와 B가 보안이 보장되지 않은 환경에서 서로 비밀 메시지를 주고 받고 싶다고 가정합니다. B가 A에게 메시지를 전달하기 위해서는 A의 공개키가 필요합니다. A는 아래와 같은 방법을 통해 자신의 공개키와 개인키를 생성합니다.

1. 서로 다른 두 소수 p와 q를 선택합니다. (p ≠ q)
2. 두 수를 곱하여 N = pq를 계산합니다.
3. ϕ(N) = (p-1)(q-1)를 계산합니다.
4. ϕ(N)보다 작고, ϕ(N)와 서로소인 정수 e를 선택합니다.
5. 확장된 유클리드 알고리즘을 사용하여 de ≡ 1 (mod ϕ(N))을 만족하는 d를 계산합니다.

A의 공개키는 <N, e>이고, 개인키는 <N, d>입니다. A는 <N, e>만을 B에게 공개하고, B는 이 공개키를 사용하여 자신의 메시지를 암호화합니다. p와 q를 알면 d와 e를 계산할 수 있기 때문에 p와 q의 보안은 매우 중요합니다. 따라서 공개키와 개인키 생성 후에는 두 수를 지우는 것이 안전합니다.

 

 

RSA로 암호화 하는 과정

평문을 암호화하기 위해서는 공개키인 N과 e가 필요합니다. 복호화할 때 필요한 개인키는 d입니다.

암호화 과정은 다음과 같습니다.

 

1. 암호화하고자 하는 평문이 n보다 작은 자연수라고 가정합니다.
2. 평문을 e번 제곱해줍니다. 즉, n^e를 계산합니다.
3. 계산된 값에 N으로 나눈 나머지를 구합니다.
4. 나머지 값이 암호화된 값입니다.

예를 들어, 평문이 8이라고 하고 공개키가 <N=34, e=3>이라면 다음과 같이 암호화됩니다.

 

1. 8의 3제곱인 512를 계산합니다.
2. 512를 34로 나눈 나머지인 2가 암호화된 값입니다.

따라서, 이 암호화된 값 2를 복호화하려면 개인키인 d를 사용해야 합니다.

 

RSA로 복호화 하는 과정

 

암호문(encrypted text)을 복호화 하려면 개인키가 필요합니다. 개인키는 N과 d가 필요합니다.

개인키로 복호화 하는 과정은 다음과 같습니다.

1. 암호문 2를 개인키인 d만큼 제곱하고 N으로 나머지 연산을 합니다.
2. 2^d를 계산합니다.
3. 계산한 결과에 N으로 나머지 연산을 합니다.
4. 예를 들어, N = 34, d = 7이라면, 2^7 = 128이고, 128 % 34 = 26 입니다.
5. 그러면 복호화된 값은 26입니다.

 

정리

 

공개키 알고리즘은 대칭키 알고리즘보다 보안성이 높고, 안전한 통신을 보장할 수 있습니다. 그러나, 공개키 알고리즘은 대칭키 알고리즘보다 느리고 복잡하며, 키 관리의 어려움이 있습니다. 따라서, 보안성이 높은 데이터에는 공개키 알고리즘을 사용하고, 처리 시간이 중요한 데이터에는 대칭키 알고리즘을 사용하는 것이 좋습니다.키를 생성하는 알고리즘이며, SSL/TLS 프로토콜에서 암호화 키를 생성하는 데 사용됩니다.