1. RSA 암호 체계의 주요 특징
- 비대칭키 암호화 : 공개키($e$)와 개인키($d$)가 한 쌍을 이룹니다. 공개키로 암호화하면 개인키로만 복호화할 수 있습니다.
- 소인수분해의 난해함 : 아주 큰 두 소수의 곱을 소인수분해하는 것이 어렵다는 수학적 원리에 기반합니다.
- 용도 : 데이터 암호화뿐만 아니라 전자서명에도 사용됩니다. (개인키로 서명하고 공개키로 검증)
- 속도 : 대칭키 암호(AES 등)에 비해 연산 속도가 느려 주로 대칭키를 교환하기 위한 키 분배용으로 활용됩니다.
2. RSA 키 생성 및 계산 프로세스
시험에서는 다음의 수치 계산 과정을 단계별로 물어보는 경우가 많습니다.
1단계: 변수 설정
- 두 개의 큰 소수 $p, q$를 선택합니다.
- $n = p \times q$를 계산합니다. ($n$은 공개키와 개인키의 일부가 됩니다.)
- 오일러 파이 함수 $\phi(n) = (p-1)(q-1)$을 계산합니다.
2단계: 키 생성
- 공개키($e$) : $1 < e < \phi(n)$이며, $\phi(n)$과 서로소인 정수를 선택합니다.
- 개인키($d$) : $e \times d \equiv 1 \pmod{\phi(n)}$을 만족하는 $d$를 구합니다. 즉, $(e \times d)$를 $\phi(n)$으로 나누었을 때 나머지가 1
3단계: 암호화 및 복호화
- 암호화 : $C = M^e \pmod n$
- 복호화 : $M = C^d \pmod n$
3. 시험에 자주 나오는 계산 문제 유형
시험장에서는 시간이 촉박하므로 모듈러(Modular) 연산의 성질을 익혀두는 것이 핵심입니다.
유형 1: 개인키($d$) 구하기
문제: $p=3, q=11, e=3$일 때, 개인키 $d$는?
- $n = 3 \times 11 = 33$
- $\phi(n) = (3-1) \times (11-1) = 2 \times 10 = 20$
- $3 \times d \equiv 1 \pmod{20}$ 만족하는 $d$ 찾기
- $3 \times 7 = 21 \equiv 1 \pmod{20}$ 이므로 $d = 7$
유형 2: 암호문($C$) 계산하기
문제: $n=33, e=3, M=7$일 때 암호문 $C$는?
- C = 7^3 \pmod{33}$
- $7^2 = 49 \equiv 16 \pmod{33}$
- $C = 16 \times 7 = 112$
- $112 = (33 \times 3) + 13 \rightarrow$ $C = 13$
유형 3: 관계식의 성질 파이하기
- $n$이 공개되면 소인수분해를 통해 $\phi(n)$을 알아낼 수 있고, 이를 통해 개인키 $d$를 유도할 수 있다는 점이 RSA의 보안 위협 요소임을 묻는 이론 문제.
- $e$와 $\phi(n)$은 반드시 서로소(Greatest Common Divisor = 1)여야 한다는 조건 확인.
💡 수험생을 위한 팁
- 지수 법칙 활용 : $M^{13} \pmod n$ 같은 큰 지수는 $M^8 \times M^4 \times M^1$ 형태로 쪼개서 계산하세요.
- 서로소 확인 : $e$를 선택할 때 $\phi(n)$의 약수가 포함되지 않도록 주의해야 합니다.
- 전자서명과 혼동 주의 : 암호화는 상대방의 공개키로, 서명은 나의 개인키로 한다는 개념을 명확히 구분하세요.