왜 이 수학이 필요한가

쉽게 말하면: 나눗셈의 나머지를 다루는 법은 알아도, “그 나머지를 만드는 두 소수를 다시 찾을 수 있는가”와 “나눗셈을 거꾸로 되돌리는 법”은 또 다른 문제다.

모듈러 연산(나머지 연산)과 모듈러 지수(거듭제곱 후 나머지 구하기)의 기본 계산법을 이미 익혔다는 전제 위에서, 이 편은 그 위에 4과목(정보보안일반)의 암호 알고리즘 편(23~25편)이 그대로 가져다 쓸 세 가지 계산 도구를 채운다.

• 소인수분해: RSA(23편)의 안전성이 왜 “큰 수를 다시 소인수로 쪼개기 어렵다”는 사실에 의존하는지 이해하려면, 소수와 소인수분해부터 정확히 알아야 한다.
• 오일러 파이 함수: RSA 키 생성식 한가운데 등장하는 값이며, 이 값을 스스로 계산할 수 있어야 키 생성 과정을 암기가 아니라 이해로 따라갈 수 있다.
• 확장 유클리드 호제법: “곱해서 나머지가 1이 되는 짝꿍 수”(모듈러 역원)를 직접 찾는 절차다. 이 절차가 없으면 RSA의 개인키 지수를 구하는 과정이 “어디선가 주어진 값을 검산만 하는” 블랙박스로 남는다.

여기에 더해 이산로그 문제를 원시근(생성자) 판정이라는 실전 계산 문제로 한 번 더 확인해, 06편(디피-헬만·공개키 알고리즘)에서 등장할 개념의 계산 기초까지 마련한다.

모듈러 연산 복습과 잉여류

쉽게 말하면: 어떤 수를 n으로 나눈 나머지가 같은 수끼리는 “같은 무리”로 묶을 수 있다.

$a \bmod n$은 $a$를 $n$으로 나눈 나머지를 뜻하고, 나머지가 같은 두 수 $a$, $b$는 $a \equiv b \pmod{n}$(합동)이라 쓴다는 것은 이미 익힌 내용이다. 이 관계로 정수 전체를 $n$개의 무리로 나눌 수 있는데, 이를 잉여류(residue class)라 한다. 예를 들어 법(modulus) 6에 대해서는 나머지가 0, 1, 2, 3, 4, 5인 여섯 개의 잉여류가 존재하고, 각 잉여류에서 대표값 하나씩 뽑은 $\{0,1,2,3,4,5\}$를 완전잉여계(complete residue system)라 부른다.

이 중에서 법 $n$과 서로소(공약수가 1뿐인 관계)인 수들만 모은 것을 기약잉여계(reduced residue system)라 한다. 법이 6일 때 $\{0,1,2,3,4,5\}$ 중 6과 서로소인 수는 1과 5뿐이므로, 6의 기약잉여계는 $\{1,5\}$이고 원소 개수는 2개다. 이 “서로소인 수의 개수”가 바로 다음 절의 오일러 파이 함수다 — 기약잉여계의 크기를 함수로 정의한 것이 오일러 파이 함수이므로, 두 개념은 사실상 같은 것을 가리킨다.

소수와 소인수분해

소수 판정: 왜 √n까지만 확인하면 되는가

쉽게 말하면: 약수는 항상 짝을 지어 나타나므로, 절반을 넘는 수까지 나눠 볼 필요가 없다.

소수(prime number)는 1과 자기 자신 외에는 약수가 없는 2 이상의 정수다. 어떤 수 $n$이 소수인지 확인하려면 2부터 $n-1$까지 나눠 볼 필요 없이, $\sqrt{n}$까지만 나눠 보면 충분하다. 그 이유는 $n = a \times b$로 나뉜다면 $a$와 $b$ 중 적어도 하나는 $\sqrt{n}$ 이하이기 때문이다(둘 다 $\sqrt{n}$보다 크면 곱이 $n$보다 커진다).

에라토스테네스의 체(Sieve of Eratosthenes)는 이 원리를 이용해 일정 범위의 소수를 한꺼번에 걸러내는 방법이다. 2부터 30까지 범위에서, 2의 배수(4, 6, 8 …)를 먼저 지우고, 남은 수 중 가장 작은 3의 배수(9, 15, 21, 27)를 지우고, 다음 5의 배수(25)를 지우는 식으로 반복하면 다음 소수만 남는다.

소인수분해: 산술의 기본 정리

소인수분해(prime factorization)는 어떤 합성수를 소수들의 곱으로 나타내는 것이며, 산술의 기본 정리(순서를 무시하면 이 소수 곱 표현이 단 하나뿐이라는 정리)에 따라 그 표현은 유일하다. 예를 들어 91을 소인수분해하면 다음과 같다.

리눅스에는 이 계산을 즉시 해 주는 factor 명령이 있다.

$ factor 91
91: 7 13

숫자가 작을 때는 이렇게 순식간에 끝나지만, 자릿수가 늘어날수록 이 계산은 기하급수적으로 오래 걸린다. RSA(23편)의 안전성은 정확히 이 사실에 의존한다 — 두 개의 큰 소수를 곱하는 것은 컴퓨터에게 순식간이지만, 그 곱을 다시 원래의 두 소수로 쪼개는 것은 현재까지 알려진 방법으로는 소수 자릿수가 늘어날수록 사실상 불가능해지기 때문이다.

소수 판정 실무: openssl prime

특정 수가 소수인지 확인하는 실무 명령으로 openssl prime이 있다. 실제 출력을 그대로 옮기면 다음과 같다.

$ openssl prime 17
11 (17) is prime

$ openssl prime 91
5B (91) is not prime

출력의 첫 번째 토큰(11, 5B)은 입력한 수를 16진수로 표시한 것이고, 괄호 안 숫자가 우리가 입력한 10진수 값이다(17을 16진수로 쓰면 11이고, 91을 16진수로 쓰면 5B다). 실제 RSA 키 생성 프로그램은 이런 소수 판정을 수백 자리 숫자에 반복 적용해, 소수로 판정된 두 값을 곱해 키의 법(modulus)을 만든다.

오일러 파이 함수: 서로소인 수를 세는 함수

쉽게 말하면: 1부터 n까지 숫자 중 n과 약수를 공유하지 않는 수가 몇 개인지 세는 함수다.

오일러 파이 함수(Euler’s totient function) $\varphi(n)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 수의 개수를 뜻한다. 직접 하나씩 세지 않고 빠르게 계산하는 공식이 세 가지 있다.

이 세 규칙을 조합하면, 소인수분해만 알면 어떤 수의 $\varphi(n)$이든 계산할 수 있다. $n = 12 = 2^2 \times 3$을 예로 들어 보자.

• $\varphi(2^2) = 4-2 = 2$: $2^2=4$의 배수를 제외하는 공식에 따른 값.
• $\varphi(3) = 3-1 = 2$: 소수 3에 대한 공식.
• $2$와 $3$은 서로소이므로 두 값을 곱한다.

직접 세어 확인하면, $1$부터 $12$까지 중 $12$와 서로소인 수는 $1, 5, 7, 11$로 정확히 4개다.

같은 방식으로 $n = 55 = 5 \times 11$(두 소수의 곱, RSA 키 생성식과 같은 형태)을 계산하면 다음과 같다.

두 서로 다른 소수 $p$, $q$의 곱 $n=pq$에 대해서는 항상 $\varphi(n)=(p-1)(q-1)$로 간단히 정리된다는 점이 23편의 RSA 키 생성 계산에서 그대로 다시 쓰인다.

오일러의 정리와 페르마의 소정리

쉽게 말하면: 어떤 수를 φ(n)번 거듭제곱해서 n으로 나누면 항상 나머지가 1로 돌아온다.

오일러의 정리(Euler’s theorem)는 $a$와 $n$이 서로소일 때 다음이 항상 성립한다는 정리다.

$n$이 소수 $p$인 특수한 경우에는 $\varphi(p)=p-1$이므로, 이 정리는 다음과 같이 더 단순한 형태가 되며 이를 페르마의 소정리(Fermat’s little theorem)라 부른다.

이 정리를 실제 숫자로 확인해 보자. $p=11$, $a=2$라 하면 $\varphi(11)=10$이므로 $2^{10} \bmod 11$이 1이 되어야 한다.

$1024 = 93\times11+1$이므로 나머지는 정확히 1이다. 이 “지수를 φ(n)만큼 채우면 1로 되돌아온다”는 성질이 바로 23편에서 다룰 RSA 복호화가 원래 평문을 정확히 복원하는 근거이므로, 여기서 정리의 형태와 계산 방식을 확실히 기억해 둔다.

확장 유클리드 호제법: 모듈러 역원을 직접 구하기

유클리드 호제법으로 최대공약수 구하기

쉽게 말하면: 큰 수를 작은 수로 나눈 나머지로 계속 바꿔 가면, 결국 두 수의 최대공약수가 남는다.

유클리드 호제법(Euclidean algorithm)은 두 수 $a$, $b$의 최대공약수(GCD, Greatest Common Divisor)를 나눗셈의 나머지를 반복해 구하는 절차다. $240$과 $46$의 최대공약수를 구해 보자.

확장 유클리드 호제법으로 모듈러 역원 구하기

쉽게 말하면: 나눗셈 과정을 거꾸로 되짚어 올라가면, 두 수를 정수배해서 더한 것만으로 최대공약수를 만드는 식을 얻을 수 있다.

앞의 절차를 거꾸로 되짚어 올라가면(후진 대입, back-substitution) $ax+by=\gcd(a,b)$를 만족하는 정수 $x$, $y$를 찾을 수 있다. 이를 확장 유클리드 호제법(Extended Euclidean Algorithm)이라 하며, 최대공약수가 1일 때 이 식이 바로 모듈러 역원을 준다. $e=7$의 법 $40$에 대한 모듈러 역원(즉 $7d \equiv 1 \pmod{40}$을 만족하는 $d$)을 이 방법으로 직접 구해 보자. 이 값은 앞서 계산한 $\varphi(55)=40$을 법으로 쓰는 것으로, 두 소수 $p=5$, $q=11$의 곱 $n=55$에서 공개 지수 $e=7$을 골랐을 때 개인 지수 $d$를 구하는 것과 정확히 같은 계산이다.

이 식은 $7 \times (-17) \equiv 1 \pmod{40}$이라는 뜻이다. 음수 지수는 법을 더해 양수 범위로 옮긴다.

검산하면 $7\times23=161=4\times40+1$이므로 나머지가 정확히 1이고, $d=23$이 맞는 역원임이 확인된다. 최신 파이썬(3.8 이상)은 pow(밑, -1, 법) 구문으로 이 계산을 한 줄로 검증할 수 있다.

>>> pow(7, -1, 40)
23

이 예시의 $e=7$, $d=23$, $n=55$는 23편에서 실제 RSA 암복호화 계산을 할 때 그대로 이어받아 쓰는 값이다.

실무에서 이 값들이 그대로 나타나는 곳: OpenSSL 키 파일

쉽게 말하면: 지금까지 손으로 구한 n, e, d, p, q가 실제 개인키 파일 안에 이름이 붙은 채로 그대로 들어 있다.

실제 RSA 개인키를 생성하고 그 구성 요소를 출력하면, 지금까지 계산한 값들이 어떤 이름으로 저장되는지 확인할 수 있다.

$ openssl genrsa -out test_key.pem 512
$ openssl rsa -in test_key.pem -text -noout
Private-Key: (512 bit, 2 primes)
modulus:
    00:a9:b7:a7:30:22:e8:af:3c:81:64:06:66:37:d9:
    ...
publicExponent: 65537 (0x10001)
privateExponent:
    4b:7c:48:db:4b:1b:8d:1d:6f:3b:6a:f1:39:f3:d1:
    ...
prime1:
    00:d9:8e:ee:5c:6d:6b:53:34:c2:6f:14:47:8f:f3:
    ...
prime2:
    00:c7:b4:ad:72:42:0d:f6:42:6d:d1:57:c4:7d:5f:
    ...
exponent1:
    00:91:ae:89:64:b1:0c:96:3a:15:1c:e6:ba:88:e5:
    ...
exponent2:
    6e:90:bd:a6:90:a3:a2:3f:cd:05:26:0e:87:4b:2b:
    ...
coefficient:
    3c:72:c3:68:03:84:3d:a2:2f:31:37:c2:89:41:82:
    ...

각 항목이 이 편에서 계산한 값과 어떻게 짝지어지는지 정리하면 다음과 같다.

publicExponent가 65537(16진수로 0x10001, 즉 $2^{16}+1$)로 거의 고정되어 있는 이유는, 이 값이 이진수로 표현했을 때 1의 개수가 적어(비트 2개) 모듈러 지수 계산의 곱셈 횟수를 줄여 암호화 속도를 높이면서도, 지나치게 작은 값(예: 3)이 가진 알려진 공격 가능성을 피할 수 있는 절충값이기 때문이다.

이산로그 문제와 원시근 판정

쉽게 말하면: 거듭제곱은 계산하기 쉽지만 거꾸로 몇 제곱인지 알아내기는 어렵다. 이 어려움을 최대로 활용하려면 “생성자” 역할을 하는 특별한 밑을 골라야 한다.

$g^a \bmod p = y$가 주어졌을 때 $a$를 구하는 문제(이산로그 문제)는 $p$가 커지면 사실상 풀 수 없을 정도로 어려워진다는 것, 그리고 이 계산 비대칭성이 공개키 암호의 안전성 근거가 된다는 것은 이미 확인한 내용이다. 여기서 한 걸음 더 들어가, 이 방식이 실제로 안전하려면 밑 $g$가 원시근(primitive root, 생성자)이어야 한다는 조건을 계산으로 확인해 본다.

원시근은 $g^1, g^2, \dots, g^{p-1} \bmod p$를 나열했을 때 $1$부터 $p-1$까지의 값이 정확히 한 번씩 골고루 나오게 만드는 밑이다. 이 조건은 $g$의 위수(order, $g^k \equiv 1 \pmod p$가 되는 가장 작은 양의 정수 $k$)가 $p-1$과 같다는 것과 같은 말이다.

원시근인지 매번 $p-1$번 전부 계산해 확인할 필요는 없다. 다음 판정법을 쓰면 훨씬 적은 계산으로 확인할 수 있다.

$p=11$일 때 $p-1=10=2\times5$이므로 소인수는 $2$와 $5$다. $g=2$가 원시근인지 확인해 보자.

두 값 모두 $1$이 아니므로, $g=2$는 법 $11$에 대한 원시근이다. 이번에는 $g=3$을 같은 방법으로 확인해 보자.

$3^5 \bmod 11$이 이미 $1$이 나왔으므로, $g=3$은 원시근이 아니다. 실제로 $3$의 위수를 끝까지 확인하면 $5$에서 이미 $1$로 돌아오므로($3^5 \equiv 1$), $3$은 $1\sim10$ 전체가 아니라 절반인 다섯 개 값만 순환하며 만들어 낸다. 원시근이 아닌 밑을 공개키 프로토콜의 생성자로 쓰면 만들어 낼 수 있는 값의 범위가 좁아져, 공격자가 시도해야 할 경우의 수가 줄어드는 약점이 된다.

이후 편에서 재사용할 계산 규칙 요약

자주 틀리는 점

• 소수 판정 시 √n을 넘어서까지 나눠 봄: $\sqrt{n}$까지만 확인하면 충분하며, 그 이상은 이미 앞에서 확인한 약수의 짝일 뿐이다.
• 오일러 파이 함수를 “n보다 작은 수의 개수”로 오해: 단순히 개수가 아니라 “n과 서로소인 수의 개수”라는 조건을 반드시 포함해야 한다.
• 확장 유클리드 호제법의 후진 대입 순서를 거꾸로 함: 나머지가 1이 나온 마지막 식부터 시작해, 그 이전 나눗셈 식을 하나씩 위로 거슬러 올라가며 대입해야 한다.
• 모듈러 역원이 음수로 나온 뒤 법을 더하는 것을 잊음: 확장 유클리드 결과가 음수(예: $-17$)로 나오면 법을 더해 양수 범위($0\sim n-1$)로 반드시 옮겨야 한다.
• 아무 숫자나 원시근으로 사용해도 된다고 오해: $g^{(p-1)/q}\equiv1$이 하나라도 성립하면 그 밑은 원시근이 아니며, 만들어 낼 수 있는 값의 범위가 좁아져 안전성이 떨어진다.

핵심 정리

• 소수 판정은 $\sqrt{n}$까지만 확인하면 충분하고, 소인수분해는 유일하게 정해지지만(산술의 기본 정리) 큰 수일수록 계산이 급격히 어려워져 RSA 안전성의 근거가 된다.
• 오일러 파이 함수 $\varphi(n)$은 $n$과 서로소인 수의 개수이며, 서로 다른 두 소수의 곱 $n=pq$에서는 $\varphi(n)=(p-1)(q-1)$로 간단히 계산된다.
• 오일러의 정리($a^{\varphi(n)}\equiv1\pmod n$)와 그 특수형인 페르마의 소정리는 RSA 복호화가 원래 평문을 복원하는 수학적 근거다.
• 확장 유클리드 호제법은 후진 대입으로 $ax+by=\gcd(a,b)$를 구해, 이를 통해 모듈러 역원(RSA의 개인 지수 등)을 직접 계산할 수 있게 해 준다.
• 원시근 판정은 $p-1$의 소인수마다 $g^{(p-1)/q}\not\equiv1$을 확인하는 방식으로 하며, 소인수분해·오일러 파이 함수가 그대로 재사용된다.
• 실제 openssl 키 파일의 modulus·publicExponent·privateExponent·prime1·prime2 필드는 이 편에서 계산한 $n$, $e$, $d$, $p$, $q$에 정확히 대응한다.

마무리 복습

참고 자료

• RFC 8017 - PKCS #1: RSA Cryptography Specifications Version 2.2 
• OpenSSL Documentation - openssl-genrsa 
• OpenSSL Documentation - openssl-prime