Задача такова: нужно сеарилозвать массив экземпляров класса в файл и при чтении быть уверенным, что каждый объект записался успешно. Для этого с каждым объектом планируется писать в файл его чексумму чтобы потом при чтении объекта из файла понять корректно ли он был записан туда. Сначала в файл пишется чексумма, потом объект и так для каждого объекта.
Планировалось сначала использовать CRC32 алгоритм для вычисления чек-суммы, но мнения разделились ибо он может быть ненадежным для больших объектов. Я в этом всем шифровании не ас, поэтому решил спросить у общественности тут какой алгоритм для вычисления чексуммы (и вообще для этой задачи) подходит лучше с точки зрения производительности.
Заранее спасибо
25.11.13 16:44: Перенесено модератором из 'C/C++' — Кодт
Здравствуйте, vit0s, Вы писали:
V>может быть ненадежным
а что понимается под надежностью (со стороны вашей команды)? и зачем вам "надежность" в вашей задаче?
если вас интересует скорость то я бы предложил простой вариант с суммой всех байтов по модулю 256, этой чексуммой пользуются в FIX протоколе, например (CRC8)
если для вас это "ненадежно", то можно предложить crc16, crc32, md5, sha1
важно понимать, что любая чексумма всегда ограничена по кол-ву значений (4 байта или 64 байта), а этой значит, что найдутся два набора байтов (возможно, очень длинных), отличающиеся одним битом, для которых чексумма совпадает.
так что либо пробуем формализовать какую надежность вы имеете в виду. либо просто используем что-то общепринятое и для которых "своя надежность" была достигнута
Здравствуйте, vit0s, Вы писали:
V>Всем привет,
V>Задача такова: нужно сеарилозвать массив экземпляров класса в файл и при чтении быть уверенным, что каждый объект записался успешно. Для этого с каждым объектом планируется писать в файл его чексумму чтобы потом при чтении объекта из файла понять корректно ли он был записан туда. Сначала в файл пишется чексумма, потом объект и так для каждого объекта. V>Планировалось сначала использовать CRC32 алгоритм для вычисления чек-суммы, но мнения разделились ибо он может быть ненадежным для больших объектов. Я в этом всем шифровании не ас, поэтому решил спросить у общественности тут какой алгоритм для вычисления чексуммы (и вообще для этой задачи) подходит лучше с точки зрения производительности.
V>Заранее спасибо
небезопасные или устаревшие алгоритмы для обратной совместимости и исторического значения:
MD2, MD4, MD5, Panama Hash, DES, ARC4, SEAL 3.0, WAKE-OFB, DESX (DES-XEX3), RC2, SAFER, 3-WAY, GOST, SHARK, CAST-128, Square
характеристики:
1. безопасность
2. скорость
3. применимость
К примеру, tiger tree hashing в некоторых p2p сетях (DC++) для идентификации именно одного файла. В торрентах используют SHA-1, хотя он теоретически небезопасен. Чем выше буква у SHA (1,2,3), тем алгоритм считается безопасней.
Так же обращаю внимание на фразу:
Поддержка OpenMP была отключена, так что только одно ядро CPU было использовано для этого теста производительности.
Иными словами для увеличения производительности, если это допустимо, можно использовать:
1. параллельные вычисления в файле
2. вычисление за раз несколько файлов (для примера, пул потоков)
А теперь моё субъективное мнение, которое не основано на огромном опыте и многолетней работе в этой области, но говорит о том, как бы поступил именно я:
Tiger — использовал бы только тогда, когда нужна работа с этой сетью.
MD5 — ненадёжен, но быстр, опять же, если есть вероятность чужого зловредного вмешательства (кто-то ещё пользуется моей программой и хеш-суммами), то однозначно нет.
Алгоритм MD5 уязвим к некоторым атакам, например возможно создание двух сообщений с одинаковой хеш-суммой, поэтому его использование не рекомендуется в новых проектах.
В случае, если бы нужна была некая гарантированная надёжность, то я бы остановился на:
SHA-256 — если бы нужен был небольшой хеш
и
SHA-512 — если бы хотел хеш чуть побольше (и ещё дайте мне таблетки от жадности)
Хотя если речь идёт о неком массиве, и никто никогда не смотрит на мои хеши, тогда MD5 в принципе нормальное решение. При прочих равных условиях CRC32 по сравнению с ним вообще не вариант.
Здравствуйте, vit0s, Вы писали:
V>Всем привет,
V>Задача такова: нужно сеарилозвать массив экземпляров класса в файл и при чтении быть уверенным, что каждый объект записался успешно. Для этого с каждым объектом планируется писать в файл его чексумму чтобы потом при чтении объекта из файла понять корректно ли он был записан туда. Сначала в файл пишется чексумма, потом объект и так для каждого объекта. V>Планировалось сначала использовать CRC32 алгоритм для вычисления чек-суммы, но мнения разделились ибо он может быть ненадежным для больших объектов. Я в этом всем шифровании не ас, поэтому решил спросить у общественности тут какой алгоритм для вычисления чексуммы (и вообще для этой задачи) подходит лучше с точки зрения производительности.
V>Заранее спасибо
Git, например, использует в качестве хэшфункции SHA1 и ей хэшируется все — слепки данных, коммиты, и пр.
Здравствуйте, uzhas, Вы писали:
U>важно понимать, что любая чексумма всегда ограничена по кол-ву значений (4 байта или 64 байта), а этой значит, что найдутся два набора байтов (возможно, очень длинных), отличающиеся одним битом, для которых чексумма совпадает.
U>ссылки по теме: U>http://ru.wikipedia.org/wiki/SHA-1 U>http://en.wikipedia.org/wiki/Cyclic_redundancy_check
Техническая поправочка — если полином CRC имеет одним из множителей (x+1), то НИКАКИЕ две последовательности, отичающиеся на один бит (ну или даже на нечетное колчество бит) не будут иметь одинаковой CRC. Об этом даже написано в вики, правда не в первых абзацах и несколько другими словами
Здравствуйте, andyp, Вы писали:
A>Техническая поправочка — если полином CRC имеет одним из множителей (x+1), то НИКАКИЕ две последовательности, отичающиеся на один бит (ну или даже на нечетное колчество бит) не будут иметь одинаковой CRC. Об этом даже написано в вики, правда не в первых абзацах и несколько другими словами
не нашел цитату, но нашел ошибку в своих рассуждениях:
я же рассуждал так: пусть значения чексуммы принимает значения в диапазоне 0 <= checksum < M
рассмотрим все вектора v бит длиной M + 1, где ровно M нулей и одна единица.
набор чисел checksum(v) для всех таких векторов будет иметь дубликат, т.к. таких чисел ровно M + 1
возьмем те самые два вектора v1 и v2: checksum(v1) = checksum(v2)
они отличаются в двух позициях
верно ли тогда другое утверждение: любая checksum (с ограниченными значениями) не может застраховать от ошибки в данных в двух битах?
CRC — это хеш-функция. Для CRC32, например, имеем набор из 2^32 хеш-значений. Если рассматривать неограниченное количество M "входных" объектов, такое, что M сильно больше 2^32, то рано или поздно найдутся два различных объекта с одинаковой CRC.
Здравствуйте, Vlad_SP, Вы писали:
V_S>рано или поздно найдутся два различных объекта с одинаковой CRC.
согласен с этим высказыванием
я пытаюсь обосновать более сильное утверждение : найдутся достаточно похожие (расстояние Хэмминга = 2) объекты, для которых хеш будет одинаковый
Здравствуйте, uzhas, Вы писали:
U>Здравствуйте, andyp, Вы писали:
A>>Техническая поправочка — если полином CRC имеет одним из множителей (x+1), то НИКАКИЕ две последовательности, отичающиеся на один бит (ну или даже на нечетное колчество бит) не будут иметь одинаковой CRC. Об этом даже написано в вики, правда не в первых абзацах и несколько другими словами U>не нашел цитату, но нашел ошибку в своих рассуждениях: U>я же рассуждал так: пусть значения чексуммы принимает значения в диапазоне 0 <= checksum < M U>рассмотрим все вектора v бит длиной M + 1, где ровно M нулей и одна единица. U>набор чисел checksum(v) для всех таких векторов будет иметь дубликат, т.к. таких чисел ровно M + 1 U>возьмем те самые два вектора v1 и v2: checksum(v1) = checksum(v2) U>они отличаются в двух позициях
U>верно ли тогда другое утверждение: любая checksum (с ограниченными значениями) не может застраховать от ошибки в данных в двух битах?
Верно для блоков начиная с определенной длины. Если блок короче определеннной величины, то все 2-х битовые паттерны вылавливаются. Я тут пишу о правильно выбранных полиномах.
PS там начинает играть роль, сколько 0 между единицами в паттерне ошибки. Как правило, CRC может исправить 2-битные ошибки, отстоящие друг от друга на 2^N — 1 бит (тут N — меньше чем число бит в CRC, зависит от выбранного полинома, максимально для так называемых примитивных полиномов)
Здравствуйте, vit0s, Вы писали:
V>Задача такова: нужно сеарилозвать массив экземпляров класса в файл и при чтении быть уверенным, что каждый объект записался успешно. V>Планировалось сначала использовать CRC32 алгоритм для вычисления чек-суммы, но мнения разделились ибо он может быть ненадежным для больших объектов.
Если речь идет об обнаружении ошибок, возникающих при записи, то не вижу смысла в использовании криптографических хеш-функций: SHA, Whirpool, MD5 и т.д. Обычные CRCXX, как раз для этого предназначены. Недавно попалось на глаза, на претендующее на исчерпывающее, сравнение некриптографических хеш-функций и CRC32 показывает весьма неплохие результаты.
