이산대수

Discrete Logarithm; 이산대수
큰 소수 p를 법으로 하는 거듭제곱 결과 y로부터 지수 x를 되찾는 문제로, 계산이 매우 어렵다는 성질이 여러 공개키 암호의 안전성 근거가 된다

이산대수 문제

소수 p와 생성원(원시근) g가 주어졌을 때 다음 식을 만족하는 x를 찾는 문제를 이산대수 문제(DLP, Discrete Logarithm Problem)라 한다.

$g^{x} \equiv y (\mod p)$

x와 g, p를 알면 y는 제곱-곱셈(square-and-multiply) 방법으로 빠르게 계산할 수 있다. 반대로 y, g, p만 알고 x를 구하는 것은 p가 충분히 크면(예: 2048비트 이상) 현실적인 시간 안에 풀 수 없다. 이렇게 한 방향은 쉽고 반대 방향은 어려운 성질을 일방향 함수라 하며, 이산대수는 소인수분해와 함께 대표적인 일방향 함수이다.

이산대수 기반 암호

방식	용도	설명
디피-헬만 키 교환	키 합의	1976년 제안된 최초의 공개키 방식. 서로 비밀 지수를 보내지 않고 공통 비밀값을 만든다. 인증이 없어 중간자 공격에 취약하다.
엘가말(ElGamal)	암호화·서명	디피-헬만을 암호화로 확장했다. 같은 평문도 매번 다른 난수를 써서 암호문이 달라지며, 암호문 길이가 평문의 2배가 된다.
DSA	전자서명	엘가말 서명을 변형한 미국 전자서명 표준(DSS) 알고리즘이다. 서명 전용이며 암호화에는 쓰지 않는다. FIPS 186-5(2023)부터는 새 서명 생성용으로 승인하지 않고 ECDSA 등을 권고한다.
타원곡선암호(ECC)	키 합의·서명	타원곡선 위 점의 스칼라 곱 Q = kP에서 k를 찾는 타원곡선 이산대수 문제(ECDLP)에 기반한다. RSA 3072비트와 비슷한 안전성을 256비트 키로 얻는다. ECDH, ECDSA가 대표적이다.

수치 예: 디피-헬만

작은 수로 원리를 확인한다. 공개값은 p = 23, g = 5이다(5는 23의 원시근).

A는 비밀값 a = 6을 고르고 $5^{6} mod 2 3 = 8$ 을 B에게 보낸다.
B는 비밀값 b = 15를 고르고 $5^{15} mod 2 3 = 19$ 를 A에게 보낸다.
A는 받은 19로 $1 9^{6} mod 2 3 = 2$ 를 계산한다.
B는 받은 8로 $8^{15} mod 2 3 = 2$ 를 계산한다.
두 사람은 같은 공유 비밀값 2(= $5^{6 \times 15} mod 2 3$ )를 얻는다.

도청자는 8과 19를 보지만 a나 b를 알려면 $5^{x} mod 2 3 = 8$ 의 이산대수를 풀어야 한다. 이 예처럼 p가 작으면 전부 대입해 x = 6을 바로 찾을 수 있으므로 실제로는 매우 큰 소수를 쓴다.

인수분해 기반 암호와 비교

구분	이산대수 기반	인수분해 기반
어려운 문제	$g^{x} mod p$ 에서 x 구하기	두 소수의 곱 n = pq에서 p, q 구하기
대표 알고리즘	디피-헬만, 엘가말, DSA, ECC	RSA 암호화, 라빈(Rabin)
주 용도	키 합의, 전자서명	암호화, 전자서명
특징	타원곡선으로 옮기면 키가 크게 짧아짐	구조가 단순하고 암호화·서명 모두 가능

양자 컴퓨터의 위협

쇼어(Shor) 알고리즘은 양자 컴퓨터에서 소인수분해와 이산대수(ECDLP 포함)를 모두 다항 시간에 풀 수 있으므로, 충분한 규모의 양자 컴퓨터가 나오면 RSA·디피-헬만·ECC가 모두 깨진다. 이에 대비해 격자 기반 ML-KEM(FIPS 203) 같은 양자 내성 암호로의 전환이 진행 중이다.

시험 포인트

디피-헬만, 엘가말, DSA, ECC는 이산대수, RSA는 소인수분해 문제에 기반한다는 분류가 자주 출제된다.
디피-헬만 공유키 계산 문제는 $K = g^{a b} mod p$ 를 직접 계산해 확인한다.
디피-헬만은 인증 기능이 없어 중간자 공격에 취약하다.
쇼어 알고리즘은 이산대수와 소인수분해 기반 암호를 모두 위협한다.

같이 보기

참고 문헌