왜 이 수학이 필요한가

쉽게 말하면: 암호는 결국 “나눗셈의 나머지”와 “매우 큰 수의 거듭제곱”으로 만들어진다.

05편부터 등장하는 대칭키·공개키 암호, 06편의 디피-헬만 키교환, 07편의 해시 함수는 모두 내부적으로 나머지 연산(모듈러 연산)과 거듭제곱(지수)을 사용한다. RSA 공개키 암호의 암호화·복호화 식도, 디피-헬만 키교환의 공유 비밀 계산도 형태는 다르지만 전부 “어떤 수를 거듭제곱한 뒤 특정 수로 나눈 나머지를 구한다”는 동일한 연산에 기반한다. 이 편에서 그 연산을 실제 작은 숫자로 완전히 계산해 두면, 뒤 편에서는 “이 계산은 03편에서 했던 것과 같은 구조다”라고 바로 알아볼 수 있다.

모듈러 연산(modular arithmetic)

정의와 기본 계산

쉽게 말하면: 나눗셈을 하고 몫은 버리고 나머지만 남기는 연산이다.

모듈러 연산(합동식, congruence)은 어떤 정수를 특정 양의 정수(법, modulus)로 나눈 나머지만을 취하는 연산이다. $a \bmod n$은 “$a$를 $n$으로 나눈 나머지”를 뜻하며, 시계가 12를 넘으면 다시 1로 돌아가는 것과 같은 원리다(시계는 12를 법으로 하는 모듈러 연산의 생활 속 예시다).

• $17 \bmod 5$: 17을 5로 나누면 몫이 3이고 나머지가 2이므로($5 \times 3 = 15$, $17 - 15 = 2$), 결과는 2다.

두 수가 같은 법에 대해 나머지가 같으면 “합동(congruent)“이라 하고 $a \equiv b \pmod n$으로 쓴다. 예를 들어 $17 \equiv 2 \pmod 5$다.

모듈러 덧셈과 곱셈

모듈러 연산은 덧셈·곱셈에 대해 다음 성질을 만족한다. 이 성질 덕분에 큰 수를 직접 계산하지 않고도 중간에 나머지를 취해가며 계산할 수 있다.

• 예시: $(14 + 9) \bmod 6$을 직접 계산하면 $23 \bmod 6 = 5$다. 성질을 이용하면 $(14 \bmod 6) + (9 \bmod 6) = 2 + 3 = 5$, 다시 $5 \bmod 6 = 5$로 같은 결과가 나온다.

• 예시: $(14 \times 9) \bmod 6$을 직접 계산하면 $126 \bmod 6 = 0$이다. 성질을 이용하면 $(2 \times 3) \bmod 6 = 6 \bmod 6 = 0$으로 같다.

이 곱셈 성질이 바로 다음 절의 모듈러 지수 연산을 큰 수 그대로 계산하지 않고도 빠르게 처리할 수 있게 해주는 근거다.

모듈러 지수(modular exponentiation): 빠른 거듭제곱

쉽게 말하면: 지수를 절반씩 쪼개면서 매번 나머지를 취하면, 아무리 큰 지수라도 몇 단계 안에 계산할 수 있다.

공개키 암호와 디피-헬만 키교환은 모두 $g^a \bmod p$ 형태의 계산(밑 $g$를 지수 $a$만큼 거듭제곱한 뒤 $p$로 나눈 나머지)을 반복한다. 지수가 매우 커도 제곱-곱 알고리즘(square-and-multiply)을 쓰면 곱셈 횟수를 크게 줄일 수 있다. $3^7 \bmod 11$을 예로 들어 단계별로 계산해 본다.

• $3$: 밑(base). 반복해서 곱해지는 수.
• $7$: 지수(exponent). 밑을 몇 번 곱할지 나타내는 수.
• $11$: 법(modulus). 나머지를 취하는 기준 수.

직접 $3^7 = 2187$을 계산해 $11$로 나눠도 $2187 \bmod 11 = 9$로 같은 값이 나오는 것을 확인할 수 있다. 차이는 제곱-곱 알고리즘이 중간중간 나머지를 취해 다뤄야 하는 숫자의 크기를 계속 작게 유지한다는 점이다. RSA에서 실제로 쓰이는 지수와 법은 수백 자리 숫자이므로, 이 방식이 아니면 계산 자체가 불가능할 정도로 느려진다. 06편의 디피-헬만 키교환과 08편의 RSA 계산은 모두 이 절차를 그대로 사용한다.

모듈러 역원(modular inverse): 나눗셈을 되돌리는 열쇠

쉽게 말하면: 모듈러 세계에는 나눗셈이 따로 없어서, “곱하면 1이 되는 짝꿍 수”를 찾아 나눗셈 대신 쓴다.

일반 산수에서 $a$로 나누는 것은 $\frac{1}{a}$을 곱하는 것과 같다. 모듈러 연산에는 분수가 없으므로, “$a$와 곱했을 때 결과가 $1$이 되는 수” $a^{-1}$을 찾아 나눗셈을 대신한다. 이를 모듈러 역원이라 하며 다음을 만족하는 $x$다.

• $a$: 역원을 구하려는 수.
• $x$: $a$의 모듈러 역원(찾으려는 값).
• $n$: 법.

예를 들어 $3 \bmod 11$의 역원을 구해 보자. $x$에 $1$부터 차례로 대입하며 $3x \bmod 11$이 $1$이 되는 값을 찾으면, $3 \times 4 = 12$, $12 \bmod 11 = 1$이므로 $x = 4$다.

작은 수는 이렇게 대입으로 찾을 수 있지만, RSA처럼 법이 수백 자리인 경우에는 확장 유클리드 호제법(extended Euclidean algorithm, 두 수의 최대공약수를 구하는 과정에서 동시에 모듈러 역원까지 구해내는 절차)을 쓴다. 이 알고리즘 자체의 세부 절차는 08편에서 RSA 키쌍 생성을 다룰 때 실제 계산으로 다시 등장하므로, 여기서는 “역원이 나눗셈의 대체 역할을 한다”는 개념만 확실히 잡아 둔다.

이산로그(discrete logarithm)와 디피-헬만의 직관

쉽게 말하면: 거듭제곱은 계산하기 쉽지만, 결과에서 거꾸로 몇 제곱인지 알아내는 것은 훨씬 어렵다.

일반 로그는 $g^a = y$일 때 $a = \log_g y$로 쉽게 구할 수 있다. 그런데 모듈러 세계에서 $g^a \bmod p = y$가 주어졌을 때 $a$를 구하는 문제(이산로그 문제)는 $p$가 커지면 사실상 계산이 불가능할 정도로 어려워진다. 이 “계산의 비대칭성”(거듭제곱은 쉽고, 역으로 지수를 구하는 것은 어려움)이 06편에서 다룰 디피-헬만 키교환과 여러 공개키 암호 방식의 안전성 근거가 된다.

작은 수로 이 비대칭성을 체감해 보자. $p = 11$, $g = 2$일 때 $2^a \bmod 11$의 값을 $a = 1$부터 나열하면 다음과 같다.

정방향(a를 알 때 결과 구하기)은 앞 절의 모듈러 지수 계산으로 즉시 구해진다. 하지만 “$2^a \bmod 11 = 10$일 때 $a$는 얼마인가”라는 역방향 질문에 답하려면, 이 작은 예제에서는 표를 훑어 $a = 5$임을 찾을 수 있지만, $p$가 수백 자리 소수가 되면 이런 무작정 대입(brute-force, 브루트포스)은 우주의 나이보다 긴 시간이 걸린다. 06편의 디피-헬만 키교환은 바로 이 계산 비대칭성을 이용해, 통신 당사자만 알 수 있는 공유 비밀을 도청자는 알아낼 수 없게 만든다.

XOR(배타적 논리합) 연산

진리표와 계산

쉽게 말하면: 두 비트가 서로 다르면 1, 같으면 0이 나오는 연산이다.

XOR(exclusive OR, 배타적 논리합)은 두 비트를 비교해 서로 다를 때만 1을 출력하는 논리 연산이며 기호로 $\oplus$를 쓴다. 스트림 암호(05편)의 핵심 연산이자, 여러 해시·블록암호 내부 연산에도 등장한다.

비트열(여러 비트를 나열한 것) 단위로 계산할 때는 같은 자리끼리 XOR한다.

• 첫째 자리: $1 \oplus 0 = 1$
• 둘째 자리: $0 \oplus 1 = 1$
• 셋째 자리: $1 \oplus 1 = 0$
• 넷째 자리: $0 \oplus 0 = 0$

XOR의 되돌리기(복호화) 성질

XOR의 가장 중요한 암호학적 성질은 같은 값을 두 번 XOR하면 원래 값으로 되돌아온다는 것이다. 이는 스트림 암호가 평문을 키와 XOR해 암호문을 만들고, 같은 키를 다시 XOR해 평문을 복원하는 원리의 근거다.

앞의 예시로 확인하면, $1010 \oplus 0110 = 1100$이었다. 여기에 다시 $0110$을 XOR하면 다음과 같다.

• 첫째 자리: $1 \oplus 0 = 1$
• 둘째 자리: $1 \oplus 1 = 0$
• 셋째 자리: $0 \oplus 1 = 1$
• 넷째 자리: $0 \oplus 0 = 0$

결과 $1010$은 처음 평문과 정확히 일치한다. 이 구조에서 "$1010$"을 평문, "$0110$"을 키, "$1100$"을 암호문이라고 이름 붙이면, 암호화는 평문과 키를 XOR하는 것이고 복호화는 암호문과 같은 키를 다시 XOR하는 것이 된다. 05편의 스트림 암호는 이 원리를 그대로 사용하되, 매번 같은 키를 반복하지 않고 키로부터 생성한 긴 난수열(키스트림)을 사용해 안전성을 높인다.

키 공간과 브루트포스 확률

키 공간(key space)

쉽게 말하면: 키가 몇 비트냐에 따라 가능한 키의 개수가 기하급수적으로 늘어난다.

키 공간은 암호에서 사용 가능한 키의 전체 경우의 수를 뜻한다. 키가 $n$비트로 이루어져 있다면, 각 비트가 0 또는 1 두 가지 값을 가질 수 있으므로 키 공간의 크기는 $2^n$이다.

• $n$: 키의 비트 길이.
• $2^n$: 가능한 키의 총 개수.

몇 가지 비트 길이에 대한 실제 값을 계산해 보면 크기 증가를 체감할 수 있다.

키 길이가 1비트 늘어날 때마다 키 공간은 정확히 두 배로 늘어난다. 이것이 128비트, 256비트 같은 현대 암호 키 길이가 왜 “충분히 안전하다”고 여겨지는지의 근거다.

브루트포스(brute-force) 성공 확률

브루트포스 공격(무차별 대입 공격)은 가능한 모든 키를 하나씩 시도해 정답 키를 찾는 방법이다. 키 공간이 $2^n$일 때, 무작위로 한 번 시도해서 정답을 맞힐 확률은 다음과 같다.

8비트 키($2^8 = 256$)를 예로 들면 한 번 시도로 맞힐 확률은 $\frac{1}{256} = 0.0039$, 즉 약 0.39퍼센트다. 평균적으로 정답을 찾기까지 시도해야 하는 횟수는 전체 키 공간의 절반 정도(운이 좋으면 더 빨리, 나쁘면 전체를 다 시도)로 어림잡을 수 있다.

8비트라면 평균 128번 정도 시도하면 찾아낼 수 있다는 뜻이며, 컴퓨터에게는 순식간이다. 반면 128비트 키의 평균 시도 횟수는 $2^{127}$로, 이는 지구상의 모든 컴퓨터가 초당 수십억 번씩 시도해도 우주의 나이보다 긴 시간이 걸리는 규모다. 05~06편에서 “이 알고리즘의 키 길이가 충분한가”를 판단할 때 이 확률 감각을 그대로 사용한다.

논리식과 진리표: 보안 정책 서술의 언어

쉽게 말하면: 방화벽 규칙이나 접근통제 정책은 결국 참·거짓을 판단하는 논리식으로 표현된다.

정보보호 관리(13~14편)의 접근통제 규칙, 방화벽 정책, 조건부 인증 규칙은 모두 논리식(참 또는 거짓 값을 갖는 명제를 연산자로 연결한 식)으로 표현할 수 있다. 기본 논리연산자는 다음과 같다.

예를 들어 “사내 IP 대역에서 접속했고(P) AND 유효한 인증서를 제시했다(Q)“라는 접근 허용 규칙을 $P \land Q$로 쓸 수 있다. 진리표로 이 규칙을 확인하면 다음과 같다.

이 표는 “IP 조건과 인증서 조건 둘 다 만족해야 접속이 허용된다”는 정책을 정확하게 표현한다. 만약 정책이 “IP 대역 조건 또는 인증서 조건 중 하나만 만족해도 허용”이라면 $P \lor Q$로 바뀌고, 진리표에서 참이 되는 경우의 수도 3가지로 늘어난다. 14편의 접근통제 모델(MAC·DAC·RBAC)이나 방화벽 규칙을 읽을 때, “그리고(AND)“인지 “또는(OR)“인지를 정확히 구분하는 것이 정책 해석의 핵심이며, 이 구분을 틀리면 정반대의 접근 결과를 예측하게 된다.

자주 틀리는 점

• 모듈러 연산을 나머지가 아니라 몫으로 착각: $17 \bmod 5$의 답은 몫인 3이 아니라 나머지인 2다.
• 모듈러 지수 계산에서 중간 나머지 생략을 잊음: 제곱-곱 알고리즘의 핵심은 매 단계 나머지를 취해 숫자를 작게 유지하는 것이다. 끝까지 큰 수로 계산한 뒤 마지막에만 나머지를 취해도 수학적으로는 같은 답이 나오지만, 실제 암호 시스템에서는 그렇게 하면 계산이 불가능할 정도로 느려진다.
• 이산로그 문제를 일반 로그처럼 쉽게 풀 수 있다고 오해: 정방향(거듭제곱)은 쉽고 역방향(지수 찾기)은 어렵다는 비대칭성이 핵심이며, 이 비대칭성 자체가 공개키 암호의 안전성 근거다.
• XOR과 OR을 혼동: $1 \oplus 1 = 0$이지만 $1 \lor 1 = 1$이다. 두 연산자의 진리표 마지막 행이 다르다는 점을 기억한다.
• 키 길이와 키 공간 크기의 관계를 선형으로 오해: 키 길이가 1비트 늘 때마다 키 공간은 더하기 1이 아니라 곱하기 2(즉 $2^n$)로 늘어난다.
• 논리식의 AND와 OR을 일상어 감각으로만 판단: 보안 정책 문서의 “그리고/또는”은 반드시 논리식으로 옮겨 진리표로 검증해야 한다.

핵심 정리

• 모듈러 연산은 나머지를 취하는 연산이며, 덧셈·곱셈에 대한 분배 성질 덕분에 큰 수를 작게 유지하며 계산할 수 있다.
• 모듈러 지수는 제곱-곱 알고리즘으로 빠르게 계산하며, 이는 RSA·디피-헬만 계산의 기초가 된다. 모듈러 역원은 모듈러 세계의 나눗셈 역할을 한다.
• 이산로그 문제는 정방향(거듭제곱)은 쉽지만 역방향(지수 찾기)은 어려운 계산 비대칭성을 가지며, 이것이 여러 공개키 암호의 안전성 근거다.
• XOR은 같은 값을 두 번 적용하면 원래대로 되돌아오는 성질이 있어 스트림 암호의 암·복호화에 그대로 쓰인다.
• 키 공간은 $2^n$으로 커지며, 브루트포스의 평균 성공 시도 횟수는 $2^{n-1}$이다. 이 감각이 안전한 키 길이 판단의 기준이 된다.
• 보안 정책은 AND·OR·NOT으로 이루어진 논리식과 진리표로 정확히 표현·검증할 수 있다.

마무리 복습

참고 자료

• NIST Computer Security Resource Center 
• 한국인터넷진흥원(KISA)