RSA 암호화 (RSA Encryption) 원리와 예시

RSA는 현재 가장 널리 사용되는 공개키 암호화(비대칭키) 알고리즘입니다. 암호화와 복호화에 서로 다른 키(공개키와 개인키)를 사용하며, 소인수 분해의 어려움(큰 숫자를 소인수 분해하는 데 걸리는 시간)을 기반으로 보안을 유지합니다.

1. 키 생성 단계 (Key Generation)

RSA의 보안은 매우 큰 두 개의 소수 $p$와 $q$를 찾아내는 데서 시작합니다.

두 소수 $p$와 $q$ 선택 (Prime Numbers) $$p = 5$$ $$q = 11$$
모듈러스 $n$ 계산 (Modulus) $$n = p \times q = 5 \times 11 = 55$$ (n은 공개키와 개인키 모두에 사용되며 공개됩니다.)
오일러 피 함수 $\phi(n)$ 계산 $$\phi(n) = (p-1) \times (q-1) = (5-1) \times (11-1) = 4 \times 10 = 40$$ ($\phi(n)$은 키를 만드는 데만 사용되며 비밀로 유지됩니다.)
공개 지수 $e$ 선택 (Public Exponent) $\phi(n)$과 서로소인 정수 $e$를 선택합니다. (일반적으로 $e=65537$을 사용하지만, 예시에서는 작은 수 사용) $$e = 3$$ (공개키: $(e, n) = (3, 55)$)
개인 지수 $d$ 계산 (Private Exponent) $d$는 $e \times d \equiv 1 \pmod{\phi(n)}$을 만족하는 수입니다. $$3 \times d \equiv 1 \pmod{40}$$ $$d = 27$$ ($3 \times 27 = 81$ 이고, $81$을 $40$으로 나누면 나머지가 $1$이기 때문입니다.) (개인키: $(d, n) = (27, 55)$)

결과: 공개키 $(3, 55)$는 모두에게 공개되고, 개인키 $(27, 55)$는 소유자만 비밀리에 보관합니다.

암호문 $C$ 계산 공식: $$C \equiv M^e \pmod{n}$$ $$C \equiv 12^3 \pmod{55}$$ $$12^3 = 1728$$ $$1728 \div 55 = 31 \text{ 나머지 } 23$$ $$\mathbf{C = 23}$$

평문 $M$ 복원 공식: $$M \equiv C^d \pmod{n}$$ $$M \equiv 23^{27} \pmod{55}$$ (실제 계산은 복잡하지만, 결과는 다음과 같습니다.) $$\mathbf{M = 12}$$