Я хотел бы создать базу данных, содержащую контрольные суммы большого количества файлов, и я боюсь за контрольную сумму-колликации (два разных файла с одной и той же контрольной суммой).обновляемый алгоритм дайджест/контрольная сумма
Вопрос 1: какова вероятность того, что два разных файла будут иметь одну и ту же сумму MD5?
В качестве обходного решения я подумал об использовании увеличивающейся контрольной суммы. Начните с небольшой контрольной суммы и, в случае столкновения, вычислите большую контрольную сумму, которая может быть выведена на меньшую контрольную сумму, поэтому мне не нужно пересчитывать контрольные суммы всех моих файлов уже в базе данных ... Я все еще хочу быть способный искать контрольные суммы меньшего размера.
Вопрос 2: какой алгоритм контрольной суммы/дайджеста мог бы сделать этот трюк? Мне нужен алгоритм контрольной суммы, который может вычислять значение определенного размера и «обратно» совместимого (меньшего размера). То есть. file1 имеет 2 байтовую контрольную сумму 0x1234 и контрольную сумму 4 байта 0x12345678, 2-байтная контрольная сумма может быть получена из 4-байтовой контрольной суммы.
Спасибо за ваш обширный ответ, но я не уверен, что он полностью отвечает на мой вопрос. Вы уверены в шансе .5 с файлами 2^64 даже с «парадоксальным днем рождения»? Какова вероятность дублирования с SHA-256? – meeuw
@meeuw: Это не точно 0,5 для 2^64, но есть несколько файлов где-то около порядка 2^64, для которых оно равно 0,5. Поскольку SHA-256 - это 256-битный хеш, вам понадобится что-то в порядке 2^128 файлов с равномерно распределенными хэшами, прежде чем вы получите 0.5 шанса хотя бы на одно столкновение. –