RSA 암호화가 무엇이며, 어떻게 동작합니까?

RSA란 보안 네트워크 연결 및 전자 서명을 생성하는 데 사용되는 공개 키 암호화 시스템입니다.

RSA 암호화 방식은 1977년 매사추세츠 공과대학교에서 암호화 알고리즘을 만든 개발자들의 성(Rivest, Shamir, Adleman)에서 이름을 따왔습니다.

RSA는 메시지의 암호화를 위해서 공개 키를 사용하고 복호화를 위해서는 개인 키를 사용합니다. RSA 알고리즘의 연산 방식은 연산하기는 쉬우나 되돌리기는 어려운 단방향 함수를 포함하고 있습니다. 바로 이것이 RSA 알고리즘을 무차별 주입 공격으로부터 안전한 암호화 알고리즘이 되게 하는 것입니다.

RSA는 공개 키와 개인 키를 사용하는 비대칭 암호화(공개 키 암호화)의 유형 중 하나입니다.

• 메시지를 암호화 하는데 공개 키를 사용합니다 – 이는 평문을 암호문으로 바꾸기 위해서 입니다. 공개 키는 누구나 자유롭게 접근하여 열람이 가능합니다.
• 암호화된 메시지를 복호화 하려면 개인 키가 필요합니다 – 이는 암호문을 평문으로 다시 바꾸기 위해서 입니다. 개인 키는 항상 비밀로 유지하십시오.

반면, 대칭 암호화 방식 (예: AES, Twofish 암호화) 에서는 메시지를 암호화하고 복호화 하는데 같은 개인 키를 사용합니다. 만약 사전에 개인 키를 안전하게 수신자와 공유할 수 있는 기회가 있다면 이 방식 또한 괜찮습니다. RSA를 포함한 공개 키 암호화 방식은 그런 기회를 가지지 못할 때에도 사용하기 좋습니다.

비대칭 암호화 알고리즘은 4가지 파트로 구성됩니다: 공개 키와 개인 키 생성, (공개) 키 교환 (키 교환 알고리즘을 이용), 암호화, 그리고 복호화 입니다.

키 생성이란 RSA 키, 즉 개인 키와 공개 키를 연산하는 절차입니다. 프로세스는 다음과 같습니다:

1. 두 개의 소수를 선택하기 (p와 q)

안전한 암호화를 위해서, 선택된 소수들이 서로 다르고 큰 숫자여야 합니다.

예를 들어, 2048 비트 RSA 암호화는 308 자리의 소수를 사용합니다. 이렇게 큰 숫자를 만들어 내는 것이 쉽지 않으므로, 생성시 소수 판별법을 사용합니다.

2. 모듈러스 (n) 계산하기

개인 키와 공개 키 생성의 첫 반쪽 부분은 모듈러스 (n) 생성을 하는 것입니다. 모듈러스는 p와 q를 곱한 값입니다.

n = p x q

이게 계산하기는 쉬울 지라도, 모듈러스 값을 얻기 위해 어떤 숫자들을 곱했는지를 추정할 수 없어야 합니다.

예를 들어서, 만약 당신의 p가 6,637이고 q가 8,971라고 합시다. 계산기로 곱셈을 하면 59,540,527 이 나올 것입니다. 하지만 당신이 단지 결과값인 59,540,527을 보고 어떤 숫자들끼리 곱해진 것인지 알 수 있을까요? 또는 그걸 알아낼 수 있는 계산기가 있을까요?

아마도 알 수 없을 것입니다. 이것이 바로 RSA 암호화의 핵심 개념입니다. 알고리즘은 간단해야 하지만 역으로 되돌릴 수 없어야 합니다.

위에서 예시로 나온 숫자들은 인수분해 계산기를 사용할 경우 분해가 가능할 수도 있습니다. 하지만, 앞에서 언급했듯이 RSA 암호화는 308자리 소수를 사용하므로 훨씬 값이 크고 계산하기 어렵습니다.

3. 공개 키(e) 생성

RSA 공개 키는 모듈러스 (n)과 공개 지수 (e)로 구성되어 있습니다. 공개 키의 두 번째 반쪽인 e를 얻으려면 n에 대한 totient인 φ를 계산해 내야 합니다. :

φ (n) = (p − 1) x (q − 1)

그런 다음 임의의 정수인 e를 골라야 하는데, 1보다는 크지만 φ보다는 작고 서로소여야 합니다. 주로 숫자 65,537이 RSA 암호화에서 정수 e로 쓰입니다.

4. 개인 키(d) 생성

RSA 개인 키는 모듈러스 (n)과 비밀 지수 (d)로 이루어져 있습니다. d는 p와 q로부터 계산되며 그 두 숫자의 최대 공약수(GCD)를 찾는 것을 포함합니다. 이 과정은 유클리드 호제법(Euclidean algorithm)이라고 불리는데, 그냥 온라인 계산기로 계산하는 것이 더 쉽습니다.

만약 누군가 RSA 알고리즘으로 메시지를 암호화하여 당신에게 보내고 싶다고 한다면, 그는 당신의 공개 키를 알아야 합니다. 당신은 공개 키를 신뢰할 수 있는 방식으로 공유하면 되는데, 꼭 비밀 경로를 사용할 필요는 없습니다.

상대방이 당신의 공개 키(e와 n)을 가지고 있고 당신에게 메시지(M)을 보내고 싶어 한다고 가정합시다. 그렇다면 다음은 어떻게 될까요?

평문을 암호문(C)로 바꾸기 위해서는, 다음 함수가 필요합니다:

C = M^e mod n

Mod란 modulo operation의 약자로서, 한 수를 다른 수로 나누고 남은 나머지 값을 의미합니다. 예를 들어, 11 mod 3 = 2 입니다. (3으로 11을 나누면 3번을 나누고도 2가 남음).

만약 전송하고자 하는 메시지가 숫자인 경우, M을 숫자로 치환하면 함수는 모두 완성입니다. 만약 텍스트 메시지라면, 텍스트를 숫자로 먼저 변환시켜야 합니다. 예를 들어, ASCIIASCII 문자를 사용하면 문자 “NORDVPN”은 숫자로 “78798268868078”이 될 것입니다.

수신한 암호문을 풀기 위해서는 개인 키(d와 n)을 비밀 장소에서 가져오고, 받은 암호문 (C)와 다음의 함수를 사용해야 합니다:

M = C^d mod n

이렇게 하면 암호문이 원래 메시지로 변환될 것입니다.

공개 키 암호화 기술인 RSA는 이전에 접근한 적 없는 상대나 서버에 안전하게 정보를 보낼 때 유용합니다. 이전에 접근한 적이 없어서 대칭 암호화에 사용되는 개인 키를 가지고 있지 않을 때 잘 활용됩니다. 그래서 RSA 기술은 브라우저, 이메일 서비스, 채팅 메신저, 클라우드 서비스, VPN, P2P 서비스 등 다른 통신 채널에서 찾아볼 수 있습니다.

그러나, 이제 디지털 암호화 분야에서 RSA는 고전적인 기술이 되었으므로 보통 다른 암호화 기술과 함께 사용합니다. 일반적인 예시로 RSA를 사용하여 대칭 암호화에 쓰이는 개인 키를 암호화 하는 것입니다. 즉, 실제 민감한 정보를 대칭 암호화 기술을 사용해 보호하면서 키를 안전하게 공유하는 것입니다.

RSA의 메인 용도는 보안 연결을 수립하고 전자 서명을 생성하는 것을 포함합니다. RSA는 메시지나 파일을 암호화하는 데 사용되지 않는데, 이는 다른 암호화 시스템들이 더 안전하고, 빠르며, 리소스도 적게 소모하기 때문입니다.

보안 연결 구축

웹 브라우저들은 스니핑 또는 중간자 공격을 예방할 수 있는 보안 인터넷 연결을 위해 RSA를 사용합니다. 대다수의 인터넷 연결은 SSL을 통해 트래픽을 지키는데, RSA가 SSL/TLS 핸드쉐이크의 한 부분을 담당합니다. OpenSSL과 같은 암호화 라이브러리에서 이것을 찾아볼 수 있습니다.

OpenVPN은 VPN 연결을 할 때 VPN 클라이언트와 VPN 서버간의 키 교환과 보안 통신을 위해 RSA를 이용합니다. 하지만 보통 VPN은 실제 데이터를 각자 다른 암호화 알고리즘을 사용하여 보호합니다. 예를 들어, NordVPN의 차세대 VPN 암호화는 AES-256-GCM을 사용합니다.

또한, RSA는 세션 키를 암호화 하는 PGP 암호화에 사용된 최초의 알고리즘이기도 합니다.

전자 서명 생성

당신은 메시지나 문서를 개인 키를 이용하여 서명할 수 있으며, 상대방은 그 메시지 혹은 문서의 진위성을 확인하기 위하여 공개 키를 사용합니다.

RSA는 다용도로 쓰일 수 있어서, 이메일부터 뱅킹 서비스, 온라인 쇼핑까지 전자 서명과 관련한 모든 분야에 사용됩니다.

예를 들어, 이메일은 RSA 알고리즘을 사용하는 PGP 암호화를 이용하여 전자 서명을 생성합니다.

RSA 암호화 시스템에는 장점과 단점이 있으므로 RSA 암호화를 구현하기 전에 고려해야 합니다.

• 

  RSA 알고리즘은 이해하기 쉬우며 구현하기도 용이합니다. 알고리즘이 꽤나 기본적이고, 함수도 다른 알고리즘에 비해 복잡하지 않은 편입니다. 예를 들어, 타원곡선 암호화 방식과 거기에 사용되는 유명한 알고리즘인 ECDSA 만큼 복잡하지 않습니다. RSA와 ECDSA 중 선택을 해야 할때, 많은 서비스들이 리소스 관리 측면에서 더 효율적이기 때문에 ECDSA로 전환하고 있는 추세입니다.
• 

  RSA 암호화 방식은 다용도로 사용되기 좋아서, 보편적으로 사용됩니다.
• 

  RSA 암호화가 올바르게 구현 된 경우, 현재의 컴퓨팅 능력 안에서 RSA를 무차별 대입 공격으로 뚫을 수 없습니다.
• 

  제대로 구현되지 않은 경우, RSA는 여러 공격에 취약합니다.
• 

  RSA 키 길이는 암호화 보안에서 매우 중요합니다. 하지만 키 길이가 길수록 컴퓨팅 하는데 많은 전력이 필요하므로 지속 가능성 측면에서 좋지 않습니다.
• 

  복호화 과정이 오래 걸리고 리소스가 많이 필요합니다.
• 

  접근 가능한 RSA 공개 키의 갯수가 많아질 수록 공격자들이 암호화를 뚫거나 넘어설 방법을 생각해 내는 것이 쉬워질 것입니다.

RSA의 보안은 구현하는 방식에 크게 좌우됩니다. 각각의 프로세스 단계 중에 암호화 결과에 영향을 주는 취약점이 포함되어 있을 수 있습니다.

약한 난수 생성기

RSA 알고리즘은 소수를 선택하는 것에서부터 시작하는데, 이 첫 단계부터가 취약점이 될 수 있습니다. 만약 선택된 소수들이 충분히 랜덤하지 않다면, 쉽게 모듈러스를 인수분해하여 암호화를 해독할 수 있습니다.

여기서 약한 난수 생성기가 결함의 원인이 되므로 의사 난수 생성기를 사용하면 취약점을 제거할 수 있습니다.

키 생성 오류

소수가 충분히 랜덤하게 선택되었다 해도 너무 작은 숫자이거나 서로 가까울 수 있습니다. 그것이 또 다른 문제를 야기할 수도 있습니다.

RSA 알고리즘은 암호화에 공개 키를 사용하므로, 인수 분해를 방지하기 위해서 키 사이즈가 중요합니다. 숫자가 작을 경우 소수 (p와 q)를 알아내는 것이 쉽습니다. 그리고 만약 숫자들이 서로 너무 가까울 경우, 개인 키 (d) 가 상대적으로 작아집니다.

그래서 보안 전문가들은 최소 2048 비트의 키 사이즈를 권장합니다. 보통 최신의 RSA 키 사이즈는 4096 비트입니다.

위에서 언급된 RSA 취약점을 무시할 경우 쉽게 RSA 공격을 받을 수 있습니다.

인수 분해 공격 (Factorization attack)

취약점이 제대로 해결되지 않는다면, 사이버 범죄자들이 취약점을 악용하여 인수분해 공격을 자행할 수 있습니다.

RSA 암호화는 아무도 곱하기 된 결과값 n에서 소수인 p와 q를 알아낼 수 없을 경우에만 안전합니다. 그러나, 그 소수들이 서로 너무 가깝거나, 랜덤하지 않은 경우, 또는 충분히 크지 않은 경우에 공격자는 인수분해를 해서 개인 키를 알아낼 수 있습니다.

부 채널 공격 (Side-channel attack)

부 채널 공격에서는 공격자들이 암호화된 키를 해독하지 않고 복호화 과정에서 생기는 추가 정보를 분석합니다. 예를 들어, 공격자들이 알고리즘을 수행하는 동안 소모하는 전력량 또는 심지어 컴퓨터가 만들어 내는 소리까지 분석합니다.

타이밍 공격 또한 부 채널 공격 중 하나입니다. RSA 타이밍 공격에서는 공격자들이 개인 키(d)를 알아내기 위하여 다른 알려진 암호문의 복호화 시간을 분석합니다.

평문 공격 (Plaintext attack)

공격자가 평문 중 어느 부분이라도 암호문과 매치 시킨다면, 평문 공격을 수행할 수 있습니다:

• 짧은 메시지 공격(Short message attack): 공격자가 평문의 일부분에 접근하여 그것을 암호화하여 암호문으로 만듭니다. 그리고 그 암호문을 나머지 평문 메시지를 추론하는데 사용합니다. 패딩을 활용하여 평문 공격을 막을 수 있습니다. 암호화 하기 전의 평문에 추가 데이터를 포함하는 것입니다.
• 낮은 지수 공격(Cycling attack): 공격자는 암호문을 생성하기 위해 수행되었을 가능성이 있는 순열 연산을 테스트합니다. 그리고 만약에 그 연산과정이 맞다면, 암호문으로부터 평문을 얻기 위해서 반대의 프로세스를 수행합니다.
• 숨겨지지 않은 메시지 공격(Unconcealed message attack): 드물지만 이론적으로 일부 암호문이 원본 평문 메시지와 동일할 수도 있습니다. 만약 이런 경우가 발생한다면, 공격자들이 나머지 암호화된 부분을 추론하여 공격할 수 있습니다.

선택 암호문 공격 (Chosen cipher attack)

앞서 언급한 바와 같이, 개인 키를 생성하기 위해 유클리드 호제법을 사용할 수 있습니다. 알고리즘은 누구에게나 공개되어 있으므로, 공격자들이 확장 유클리드 호제법을 사용하여 암호문으로부터 평문을 얻어낼 수 있습니다. 그것이 선택 암호문 공격이 동작하는 방식입니다.

RSA의 취약점과 공격 위협을 고려했을 때, RSA 암호화가 안전한지에 대해 의문을 가지는 것은 당연합니다. 정답은 “그때 그때 다르다”입니다.

보다 명확하게는, 구현 방식에 따라 달라질 수 있습니다.

취약점을 고려하지 않고 구현한 RSA 암호화는 보안 위협을 견뎌낼 수 없습니다. 불행히도, 연구에 따르면 많은 RSA 사용자들이 꽤 자주 취약점을 무시한다고 합니다.

2012년 연구에 따르면 550만개의 공개 키가 수집되었고, 1024비트 RSA 암호화 키는 기껏해야 99.8%까지만의 보안을 제공합니다. 즉, 13,000개의 키는 쉽게 해독될 수 있는 것입니다.

Keyfactor에서 내놓은 더 최근의 연구 결과에 따르면, 인증서 172장당 한 장 꼴로 인수분해 공격에 대해 취약점이 있다고 밝혀졌습니다.

그러나, RSA 알고리즘의 취약점을 예방하고, 적당한 키 길이를 준수하며, 패딩과 같은 추가 보안 조치를 취할 경우에 RSA 암호화는 대부분의 최신 컴퓨터에서 안전하며 뚫을 수 없습니다. 적어도 당분간은 말입니다.

RSA 암호화는 보안이나 효율성 측면에서 볼 때 최고의 암호화 알고리즘이 아니므로 미래는 그다지 밝지 않습니다.

기존의 컴퓨터가 RSA 암호화를 풀려면 300조 년이 소요되지만, 양자 컴퓨터는 단 10초만에 깰 수가 있습니다. 하지만 이런 컴퓨터는 아직 존재하지 않으므로, 현재로서는 RSA 암호화도 괜찮다고 생각할 수도 있습니다. 하지만 RSA 알고리즘의 미래가 암울한 이유는 이것 뿐만이 아닙니다.

미국 표준 기술 연구소의 권고안에 따르면, 2048 비트 암호화 키를 사용하는 RSA 암호화가 2030년 까지는 안전하다고 합니다. 4096 비트 길이의 키를 사용한다면 조금 더 오래 사용할 수도 있지만, 그건 지속 가능하지 않을 것입니다.

결국, 암호화 알고리즘을 잘 선택하기 위해서는 보안만 고려해서는 안됩니다. 암호화의 효율성 또한 중요합니다. 바로 그 점이 RSA의 부족한 부분입니다.

RSA 알고리즘은 작동할 때 리소스를 많이 소모합니다. 이 알고리즘은 느린데 특히 길이가 긴 키를 사용하면 더 느립니다. 그러나 짧은 키를 사용한다면 암호화 시스템의 보안이 취약해집니다. 4096 비트 키를 사용하는 것은 현재로써는 괜찮으나, 그 이상의 것은 컴퓨팅 파워를 너무 많이 소모합니다.

RSA는 몇 년에 걸쳐 점점 사용하지 않는 추세입니다. 타원 곡선 암호화 알고리즘처럼 더 안전하고 효율적인 대체 시스템들이 있는 상황에서 RSA를 사용하는 것은 너무 번거로운 일로 느껴집니다. 그러므로 RSA가 더 이상 사용되지 않는 것은 시간 문제입니다.