CMATH-07. 이산 로그 문제를 풀기 어려운 이유

이 문제의 어려움은 간단한 지름길이나 공식이 없어서, 답을 찾으려면 사실상 거의 모든 가능성을 하나하나 확인해야 한다는 데 있습니다.

시계 위에서의 점프 게임

먼저, 모듈러 연산을 거대한 눈금을 가진 시계라고 상상해 보겠습니다. 일반 시계는 눈금이 12개지만, 암호학에서 사용하는 시계(법, p)는 그 눈금의 수가 상상도 할 수 없을 만큼 많습니다.

​

쉬운 문제 (앞으로 점프하기)

​

3을 5번 곱하고 17로 나눈 나머지(3^5 mod 17)를 구하는 것은 쉽습니다. 이는 "17칸짜리 시계에서, 3배씩 점프하는 규칙으로 5번 뛰어라. 최종 위치는 어디인가?"와 같습니다.

1. 3^1 → 3
2. 3^2 → 9
3. 3^3 → 27 ≡ 10 (mod 17)
4. 3^4 → 10 * 3 = 30 ≡ 13 (mod 17)
5. 3^5 → 13 * 3 = 39 ≡ 5 (mod 17)

​컴퓨터는 이처럼 정해진 규칙대로 앞으로 점프하는 것은 눈 깜짝할 사이에 해냅니다.

​

어려운 문제: 몇 번 점프했는지 맞히기

​

"17칸짜리 시계에서, 3배씩 점프하는 규칙으로 뛰었더니 최종 위치가 5였다. 총 몇 번 점프했을까?"

(즉, 3^x ≡ 5 (mod 17)을 만족하는 x를 찾아라)

​

우리는 위에서 답이 5라는 것을 알지만, 결과값 5만 보고 어떻게 x를 찾을 수 있을까요? 점프 결과는 시계 위에서 무작위처럼 보입니다.

​

3 → 9 → 10 → 13 → 5 → 15 → 11 → 16 → 14 → 8 → 7 → 4 → 12 → 2 → 6 → 1

​

결과값 5가 나왔다고 해서 x가 5라는 것을 바로 알 수 있는 방법이 없습니다. 이전 값이 13이라는 것을 알지 못하면 역추적이 불가능합니다. 결국, 우리는 x가 1일 때, 2일 때, 3일 때... 모든 가능성을 하나씩 시도해보는 수밖에 없습니다.​

"경우의 수가 많다"의 진짜 의미

작은 17칸짜리 시계에서는 최대 16번만 시도하면 답을 찾을 수 있습니다. 하지만 실제 암호학에서는 어떨까요?

​

암호학에서 사용하는 시계의 눈금 수(소수 p)는 2048비트 수준입니다. 이 숫자는 10진수로 변환하면 617자리의 숫자입니다.​

• 이것이 바로 '경우의 수'입니다. 우리가 찾아야 할 x (점프 횟수)는 1부터 이 617자리 숫자 사이의 값 중 하나입니다.
• 경우의 수: 약 1,000,000,000,....(0이 617개).... 개

​이 숫자가 얼마나 거대한지 감을 잡기 위해 다른 것과 비교해 보겠습니다.

• 관측 가능한 우주에 있는 모든 원자의 수: 약 10^80개 (0이 80개)
• 이산 로그 문제의 경우의 수: 약 10^617개 (0이 617개)

​즉, 우리가 찾아야 할 정답 x가 숨어있는 가능성의 바다는 우주의 모든 원자를 합친 것보다도 비교할 수 없을 정도로 넓습니다.

​

현재 인류가 가진 가장 빠른 슈퍼컴퓨터를 모두 동원해서 1초에 수십억 개씩 답을 확인한다고 해도, 이 모든 경우의 수를 다 확인하려면 우주의 나이보다 훨씬 더 긴 시간이 걸립니다.

​

정리하자면, 이산 로그 문제가 어렵다는 것은 '답을 찾는 공식적인 방법이 없어 모든 가능성을 다 확인해야 하는데, 그 가능성의 개수가 현실적으로 계산이 불가능할 만큼 천문학적이기 때문'입니다. 바로 이 계산적 불가능성이 현대 암호 시스템의 안전을 지키는 핵심 원리입니다.