CMATH-11. 암호학에서 유한체를 정의할 때 소수를 사용하는 이유

암호학에서 유한체를 정의할 때 소수($p$)를 사용하는 이유는 단순히 숫자가 커서가 아니라, 수학적으로 '체(Field)'라는 완벽한 대수 구조를 형성하기 위한 필수 조건이기 때문입니다.

 

물리학에서 계(system)가 붕괴하지 않기 위해 보존 법칙이 필요하듯, 암호 연산이 성립하기 위해서는 모든 원소에 대해 역원(Inverse)이 존재해야 합니다.

1. 모든 원소의 역원 존재 (나눗셈의 가능성)

가장 핵심적인 이유는 '0을 제외한 모든 원소로 나눌 수 있어야 한다'는 것입니다.

• 합성수($n$)를 사용할 때: 예를 들어 $\pmod 6$의 세계를 가정해 봅시다.
  • $2 \times 3 = 6 \equiv 0 \pmod 6$ 입니다.
  • 여기서 $2$에 무엇을 곱해도 $1$이 될 수 없습니다. 즉, 2의 역원($1/2$)이 존재하지 않습니다.
  • 이런 경우를 '영인자(Zero-divisor)'라고 하며, 이 현상이 발생하면 방정식의 해가 유일하지 않거나 연산 도중 에러가 발생하여 암호 체계가 깨집니다.
• 소수($p$)를 사용할 때: $p$가 소수이면 $1$부터 $p-1$까지의 모든 정수는 $p$와 서로소(coprime)입니다.
  • 확장 유클리드 호제법에 의해 모든 원소 $a$에 대해 $a \times x \equiv 1 \pmod p$를 만족하는 역원 $x$가 반드시 단 하나 존재합니다.
  • 덕분에 자유롭게 더하고, 빼고, 곱하고, 나눌 수 있는 완벽한 '체(Field, $\mathbb{F}_p$)'가 형성됩니다.

2. '분할 정복' 공격 방지 (Pohlig-Hellman Attack)

만약 소수가 아닌 합성수 $n$을 모듈러스로 사용하면, 공격자는 중국인의 나머지 정리(CRT)를 이용해 문제를 쪼개서 풀 수 있습니다.

• $n = p \times q$ 라면, $\pmod n$에서의 이산 로그 문제는 $\pmod p$와 $\pmod q$에서의 작은 문제 두 개로 나뉩니다.
• 공격자는 큰 문제를 푸는 대신, 훨씬 쉬운 작은 문제 두 개를 풀어 답을 조합할 수 있습니다. 이를 Pohlig-Hellman 공격이라고 합니다.
• 따라서, 이산 로그 문제의 난이도를 최대로 유지하려면 문제를 쪼갤 수 없도록 커다란 소수(또는 소수 차수의 부분군)를 사용해야만 합니다.

3. 최대 주기와 순환성 확보

암호학에서는 생성원(Generator) $g$를 반복 연산했을 때, 체 안의 모든 원소를 골고루 거쳐서 원래대로 돌아오기를 기대합니다.

• 소수 $p$를 사용하면 $(\mathbb{Z}_p^*, \times)$는 순환 군(Cyclic Group)이 되며, 적절한 생성원을 선택할 경우 $1$부터 $p-1$까지 모든 숫자를 빠짐없이 순회하는 최대 주기를 가집니다.
• 만약 주기가 짧다면 공격자가 금방 패턴을 찾아낼 수 있지만, 소수를 사용하면 이러한 '지름길'을 수학적으로 차단할 수 있습니다.

4. 타원 곡선에서의 소수 (Scalar Multiplication)

타원 곡선에서도 마찬가지입니다. 점 $P$를 $k$번 더할 때, $k$가 정의되는 공간이 소수 $p$를 모듈러스로 하는 유한체여야 합니다.

• 타원 곡선 위의 점들의 개수(군계수, Order) 역시 커다란 소수 $n$이 되도록 곡선을 설계합니다 (예: secp256k1).
• 이렇게 해야만 $Q = kP$ 연산에서 $k$를 찾는 과정이 어떤 수학적 구조적 결함 없이 순수하게 어려운 이산 로그 문제로 남게 됩니다.

요약

특징	합성수 (n) 사용 시	소수 (p) 사용 시
대수 구조	환 (Ring) - 나눗셈 불가능한 원소 존재	체 (Field) - 모든 원소 나눗셈 가능
보안성	작은 인수로 쪼개서 공격 가능 (취약)	쪼개기 불가능 (안전)
연산 결과	결과값이 0이 되어 정보가 소실될 수 있음	모든 연산 결과가 유일하게 보존됨

 

결국 소수를 사용하는 것은 암호 연산의 정당성(Correctness)을 보장하고, 공격자의 지름길(Attack shortcut)을 원천 봉쇄하기 위한 수학적 장치라고 이해하면 됩니다.