RSA

 

RSA 알고리즘은 공개키 암호 시스템(Public Key Infrastructure)의 대표적인 알고리즘이다.

전자 상거래, 금융 거래, 디지털 인증서 등 보안이 필수적인 다양한 분야에서 가장 널리, 그리고 표준적으로 사용되고 있다.

 

RSA의 보안성은 소인수분해 문제의 어려움에 기반을 둔다. 아주 큰 두 소수를 곱해서 합성수를 만드는 것은 쉽지만, 반대로 그 합성수를 다시 원래의 두 소수로 분해하는 것은 수학적으로 매우 어렵다는 점을 이용한다.

 

RSA는 암호화 및 복호화 과정에서 복잡한 수학적 연산을 수행한다. 이로 인해 AES와 같은 대칭키 암호 알고리즘에 비해서 연산 비용이 많이 들고 속도가 느리다. 

따라서 대용량 데이터를 직접 암호화하기 보다는 Key Exchange나 전자 서명과 같이 적은 양의 중요 정보를 안전하게 전달하는 용도로 주로 사용된다. 실제 통신 데이터는 대칭키로 암호화하고, 그 대칭키를 RSA로 잠가서 보내는 방식이 일반적이다.

 

RSA 암호 알고리즘

RSA 암호 알고리즘에서는 두 개의 키가 사용된다.

• Public key(공개키) : 모든 사용자에게 공개되며, 평문 암호화시에 사용된다.
• Private key(비밀키) : 소유자만이 가지고 있으며 타인에게 노출되면 안된다. 공개키로 암호화된 암호문을 복호화할 때 사용된다.

 

Key Generation

공개키 암호 알고리즘에서는 공개키와 비밀키를 생성하는 키 생성 과정이 필요하다.

소인수분해를 어렵게 만들기 위해서 복잡한 연산을 거쳐 키를 생성해야한다.

 

1. 먼저 서로 다른 두 소수 $p$와 $q$를 선택한다. 일반적으로 1024비트 이상의 비트 길이가 같은 수로 생성한다. 그 뒤, $p$와 $q$를 곱해서 $n$을 구하고, $\phi(n)$을 계산한다.

$n = p \cdot q$

$\phi(n) = (p-1)(q-1)$

 

2. $\phi(n)$보다 작은 수 중 $\phi(n)$과 서로소인 $e$를 선택하고, $d \equiv e^{-1} \pmod{\phi(n)}$인 $d$를 구한다.

$e$의 곱셈의 역원이 존재하기 위해서는 $\phi(n)$과 $e$가 서로소임이 필수적이다.

 

$d \equiv e^{-1} \pmod{\phi(n)}$

 

• Public key(공개키) : $n$ (Modulus), $e$ (Public exponent)
• Private key(비밀키) : $d$ (Private exponent)

이론적으로는 $\phi(n)$을 구한 뒤 그와 서로소인 $e$를 찾지만, 실제 구현에서는 효율성을 위해 Public exponent $e$ 값을 미리 고정해 두는 경우가 많다(예: 65537). $e$를 고정한 상태에서 임의의 $p, q$를 생성하여 $\phi(n)$을 계산하고, 만약 $\phi(n)$이 고정된 $e$와 서로소가 아니라면 $n$($p, q$)을 다시 생성하는 방식을 주로 사용한다.

 

 

RSA 암복호화 

암호화

• $C \equiv M^e \pmod{n}$
• 사용되는 키 : 공개키 $(n, e)$

복호화

• $M \equiv C^d \pmod{n}$
• 사용되는 키 : 비밀키 $d$

 

• $M$ : 평문 (숫자로 변환된 데이터)
• $C$ : 암호문
• $n$ : Modulus (두 소수의 곱)
• $e$ : Public Exponent (공개 지수)
• $d$ : Private Exponent (비밀 지수)

 

암복호화 원리

$C^d \equiv (M^e)^d \equiv M^{ed} \pmod{n}$

 

오일러 정리에 따르면 $d \equiv e^{-1} \pmod{\phi(n)}$이므로 $e \cdot d = k \cdot \phi(n) + 1$을 만족하는 자연수 $k$가 존재한다. 따라서 다음 등식이 성립한다.

 

$M^{ed} \equiv M^{k\cdot \phi(n) + 1} \equiv M^{k\cdot \phi(n)}M \equiv (M^{\phi(n)})^kM \pmod{n}$

 

오일러 파이 정리에 의해서 $M^{\phi(n)} \equiv 1 \pmod{n}$이므로 $(M^{\phi(n)})^kM \equiv 1^k \cdot M \equiv M \pmod{n}$이 되어 복호화가 된다.

 

 

단계별 과정

상황 : A(송신자)가 B(수신자)에게 비밀 메세지를 보내려고 함.

 

1단계 : 키 배포

• B는 자신의 공개키 $(n,e)$를 A에게 알려준다.
• B는 자신의 비밀키 $d$를 아무도 모르게 보관한다.

2단계 : 암호화 Encryption by A

• A는 보내려는 평문 메시지를 숫자로 바꾼다. 이를 $M$이라고 한다.
  • 주의 : 이때 $M$은 반드시 $n$보다 작아야 한다. $M<n$
• A는 B의 공개키 $(n,e)$를 사용해서 암호문 $C$를 계산한다.

$ C \equiv M^e \pmod{n}$

• 계산된 암호문 $C$를 B에게 전송한다.

3단계 : 복호화 Decryption by B

• B는 암호문 $C$를 받는다.
• 자신의 비밀키 $d$와 $n$을 사용해서 원래 숫자를 계산한다.

$M \equiv C^d \pmod{n}$

• 계산된 숫자 $M$을 다시 원래 문자열로 변환해서 내용을 확인한다.

 

가장 많이 사용되는 Public Exponent

 

Public Exponent 값으로 65537(0x10001)을 가장 많이 사용한다.

• 소수이기 때문에 대부분의 $\phi(n)$과 서로소 관계가 성립하여 n을 재생성해야 할 가능성이 적다.
• 1인 비트가 적어서 거듭제곱 연산 시 적은 시간이 소요된다.
• 3, 5 같이 작은 $e$에 비해 많은 공격으로부터 안전하다.

 

RSA & RSA-CRT

이론적으로 RSA는 완벽해보이지만, 현식에서는 큰 수의 곱셈과 거듭제곱 때문에 속도가 매우 느리고 메모리를 많이 잡아 먹는다. 그래서 대용량 데이터 암호화에는 거의 사용되지 않는다. 대신 전자 서명이나, 대칭치 교환 같은 짧고 중요한 정보에만 주로 사용한다.

 

 

PEM (Privacy Enhanced Mail)

리눅스나 웹 서버 설정 시 자주 보는 public.pem, key.pem 파일들은 Base64 방식으로 인코딩되어 있어 사람이 읽을 수 없는 데이터처럼 보이지만 실제로는 다음과 같은 정보를 담고 있다.

 

① 공개키 파일 (public.pem)

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCPKPRtuUFfRXy3FJ0/kGfOEXgw
2FjXq0AXXniG557NU3z4uVa2u71uJua91ihvUlSChRd2RMTaw2sBcnT99FeNMHTy
e0y0GTf01bk+rPkSoj7EiyEt09TkvP1Mbd+tDlFEIW0Q5Vt8qtB72QDkgJ6KcM+A
lJ25bFrIHNN0+sF99wIDAQAB
-----END PUBLIC KEY-----

 

• 내용: 암호화에 필요한 딱 두 가지 정보만 들어 있다.
• 구성: $n$ (모듈러스), $e$ (공개 지수)

② 개인키 파일 (key.pem)

-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCPKPRtuUFfRXy3FJ0/kGfOEXgw2FjXq0AXXniG557NU3z4uVa2
u71uJua91ihvUlSChRd2RMTaw2sBcnT99FeNMHTye0y0GTf01bk+rPkSoj7EiyEt
09TkvP1Mbd+tDlFEIW0Q5Vt8qtB72QDkgJ6KcM+AlJ25bFrIHNN0+sF99wIDAQAB
AoGAbBvechnLPzoHU26SzVSsv1Y78I8AkGV3ce5akG3LY30fy+iSjk46YDuqVkOq
p16CCUqejCakjhuy7BXWOY1Sq1T4sFzTuPtZkKmp2wWi4EA1rEtoUNCuP0eq4k80
jwfo3gje5GPsh0kNYaddkzth0vB+xg9kPhjFpqZf60uC87ECQQD9queZ48e5oXHg
gaenpDBeN1ipHAmC6qXc4ynnhqAOkX2Opb+3d9xmzJZhpQQYWE/5sPY64VsjsyJE
qQRumc3vAkEAkHnujBTNJ/FdMkB3w9ydbsgJycchgeELLNUbGgCGUj+U/VdEAWT2
S1i6vcyIszCMUNfWcdQXvoPjFqn/xAtYeQJAEpoj3c8saFqEhVg8uTh7K42XfN9H
e0hF3YrzGb1vo2Hb+UgCZSvvB8LdDFATms1vH/pwNCUuj9GlI6/ZWVsCFQJABaiw
/k2mR4U9uEUsK8DNbdRqBbxGBLdS37utJxSULk6NQGsVn9RbjVH5ZovHYvVo2ZXK
sYS0NWMnFvErsnsbSQJBAKD1FRZ5NTFWWV4Z1l9BIPHo7unQocOxKPEYgwTs/3Np
0/oErIudtTkalMsdXW6AU+ucIpzks8FWhGqwgFTTWGc=
-----END RSA PRIVATE KEY-----

• 내용: 복호화에 필요한 $d$만 있는 게 아니다. 키 생성에 쓰였던 $p, q$와 최적화를 위한 추가 정보들이 들어있다.
• 구성: $n, e, d, p, q$ + CRT 파라미터($d_p, d_q, q_{inv}$)

개인키 파일에 왜 $p, q$까지 다 들어있을까?
RSA-CRT(최적화) 기법을 쓰려면 $p$와 $q$가 반드시 필요하기 때문이다.

 

 

 

RSA-CRT

복호화 과정($M \equiv C^d \pmod{n}$)은 암호화보다 훨씬 느리다. 비밀 지수 $d$가 매우 큰 수이기 때문이다. 이 느린 속도를 해결해주는 것이 RSA-CRT 이다.

 

RSA-CRT란 어려운 계산($n$으로 나눈 나머지)을 한 번에 하는 대신, 문제를 두 개의 쉬운 계산($p$와 $q$로 나눈 나머지)로 쪼개서 푸는 방식이다.

• 일반 복호화 : 거대한 $n$과 $d$를 가지고 힘들게 계산.
• CRT 복호화 : 좀 더 작은 $p,q$를 가지고 가볍게 두 번 계산 후 합침.

 

다음 3개의 값이 바로 쪼개서 계산하기 위해서 미리 만들어준 값이다.

• $d_p = d \pmod{p-1}$ : $p$의 세계에서 사용할 작은 비밀키
• $d_q = d \pmod{q-1}$ : $q$의 세계에서 사용할 작은 비밀키
• $q_{\text{inv}} = q^{-1} \pmod{p}$ : 나중에 두 결과를 합칠 때 사용하는 접착제 역할

 

실제 복호화 과정은 복잡해 보이지만 원리는 간단하다.

거대한 지수 $d$와 $n$을 쓰는 대신, 작아진 지수 $d_p, d_q$와 $p, q$를 사용한다.

 

1. $m_p$ 구하기 : $p$로 나눈 나머지 세상에서의 평문 조각  

$m_p = C^{d_p} \pmod{p}$

 

2. $m_q$ 구하기 : $q$로 나눈 나머지 세상에서의 평문 조각

$m_q = C^{d_q} \pmod{q}$

 

3. 합치기(최종 평문)

• 구해놓은 두 조각($m_p, m_q$)을 합쳐서 원래의 $M$을 만들어야 한다.
• 이때 Garner의 공식을 사용한다.

$h = (m_p - m_q) \times q_{\text{inv}} \pmod{p}$

(단, $m_p - m_q$가 음수면 $p$를 더해서 양수로 만든다.)

 

• 최종 평문은 다음과 같다.

$M = m_q + (h \times q) = m_q + q \cdot q_{\text{inv}} \cdot (m_p - m_q)$

이 식을 $q$로 나누면 뒤쪽 항($h \times q$)가 사라지니 나머지는 $m_q$가 된다.
이 식을 $p$로 나누면 식을 정리했을 때 나머지가 $m_p$가 되도록 $h$를 만든 것이다.

 

 

이 방식을 사용하면 일반적인 복호화보다 평균 3배 이상 속도가 빨라진다. 3배면 엄청난 차이이기 때문에, OpenSSL이나 Java Security 등 실제 라이브러리들은 대부분 기본적으로 이 CRT 방식을 사용하고 있다.