RSA 원리와 계산

핵심 요약

소수·모듈러 역원을 이용해 작은 RSA 키를 만들고 암호화·복호화를 계산합니다.

본문

나머지 연산과 모듈러 역원

a mod n은 a를 n으로 나눈 나머지다. ed ≡ 1 (mod m)은 곱 ed가 m으로 나누어 나머지 1을 남긴다는 뜻이다. d는 실수 1/e가 아니라 모듈러 곱셈 역원이다.

예를 들어 5 × 77 = 385 = 2 × 192 + 1이므로 77은 192를 법으로 한 5의 역원이다. 역원이 존재하려면 e와 법이 서로소여야 한다.

두 소수를 사용하는 키 생성

학습용 표현에서 공개키는 (n,e), 개인키는 (n,d)다. 실제 개인키 형식에는 효율적인 연산을 위한 p·q 등의 값도 포함될 수 있다. 공개키가 (p,q)인 것은 아니다.

학습용 키 만들기

p = 13, q = 17
n = 13 × 17 = 221
φ(n) = 12 × 16 = 192
e = 5  (192와 서로소)
d = 77 (5 × 77 mod 192 = 1)
공개키 = (221, 5)
개인키 = (221, 77)

암호화와 복호화 계산

평문을 0 ≤ m < n인 정수로 표현하는 RSA 원시 연산은 다음과 같다.

암호화: c = m^e mod n
복호화: m = c^d mod n

위 키에서 m=42를 암호화한다. 큰 거듭제곱을 한 번에 계산하지 않고 제곱할 때마다 나머지를 구한다.

42^2 mod 221 = 217
42^4 mod 221 = 217^2 mod 221 = 16
42^5 mod 221 = 16 × 42 mod 221 = 9

복호화 지수 77 = 64 + 8 + 4 + 1을 이용한다.

9^77 mod 221
= (35 × 120 × 152 × 9) mod 221
= 42

암호문 9에서 원래 값 42가 복원된다. 이 작은 수는 원리 확인용이며 실제 데이터 보호에 사용할 수 없다.

안전성·패딩·서명과의 구분

n을 인수분해해 p·q를 알면 φ(n)과 d를 계산할 수 있다. 그래서 RSA는 소인수분해 기반 공개키 방식으로 분류한다. 하지만 모든 RSA 공격이 반드시 소인수분해부터 해야 한다는 뜻은 아니다. 부적절한 키 생성, 패딩·오류 응답, 키 유출로도 보호가 깨질 수 있다.

원문 정수에 위 식만 적용하는 textbook RSA는 동일 입력에 동일 결과가 나오는 등 안전한 암호화 스킴의 요건을 갖추지 못한다. 실제 RSA 암호화에는 OAEP 같은 검증된 인코딩·패딩 방식이 필요하다. 단순히 빈 공간에 0을 채우는 것이 아니다.

RSA 서명은 별도의 서명 스킴이다. OAEP는 암호화, PSS는 서명에 쓰이는 이름으로 구별하고 상세 인코딩 내부는 필기 핵심 밖으로 확장하지 않는다.