Пирсоновское хеширование

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

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

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

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

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

algorithm pearson hashing is
    h := 0

    for each c in C loop
        h := T[ h xor c ]
    end loop

    return h

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

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

С# , 8-битный

public class PearsonHashing
{
    public static byte Hash(string input)
    {
        byte[] T = { /* Permutation of 0-255 */ };
        
        byte hash = 0;
        byte[] bytes = Encoding.UTF8.GetBytes(input);

        foreach (byte b in bytes)
        {
            hash = T[hash ^ b];
        }

        return hash;
    }
}

См. также

Некриптографические хэш-функции

Ссылки

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

[acmref-1] Пирсон, Питер К. (июнь 1990 г.), «Быстрое хеширование текстовых строк переменной длины» (PDF) , Communications of the ACM , 33 (6): 677, doi : 10.1145/78973.78978 , заархивировано из оригинала (PDF) на 04 июля 2012 г. , получено 13 июля 2013 г.

[univ-2] Лемир, Дэниел (2012), «Универсальность итерационного хеширования строк переменной длины», Discrete Applied Mathematics , 160 (4–5): 604–617, arXiv : 1008.1715 , doi : 10.1016/j.dam.2011.11.009

[1]

[2]