맨위로가기

이산 로그

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

이산 로그는 유한 순환군에서 정의되는 연산으로, 이산 거듭제곱의 역함수이다. 이산 로그 문제는 이산 거듭제곱의 결과를 알고 있을 때 밑과 지수를 찾는 문제이며, 효율적인 알고리즘이 알려져 있지 않아 암호학에 널리 활용된다. 이산 로그는 정수 인수분해와 유사한 성질을 공유하며, 디피-헬만 키 교환, 엘가말 암호, 전자 서명 알고리즘 등 다양한 암호 시스템의 보안 기반으로 사용된다.

더 읽어볼만한 페이지

  • 컴퓨터 과학의 미해결 문제 - 인공지능
    인공지능은 인간의 지능적 행동을 모방하는 컴퓨터 시스템으로, 인간 수준의 일반 지능을 가진 강인공지능과 특정 문제 해결에 특화된 약인공지능으로 나뉘며, 딥러닝 기술 발전으로 다양한 분야에서 성과를 거두고 있지만 윤리적, 사회적 문제에 대한 고려가 필요하다.
  • 컴퓨터 과학의 미해결 문제 - P-NP 문제
    P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.
  • 로그 - 상용로그
    상용로그는 10을 밑으로 하는 로그로, 십진법에 기반하여 log x 또는 lg x로 표기되며, 지표를 통해 진수의 자릿수 파악이 용이하여 과학적 측정에 활용되고 헨리 브리그스의 공로로 '브리그스의 로그'라고도 불린다.
  • 로그 - 자연로그
    자연로그는 밑이 e인 로그 함수로, ln(x) 등으로 표기되며 직교쌍곡선 아래 면적으로 정의되거나 지수 함수의 역함수로 정의될 수 있고, 다양한 수학적 성질과 함께 여러 분야에서 활용되며 복소 로그 함수로 확장되기도 한다.
  • 유한체 - 순환 중복 검사
    순환 중복 검사(CRC)는 데이터 전송 또는 저장 시 오류 검출을 위해 데이터를 다항식으로 간주하고 생성 다항식으로 나눈 나머지를 검사 값으로 사용하여 오류를 감지하는 기술이다.
  • 유한체 - 타원곡선 암호
    타원 곡선 암호는 타원 곡선 이론에 기반한 공개 키 암호 방식으로, 작은 키 크기로 높은 보안성을 제공하며 타원 곡선 이산 로그 문제의 어려움을 이용해 ECDH, ECDSA 등 다양한 암호 프로토콜에 활용되어 널리 사용된다.
이산 로그
수학
분야군론, 암호학
종류수론
관련 항목이산 지수
역함수이산 지수
응용공개 키 암호 방식
타원 곡선 암호
디피-헬만 키 교환
디지털 서명

2. 정의

'''이산 로그'''는 에서 정의되는 연산으로, 일반적인 로그의 개념을 이산적인 경우로 확장한 것이다.

''G''가 ''n''개의 원소를 가진 유한 순환군이고, ''b''가 ''G''의 생성원이면, ''G''의 모든 원소 ''x''는 임의의 정수 ''k''에 대하여 ''x'' = ''b''''k'' 형태로 쓸 수 있다. 이때, ''x''를 표현하는 모든 원소들은 모듈로 ''n''에 대해 합동이다. 이러한 조건에서 다음과 같은 함수를 정의할 수 있다.

:\log_b:\ G\ \rightarrow\ \mathbf{Z}_n

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

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

:\log_c (x) = \log_c(b) \cdot \log_b(x).

2. 1. 기본 정의 (Zp*)

'''Z'''''p''*에서 정의되는 이산 로그는 가장 단순한 형태이다. 여기서 '''Z'''''p''*는 {1, …, ''p'' − 1}의 집합을 나타내며, 소수 ''p''에 대한 모듈로 곱셈 연산에 대해 닫혀 있다. 이 군에서 어떤 수의 ''k'' 제곱을 계산하려면, 해당 수를 ''k''번 제곱한 후 ''p''로 나눈 나머지를 구하면 된다. 이러한 연산을 '''이산 거듭제곱'''이라고 한다. 예를 들어 '''Z'''7*에서 3의 5제곱을 구하는 경우, 35 = 243이고, 243을 7로 나눈 나머지는 5이므로, '''Z'''''7''*에서 35 = 5이다.

이산 로그는 이산 거듭제곱의 역함수이다. 즉, 3k ≡ 5 (mod 7)일 때, 이 조건을 만족하는 가장 작은 ''k''를 찾는 것이 '''Z'''''7''*에서 밑이 3인 5의 이산 로그값이다. 이를 이산로그문제(discrete logarithm problem)라고도 한다.

소수 ''p''를 법으로 하는 정수의 합동류로 구성된 집합 {1, 2, ..., ''p'' − 1}에 곱셈을 적용한 ('''Z'''/''p'''''Z''')×을 통해 이산 로그를 쉽게 이해할 수 있다.

이 군에서 어떤 원소의 ''k''제곱을 구하려면, 일반적인 정수로 간주하여 ''k''제곱을 계산하고, ''p''로 나눈 나머지(잉여)를 구한다 (이를 '''이산 거듭제곱'''이라고도 한다). 예를 들어 ('''Z'''/17'''Z''')×에서 34를 계산하려면, 34 = 81을 계산하고, 81을 17로 나누어 나머지 13을 얻는다. 따라서, ('''Z'''/17'''Z''')×에서 34 ≡ 13 (mod 17)이 된다.

'''이산 로그'''는 이 연산의 역연산이다. 예를 들어, 3''k'' ≡ 13 (mod 17)에서 ''k'' = 4가 해가 되지만, 유일한 해는 아니다. 316 ≡ 1 (mod 17)이므로, ''n''이 정수일때, 34+16 ''n'' ≡ 13 × 1''n'' ≡ 13 (mod 17) 이며, 4 + 16 ''n'' 형태의 무한한 해를 가진다. 3''m'' ≡ 1 (mod 17)을 만족하는 최소 양의 정수 ''m''은 16이므로(3의 위수), 방정식의 해는 ''k'' ≡ 4 (mod 16)으로 표현된다.

일반적으로, ''n''이 정수이고 기약 잉여류군 ''G'' = ('''Z'''/''n'''''Z''')×가 순환군일 때 (''n''은 2, 4, 소수 거듭제곱 ''q'', 2 ''q'' 형태), 군 ''G''의 위수는 φ(''n'')이다. 위수 φ(''n'')인 원소 ''b''(원시근 (primitive root of modulo ''n'')영어)가 존재하여, ''G''의 각 원소 ''a''에 대해 ''b''''k'' ≡ ''a''가 되는 ''k''는 φ(''n'')을 법으로 유일하게 정해진다(이 때의 이산 로그는 '''지수''' (index)영어라고도 한다). 앞선 예에서 φ(17) = 16이고, ''b'' = 3은 ('''Z'''/17'''Z''')×를 생성하는 위수 16의 원소이며, ''a'' = 13에 대해 ''k'' mod 16이 유일하게 결정된다.

2. 2. 일반적인 정의

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

:\log_b:\ G\ \rightarrow\ \mathbf{Z}_n

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

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

:\log_c (x) = \log_c(b) \cdot \log_b(x).

3. 예시

이산 로그를 이해하는 쉬운 방법은 소수 ''p''를 법으로 하는 정수의 합동류로 구성된 집합 {1, 2, ..., ''p'' - 1}에 곱셈을 적용한 ('''Z'''/''p'''''Z''')×를 살펴보는 것이다.

이 군의 원소 ''k'' 제곱을 구하려면, 일반적인 정수로 간주하여 ''k'' 제곱을 계산한 다음 ''p''로 나눈 나머지(잉여)를 구하면 된다. 이를 '''이산 거듭제곱'''이라고도 한다. 예를 들어 ('''Z'''/17'''Z''')×에서 34을 계산하려면, 먼저 34 = 81을 계산하고, 81을 17로 나누어 나머지 13을 얻는다. 따라서, ('''Z'''/17'''Z''')× 안에서 34 ≡ 13 (mod 17)이 성립한다.

'''이산 로그'''는 이산 거듭제곱의 역 연산이다. 예를 들어, ''k''에 대한 방정식 3''k'' ≡ 13 (mod 17)을 생각하면, ''k'' = 4가 해가 된다. 하지만, 페르마의 소정리에 의해 316 ≡ 1 (mod 17)이므로, 34+16''n'' ≡ 13 (mod 17) (''n''은 정수) 또한 성립한다. 즉, 4 + 16''n'' 형태의 무수히 많은 해가 존재한다. 3''m'' ≡ 1 (mod 17)을 만족하는 최소 양의 정수 ''m''은 16이므로(16은 ('''Z'''/17'''Z''')×에서 3의 위수이다), 방정식의 해는 ''k'' ≡ 4 (mod 16)으로 나타낼 수 있다.

일반적으로, ''n''을 정수로 하여 ''G'' = ('''Z'''/''n'''''Z''')×순환군이면(이러한 ''n''은 2, 4 및 소수 거듭제곱 ''q''와 2''q'' 형태로 제한된다), 군 ''G''의 위수는 φ(''n'')이다. 위수가 φ(''n'')인 원소 ''b'' (''n''을 법으로 하는 '''원시근''')가 존재하여, ''G''의 각 원소 ''a''에 대해 ''b''''k'' ≡ ''a''가 되는 ''k''는 φ(''n'')을 법으로 하여 유일하게 정해진다.[1]

3. 1. 10의 거듭제곱

10의 거듭제곱은 ..., 0.001, 0.01, 0.1, 1, 10, 100, 1000, ... 과 같이 표현되며, 이 목록의 모든 숫자 ''a''에 대해 log10''a''를 계산할 수 있다. 예를 들어 log1010000 = 4이고, log100.001 = −3이다. 이는 이산 로그 문제의 예시이다.

군론 용어에서, 10의 거듭제곱은 곱셈 아래에서 순환군 ''G''를 형성하고, 10은 이 군의 생성자이다. 이산 로그 log10''a''는 ''G''의 모든 ''a''에 대해 정의된다.

3. 2. 모듈러 산술

모듈러 산술 그룹 '''Z'''''p''×소수 ''p''에 대한 곱셈 그룹이다. '''Z'''17×에서 34를 계산하는 예시를 살펴보면, 34 = 81이고, 81을 17로 나누면 나머지 13을 얻는다. 따라서 '''Z'''17×에서 34 = 13이다.

이산 로그는 이 연산의 역 연산이다. 예를 들어, 3''k'' ≡ 13 (mod 17) 이라는 방정식을 생각해보자. ''k'' = 4가 해가 되지만, 유일한 해는 아니다. 페르마의 소정리에 의해 316 ≡ 1 (mod 17)이므로, 34+16''n'' ≡ 13 (mod 17) (''n''은 정수) 또한 성립한다. 즉, 4 + 16''n'' 형태의 무한히 많은 해가 존재한다. 3''m'' ≡ 1 (mod 17)을 만족하는 가장 작은 양의 정수 ''m''은 16이므로, 가능한 모든 해의 집합은 ''k'' ≡ 4 (mod 16)으로 표현할 수 있다.

4. 성질

거듭제곱은 일반적인 대수적 성질 ''b''''k''+''l'' = ''b''''k''''b''''l''을 따른다.[2] 즉, 함수 ''f''(''k'') = ''b''''k''는 덧셈에 대한 정수 '''Z'''에서 ''b''로 부분군 ''H''를 생성하는 군 준동형사상이다. ''H''의 모든 ''a''에 대해 log''b'' ''a''가 존재하며, ''H''에 속하지 않는 ''a''에 대해서는 log''b'' ''a''가 존재하지 않는다.

만약 ''H''가 무한이면, log''b'' ''a'' 역시 유일하며, 이산 로그는 군 동형사상 logb: H → Z와 같다.

반면에, ''H''가 유한 위수 ''n''을 갖는다면, log''b'' ''a''는 ''n''을 법으로 한 합동까지 유일하며, 이산 로그는 군 동형사상 logb: H → Zn과 같다. 여기서 '''Z'''''n''은 ''n''을 법으로 한 정수의 가산군을 나타낸다.

일반적인 로그에 대한 밑변환 공식은 유효하다. 만약 ''c''가 ''H''의 또 다른 생성자라면, logc a = logc b · logb a이다.

''G''를 위수 ''n''의 유한 순환군으로 하고(''군은 곱셈적으로 표기한다고 한다''), ''b''를 ''G''의 생성원으로 하면, ''G''의 임의의 원소 ''g''는 적당한 정수 ''k''를 사용하여 ''g'' = ''b''''k''의 형태로 나타낼 수 있다. 또한, ''g''를 표현하는 두 정수 ''k''1, ''k''2는 반드시 ''n''을 법으로 합동이다. 따라서, ''g''에 ''n''을 법으로 하는 ''k''의 합동류를 대응시킴으로써 logb: G → Z/nZ 와 같은 함수를 정의할 수 있다. 여기서 '''Z'''/''n'''''Z'''는 ''n''을 법으로 하는 정수의 잉여류환이다. 이 함수는 군동형사상이며, ''b''를 밑으로 하는 '''이산 로그'''라고 불린다.

일반적인 로그와 마찬가지로 밑의 변환 공식이 성립하는데, ''c''를 ''G''의 다른 생성원으로 하면 logc(g) = logc(b) · logb(g) 가 된다.

5. 알고리즘

이산 로그를 다항 시간 안에 계산하는 효율적인 알고리즘은 아직 알려져 있지 않다. 가장 단순한 방법은 ''a''''x'' = ''b''에서 ''x''를 0부터 하나씩 증가시키면서 ''b''를 찾는 것이다. 이 방법은 군의 크기에 비례하는 시간이 걸리며, 군의 크기의 자릿수에 대해서는 지수적인 복잡도를 가진다.

이보다 효율적인 알고리즘들이 여럿 제안되었지만, 이들 역시 대부분 지수적 복잡도를 가진다. 예를 들어 어떤 알고리즘들은 군의 크기의 제곱근에 비례하는 시간이 걸리는데, 이는 군의 크기 자릿수의 절반에 대해 지수적인 것이다.

5. 1. 알려진 알고리즘 목록


  • 아기 걸음 거인 걸음
  • 폴라드 로 이산 로그 알고리즘
  • 폴리그-헬만 알고리즘
  • 인덱스 계산 알고리즘
  • 함수체 체
  • 수체 체
  • 폴라드의 캥거루 알고리즘 (폴라드의 람다 알고리즘이라고도 함)

5. 2. 양자 알고리즘

피터 쇼어가 제안한 효율적인 양자 알고리즘이 있다.[3] 이 알고리즘은 이산 로그 문제를 효율적으로 해결할 수 있다.[7]

6. 정수 인수분해와의 비교

이산 로그 계산과 정수 인수분해는 별개의 문제이지만, 다음과 같은 몇 가지 속성을 공유한다.


  • 두 문제 모두 유한 아벨 군에 대한 숨겨진 부분군 문제의 특수한 경우이다.
  • 두 문제 모두 어려운 문제로 보인다(비-양자 컴퓨터에서 효율적인 알고리즘이 알려져 있지 않음).
  • 두 문제 모두 양자 컴퓨터에서 효율적인 알고리즘이 알려져 있다.
  • 한 문제의 알고리즘이 다른 문제에 자주 적용된다.
  • 두 문제의 어려움은 다양한 암호 시스템을 구축하는 데 사용되었다.

6. 1. 공통점


  • 두 문제 모두 유한 아벨 군에 대한 숨겨진 부분군 문제의 특수한 경우이다.
  • 두 문제 모두 어려운 문제로 보인다(비-양자 컴퓨터에서 효율적인 알고리즘이 알려져 있지 않음).
  • 두 문제 모두 양자 컴퓨터에서 효율적인 알고리즘이 알려져 있다.
  • 한 문제의 알고리즘이 다른 문제에 자주 적용된다.
  • 두 문제의 어려움은 다양한 암호 시스템을 구축하는 데 사용되었다.[1]

7. 암호학적 응용

암호학에서 이산 로그 문제는 일방향 함수의 중요한 예시로 활용된다. 제곱에 의한 거듭제곱을 사용하면 이산 거듭제곱 연산은 쉽게 계산할 수 있지만, 반대로 이산 로그를 계산하는 것은 어렵기 때문이다. 이러한 비대칭성은 정수 인수 분해 문제와 곱셈의 관계와 유사하며, 암호 시스템 구축에 활용된다.

디피-헬만 키 교환, 엘가말 암호, 전자 서명 알고리즘 등 많은 암호 체계가 이산 로그 문제의 어려움을 기반으로 설계되었다. 타원 곡선 암호의 경우 유한체에서 정의된 타원 곡선의 순환 부분군의 이산 로그 문제를 사용한다.[4]

이산 로그 문제의 어려움은 특정 그룹(예: '''Z'''''p''×의 큰 소수 차수 부분군)에서 두드러지는데, 평균 사례 복잡도가 임의 자기 감소성을 사용하여 최악의 경우만큼 어렵다는 것이 알려져 있다.[4]

하지만, 수체 체 알고리즘을 특정 그룹에 대해 미리 계산해두면, 해당 그룹에서 특정 로그를 얻는 계산 비용을 줄일 수 있다.[6]

2012년 6월 18일, 후지쯔(Fujitsu), 정보통신연구기구(NICT), 규슈 대학은 278자리(923비트)의 이산 로그를 사용한 "페어링 암호"를 해독했다고 발표했다. 이는 슈퍼컴퓨터 "케이"(京)로 환산하면 13.6분에 해당한다.[8]

7. 1. 주요 암호 시스템

암호학에서 이산 로그는 효율적으로 계산하기 어렵지만, 그 반대인 거듭제곱 연산은 제곱에 의한 거듭제곱을 사용하면 쉽게 계산할 수 있다. 이러한 일방향 함수의 성질은 RSA 암호와 마찬가지로 여러 암호 시스템에서 활용된다.

디피-헬만 키 교환은 비밀 키를 안전하게 교환하기 위해 이산 로그 문제의 어려움을 이용한다. 엘가말 암호는 공개키 암호 시스템의 한 종류이며, 전자 서명 알고리즘(DSA)은 전자 서명의 표준으로 사용된다. 이들 모두 이산 로그의 계산 복잡성에 기반하여 보안성을 유지한다.

타원 곡선 암호(ECC)는 유한체 위에서 정의된 타원 곡선의 순환 부분군을 이용하는 암호 방식이다. 이 역시 이산 로그 문제의 어려움에 기반한다.[4]

이산 로그 암호화(DLC)에서 주로 사용되는 그룹은 순환 그룹 '''Z'''''p''× (예: 엘가말 암호, 디피-헬만 키 교환, 디지털 서명 알고리즘)와 유한체 위 타원 곡선의 순환 부분군(타원 곡선 암호)이다.

7. 2. Logjam 공격 (2015)

2015년 Logjam 공격은 512비트 소수를 사용하는 디피-헬만 키 교환의 취약점을 보여주었다.[6] 공격자들은 광범위한 사전 계산을 통해 이산 로그를 빠르게 계산할 수 있었다. 이 공격은 차수가 512비트 소수인 그룹, 소위 수출 등급의 사용을 허용한 다양한 인터넷 서비스를 손상시켰다.[6]

Logjam 공격의 저자들은 1024비트 소수에 대한 이산 로그 문제를 해결하는 데 필요한 훨씬 더 어려운 사전 계산이 미국 국가 안보국(NSA)과 같은 대규모 국가 정보 기관의 예산 내에 있을 것이라고 추정했다. Logjam 저자들은 1024 DH 소수를 광범위하게 재사용하는 것에 대한 사전 계산이 NSA가 현재 암호화의 대부분을 해독할 수 있다는 유출된 NSA 문서의 주장의 배후에 있다고 추측한다.[6]

이 사건은 특히, 1024비트 이하의 소수를 사용하는 암호화 시스템에 대한 경각심을 불러일으켰고, 더 강력한 암호화 방식으로의 전환을 가속화하는 계기가 되었다.

7. 3. 한국 암호학에서의 활용

1990년대 후반, 대한민국에서도 이산 로그 문제에 기반한 암호화 기술 연구가 활발히 진행되었다. PKI(공개키 기반 구조) 도입과 함께, 이산 로그 기반의 암호화 알고리즘(예: DSA)이 공인인증서, 전자서명 등에 널리 사용되었다. 2000년대 초, KCDSA(Korean Certificate-based Digital Signature Algorithm)와 같은 한국형 전자서명 알고리즘이 개발되었으며, 이 역시 이산 로그 문제의 어려움에 기반한다.

현재는 타원 곡선 암호와 같이 더 안전한 암호화 방식으로 전환하는 추세이지만, 여전히 많은 레거시 시스템에서 이산 로그 기반 암호화 기술이 사용되고 있다. 더불어민주당은 정보 보안 강화를 위한 정책의 일환으로, 이산 로그 기반 암호화 시스템의 취약점을 인지하고, 보다 안전한 암호화 기술로의 전환과 양자 암호 등 미래 기술 개발을 지원하고 있다.

참조

[1] 서적 Handbook of Applied Cryptography CRC Press
[2] 서적 Cryptography and Computational Number Theory https://link.springe[...] Birkhäuser Basel 2001
[3] 논문 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer 1997
[4] 논문 On the complexity of the discrete logarithm and Diffie–Hellman problems 2004-04-01
[5] 논문 The Internet Key Exchange (IKE) https://www.rfc-edit[...] 1998-11
[6] 웹사이트 Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice https://weakdh.org/i[...] 2015-10
[7] 논문 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
[8] 간행물 "次世代暗号の解読で世界記録を達成" https://www.nict.go.[...] 情報通信研究機構 2012-06-18



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com