Передавать файлы, используя только контрольные суммы?

Question

Можно ли было бы передавать большие файлы, используя только систему контрольных сумм, а затем восстанавливать исходный файл с помощью вычислений?

Скажите, что вы передаете контрольную сумму MD5 файла и размер файла. Создавая «виртуальный файл» и вычисляя его контрольную сумму, пробуя каждую битовую комбинацию, вы должны в конечном итоге «добраться» до исходного файла. Но по дороге вы также получите множество «коллизий», в которых контрольная сумма также совпадает.

Таким образом, мы меняем первый байт исходного файла на некоторое указанное значение, снова вычисляем контрольную сумму и отправляем это тоже. Если мы сделаем такую ​​же замену в виртуальном файле, мы сможем проверить каждое «столкновение», чтобы увидеть, совпадает ли оно по-прежнему. Это должно немного сузить его, и мы можем сделать это несколько раз.

Конечно, вычислительная мощность для этого была бы огромной. Но возможно ли это теоретически, и сколько контрольных сумм вам потребуется для передачи чего-либо (скажем, 1 МБ)? Или, может быть, объем данных, необходимых для передачи контрольных сумм почти такого же размера, как файл, делает его бессмысленным?

Answer 1

Объем данных, которые вам нужно передать, наверняка будет того же размера, что и файл.Подумайте: если вы могли бы передать n байтовый файл с n-1 байтами данных, это означает, что у вас есть 256^(n-1) возможных шаблонов данных, которые вы, возможно, отправили, но выбираете из пространства размером 256^n.Это означает, что один из каждых 256 файлов не может быть выражен с помощью этого метода - это часто называют принципом pidegonhole .

Теперь, даже если это не было проблемойнет никакой гарантии, что у вас не будет столкновения после любого заданного количества контрольных сумм.Алгоритмы контрольной суммы разработаны, чтобы избежать коллизий, но для большинства алгоритмов контрольной суммы / хеша нет веских доказательств того, что после хэширования X вы можете гарантировать отсутствие коллизий в N-байтовом пространстве.

Наконец, по крайней мереразработан так, чтобы его было трудно перевернуть, поэтому даже если бы это было возможно, потребовалось бы невероятное количество ресурсов процессора, чтобы сделать это.

Тем не менее, для подобного подхода вы могли бы бытьзаинтересован в чтении кодов прямого исправления ошибок - они вовсе не являются алгоритмами хеширования, но я думаю, что вы можете найти их интересными.

Answer 2

Я думаю, что то, о чем вы думаете, на самом деле интересная тема, но вы не нашли правильный метод. Если я могу попытаться перефразировать ваш вопрос, вы спрашиваете, есть ли способ применить функцию к некоторым данным, передать результат функции, а затем восстановить исходные данные из более краткого результата функции. Для одной контрольной суммы MD5 ответ - нет, но с другими функциями, если вы готовы отправить несколько результатов функции, это возможно. В целом эта область исследований называется сжатым зондированием . Иногда возможна точная реконструкция, но чаще она используется в качестве схемы сжатия с потерями для изображений и других визуальных или звуковых данных.

Answer 3

Короче говоря "нет".

Чтобы взять гипотетический пример, рассмотрим фотографию с 24 пикселями в секунду с 6 пикселями - существует 2 ^ (24 * 6) (2 ^ 144) возможных комбинаций интенсивностей длякаждый цветовой канал на этих шести пикселях, так что вы можете гарантировать, что если вы оцените каждую возможность, вам гарантировано коллизия MD5 (поскольку MD5 - это 128-битное число).

Answer 4

Краткий ответ: не в какой-либо значимой форме.

Длинный ответ:

Предположим, произвольный файл file.bin размером 1000 байт.Существует 2^(8*1000) различных комбинаций, которые могут быть его фактическим содержанием.Посылая, например, 1000-битную контрольную сумму, вы по-прежнему имеете около 2^(7*1000) альтернативных коллизий.

Отправляя один дополнительный бит, вы можете сократить их вдвое ... и у вас все еще будет 2^6999 столкновения.К тому времени, когда вы устраните коллизии, вы отправите по крайней мере 8000 битов, т.е. сумму, равную или превышающую размер файла.

Единственный способ сделать это теоретически возможным (Примечание: я не сказал "выполнимый, не говоря уже о практическом, был бы, если бы файл не содержал случайных данных, и вы могли бы использовать эти знания для сокращения альтернатив.В таком случае вам лучше использовать сжатие.Алгоритмы сжатия с учетом содержимого (например, FLAC для аудио) используют априорные знания о свойствах входных данных для улучшения степени сжатия.

Answer 5

То, что у вас есть, это проблема информации.Контрольная сумма не обязательно уникальна для конкретного набора данных, фактически она должна быть такова, что в качестве источника ей потребуется много битов информации.Это может означать, что полученные данные не являются точными данными, из которых была сгенерирована контрольная сумма, но в большинстве случаев это не может доказать.