정보 보안의 핵심 개념, 모듈러 산술이란 무엇일까?

모듈러 산술이란?

모듈러 산술(Modular Arithmetic)은 정수를 대상으로 하는 연산 체계로, 숫자가 특정 값에 도달하면 다시 처음으로 '돌아가는(wrap around)' 순환 구조를 가집니다. 시계를 떠올리면 쉽습니다. 12시를 지나면 다시 1시부터 시작되는 것처럼요. 모듈러 산술을 활용하면 군(group), 환(ring), 체(field)와 같은 대수적 구조를 손쉽게 구성할 수 있으며, 이는 현대 공개키 암호 시스템의 기본 구성 요소입니다.

암호학에서 모듈러 산술이 중요한 이유

대표적인 예로 디피-헬만(Diffie-Hellman) 키 교환은 소수 p에 대한 정수의 곱셈군(multiplicative group)을 필요로 합니다. 물론 이 외에도 다양한 군이 활용될 수 있습니다. 모듈러 산술은 수직선이 아닌 원(circle) 위에서 이루어지는 연산으로 이해할 수 있으며, 모듈로 N에서는 0부터 N-1까지의 N개 정수만 사용합니다.

또한 모듈러 산술은 여러 기본 연산에 대한 알고리즘이 잘 정립되어 있다는 점도 큰 장점입니다. 이 때문에 대칭키 암호인 AES에서 유한체(finite field)를 사용할 수 있는 것입니다. 암호학은 계산하기 어려운 복잡한 문제를 필요로 하는데, 모듈러 감산(modular reduction)을 도입하면 일부 문제가 급격히 어려워집니다.

예를 들어 로그(logarithm)는 일반 정수 범위에서는 비교적 쉽게 계산할 수 있지만, 모듈러 감산이 적용되면 계산 난이도가 크게 올라갑니다. 거듭제곱근(root)을 찾는 문제도 마찬가지입니다. 이처럼 모듈러 산술은 암호학의 중심에 있는 핵심 수학적 개념이라 할 수 있습니다.

모듈러 산술의 정의

현대 정수론의 상당 부분과 여러 실용적 문제가 모듈러 산술과 관련되어 있습니다. 모듈로 N 산술에서는 N의 배수만큼 차이가 나는 수들을 서로 같은 것으로 취급합니다. 즉, 어떤 정수 m에 대해 다음이 성립하면 x와 y는 모듈로 N에 대해 합동입니다.

x ≡ y (mod N)  if  x = y + mN (m은 정수)

이러한 동치 관계는 모든 정수를 N개의 동일한 클래스로 나누며, 일반적으로 각 클래스는 가장 단순한 대표원인 0, 1, …, N-1로 표시합니다.

정수 a와 양의 정수 n이 주어졌을 때, a mod n은 a를 n으로 나눈 나머지를 의미하며 다음 식이 성립합니다.

a = ⌊a/n⌋ × n + (a mod n)

예시: 11 mod 7 = 4

합동과 잉여류

정리(Theorem) — mod n 연산은 정수 집합 위의 동치 관계(equivalence relation)입니다. 하나의 동치류에는 n으로 나눌 때 같은 나머지를 갖는 정수들이 포함되며, 이를 '모듈로 n의 합동 클래스(congruence class)'라고 부릅니다. 두 정수 a와 b가 '동치'라고 말하는 대신 '모듈로 n에 대해 합동(congruent modulo n)'이라고 표현합니다.

a와 합동인 모든 정수들의 집합을 잉여류(residue class) [a]라고 합니다.

모듈로 연산자의 성질

• n | (a − b)이면 a ≡ b (mod n)
• (a mod n) = (b mod n)이면 a ≡ b (mod n)
• a ≡ b (mod n)이면 b ≡ a (mod n)
• a ≡ b (mod n)이고 b ≡ c (mod n)이면 a ≡ c (mod n)

모듈러 산술 연산의 성질

• [(a mod n) + (b mod n)] mod n = (a + b) mod n
• [(a mod n) − (b mod n)] mod n = (a − b) mod n
• [(a mod n) × (b mod n)] mod n = (a × b) mod n

Zn = {0, 1, 2, …, (n−1)}을 모듈로 n의 잉여 집합이라고 할 때, 주요 연산 법칙은 다음과 같습니다.