이산 로그 문제 (Discrete Logarithm Problem, DLP)

이산 로그 문제(DLP)는 유한 군에서 생성원 g와 원소 h = gˣ가 주어졌을 때 지수 x를 찾는 문제입니다. 거듭제곱은 빠르게 계산할 수 있지만 역으로 지수를 찾는 것은 큰 군에서 현실적으로 불가능하다고 여겨지며, 이 비대칭성이 디피-헬만 키 교환, DSA·ECDSA, 슈노르 서명, 대부분의 블록체인 지갑 키의 안전성 근거입니다.

자세히 알아보기

'이산'이라는 말은 실수가 아닌 정수 나머지 세계에서 로그를 구한다는 뜻입니다. 대표적인 무대는 두 가지입니다. ① 소수 p를 법으로 하는 곱셈군: gˣ ≡ h (mod p). ② 타원곡선 위 점의 덧셈군: x·G = H. 후자를 타원곡선 이산 로그 문제(ECDLP)라고 부르며, 곱셈 표기 대신 덧셈 표기를 씁니다.

공격 알고리즘의 성능이 키 길이를 결정합니다. 어떤 군에나 쓸 수 있는 일반 알고리즘(베이비 스텝-자이언트 스텝, 폴라드 로)은 군 크기 n에 대해 약 √n 단계가 필요합니다. 그래서 256비트 타원곡선은 약 128비트 보안을 제공합니다. 반면 유한체 곱셈군에는 지수 계산법(index calculus), 수체 체(NFS) 같은 더 빠른 준지수 시간 공격이 있어 2048~3072비트 이상의 큰 소수가 필요합니다. 또한 군의 위수가 작은 소인수로만 이루어지면 폴리그-헬먼 알고리즘으로 쉽게 풀리므로 큰 소수 위수 부분군을 사용해야 합니다.

엄밀히는 DLP와 관련된 계산 디피-헬만(CDH), 결정 디피-헬만(DDH) 가정이 따로 있으며, 프로토콜마다 필요한 가정이 다릅니다. 양자 컴퓨터의 쇼어 알고리즘은 DLP를 다항 시간에 풀 수 있으므로, 장기적으로는 격자 기반 등 양자 내성 암호로의 전환이 필요합니다.

블록체인·암호화폐에서는

Bitcoin·Ethereum·Tron 지갑에서 개인 키 d와 공개 키 Q = d·G의 관계가 바로 ECDLP입니다. 공개 키와 주소는 누구나 볼 수 있지만, ECDLP가 어렵기 때문에 그로부터 개인 키를 계산해 USDT나 BTC를 훔칠 수 없습니다. 페더슨 커밋먼트, 불릿프루프, 링 서명 등 프라이버시 기술도 같은 가정 위에 서 있습니다.

쉽게 말하면

시계 바늘을 정해진 칸씩 몇 바퀴 돌렸는지 맞히는 문제와 비슷합니다. 최종 위치만 보고 돌린 횟수를 알아내기가 매우 어렵습니다.

예시

17을 법으로 3ˣ ≡ 13을 풀면 x = 4입니다(3⁴ = 81 = 4·17 + 13). 작은 수에서는 쉽게 찾지만, 법이 256비트 이상이면 모든 x를 시도하는 것은 불가능합니다.