RSA 원리와 계산 | 정보보안기사 필기

1. 나머지 연산과 모듈러 역원

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와 법이 서로소여야 한다.

2. 두 소수를 사용하는 키 생성

단계	계산	의미
1	서로 다른 소수 p, q 선택	비밀로 보호할 소수
2	n = pq	공개 모듈러스
3	φ(n) = (p−1)(q−1)	서로 다른 두 소수의 곱에 대한 식
4	1 < e < φ(n), gcd(e, φ(n)) = 1	공개 지수 선택
5	ed ≡ 1 (mod φ(n))	개인 지수 계산

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

3. 학습용 키 만들기

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

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)

4. 암호화와 복호화 계산

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

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

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

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

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

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을 이용한다.

거듭제곱	mod 221 결과
9^1	9
9^2	81
9^4	152
9^8	120
9^16	35
9^32	120
9^64	35

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

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

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

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

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

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

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