Хеширование Пирсона
Хеширование Пирсона — хеш-функция, предназначенная для быстрого выполнения на процессорах с 8-разрядным регистром. Получая вход, состоящий из любого количества байтов, он возвращает на выходе один байт, который сильно зависит от каждого байта ввода. Его реализация требует только нескольких инструкций, а также 256-байтной таблицы поиска, содержащей перестановку значений от 0 до 255[1][2].
Эта хеш-функция представляет собой CBC-MAC, которая использует 8-битный шифр подстановки, реализованный через таблицу замещения. 8-битный шифр имеет малую криптографическую стойкость, поэтому хеш-функция Пирсона также не является криптографической, но она полезна для реализации хеш-таблиц или проверки целостности данных, имея следующие преимущества:
- Она очень простая.
- Она быстро выполняется на маломощных процессорах.
- Нет простого класса входов, для которых очень вероятны коллизии (идентичные выходы).
- Имея небольшой набор входов (например, зарезервированные слова для компилятора), таблица перестановок может быть отрегулирована так, чтобы эти входы выдавали разные значения хеша, создавая так называемую идеальную хеш-функцию.
- Две входные строки, отличающиеся одним символом, никогда не сталкиваются[3]. Например, применение алгоритма для строк ABC и AEC не даст одинакового значения.
Одним из его недостатков, по сравнению с другими алгоритмами хеширования, предназначенными для 8-разрядных процессоров, является предлагаемая таблица поиска в 256 байт, которая может быть слишком большой для небольшого микроконтроллера с размером программной памяти порядка нескольких сотен байтов. Обходным путем для этого является использование простой функции перестановки вместо таблицы, хранящейся в памяти программы. Однако использование слишком простой функции, такой как T[i] = 255-i, доставляет неудобство для использования её в качестве хеш-функции, поскольку анаграммы будут приводить к одному и тому же значению хеша; с другой стороны, слишком сложная функция будет отрицательно влиять на скорость. Использование функции, а не таблицы также позволяет расширить размер блока. Такие функции, естественно, должны быть биективными, как и их табличные варианты.
Алгоритм может быть описан следующим псевдокодом, который вычисляет хеш сообщения C, используя таблицу перестановок T:
h := 0
for each c in C loop
h := T[h xor c]
end loop
return h
Хеш-переменная h может быть инициализирована по-разному, например, длиной строки входных данных C по модулю 256; конкретно это решение используется в реализации Python.
Реализация на Python для генерации 8-битной таблицы поиска
правитьПараметр table требует псевдослучайного перетасованного списка в диапазоне [0..255]. Она может быть легко сгенерирована с помощью встроенной функции range и использования random.shuffle для перестановки:
from random import shuffle
example_table = list(range(0, 256))
shuffle(example_table)
def hash8(message, table):
hash = len(message) % 256
for i in message:
hash = table[(hash+ord(i)) % 256]
return hash
Генерация 64-битного хеша (16 шестнадцатеричных символов)
правитьРеализация генерации 64-битного хеша на языке C.
void Pearson16(const unsigned char *x, size_t len,
char *hex, size_t hexlen)
{
size_t i;
size_t j;
unsigned char h;
unsigned char hh[8];
static const unsigned char T[256] = {
// 0-255 shuffled in any (random) order suffices
98, 6, 85,150, 36, 23,112,164,135,207,169, 5, 26, 64,165,219, // 1
61, 20, 68, 89,130, 63, 52,102, 24,229,132,245, 80,216,195,115, // 2
90,168,156,203,177,120, 2,190,188, 7,100,185,174,243,162, 10, // 3
237, 18,253,225, 8,208,172,244,255,126,101, 79,145,235,228,121, // 4
123,251, 67,250,161, 0,107, 97,241,111,181, 82,249, 33, 69, 55, // 5
59,153, 29, 9,213,167, 84, 93, 30, 46, 94, 75,151,114, 73,222, // 6
197, 96,210, 45, 16,227,248,202, 51,152,252,125, 81,206,215,186, // 7
39,158,178,187,131,136, 1, 49, 50, 17,141, 91, 47,129, 60, 99, // 8
154, 35, 86,171,105, 34, 38,200,147, 58, 77,118,173,246, 76,254, // 9
133,232,196,144,198,124, 53, 4,108, 74,223,234,134,230,157,139, // 10
189,205,199,128,176, 19,211,236,127,192,231, 70,233, 88,146, 44, // 11
183,201, 22, 83, 13,214,116,109,159, 32, 95,226,140,220, 57, 12, // 12
221, 31,209,182,143, 92,149,184,148, 62,113, 65, 37, 27,106,166, // 13
3, 14,204, 72, 21, 41, 56, 66, 28,193, 40,217, 25, 54,179,117, // 14
238, 87,240,155,180,170,242,212,191,163, 78,218,137,194,175,110, // 15
43,119,224, 71,122,142, 42,160,104, 48,247,103, 15, 11,138,239 // 16
};
for (j = 0; j < 8; ++j) {
h = T[(x[0] + j) % 256];
for (i = 1; i < len; ++i) {
h = T[h ^ x[i]];
}
hh[j] = h;
}
snprintf(hex, hexlen, "%02X%02X%02X%02X%02X%02X%02X%02X",
hh[0], hh[1], hh[2], hh[3], hh[4], hh[5], hh[6], hh[7]);
}
Используемая выше схема представляет собой очень простую реализацию алгоритма с простым расширением для генерации хеша длиной более 8 бит. Это расширение содержит внешний цикл (т. е. все строки операторов, которые включают переменную j) и массив hh.
Для данной строки или фрагмента данных исходный алгоритм Пирсона создаёт только 8-битный выход, целое число [0..255]. Однако алгоритм позволяет чрезвычайно легко генерировать хеш любой длины. Как заметил Пирсон, изменение любого бита в строке приводит к тому, что его алгоритм создаёт совершенно другой хеш. В приведённом выше коде, после каждого завершения внутреннего цикла, первый байт строки увеличивается на единицу (без изменения самой строки).
Каждый раз, когда выполняется простое изменение первого байта данных, генерируется другой хеш Пирсона, в переменной h. Функция C создаёт хеш 16-ричных символов, объединяя ряд 8-битовых хешей Пирсона (собранных в переменной hh). Вместо того, чтобы возвращать значение от 0 до 255, эта функция генерирует значение от 0 до 18446744073709551615 (= 264 - 1).
Этот пример показывает, что алгоритм Пирсона может быть использован для генерации хешей любой желаемой длины путём объединения последовательности 8-битных хеш-значений, каждый из которых вычисляется просто путем незначительной модификации строки каждый раз, когда вычисляется хеш-функция. Таким образом, одна и та же основная логика может быть применена для генерации 32 или 128-битных хешей.
Примечания
править- ↑ Peter K. Pearson. Fast Hashing of Variable-Length Text Strings // Communications of the ACM. — 1990. — Июнь (т. 33, № 6). — С. 677.
- ↑ Online PDF file of the CACM paper (англ.). Дата обращения: 28 августа 2018. Архивировано из оригинала 4 июля 2012 года.
- ↑ Daniel Lemire. The universality of iterated hashing over variable-length strings // Discrete Applied Mathematics. — 2012. — Т. 160, № 4—5. — С. 604—617. Архивировано 26 ноября 2018 года.