2.1 Универсальное хеширование Картера – Вегмана
Универсальное хеширование определяет доказуемо стойкую аутентификацию со счетчиком в представлении Картера – Вегмана [29,30] и определяется семействами хеш функций с заданными комбинаторными свойствами. Основные результаты исследований представлены в работах Стинсона, Биербрауэра и др. [32-34,36].
Построение универсальных хеш- функций в рамках определения 1.2 предложено Картером и Вегманом в методе скалярного произведения [30].
Хеш
вычисление
над конечным
полем 
определяется
функцией вида
, (2.1)
где
,.
- слова сообщения,
-
слова ключа,
-
число слов сообщения.
Замечание 2.1.
1.
Хеш функция на основе скалярного
произведения
определяет хеш класс
c
вероятностью
коллизии
.
2. Решение задачи построения доказуемо секретной аутентификации с максимальной теоретически достижимой секретностью достигается в классе универсальных хеш-функций со скалярным произведением.
3. Недостатком универсального хеширования (2.1)является требование - размер ключевого пространства должен быть не меньше пространства сообщения.
Ограничение на размер ключевого пространства снимается в методе полиномиального хеширования.
2.2 Метод полиномиального универсального хеширования
Полиномиальное универсальное хеширование PolyCW хеширование (polynomial Carter-Wegman hashing) предложено для снятия ограничения на пространство ключей.
Полиномиальное
хеширование
над конечным
полем 
определяется
функцией вида
, (2.2)
где
,.
- слова сообщения,
-
ключевое слово,
-
число слов сообщения
.
Замечание 2.1.
1.
Хеш функция на основе полиномиального
вычисления определяет хеш класс
c
вероятностью
коллизии
.
Вероятность
коллизии для полиномиальной хеш-функции
ограничивается отношением
,
где
простое число, определяющее поле 
.
Значение
определяется фундаментальной теоремой
алгебры: многочлен отличный от нуля,
степени не меньше
,
имеет не меньше
корней.
2.
Множество
ключей определяется значением
.
Чем больше размер ключевого пространства,
тем большее количество слов можно
хешировать до достижения допустимой
вероятности коллизии.
3.
Вычисления хеш- кодов в простом поле
определяется модулярной арифметикой.
Вычисление хеш-функции (2.2) можно
осуществить по итерационной схеме
Горнера, с одной операцией умножения и
сложения в конечном поле на каждом шаге.
Лучший результат достигается в арифметике
при как можно большом простом числе 
.
Итерационная схема Горнера вычисления
хеш-функции предполагает вычисление
(2.3)
Как
следует из анализа зависимостей
вероятности коллизии от значения поля
вычислений, размер конечного
поля 
должен быть как можно большим.
4.
Практическая
схема эффективного алгоритма хеш
вычисления должна включать ещё одно
дополнительное преобразование. Векторы
чисел с w
битами, которые имеют элементы вне
диапазона представления 
,
необходимо преобразовать в вектор,
который их не имеет, с помощью так
называемого двойного представления,
как это сделано в UMAC
алгоритме. Это приводит к удвоению
размера данных и соответственно к
увеличению вероятности коллизии и
соответственно снижается скорость
вычислений.
5.
Арифметика над расширенным полем 
характеристики 2
является менее удобной для современных
микропроцессоров, хотя обеспечивает
легкое разделение хешируемых битовых
строк на 
битовые подстроки. При этом отсутствуют
потери по вероятности коллизии и по
объему ключевых данных, которые возникают
при хешировании в арифметике 
.
Известно несколько эффективных алгоритмов
быстрого умножения в 
,
ориентированных на табличное умножение
элементов поля или являющихся модификациями
схемы Монтгомери.
Недостатком
полиномиального хеширования является
требование - размер пространства
сообщений ограничивается условием для
вероятности коллизии
и размером
поля вычислений.
Ограничение на размер пространства сообщений снимается в методе на основе алгебраического кодирования.