661. 비대칭키의 수학적 문제 기반 (소인수분해, 이산대수)

핵심 인사이트: 세상에서 가장 풀기 쉬운 수학 문제는 곱하기(13 x 17 = 221)다. 하지만 반대로 "221은 어떤 소수 두 개의 곱인가?"라고 묻는 소인수분해는 숫자가 커지면 슈퍼컴퓨터로도 억 년이 걸린다. 비대칭키 암호학은 한 방향으로는 1초 만에 계산되지만, 반대 방향으로는 절대 풀 수 없는 이러한 일방향 수학적 난제들을 암호의 절대 반지로 활용한 천재적인 발상이다.

Ⅰ. 비대칭키(공개키) 암호학의 수학적 근간

대칭키(AES)가 데이터를 '섞고 비틀어서' 해독을 못 하게 막는 물리적인 미로라면, 비대칭키(RSA, ECC)는 처음부터 해커가 풀 수 없도록 증명된 **'수학적 난제(Hard Problem)'**를 자물쇠의 구조로 사용합니다.
핵심은 **일방향 함수 (Trapdoor One-way Function)**입니다. 자물쇠를 잠그는 연산(정방향 연산)은 매우 쉽고 빠르지만, 열쇠 없이 자물쇠를 부수고 여는 연산(역방향 연산)은 물리적으로 불가능한 수학 공식들입니다.

Ⅱ. 주요 수학적 난제 3가지 🌟

1. 소인수분해 (Integer Factorization) 문제

원리: 두 개의 엄청나게 큰 소수(Prime Number) $p$와 $q$를 곱해서 $N$을 만드는 것은 컴퓨터로 0.001초면 됩니다. 하지만 해커에게 $N$만 달랑 던져주고 "이거 어떤 두 소수를 곱한 건지 맞춰봐"라고 하면(소인수분해), 숫자가 600자리(2048비트)를 넘어가는 순간 전 세계 슈퍼컴퓨터 수만 대를 돌려도 우주의 수명보다 오랜 시간이 걸립니다.
적용 알고리즘: 세상에서 가장 유명한 RSA 알고리즘(662번 문서)의 근간이 됩니다.

2. 이산대수 문제 (DLP, Discrete Logarithm Problem)

원리: $y = g^x \mod p$ 라는 모듈러(나머지) 연산 공식에서, $g$와 $x$, $p$를 알면 $y$를 구하는 것은 쉽습니다. 하지만 반대로 $g$, $y$, $p$를 해커에게 주고 지수(Exponent)인 $x$를 구하라고 하면, 값이 무작위로 튀어서 패턴이 없기 때문에 숫자가 커질수록 무차별 대입 외에는 풀 방법이 없습니다.
적용 알고리즘: 전자 서명 표준인 DSA, ElGamal, 그리고 키 교환 방식인 디피-헬만(Diffie-Hellman) 알고리즘이 이 원리를 사용합니다.

3. 타원 곡선 이산대수 문제 (ECDLP)

원리: $y^2 = x^3 + ax + b$ 형태의 특이한 곡선(타원 곡선) 위에서 점들을 더하고 곱하는 기하학적 연산입니다. 시작점에서 특정 연산을 반복해 도착점을 찾는 건 쉽지만, 도착점만 보고 "시작점에서 몇 번 연산해서 예가 나왔어?"라고 역추적하는 것은 극도로 어렵습니다.
효과: 기존의 소인수분해나 이산대수보다 수학적으로 훨씬 더 꼬여있어서, 키 길이가 훨씬 짧아도 동일한 방어력을 냅니다.
적용 알고리즘: 현대 모바일 통신의 절대 강자인 **ECC (타원 곡선 암호)**가 이 수학을 씁니다.

Ⅲ. 양자 컴퓨터(Quantum Computer)의 위협 🌟

위의 3가지 수학적 난제는 현재 인류의 폰 노이만 컴퓨터 구조에서는 '절대 풀 수 없는 문제'로 취급되어 인터넷 뱅킹과 블록체인을 지키고 있습니다. 하지만 큐비트(Qubit)를 써서 모든 경우의 수를 한 번에 동시에 병렬 계산해 버리는 **'쇼어 알고리즘(Shor's Algorithm)'을 탑재한 양자 컴퓨터가 상용화되면, 이 소인수분해와 이산대수 문제가 10분 만에 털려버리는 수학적 멸망의 날(Q-Day)**이 도래합니다. 이에 대비하기 위해 전 세계 수학자들이 현재 격자 기반 암호 등 새로운 난제를 찾는 양자 내성 암호(PQC)를 서둘러 개발하고 있습니다.

📢 섹션 요약 비유: 소인수분해 난제는 노란색 페인트와 파란색 페인트를 섞어서 초록색을 만드는 것(곱하기)과 같습니다. 섞는 건 1초면 되지만, 해커에게 초록색 페인트통 하나를 던져주고 "이게 어떤 노란색 1방울과 어떤 파란색 1방울을 섞어서 만든 건지 완벽히 분리해 내라"라고 명령하면 100년이 걸려도 불가능한 것과 같은 마법의 일방향 자물쇠입니다.