이산 로그

위키백과 ― 우리 모두의 백과사전.

추상대수 분야에서, 이산 로그(離散 -, discrete logarithms)는 일반 로그와 비슷하게 군에서 정의된 연산이다. 로그(logarithm)를 대수(對數)라 부르기도 하므로, 이산대수(離散對數)라고 하기도 한다.

이산 로그의 가장 단순한 형태는 Z_p^*에서 정의하는 것이다. Z_p^*의 집합은 {1, …, p − 1}이고 소수 p를 법으로 가지는 모듈로 곱셈에 대하여 닫혀있다. 이 군에서 어떤 수의 k 제곱을 구하려면, 그 수를 k번 제곱한 다음 p로 나눈 나머지를 구하면 된다. 이런 연산을 이산 거듭제곱(discrete exponentiation)이라고 한다. 예를 들어, Z₇^*에서 3의 5제곱을 구하는 경우, 3⁵=243 이고 243을 7로 나눈 나머지가 5이므로 Z₇^*에서 3⁵=5이다. 이산 로그는 이산 거듭제곱의 역함수이다. 앞의 예제를 사용하여 설명하면, 3^k ≡ 5 (mod 7)일때 이 조건을 만족시키는 가장 작은 k가 Z₇^*에서 밑이 3인 5의 이산 로그값이다.

이산 로그의 정의를 일반화하면 다음과 같다. G가 n개의 원소를 가진 유한 순환군이라고 하자. 이 군은 곱셈군이라고 가정한다. b가 G의 생성원이면 G의 모든 원소 x는 임의의 정수 k에 대하여 x = b^k의 형태로 쓸 수 있다. 또한 x를 표현하는 모든 원소들은 모듈로 n에 대해 합동이다. 이런 조건에서 다음과 같은 함수를 정의한다.

여기서 Z_n은 정수 n을 법으로 가지는 환이고 x에는 모듈로 n에 대한 congruence class를 할당한다. 이와 같은 군 동형사상을 밑이 b인 이산 로그라고 부른다.

로그 함수의 밑변환은 이산 로그에서도 그대로 적용된다. c가 G의 또다른 생성원이면, 다음 식이 성립한다.

[편집] 실제 사용

이산 로그의 역함수인 이산 거듭제곱은 효율적으로 계산할 수 있지만, 이산 로그 계산은 어려운 것으로 알려진 군이 존재한다. (이산 거듭제곱의 경우 제곱을 여러번 반복해서 효율적으로 계산하는 방법등이 있다.) 일부 암호는 이런 비대칭성을 바탕으로 설계되기도 한다. 일반 이산 로그를 구하는 문제는 일반 이산 로그 문제(generalized discrete logarithm problem, 혹은 줄여서GDLP)라고 부르며, 현재까지 이에 대한 효율적인 알고리즘을 찾지 못하고 있다.

암호학에서 G는 보통 순환군 (Z_p)^*를 사용한다. 자세한 내용은 엘가말 암호, 디피-헬만 열쇠교환, DSA등에 있다.

최근에는 유한체에서 정의된 타원 곡선의 순환 부분군을 암호에 적용하기 위해 많은 연구가 진행되고 있다. 자세한 내용은 타원 곡선 암호에 있다.

[편집] 이산 로그 알고리즘

이산로그에는 소인수분해 알고리즘과 비슷한 알고리즘이 많이 있다. 소인수분해 역시 암호학에서 널리 사용되고 있다.

• 단순 곱셈
• 아기걸음 거인걸음
• 폴라드 로 알고리즘
• Pohlig-Hellman 알고리즘
• Index calculus 알고리즘

v · d · e  공개 키 암호 방식
알고리즘	Cramer-Shoup · DH · DSA · ECDH · ECDSA · EKE · ElGamal · GMR · MQV · NTRUEncrypt · NTRUSign · Paillier · 라빈 · Rabin-Williams · RSA · Schnorr · SPEKE · SRP · XTR
이론	이산 로그 · 타원곡선 암호 · RSA 문제
표준	ANS X9F1 · CRYPTREC · IEEE P1363 · NESSIE
기타	전자 서명 · 공개 키 기반 구조(PKI) · Web of trust · 키 크기