큰 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%를 조금 상회할 것이다. Birthday Attack은 항상 정확한 해답을 얻지 못한다는 것을 염두에 두어야 한다. 즉, 이 알고리즘은 답을 구할 수도 있고, 그렇지 못할 수도 있다. Baby Step, Giant Step 방법은 시간은 걸리지만 확실히 답을 얻을 수 있는 결정적 알고리즘인 반면, Birthday Attack은 언제나 답을 얻을 수 있다는 보장이 없다.
여기서 한가지 더, 나머지 연산에 대한 곱셈의 역은 무엇인가? 즉, 임의로 선택되는 l의 경우, α^(-l)은 어떻게 구하는가? 일반적으로, 3^(-1) (mod 7)이라고 하면, 3 * x ≡ 1 (mod 7)에서 x를 구하는 것과 같은 문제이다. 그렇다면, 3^(-2) (mod 7)의 경우는 어떤가? 같은 방법으로 생각한다면, 3 * x ≡ 2 (mod 7)을 의미한다고 할 수 있다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptography with Coding Theory, Second Edition, PEARSON Education
먼저, 일반적인 Birthday Attakc의 경우와 마찬가지로, root(p) 길이를 가지는 두 목록을 만든다.
1. 첫 번째 목록은, 임의로 선택되는 k 값에 대한, α^k (mod p)
2. 두 번째 목록은, 임의로 선택되는 l 값에 대한, βα^(-l) (mod p)
두 목록이 구해졌다면, 계산 결과가 일치하는 값을 찾는다. α^k ≡ βα^l이라면, α^(k + l) ≡ β이고, 구하고자 하는 x 값을 알 수 있다. 이 확률은 50%를 조금 상회할 것이다. Birthday Attack은 항상 정확한 해답을 얻지 못한다는 것을 염두에 두어야 한다. 즉, 이 알고리즘은 답을 구할 수도 있고, 그렇지 못할 수도 있다. Baby Step, Giant Step 방법은 시간은 걸리지만 확실히 답을 얻을 수 있는 결정적 알고리즘인 반면, Birthday Attack은 언제나 답을 얻을 수 있다는 보장이 없다.
여기서 한가지 더, 나머지 연산에 대한 곱셈의 역은 무엇인가? 즉, 임의로 선택되는 l의 경우, α^(-l)은 어떻게 구하는가? 일반적으로, 3^(-1) (mod 7)이라고 하면, 3 * x ≡ 1 (mod 7)에서 x를 구하는 것과 같은 문제이다. 그렇다면, 3^(-2) (mod 7)의 경우는 어떤가? 같은 방법으로 생각한다면, 3 * x ≡ 2 (mod 7)을 의미한다고 할 수 있다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptography with Coding Theory, Second Edition, PEARSON Education