Skip to content
Beside the Wheel

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배 향상시킨다.
  • 대부분의 실제 구현에서 사용된다.

BOJ 3734 RSA 인수 분해

https://www.acmicpc.net/problem/3734 http://acm.ro/2009/index.html

  • 문제: 양의 정수 n과 k가 주어졌을 때, n = p × q이고, p ≤ q, |q-kp| ≤ 10⁵를 만족하는 소수 p와 q를 찾는다.
  • 입력: 첫째 줄에 n과 k가 주어진다. (1 < n < 10¹²⁰, 1 < k < 10⁸)
  • 출력: “p* q” 형태로 출력한다.

이 문제는 RSA의 보안 취약점을 보여주는 특수한 경우의 소인수분해 문제이다. 일반적인 RSA는 p와 q가 비슷한 크기의 소수이지만 충분히 떨어져 있을 때 안전하다. 하지만 두 소수가 특정 관계식을 만족하면 효율적으로 분해할 수 있다.

조건 |q - kp| ≤ 10⁵에서:

  • q ≈ kp (약 10⁵ 오차 범위 내)
  • n = p × q ≈ kp²
  • 따라서 p ≈ √(n/k)

이를 이용하면 √(n/k) 근처에서만 탐색하면 되므로 10¹²⁰ 크기의 수도 빠르게 소인수분해할 수 있다.

Fermat의 소인수분해나 Pollard의 rho 알고리즘 등도 특수한 경우에 효율적이므로, RSA 키 생성 시 안전한 난수 생성기와 검증 과정이 필수적이다.

import math


def is_prime(n):
    """Miller-Rabin 소수 판별 알고리즘"""
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False


    # n-1 = 2^r × d로 표현
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2


    def witness_test(a):
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            return True
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                return True
        return False


    # 여러 witness로 테스트 (큰 수에도 충분히 정확)
    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n == a:
            return True
        if n > a and not witness_test(a):
            return False
    return True


def solve(n, k):
    # p의 시작점: √(n/k)
    start = math.isqrt(n // k)


    # ±2×10⁵ 범위 탐색
    search_range = 2 * 10**5
    for delta in range(search_range):
        for p in [start + delta, start - delta]:
            if p <= 1:
                continue


            # p가 n의 약수가 아니면 스킵
            if n % p != 0:
                continue


            q = n // p


            # p ≤ q 조건 확인
            if p > q:
                continue


            # |q - kp| ≤ 10⁵ 확인 (조기 필터링)
            if abs(q - k * p) > 10**5:
                continue


            # 둘 다 소수인지 확인
            if not is_prime(p):
                continue
            if not is_prime(q):
                continue


            return p, q


    return None, None


n, k = map(int, input().split())
p, q = solve(n, k)
print(f"{p}* {q}")

참고

관련글
암호화AES&IV암호화Cipher암호화Diffie–Hellman 키교환암호화대칭암호화암호화비대칭암호화암호화서명과 영지식 증명