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)$의 약수가 포함되지 않도록 주의해야 합니다.
- 전자서명과 혼동 주의 : 암호화는 상대방의 공개키로, 서명은 나의 개인키로 한다는 개념을 명확히 구분하세요.
추가적으로 위에서 개인키를 구하는건 대부분 계산이 좀 쉬운 숫자를 주는데 암호문은 구하기 어려운 경우가 있습니다. 그건 비교적 큰 숫자를 지수로 주어지기 때문입니다. 가령 7의 3제곱만 하더라고 7을 세번 곱해야 하므로 343이므로 벌써 계산하는데 시간이 오래 걸립니다.
즉 지수 계산이 복잡하게 느껴지는 이유는 숫자가 기하급수적으로 커지기 때문입니다. 시험장에서는 계산기를 쓸 수 없으니, "숫자를 키우지 않고 가두는 기술"이 핵심입니다. 가장 직관적인 '계단식 계산법'을 아주 잘게 쪼개서 생각해 봅시다. 이번에는 $3^7 \pmod{10}$이라는 아주 쉬운 숫자로 연습해봅시다. (원리는 RSA와 똑같습니다.)
1단계: 지수를 '2의 배수'로 쪼개기
지수 $7$을 직접 계산하는 대신, $1, 2, 4, 8...$ 같은 숫자의 합으로 만듭니다.
- $7 = 4 + 2 + 1$
즉,우리는 $3^4 \times 3^2 \times 3^1$을 구하면 됩니다.
2단계: 숫자가 커지기 전에 '싹둑' 자르기 (나머지 구하기)
이게 제일 중요합니다. 제곱을 한 번 할 때마다 바로 나머지를 구하세요.
- $3^1 = 3$ (나머지 3)
- $3^2 = 9$ (나머지 9)
$3^4$은 어떻게 구할까요? $3 \times 3 \times 3 \times 3$을 하는 게 아니라, 방금 구한 $3^2$의 결과(9)를 다시 제곱합니다.
- $9 \times 9 = 81$
- $81 \div 10$의 나머지는? 1
보세요! $81$을 계산하는 대신 바로 1로 숫자를 줄였습니다.
3단계: 쪼갠 조각들만 곱하기
이제 1단계에서 쪼갰던 지수들에 해당하는 결과값들만 가져와서 곱합니다.
- $3^7 = 3^4 \times 3^2 \times 3^1$
- 결과값 대입 : $1 \times 9 \times 3 = 27$
- 마지막으로 한 번 더 나누기 : $27 \div 10$의 나머지는 7
💡 시험장에서 유용한 '암산 꿀팁'
만약 계산 중에 법($n$)에 아주 가까운 숫자가 나오면 적극적으로 활용하세요. 예를 들어 $n=33$인데 계산 결과가 $32$가 나왔다면?$32$라고 쓰지 말고 $-1$이라고 생각하세요.
왜냐하면 $(-1)^2$은 그냥 $1$이 되어버려서 다음 계산이 엄청나게 쉬워지기 때문입니다.$32^2$을 계산하는 것보다 $(-1)^2$을 계산하는 게 훨씬 빠르겠죠? 정리하자면 이 루틴만 기억하세요!
"제곱한다 → 바로 나눈다 → 그 결과로 다시 제곱한다 → 바로 나눈다"
이 과정을 반복하면 아무리 큰 지수라도 결국 한 자리나 두 자리 수의 곱셈으로 끝납니다.