Хеширование Пирсона - Pearson hashing

Хеширование Пирсона это хэш-функция разработан для быстрого выполнения на процессорах с 8-битным регистры. Учитывая, что вход состоит из любого количества байтов, на выходе получается один байт, который сильно зависит от каждого байта входа. Для его реализации требуется всего несколько инструкций плюс 256-байтовый Справочная таблица содержащий перестановка значений от 0 до 255.[1]

Эта хеш-функция является CBC-MAC который использует 8-битный подстановочный шифр реализуется через таблица замены. 8-битный шифр имеет незначительную криптографическую безопасность, поэтому хеш-функция Пирсона не криптографически сильный, но это полезно для реализации хеш-таблицы или как код проверки целостности данных, для чего он предлагает следующие преимущества:

  • Это очень просто.
  • Он быстро выполняется на процессорах с ограниченными ресурсами.
  • Не существует простого класса входов, для которого столкновения (идентичные выходы) особенно вероятны.
  • Учитывая небольшой привилегированный набор входных данных (например, зарезервированные слова для компилятор ), таблицу перестановок можно настроить так, чтобы эти входные данные давали разные хеш-значения, создавая то, что называется идеальная хеш-функция.
  • Две входные строки, отличающиеся ровно на один символ, никогда не сталкиваются.[2] Например, применение алгоритма к строкам ABC и AEC никогда не даст одно и то же значение.

Один из его недостатков по сравнению с другими алгоритмами хеширования, предназначенными для 8-битные процессоры предлагаемая таблица поиска на 256 байт, которая может быть слишком большой для небольшого микроконтроллер с размером программной памяти порядка сотен байт. Обходной путь - использовать простую функцию перестановки вместо таблицы, хранящейся в памяти программы. Однако с помощью слишком простой функции, например Т [я] = 255-я, частично снижает удобство использования в качестве хэш-функции, поскольку анаграммы приведет к тому же хеш-значению; С другой стороны, использование слишком сложной функции отрицательно скажется на скорости. Использование функции вместо таблицы также позволяет увеличить размер блока. Такие функции, естественно, должны быть биективный, как и их варианты таблиц.

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

алгоритм хеширование Пирсона является    ч: = 0 для каждого c в C петля        ч: = Т [ч xor c] конец цикла    вернуть час

Хеш-переменная (час) может быть инициализирован по-разному, например к длине данных (C) по модулю 256; этот конкретный выбор используется в примере реализации Python ниже.

Примеры реализации

Python, 8-битный вывод

Параметр 'table' требует псевдослучайно перемешанного списка диапазона [0..255]. Это можно легко сгенерировать с помощью встроенного в python ассортимент функция и использование random.shuffle чтобы переставить его:

 1 от случайный импорт тасовать 2  3 example_table = список(ассортимент(0, 256)) 4 тасовать(example_table) 5  6 def hash8(сообщение: ул, Таблица) -> int: 7     "" "Хеширование Пирсона" "" 8     хэш = len(сообщение) % 256 9     для я в сообщение:10         хэш = Таблица[хэш ^ ord(я)]11     вернуть хэш

C, 64-бит

 1 #включают <stdint.h> 2 статический const беззнаковый char Т[256] = { 3     // TODO: добавить 0–255 в произвольном (случайном) порядке 4 }; 5  6 uint64_t Пирсон64(const беззнаковый char *Икс, size_t len) { 7   size_t я; 8   size_t j; 9   беззнаковый char час;10   uint64_t Retval;11 12   для (j = 0; j < размер(Retval); ++j) {13     // Изменяем первый байт14     час = Т[(Икс[0] + j) % 256];15     для (я = 1; я < len; ++я) {16       час = Т[час ^ Икс[я]];17     }18     Retval = ((Retval << 8) | час);19   }20 21   вернуть Retval;22 }

Схема, использованная выше, представляет собой очень простую реализацию алгоритма с простым расширением для генерации хэша длиной более 8 бит. Это расширение включает внешний цикл (то есть все строки операторов, которые включают переменную j).

Для данной строки или блока данных исходный алгоритм Пирсона производит только 8-битный байт или целое число, 0–255. Однако алгоритм позволяет очень легко сгенерировать хэш любой желаемой длины. Как заметил Пирсон, изменение любого бита в строке заставляет его алгоритм создавать совершенно другой хэш (0–255). В приведенном выше коде после каждого завершения внутреннего цикла первый байт строки фактически увеличивается на единицу (без изменения самой строки).

Каждый раз, когда делается это простое изменение в первом байте данных, новый хеш Пирсона, час, генерируется. Функция C создает хэш из 16 шестнадцатеричных символов путем объединения серии 8-битных хешей Пирсона (собранных в Retval). Вместо получения значения от 0 до 255 эта функция генерирует значение от 0 до 18 446 744 073 709 551 615 (= 264 - 1).

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

C #, 8 бит

 1 общественный класс Пирсон Хеширование 2 { 3     общественный байт Хеш(строка ввод) 4     { 5         const байт[] Т = { / * Перестановка 0-255 * / }; 6          7         байт toRet = 0; 8         байт[] байты = Кодирование.UTF8.GetBytes(ввод); 9 10         для каждого (вар б в байты)11         {12             toRet = Т[(байт)(toRet ^ б)];13         }14 15         вернуть toRet;16     }17 }

Смотрите также

использованная литература

  1. ^ Пирсон, Питер К. (июнь 1990 г.), «Быстрое хеширование текстовых строк переменной длины» (PDF), Коммуникации ACM, 33 (6): 677, Дои:10.1145/78973.78978, заархивировано из оригинал (PDF) на 2012-07-04, получено 2013-07-13
  2. ^ Лемир, Даниэль (2012), «Универсальность итерационного хеширования для строк переменной длины», Дискретная прикладная математика, 160 (4–5): 604–617, arXiv:1008.1715, Дои:10.1016 / j.dam.2011.11.009