정수론 RSA 쉽게 이해하기: 유클리드 호제법과 합동식 기준

핵심 정의와 기호

정수 a,b에 대해 a|b는 ‘a가 b를 나눈다’로 읽으며 b=ak인 정수 k가 있다는 뜻입니다. gcd(a,b)는 두 수의 최대공약수입니다. 양의 정수 a와 b>0에서 gcd(a,b)=gcd(b,a mod b)를 반복하고 두 번째 값이 0이 되면 첫 번째 값이 답입니다.

소수는 1보다 크며 양의 약수가 1과 자기 자신뿐인 정수입니다. 1은 소수가 아닙니다. 양의 정수 n에 대해 a mod n은 0≤r<n인 나머지 r입니다. a≡b (mod n)은 ‘a와 b는 n을 법으로 합동’이며 n이 a−b를 나눈다는 뜻입니다.

가장 작은 예제

48=18×2+12,18=12×1+6,12=6×2+0이므로 gcd(48,18)=6입니다. 나머지로 바꿔도 공약수 집합이 유지되기 때문에 마지막 0이 아닌 나머지를 사용합니다.

17≡5 (mod12)는 두 수의 차이12가12의 배수이므로 참입니다. 수 자체가 같다는 뜻은 아닙니다.

헷갈리는 반례

나머지 식에서 약분을 항상 할 수는 없습니다. 2×1≡2×3 (mod4)는 참이지만 1≡3 (mod4)는 거짓입니다. 나누려는 수의 모듈러 역원이 존재하는지 확인해야 합니다. 역원은 그 수와 법 n이 서로소일 때 존재합니다.

JavaScript의 %는 remainder 연산이어서 −1%12는 −1입니다. 수학의 비음수 나머지 −1 mod12=11과 구분합니다.

손으로 풀어보기

252=105×2+42,105=42×2+21,42=21×2+0이므로 gcd(252,105)=21입니다. 29−5=24는12의 배수라 29≡5 (mod12)입니다.

교육용 RSA 손계산은 다음과 같습니다. 작은 수는 원리 설명용이며 실제 보안에 사용할 수 없습니다.

1. 서로 다른 소수 p=3,q=11을 정하면 n=pq=33, φ(n)=(p−1)(q−1)=20입니다. φ는 n과 서로소인1부터 n까지 정수의 개수입니다.
2. e=3은20과 서로소입니다. d=7이면 ed=21≡1 (mod20)이므로 지수의 역원 조건을 만족합니다.
3. 메시지 m=4에 대해 c=mᵉ mod n=4³ mod33=64 mod33=31입니다.
4. cᵈ mod n=31⁷ mod33입니다. 31≡−2이므로 (−2)⁷=−128≡4 (mod33)으로 원래 값이 돌아옵니다.

이 계산은 한 메시지의 예시이며 RSA 정당성 전체 증명이나 키 생성 절차가 아닙니다. 실제 사용에는 검증된 암호 라이브러리와 안전한 프로토콜·패딩이 필요하고 직접 만든 교육 코드를 사용하지 않습니다. RSA 연산과 암호 방식의 구분은 RFC 8017의 정의를 참고합니다.

선택: JavaScript로 검산하기

코드 직접 실행

본문 예제를 선택하고 실제 계산 결과를 확인합니다.

예제 크게 보기 (새 탭)

손풀이 뒤 선택해서 실행하는 짧은 전체 코드입니다. 브라우저 Console 또는 Node.js가 준비된 환경의 check.mjs에서 실행할 수 있으며 수학 학습에 설치는 필수가 아닙니다.

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return Math.abs(a);
}
console.log(gcd(252, 105));
console.log(29 % 12, 5 % 12);

기대 결과: 21, 이어서 5 5가 출력됩니다.

gcd 코드의 입력은 예시의 작은 정수입니다. 임의 실수·NaN·큰 정수 검증이나 RSA 암호 구현을 제공하지 않습니다.

자주 발생하는 오해와 교정

1을 소수에 포함하지 않습니다. 합동에서 임의로 양변을 약분하지 않고 역원 조건을 확인합니다. 작은 소수의 RSA 손계산은 실사용 암호가 아니며 %의 음수 결과를 수학적 비음수 mod와 구분합니다.

직접 풀어볼 문제와 해설

쉬운 개념

최대공약수는 큰 수를 작은 수로 나눈 나머지로 두 수를 바꾸어 반복합니다. a≡b (mod n)은 a−b가 n의 배수라는 뜻입니다.

단계별 예제

1. 84=30×2+24를 씁니다.
2. 30=24×1+6, 24=6×4+0이므로 gcd(84,30)=6입니다.
3. 35−11=24=12×2이므로 35≡11 (mod 12)입니다.

직접 풀 문제

gcd(84,30)과 35 mod 12를 구한 뒤, 3의 mod 11 곱셈 역원이 4인지 확인하세요.

정답·해설 보기

1. 유클리드 과정의 마지막 0이 아닌 나머지는 6이므로 gcd=6입니다.
2. 35=12×2+11이므로 나머지는 11입니다.
3. 3×4=12≡1 (mod 11)이므로 4는 3의 곱셈 역원입니다. 작은 숫자의 손계산은 실서비스 RSA 구현이 아닙니다.

다음 학습

13회차에서 집합·함수·관계·그래프를 상태 전이 모델로 묶습니다. 다음 글 읽기

학습 완료 체크리스트

• 정의의 적용 범위와 기호를 말로 설명할 수 있습니다.
• 위 손풀이를 답을 가린 상태에서 다시 계산합니다.
• 반례가 어떤 조건을 어기는지 설명합니다.

알고리즘 수학 노트

누적 이전 체크포인트: discrete-step-11-graph-problems. 아래는 이번 회차의 완성 예시입니다. 자신의 다른 예제 하나를 덧붙여도 좋습니다.

mod12에서 같은 나머지를 갖는 정수는 같은 동치류로 묶입니다. 관계 회차와 연결해 29와5의 차이24를 적습니다. Euclid의 나머지 표, 약분 반례, toy RSA의 n=33·e=3·d=7·4→31→4를 기록합니다. 보안 구현과 손계산의 경계도 함께 남깁니다.

완료 체크포인트

discrete-step-12-number-theory

다음 학습

오토마타 이론 쉽게 이해하기: DFA NFA와 형식 문법 기준에서 다음 개념을 이어갑니다.