Brirthday Attack on Discrete Logarithm
큰 Prime Number p의 경우, Lα(β)의 경우를 생각해보자. 즉, β ≡ α^x (mod p)에서 x를 구하자는 것인데, 이것은 discrete logarithm 문제를 해결하는 데 Birthday Attack을 적용해본다는 의미이다. 먼저, 일반적인 Birthday Attakc의 경우와 마찬가지로, root(p) 길이를 가지는 두 목록을 만든다. 1. 첫 번째 목록은, 임의로 선택되는 k 값에 대한, α^k (mod p) 2. 두 번째 목록은, 임의로 선택되는 l 값에 대한, βα^(-l) (mod p) 두 목록이 구해졌다면, 계산 결과가 일치하는 값을 찾는다. α^k ≡ βα^l이라면, α^(k + l) ≡ β이고, 구하고자 하는 x 값을 알 수 있다. 이 확률은 50%를 조금 상회할 것이..
더보기
Computing Discrete Logarithm
discrete logarithm 문제를 효율적으로 해결하는 방법은 알려져 있지 않지만, 간단한 수로 이루어져 있을 경우 쉽게 계산할 수 있다. β ≡ α^x (mod p)가 주어졌다고 하고, x를 구한다고 하자. 먼저, 오일러의 정리를 적용하면, p는 Prime Number이므로, α^(p - 1) ≡ 1 (mod p)이다. 여기서, α^((p - 1) / 2)^2 ≡ ±1 (mod p) 위와 같은 형태를 얻어낼 수 있으며, discrete logarithm의 정의를 살펴보면 p - 1이 α^(p - 1) ≡ 1 (mod p)를 만족하는 가장 적은 지수여야 하기 때문에, α^((p - 1) / 2) ≡ -1 (mod p)가 된다. 이제, β ≡ α^x (mod p)를 알아보면, β^((p - 1) / ..
더보기
Discrete Logarithm
어떤 Primve Number p가 있고, 0이 아닌 정수 α, β가 존재한다고 했을 때, β ≡ α^x (mod p) 여기서, x를 구하는 것을 discrete logarithm 문제라고 한다. 여기서, α^n ≡ 1 (mod p)라고 했을 때, n이 이것을 만족하는 가장 작은 양의 정수라면, 0 ≤ x ＜ n이며, 여기서 x = Lα(β) 이것을 α를 밑으로 가지는 β의 discrete logarithm이라 한다. 자주, α는 모든 β의 α^n (mod p)의 형태로 나타나는 Primitive Root (mod p)에서 선택된다. discrete logarithm 문제는 일반적으로 해결하기가 매우 어렵다고 알려져 있다. 여기서 어렵다는 말은, discrete logarithm 문제를 효율적으로 계산할..
더보기