이산로그 편집하기
최신판 | 당신의 편집 | ||
22번째 줄: | 22번째 줄: | ||
이산대수 문제(Discrete Logarithm Problem, DLP)는 군(group)을 이용한다. 일반적으로 차수가 <math>t</math>인 집합 <math>G</math>의 원소 <math>g</math>와 집합 <math>G</math>의 다른 원소가 주어졌을 때 <math>x</math>를 구하는 것은 어려우며 이를 이산대수 문제(DLP: Discrete Logarithm Problem)라 한다. 여기서 <math>0 \le x \le t-1</math>이다. <math>y</math>는 <math>g</math>를 <math>x</math>번 곱한 결과이다. 원소 <math>g</math>는 전형적으로 <math>G</math>의 모든 원소들을 생성하거나 또는 적어도 <math>0</math>에서 <math>t-1</math>사이의 모든 정수들을 가지고 누승함으로서(즉, 반복적으로 그룹 연산을 함으로서)큰 부분집합을 생성할 수 있다. 원소 <math>g</math>가 군 내의 모든 원소들을 생성할 수 있다면 원소 <math>g</math>를 생성자(generator)라고 한다. 유한체의 이산대수문제는 유한체의 곱셈군에 대한 이산대수문제이다. 소인수분해 문제와 마찬가지로 이산대수 문제는 일방향 함수의 어려운 문제라 여겨지고 있다. 이러한 이유로 이산대수 문제는 [[엘가말]](ElGamal) 시스템과 DSS를 포함한 여러 공개키 암호 시스템들의 기초를 이루어 왔다. 이들 시스템들의 안전성은 이산대수를 계산하기가 어렵다는 가정에 의존하고 있다. 이산대수 문제는 유한체(finite fields)상에서 보다 임의의 군(group)상에서 훨씬 어려운 듯하다. 즉, 이것은 [[타원 곡선]](elliptic curve)군에 기초한 암호 시스템의 동기 부여이다.<ref>Fist1stPark, 〈[https://fistpark.tistory.com/entry/%EC%9C%A0%ED%95%9C%EC%B2%B4%EC%9D%98-%EC%9D%B4%EC%82%B0%EB%8C%80%EC%88%98 유한체의 이산대수]〉, 《티스토리》, 2009-04-03</ref> | 이산대수 문제(Discrete Logarithm Problem, DLP)는 군(group)을 이용한다. 일반적으로 차수가 <math>t</math>인 집합 <math>G</math>의 원소 <math>g</math>와 집합 <math>G</math>의 다른 원소가 주어졌을 때 <math>x</math>를 구하는 것은 어려우며 이를 이산대수 문제(DLP: Discrete Logarithm Problem)라 한다. 여기서 <math>0 \le x \le t-1</math>이다. <math>y</math>는 <math>g</math>를 <math>x</math>번 곱한 결과이다. 원소 <math>g</math>는 전형적으로 <math>G</math>의 모든 원소들을 생성하거나 또는 적어도 <math>0</math>에서 <math>t-1</math>사이의 모든 정수들을 가지고 누승함으로서(즉, 반복적으로 그룹 연산을 함으로서)큰 부분집합을 생성할 수 있다. 원소 <math>g</math>가 군 내의 모든 원소들을 생성할 수 있다면 원소 <math>g</math>를 생성자(generator)라고 한다. 유한체의 이산대수문제는 유한체의 곱셈군에 대한 이산대수문제이다. 소인수분해 문제와 마찬가지로 이산대수 문제는 일방향 함수의 어려운 문제라 여겨지고 있다. 이러한 이유로 이산대수 문제는 [[엘가말]](ElGamal) 시스템과 DSS를 포함한 여러 공개키 암호 시스템들의 기초를 이루어 왔다. 이들 시스템들의 안전성은 이산대수를 계산하기가 어렵다는 가정에 의존하고 있다. 이산대수 문제는 유한체(finite fields)상에서 보다 임의의 군(group)상에서 훨씬 어려운 듯하다. 즉, 이것은 [[타원 곡선]](elliptic curve)군에 기초한 암호 시스템의 동기 부여이다.<ref>Fist1stPark, 〈[https://fistpark.tistory.com/entry/%EC%9C%A0%ED%95%9C%EC%B2%B4%EC%9D%98-%EC%9D%B4%EC%82%B0%EB%8C%80%EC%88%98 유한체의 이산대수]〉, 《티스토리》, 2009-04-03</ref> | ||
− | == | + | == 풀이법 == |
* '''전수조사''' | * '''전수조사''' | ||
이 방법은 가장 떠올리기 쉽고 간단한 풀이법이다. 바로 <math> x \ </math>에 0부터 <math> p \ - \ 1 </math>까지 차례로 넣어보며 <math> a^{x} \ = \ b </math>를 만족하는 <math> x \ </math>를 찾는 것 이다. 아쉽게도 이 방식은 최악의 경우 <math> p \ </math>번의 곱셈이, 평균적으로는 <math> p \ / \ 2 </math>번의 곱셈이 필요하기 때문에 <math> p \ </math>가 1024 bit 혹은 2048 bit인 보통의 경우에서는 현실적인 시간 내에 풀이가 불가능하다. | 이 방법은 가장 떠올리기 쉽고 간단한 풀이법이다. 바로 <math> x \ </math>에 0부터 <math> p \ - \ 1 </math>까지 차례로 넣어보며 <math> a^{x} \ = \ b </math>를 만족하는 <math> x \ </math>를 찾는 것 이다. 아쉽게도 이 방식은 최악의 경우 <math> p \ </math>번의 곱셈이, 평균적으로는 <math> p \ / \ 2 </math>번의 곱셈이 필요하기 때문에 <math> p \ </math>가 1024 bit 혹은 2048 bit인 보통의 경우에서는 현실적인 시간 내에 풀이가 불가능하다. |