Вычисление «основанной» контрольной суммы данных.(SHA1 / 2 и т. Д.) - PullRequest
Новая
       35

Вычисление «основанной» контрольной суммы данных.(SHA1 / 2 и т. Д.)

1 голос
/ 04 января 2011

Я не уверен, как именно это задать, но вот на что я надеюсь, учитывая структуру, которая может содержать ключи 5+n (таким образом, для моей системы есть 5 ключей, дополнительные ключи не обязательны) - Мне нужен механизм хеширования, который может определить, что хеш-ключ 6 с идентичными 5 ключами является расширенным набором структуры ключа 5 и предлагает дополнительную информацию. В частности, механизм хеширования, поскольку существуют ограничения, которые не позволяют отправлять полную структуру по проводам при каждом запросе.

Для пояснения, вот некоторая информация (для примера требуется 2+n ключей): 

---
  name: codebeaker
  occupation: developer

Хешируется с SHA-512, а -256 выглядит так: 

SHA-512
04fe500f2b3e779aba9ecb171224a04d35cc8453eb1521c7e31fd48b56b1cce9
b1e8af775e177e110982bfb16a6ca8652d7d9812ab8a8c316015dc9d6b3b54f7

SHA-256
4833be7086726e7ffd82db206f94f0a4f9fdf7fba00692f626157afed4587c74

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

---
  name: codebeaker
  occupation: developer
  telephone: 49 (0) 123 45 67

Однако неудивительно, что в MD5, SHA-n и любой другой хэш-функции, которую я изучал, нет способа сделать это, например: 

SHA-512
2fe2c1f01e39506010ea104581b737f95db6b6f71b1497788afc80a4abe26ab0
fc4913054278af69a89c152406579b7b00c3d4eb881982393a1ace83aeb7b6a2

SHA-256
77c2942e9095e55e13c548e5ef1f874396bfb64f7653e4794d6d91d0d3a168e2

(очевидно) сходства нет ...

В нашем случае использования эти данные, отформатированные как структура, передаются в нашу систему третьей стороной. Обработка данных очень дорогая, 2-3 секунды на операцию, мы можем получить около 50% этого времени назад, если мы знаем, что у нас есть результат предыдущего запуска, однако алгоритмы разности текста Байеса и Левенштейна не здесь подходит, так как мы часто видим пары ключ / значение, которые являются аббревиатурами, и другой текст, который может показаться похожим, когда он совершенно не связан.

Нам нужен способ проверки данных контрольной суммы (я мог бы здесь сместить мой ответ), чтобы мы могли определить, что B - это расширенный набор A, если он содержит все те же ключи и те же данные , Однако часто в записях ключа / значения в нашем struc содержится так много данных, что отправка их по проводам каждый раз, только чтобы определить, что мы уже видели более полную копию, была бы дорогой и расточительной.

Ответы [ 2 ]

0 голосов
/ 04 января 2011

Криптографические хеши специально разработаны с такими свойствами:

  • Они являются односторонними функциями.Практически невозможно пересчитать конкретный вход для данного значения хеш-функции или даже любой случайный вход, который хэширует до этого значения.
  • Хотя должны быть коллизии, потому что размер входного файла намного больше фиксированного выходного размера,также практически невозможно найти два разных входных значения, которые приводят к одному и тому же хеш-значению.
  • Точно одинаковое входное значение всегда хэшируется к одному и тому же хеш-значению.
  • Любое небольшое изменение ввходные результаты в совершенно другом значении хэша.Отражение любого отдельного входного бита изменяет в среднем 50 процентов выходных битов.

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

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

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

Помимо этого, криптографические хеши могут быть не подходящим инструментом для работы.

[Редактировать]

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

0 голосов
/ 04 января 2011

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

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

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

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

...