Каковы возможности, что два сообщения имеют тот же обзор MD5 и тот же обзор SHA1?
Адрес электронной почты не должен превышать 254 символы.
Это было принято IETF после отправленная опечатка . Полный диагноз любого данного адреса доступен онлайн . Исходная версия RFC 3696 описала 320 как максимальную длину, но John Klensin впоследствии принял неправильное значение, так как Путь определяется как
Path = "<" [ A-d-l ":" ] Mailbox ">"
, Таким образом, элемент Почтового ящика (т.е. адрес электронной почты) имеет угловые скобки вокруг этого для формирования Пути, который максимальная длина 254 символов ограничить Длину пути до 256 символов или меньше.
максимальная длина указала в состояния RFC 5321 :
максимальная общая длина обратного пути или передавать-пути является 256 символами.
RFC 3696 был исправлен здесь .
Люди должны знать эти опечатки против RFC 3696 в частности. Тремя из канонических примеров являются на самом деле недопустимые адреса.
я сопоставил пару сотни тестовых адресов, которые можно найти в http://www.dominicsayers.com/isemail
4 ответа
Предполагая равномерное распространение в диапазоне хэшей MD5 и SHA-1 для случайных строк (что не так), и предполагая, что мы говорим только о двух строках и не говорим о пул строк (поэтому мы избегаем сложностей типа парадокса дня рождения):
Хэш MD5 имеет ширину 128 бит, а SHA-1 - 160. С приведенными выше предположениями две строки A и B имеют вероятность столкновения P, если оба хэша сталкиваются. Итак
P(both collide) = P(MD5 collides) * P(SHA-1 collides)
И
P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)
Итак
P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87
Опять же, если у вас есть пул строк и вы пытаетесь определить вероятности столкновений с пулом, вы находитесь в области парадокса дня рождения , и эта вероятность, которую я здесь рассчитал, неприменима. Это и хеши не так единообразны, как должны быть. На самом деле у вас будет гораздо более высокая частота столкновений, но он все равно будет крошечным.
EDIT
Поскольку вы имеете дело с ситуацией парадокса дня рождения, примените ту же логику, что и решение парадокса дня рождения. Давайте посмотрим на это с точки зрения только одной хеш-функции:
N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)
Давайте представим, что у нас есть хорошее четное количество хешей, например 2 ^ 29 (примерно 530 миллионов).
P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)
Короче говоря, я даже не хочу подумать о вычислении этого числа. Я даже не знаю, как вы можете это оценить. Вам, по крайней мере, понадобится калькулятор произвольной точности, который может обрабатывать огромные факториалы, не умирая.
Обратите внимание, что вероятности будут следовать кривой, которая начинается почти с 0, когда N = 1 или 2 , и это достигнет 1, когда N> = 2 ^ 288 , что похоже на форму на странице Википедии для парадокса дня рождения.
Парадокс дня рождения достигает P = 0,5 , когда N = 23 . Другими словами, вероятность столкновения составляет 50%, когда N равно 6% от S. Если это масштабируется (я не уверен, что это так), это означает, что вероятность столкновения будет 50%, когда у вас 6% от 2 ^ 288 хешей. 6% от 2 ^ 288 составляет около 2 ^ 284. Ваше значение N (несколько сотен миллионов) и близко не стоит. Это практически несущественно по сравнению с вашим S, поэтому я не думаю, что вам есть о чем беспокоиться. Столкновения маловероятны.
Если размер сообщения не ограничен, вероятность асимптотически приближается к 100%, так как существует бесконечное число возможных сообщений и конечное число возможных хэшей.
(примечание: редактирование вопроса делает сейчас это менее актуально)
Обычно, когда один выбирает N элементов случайным образом, легче вычислить ожидаемое количество столкновений, чем вероятность столкновения. Поскольку ожидаемое количество столкновений не может быть меньше вероятности столкновения, его часто можно использовать в качестве подходящей верхней границы.
Предположим, что p - это вероятность столкновения двух случайно выбранных элементов. Если мы выберем N случайных элементов, то будет N * (N-1) / 2 пары элементов, и, следовательно, ожидаемое количество столкновений будет
p * N * (N-1) / 2.
Например, если мы предполагаем, что вероятность коллизии как для MD5, так и для SHA1 равна p = 2 -288 , тогда даже после случайного выбора 2 100 элементов мы все равно ожидаем только около 2 -89 коллизии.
Другой пример: если мы выберем 2 30 случайных элементов и вычислим только MD5. Предполагая, что коллизия между двумя хешами MD5 равна p = 2 -128 , это дает ожидаемое число 2 -59 для количества коллизий. Следовательно, даже вероятность того, что хеш-код MD5 столкнется для двух входов, уже очень мала.
добавление к сообщению Велбога:
Отношения больших факториалов могут быть вычислены без использования арифметики произвольной точности, используя приближение Стирлинга :
n! ≈ sqrt (2πn) * (n / e) n
Итак (S!) / (S ^ N * (S - N)!) ≈ sqrt (2πS) / sqrt (2π (SN)) * (S / e) S / ((SN) / e) SN / S N
= sqrt (S / (SN)) * (S / ( SN)) SN * e -N
= sqrt (1 + α) * (1 + α) SN * e -N где α = N / (SN) мало.
Приближение (1 + a / n) nx ≈ e ax выполняется при n → ∞ (или, по крайней мере, становится очень large)
** так что это означает (1+ (N / (SN))) SN ≈ e N для SN >> N.
Поэтому я ожидал что
(S!) / (S ^ N * (S - N)! ) ≈ sqrt (1 + N / (SN)) * e N * e -N = sqrt (1 + N / (SN)) для SN >> N ... .
за исключением того, что это больше 1 ... поэтому одно из приближений недостаточно хорошее. : p
(** предостережение: значение N / S должно быть маленьким: для N = 22, S = 365 это отклонение в 2 раза)