암호문은 계산하기 쉽지만 원문을 되찾는 규칙은 따로 가진다는 공개키 암호의 아이디어를 작은 수로 살펴봅시다. 이 글은 실제 통신에 쓰는 암호가 아니라 거듭제곱과 나머지를 손으로 확인하는 RSA의 축소 계산이에요. 메시지 m은 0부터 32까지의 정수라고 정해요.
3×11=33을 나누는 수로 사용해요. 두 소수의 값에서 (3−1)(11−1)=20을 구하고, 지수 e=3과 d=7을 골라요. 두 지수의 곱 21은 20으로 나누었을 때 나머지가 1입니다. 암호화는 m의 세제곱을 33으로 나눈 나머지를 기록하는 규칙이에요.
m=4를 넣으면 4³=64이고, 64를 33으로 나눈 나머지는 31이므로 암호문 c=31입니다. 복호화는 이 c의 일곱제곱을 같은 33으로 나눈 나머지를 구하는 규칙이에요.
마지막 나머지가 4인 까닭은 −128=−4×33+4이기 때문이에요. 이 메시지의 왕복 계산이 확인돼요. 큰 정수를 그대로 전개하지 않고 중간 단계에서 나머지로 바꾸어도 같은 결과를 얻어요. 작은 33의 인수는 누구나 쉽게 찾으므로 비밀 통신의 안전성을 보인 예는 아니에요. 서로 짝이 되는 두 계산을 확인하는 데 목적이 있어요.
참고한 수학 개념: Plus · Maths in a minute: Cryptography.
이 글의 생활 상황과 계산 예시는 수학 이야기에서 새로 구성했습니다.