RSA 암호화 완전 정리

기본 수학 기호

• ^e: e제곱 (거듭제곱), 예: 2³ = 2×2×2 = 8
• mod n: n으로 나눈 나머지 연산
• ≡: 합동 기호, a ≡ b (mod n)은 "a와 b를 n으로 나눈 나머지가 같다"

모듈러 연산에서 n의 의미

mod n에서 n은 모듈러스(modulus)라고 하며, 나누는 수입니다.

예시:

• 17 mod 5에서 n = 5 (17을 5로 나눈 나머지 = 2)
• 25 mod 7에서 n = 7 (25를 7로 나눈 나머지 = 4)
• 시계에서는 mod 12 (n = 12)

RSA에서 n의 역할

RSA에서 n은 두 소수의 곱입니다.

• n = p × q (p, q는 큰 소수)
• 이 n이 암호화/복호화에서 모듈러스로 사용됩니다

핵심 개념

오일러 파이 함수 φ(n)

1부터 n까지 수 중에서 n과 서로소인 수의 개수

• φ(12) = 4 → {1, 5, 7, 11}
• φ(p) = p-1 (p가 소수)
• φ(p×q) = (p-1)(q-1) (p, q가 서로 다른 소수)

RSA 알고리즘

1. 키 생성

1. 서로 다른 큰 소수 p, q 선택
2. n = p × q ← 이것이 RSA의 모듈러스
3. φ(n) = (p-1)(q-1)
4. e 선택: 1 < e < φ(n)이고 gcd(e, φ(n)) = 1
5. d 계산: e × d ≡ 1 (mod φ(n))

공개키: (n, e)
개인키: (n, d)

2. 암호화/복호화

• 암호화: C = M^e mod n ← 여기서 n으로 나눈 나머지
• 복호화: M = C^d mod n ← 여기서도 같은 n으로 나눈 나머지

구체적 예시

키 생성

• p = 7, q = 11
• n = 77 ← 이것이 모듈러스
• φ(77) = 6 × 10 = 60
• e = 13, d = 37

암호화 (평문 M = 2)

C = 2¹³ mod 77 = 8192 mod 77 = 30
(8192를 77로 나눈 나머지가 30)

복호화

M = 30³⁷ mod 77 = 2
(같은 77로 나눈 나머지 연산으로 원문 복구)

보안 원리

n = p × q를 공개하지만, p와 q는 비밀로 유지합니다.

• n을 소인수분해하여 p, q를 찾는 것이 매우 어려움
• 실제로는 수백 자리 소수를 사용하여 현실적으로 불가능

요약: RSA에서 n은 두 소수의 곱이며, 모든 계산의 기준이 되는 모듈러스입니다.