RSA

RSA는 Ron Rivest, Adi Shamir, Leonard Adleman에 의해 1977년 개발된 최초의 실용적인 공개 키 암호화 알고리즘이다. 두 큰 소수를 곱하는 것은 쉽지만, 그 결과를 소인수분해하는 것은 계산적으로 매우 어렵다는 수학적 난제를 기반으로 한다. 충분히 큰 키 크기를 사용하면 현재 알려진 알고리즘으로는 현실적인 시간 내에 해독이 불가능하다.

키 생성 과정

RSA 키 쌍을 생성하는 단계는 다음과 같다:

1. 두 소수 선택

   • 두 개의 큰 소수 p와 q를 무작위로 선택한다.
   • 실제 사용에서는 각각 1024비트 이상의 소수를 선택한다.

2. 모듈러스 계산

   • n = p × q를 계산한다.
   • n은 공개 키와 개인 키 모두에 포함되는 모듈러스이다.

3. 오일러 피 함수 계산

   • φ(n) = (p-1)(q-1)을 계산한다.
   • φ(n)은 n과 서로소인 n 이하 양의 정수의 개수이다.

4. 공개 지수 선택

   • 1 < e < φ(n)이고 φ(n)과 서로소인 e를 선택한다.
   • 실무에서는 보통 e = 65537 = 2^16 + 1을 사용한다.
   • 65537은 충분히 크면서도 1비트가 2개만 설정되어 있어 빠른 연산이 가능하다.

5. 개인 지수 계산

   • d × e ≡ 1 (mod φ(n))를 만족하는 d를 계산한다.
   • 확장 유클리드 호제법을 사용하여 계산한다.
   • d는 e의 모듈러 역원이다.

6. 키 쌍 생성

   • 공개 키: (e, n)
   • 개인 키: (d, n) 또는 (d, p, q) (CRT 최적화를 위해)

암호화와 복호화

암호화

• 평문 m을 암호문 c로 변환한다.
• 수신자의 공개 키 (e, n)을 사용한다.

c = m^e mod n

• 평문 m은 n보다 작은 정수여야 한다.
• 긴 메시지는 블록으로 나누어 처리한다.

복호화

• 암호문 c를 평문 m으로 복원한다.
• 수신자의 개인 키 (d, n)을 사용한다.

m = c^d mod n

정확성 증명

RSA가 올바르게 동작하는 이유는 다음과 같이 증명된다:

c^d ≡ (m^e)^d ≡ m^(ed) (mod n)

ed ≡ 1 (mod φ(n))이므로
ed = k×φ(n) + 1 (k는 정수)

따라서:
m^(ed) = m^(k×φ(n) + 1) = (m^φ(n))^k × m

오일러의 정리에 의해:
m^φ(n) ≡ 1 (mod n) (gcd(m, n) = 1일 때)

따라서:
(m^φ(n))^k ≡ 1^k ≡ 1 (mod n)

결론:
m^(ed) ≡ 1 × m ≡ m (mod n)

관련 수학 개념

오일러 피 함수 (Euler’s Totient Function)

• φ(n)은 n 이하의 양의 정수 중 n과 서로소인 정수의 개수이다.
• n이 소수 p일 때: φ(p) = p - 1
• n이 두 소수의 곱 p×q일 때: φ(p×q) = (p-1)(q-1)

예시:

φ(15) = φ(3×5) = (3-1)(5-1) = 2×4 = 8
15 이하에서 15와 서로소: 1, 2, 4, 7, 8, 11, 13, 14 (8개)

오일러의 정리 (Euler’s Theorem)

• a와 n이 서로소일 때: a^φ(n) ≡ 1 (mod n)
• 페르마의 소정리의 일반화이다.
• RSA의 수학적 기반이 되는 핵심 정리이다.

중국인의 나머지 정리 (CRT)

• RSA 복호화 최적화에 사용된다.
• p와 q를 알고 있을 때 계산 속도를 약 4배 향상시킬 수 있다.

m_p = c^d mod p
m_q = c^d mod q

CRT를 사용하여 m을 복원:
m = CRT(m_p, m_q, p, q)

구체적인 예시

작은 수를 사용한 예시:

1. 키 생성
   p = 61, q = 53
   n = 61 × 53 = 3233
   φ(n) = 60 × 52 = 3120
   e = 17 (3120과 서로소)
   d = 2753 (17 × 2753 = 46801 = 15 × 3120 + 1)

   공개 키: (17, 3233)
   개인 키: (2753, 3233)

2. 암호화
   평문: m = 123
   c = 123^17 mod 3233 = 855

3. 복호화
   암호문: c = 855
   m = 855^2753 mod 3233 = 123

실제 사용 예시 (RSA-2048):

p, q: 각각 1024비트 소수
n: 2048비트 (약 617자리 십진수)
e: 65537
d: 2048비트 개인 지수

디지털 서명

RSA는 암호화뿐만 아니라 디지털 서명에도 사용된다.

서명 생성

• 개인 키로 서명을 생성한다.

s = hash(m)^d mod n

• 실제로는 메시지의 해시값에 서명한다.
• 패딩 스킴(PSS 등)을 적용한다.

서명 검증

• 공개 키로 서명을 검증한다.

hash(m) = s^e mod n

• 계산된 해시값과 메시지의 실제 해시값을 비교한다.

패딩 스킴

순수 RSA는 여러 보안 취약점이 있어 실제로는 패딩 스킴과 함께 사용한다.

PKCS#1 v1.5

• 가장 오래되고 널리 사용되는 패딩 방식이다.
• 암호화와 서명 모두에 사용된다.
• Bleichenbacher 공격 등의 취약점이 알려져 있다.

0x00 || 0x02 || 랜덤 바이트들 || 0x00 || 평문

OAEP (Optimal Asymmetric Encryption Padding)

• 현대적이고 안전한 암호화 패딩 방식이다.
• 해시 함수와 마스크 생성 함수를 사용한다.
• 선택 평문 공격에 안전하다.

PSS (Probabilistic Signature Scheme)

• 서명을 위한 안전한 패딩 방식이다.
• 확률적 요소를 포함하여 동일한 메시지라도 매번 다른 서명이 생성된다.
• RSA-PSS가 권장되는 서명 방식이다.

키 크기와 보안 강도

키 크기	대칭 키 강도	상태	권장 사용
1024비트	~80비트	취약	사용 금지
2048비트	~112비트	안전	현재 표준
3072비트	~128비트	안전	장기 보안
4096비트	~152비트	안전	최대 보안

• NIST는 2030년까지 최소 2048비트 사용을 권장한다.
• 키 크기가 커질수록 연산 시간이 기하급수적으로 증가한다.
• 현재 RSA-2048이 가장 널리 사용되는 표준이다.
• 양자 내성
  • Shor의 알고리즘을 사용하면 양자 컴퓨터로 효율적인 소인수분해가 가능하다.
  • 충분한 큐비트를 가진 양자 컴퓨터가 등장하면 RSA는 안전하지 않다.
  • NIST는 양자 내성 암호 알고리즘 표준화를 진행 중이다.
  • 장기 보안이 필요한 경우 양자 내성 알고리즘으로의 전환을 고려해야 한다.

성능

연산 속도

• 암호화: e가 작으면 빠르다 (65537 사용 시)
• 복호화: 암호화보다 훨씬 느리다 (d가 크기 때문)
• 서명 생성: 복호화와 동일하게 느리다
• 서명 검증: 암호화와 동일하게 빠르다

CRT 최적화

• 개인 키에 p, q를 포함시켜 중국인의 나머지 정리를 사용한다.
• 복호화 속도를 약 4배 향상시킨다.
• 대부분의 실제 구현에서 사용된다.

---

참고

• ”리얼월드 암호학” - 데이비드 웡
• ”Cryptography Engineering” - Niels Ferguson, Bruce Schneier, Tadayoshi Kohno
• https://en.wikipedia.org/wiki/RSA_(cryptosystem)
• https://www.rfc-editor.org/rfc/rfc8017.html (PKCS #1: RSA Cryptography Specifications)
• https://csrc.nist.gov/publications/detail/sp/800-56b/rev-2/final (NIST Recommendation for Pair-Wise Key-Establishment)
• https://cr.yp.to/factorization/rsa2048.html (RSA-2048 소인수분해 현황)