Клиент, К
Сервер, С
1. Для одного Y вероятность того, что H (X) = H (Y), равна 1/n.
2. Соответственно, вероятность того, что H(X)
3. Если создать k значений, то вероятность того, что ни для одного из них не будет совпадений, равна произведению вероятностей, соответствующих одному значению, т.е. (1 - 1/n)k.
Следовательно, вероятность, по крайней мере, одного совпадения равна 1 - (1 - 1/n)k.
По формуле бинома Ньютона (1 - a)k = 1 - ka + (k(k-1)/2!)a2 - ... ≈ 1 – ka.
Т.е. 1 - (1 - k/n) = k/n = 0,5,
откуда k = n/2.
Для m-битового хэш-кода достаточно выбрать 2m-1 сообщений, чтобы вероятность совпадения хэш-кодов была больше 0,5.
H(Y), равна 1 - 1/n.
Стратегия криптоанализа хэш -функции
Вероятность того, что есть дубли, соответственно равна:
1 - n!/(n-k)!nk.
P(n, k) = 1 - n! / ((n-k)! × nk) =
1 - (n × (n-1) × … × (n-k-1)) / nk =
1 - [ (n-1)/n × (n-2)/n × … × (n-k+1)/n] =
1 - [(1- 1/n) × (1 - 2/n) × … × (1 - (k-1)/n)].
Известно, что 1 - x ≤ e - x
т.е.
По условию задачи
P(n, k) > 1 - [e-1/n × e-2/n × … × e-k/n],
P(n, k) > 1 - e-k(k-1)/n.
Следовательно,
и
2 = ek(k-1)/n.
1/2 = 1 - e-k(k-1)/n,
Отсюда
ln 2 = k (k-1) / 2n
и k (k-1) ≈ k2.
Окончательно имеем k = (2n × ln 2)1/2 = 1,17 n1/2 ≈ n1/2.
Таким образом, если хэш-код имеет длину m бит, т.е. принимает 2m значений,
то k = √2m = 2m/2. "Парадокс дня рождения" - для того, чтобы вероятность совпадения дней рождения у двух человек была больше 0,5, в группе должно быть всего 23 человека.
Достарыңызбен бөлісу: |
