| dbo:abstract
|
- Pearson hashing is a hash function designed for fast execution on processors with 8-bit registers. Given an input consisting of any number of bytes, it produces as output a single byte that is strongly dependent on every byte of the input. Its implementation requires only a few instructions, plus a 256-byte lookup table containing a permutation of the values 0 through 255. This hash function is a CBC-MAC that uses an 8-bit substitution cipher implemented via the substitution table. An 8-bit cipher has negligible cryptographic security, so the Pearson hash function is not cryptographically strong, but it is useful for implementing hash tables or as a data integrity check code, for which purposes it offers these benefits:
* It is extremely simple.
* It executes quickly on resource-limited processors.
* There is no simple class of inputs for which collisions (identical outputs) are especially likely.
* Given a small, privileged set of inputs (e.g., reserved words for a compiler), the permutation table can be adjusted so that those inputs yield distinct hash values, producing what is called a perfect hash function.
* Two input strings differing by exactly one character never collide. E.g., applying the algorithm on the strings ABC and AEC will never produce the same value. One of its drawbacks when compared with other hashing algorithms designed for 8-bit processors is the suggested 256 byte lookup table, which can be prohibitively large for a small microcontroller with a program memory size on the order of hundreds of bytes. A workaround to this is to use a simple permutation function instead of a table stored in program memory. However, using a too simple function, such as T[i] = 255-i, partly defeats the usability as a hash function as anagrams will result in the same hash value; using a too complex function, on the other hand, will affect speed negatively. Using a function rather than a table also allows extending the block size. Such functions naturally have to be bijective, like their table variants. The algorithm can be described by the following pseudocode, which computes the hash of message C using the permutation table T: algorithm pearson hashing is h := 0 for each c in C loop h := T[ h xor c ] end loop return h The hash variable (h) may be initialized differently, e.g. to the length of the data (C) modulo 256; this particular choice is used in the Python implementation example below. (en)
- Хеширование Пирсона — хеш-функция, предназначенная для быстрого выполнения на процессорах с 8-разрядным регистром. Получая вход, состоящий из любого количества байтов, он возвращает на выходе один байт, который сильно зависит от каждого байта ввода. Его реализация требует только нескольких инструкций, а также 256-байтной таблицы поиска, содержащей перестановку значений от 0 до 255. Эта хеш-функция представляет собой CBC-MAC, которая использует 8-битный шифр подстановки, реализованный через таблицу замещения. 8-битный шифр имеет малую криптографическую стойкость, поэтому хеш-функция Пирсона также не является криптографической, но она полезна для реализации хеш-таблиц или проверки целостности данных, имея следующие преимущества:
* Она очень простая.
* Она быстро выполняется на маломощных процессорах.
* Нет простого класса входов, для которых очень вероятны коллизии (идентичные выходы).
* Имея небольшой набор входов (например, зарезервированные слова для компилятора), таблица перестановок может быть отрегулирована так, чтобы эти входы выдавали разные значения хеша, создавая так называемую идеальную хеш-функцию.
* Две входные строки, отличающиеся одним символом, никогда не сталкиваются. Например, применение алгоритма для строк ABC и AEC не даст одинакового значения. Одним из его недостатков, по сравнению с другими алгоритмами хеширования, предназначенными для 8-разрядных процессоров, является предлагаемая таблица поиска в 256 байт, которая может быть слишком большой для небольшого микроконтроллера с размером программной памяти порядка нескольких сотен байтов. Обходным путем для этого является использование простой функции перестановки вместо таблицы, хранящейся в памяти программы. Однако использование слишком простой функции, такой как T[i] = 255-i, доставляет неудобство для использования её в качестве хеш-функции, поскольку анаграммы будут приводить к одному и тому же значению хеша; с другой стороны, слишком сложная функция будет отрицательно влиять на скорость. Использование функции, а не таблицы также позволяет расширить размер блока. Такие функции, естественно, должны быть биективными, как и их табличные варианты. Алгоритм может быть описан следующим псевдокодом, который вычисляет хеш сообщения C, используя таблицу перестановок T: h := 0for each c in C loop h := T[h xor c]end loopreturn h Хеш-переменная h может быть инициализирована по-разному, например, длиной строки входных данных C по модулю 256; конкретно это решение используется в реализации Python. (ru)
|
| rdfs:comment
|
- Pearson hashing is a hash function designed for fast execution on processors with 8-bit registers. Given an input consisting of any number of bytes, it produces as output a single byte that is strongly dependent on every byte of the input. Its implementation requires only a few instructions, plus a 256-byte lookup table containing a permutation of the values 0 through 255. The algorithm can be described by the following pseudocode, which computes the hash of message C using the permutation table T: (en)
- Хеширование Пирсона — хеш-функция, предназначенная для быстрого выполнения на процессорах с 8-разрядным регистром. Получая вход, состоящий из любого количества байтов, он возвращает на выходе один байт, который сильно зависит от каждого байта ввода. Его реализация требует только нескольких инструкций, а также 256-байтной таблицы поиска, содержащей перестановку значений от 0 до 255. Алгоритм может быть описан следующим псевдокодом, который вычисляет хеш сообщения C, используя таблицу перестановок T: h := 0for each c in C loop h := T[h xor c]end loopreturn h (ru)
|