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

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

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

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

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

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

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

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

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

С# , 8-битный

общественный   класс   PearsonHashing  {      public   static   byte   Hash  (  строковый   ввод  )      {          byte  []   T   =   {   /* Перестановка 0-255 */   };                  байтовый   хеш   =   0  ;          байт  []   байт   =   Кодировка  .  UTF8  .  GetBytes  (  вход  );          foreach   (  байт   b   в   байтах  )          {              хэш   =   T  [  хэш   ^   b  ];          }          вернуть   хеш  ;      }  }

См. также

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

Ссылки

^ Пирсон, Питер К. (июнь 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]