ECC-3. 이산 로그 문제를 풀기 어려운 이유

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

시계 위에서의 점프 게임

먼저, 모듈러 연산을 거대한 눈금을 가진 시계라고 상상해 보겠습니다. 일반 시계는 눈금이 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초에 수십억 개씩 답을 확인한다고 해도, 이 모든 경우의 수를 다 확인하려면 우주의 나이보다 훨씬 더 긴 시간이 걸립니다.

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