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%를 조금 상회할 것이..
더보기
Birthday Attack, Birthday Paradox
만약, 한 방에서 같은 생일을 가진 사람이 존재할 확률이 50% 이상이 되려면, 몇 명의 사람이 있어야 할까? 그 답은 놀랍게도 23명이면 충분하다. 윤년을 생각하지 않더라도 1년이 365일이므로, 23명이란 표본의 수는 일반적으로 생각되는 것보다 훨씬 적은 수이다. 이것을 생일 파라독스(Birthday Paradox)라고 한다. 먼저, 이 사람들이 모두 다른 생일을 가지고 있을 확률을 알아보면, 첫 번째 사람은 365일 중 어떤 날을 선택할 수 있다. 두 번째 사람은 첫 번째 사람과 다른 날을 선택해야 하며, 이 확률은 (1 - 1 / 365)이다. 세 번째 사람은, 365일에서 선택할 수 있는 날이 2개 줄었으며, 따라서 (1 - 2 / 365)이다. 이와 같이 23명까지 전개해보면, 1 * (1 -..
더보기