- •Глава 2 анализ методов универсального хеширования (доказуемо стойкой аутентификации) Лекція 1
- •2.1 Универсальное хеширование Картера – Вегмана
- •2.2 Метод полиномиального универсального хеширования
- •2.3 Универсальное хеширование по алгебраическим кодам
- •2.4 Универсальное хеширование по алгеброгеометрическим кодам
- •2.5 Метод универсального хеширования по рациональным функциям алгебраических кривых
- •2.6 Строго универсальное хеширование
- •2.6.1 Строго универсальное хеширование на основе ортогональных массивов
- •2.6.2 Строго универсальное хеширование на основе почти независимых массивов
- •2.6.3 Строго универсальное хеширование на основе слабосмещенных массивов.
- •2.7 Выводы раздела
2.3 Универсальное хеширование по алгебраическим кодам
Связь между универсальным семейством хеш-функций и кодовыми схемами впервые была отмечена Биербрауэром, Джохансоном, Кабатиански и Смитом [6]. Вычисление хеш значений с использованием алгебраического кода с кодовым расстоянием заключается в отображении -ичного кодового слова, соответствующего передаваемому сообщению, в значение кодового символа, порядковый номер которого определяется ключевыми данными.
Универсальное хеширование для сообщения , определяется выражением
,(2.2)
где изначения элементов столбцапорождающей матрицы линейного кода .
Параметры универсального хеширования по алгебраическим кодам устанавливает следующая теорема [].
Теорема 2.1. Если существует код, тогда существуетуниверсальное семейство хеш- функций, где
. (2.4)
Замечание 2.2.
1. Справедливо обратное утверждение. Если - хеш семейство, тогда существует код [].
2. Семейство хеш- функций является линейным в силу линейности алгебраических кодов.
3. Если есть линейный код с единицей, то есть содержит кодовые слова константы,, тогда справедливы отношения для вероятности успеха имитационной атаки Рими вероятности подменыРпод.
4. Если -линейный код без единицы, тогда Рим, Рпод. Верхняя граница вероятности навязывания для универсального семейства хеш функций на основе алгебраического кода без единицы определяется относительным кодовым расстоянием, нижняя граница - значностью кода.
5. Вероятность навязывания путем подмены и угадывания сообщений обратно пропорционально зависит от значности кодовых слов и относительного кодового расстояния кода.
6. Верхняя граница вероятности навязывания для универсального семейства хеш функций на основе алгебраического кода достигается на кодах Рида-Соломона (RS), которые являются обобщением кодов БЧХ и не может быть меньше значения, которое обратно пропорционально значности кода.
Универсальный хеш класс с кодами Рида-Соломона эквивалентный полиномиальному хешированию. Отличие заключается в том, что вычисление хеш кода может быть реализовано не только в конечном поле простого числа, но и в расширенном поле Галуа. В ряде случаев это может быть более предпочтительным, так как упрощается разбиение сообщения на слова, которые должны быть приведены к размеру поля вычисления хеша. Анализ показывает, что наиболее приемлемыми значениями для хеширования данных, которые лежат в диапазоне разрядности современных процессоров, являются 232 и 264 [XX]. Вероятность коллизии возрастает линейно с возрастанием объем данных. Для вероятности коллизии в диапазоне значений 10-3 (2-10) 10-9 (2-30) размер хешируемых данных должен лежать в диапазоне 23222 32-х разрядных слов.
Для построения универсальных классов хеш функций практический интерес представляют коды большой длины в поле большой размерности и большим относительным кодовым расстоянием.
2.4 Универсальное хеширование по алгеброгеометрическим кодам
Алгеброгеометрический подход к построению кодов по алгебраическим кривым предложен Гоппой В.Д. [].В основу алгеброгеометрического кодирования положено отображение векторного пространства над конечным полем рациональных функций по точкам алгебраической кривой.
Для построения кода по гладкой алгебраической кривойроданад, фиксируются наборы точек,,, эффективный дивизорстепении. С дивизоромассоциируется линейное пространствоиз рациональных функцийнакак множество всех функцийтаких, что порядокв каждой точкеудовлетворяет условию([71] теорема 4).
Алгеброгеометрический код имеет параметры
,(2.6)
и определяется как
. (2.7)
Двойственный код является алгеброгеометрическим с параметрами,.
Рассмотрим представление кода Рида-Соломона в алгеброгеометрической интерпретации.
Пусть алгебраическое покрытие. Точкиопределяются гомогенными координатамиимеют значения,и- особая точка (точка неопределенности). Пусть- рациональные функции, которые определены в каждойс коэффициентами ви которые имеют полюс порядка меньше, чемв точкеи нет других полюсов. Рациональная функцияимеет вид, гдеигомогенные полиномы степени. Алгеброгеометрический код определим как .
Код имеет размерность пространства,,и минимальное расстояние
Таким образом, получим коди по теореме 2.1 -универсальный класс хеш-функций
Важными длинными алгеброгеометрическими кодами являются коды Эрмита (НС) и Судзуки (SC). Коды Эрмита и Судзуки относятся к классу алгеброгеометрических кодов определённых над полем рациональных функций ассоциированным с алгебраической кривой Эрмита и группой Судзуки.
Алгеброгеометрический код Эрмита (НС код) определяется функциональным полем, связанным с проективным многообразием построенным по кривой Эрмита. Кривая Эрмита определяется уравнением
над квадратичным полем .
Число точек кривой , род.
Пусть и . Базис пространства задается функциями вида.
Алгеброгеометрический код имеет параметры и приводит к универсальному хешированию.
Алгеброгеометрический код Судзуки определен над расширенным полем , и имеет параметры
(8)
где род кривой и приводит к универсальному хешированию .
Зависимости вероятности коллизий для универсального хеширования на РС кодах, кодах Эрмита и Судзуки от длины хешируемого сообщения представлены на рис. 2.1 [].
RSh
HCh
SCh
1
0
Рис. 2.1 Зависимости вероятности коллизий универсального хеширования с РС кодами, кодами Эрмита и Судзуки от длины сообщения.
На рис. 2.1 представлены так же, абсолютно лучшие результаты для универсального хеширования по алгеброгеометрическим кодам. Алгеброгеометрические коды Эрмита и Судзуки обеспечивают меньшую вероятность коллизии универсального хеширования по сравнению с алгебраическим РС кодом. Для больших значений это следует прямо из графиков. Для малыхпроигрыш по вероятности коллизии РС коду (RSh) определяется неточной оценкой кодового расстояния кода Эрмита (HCh) и Судзуки (SCh).
В работе [X] представлены результаты зависимости вероятности коллизии для HChq хеширования от длины данных и размера поля вычислений для асимптотической границы. Анализ показывает, что хеширование с кодами Эрмита обеспечивает увеличение объёма хешируемых данных в q раз. Для q=232 объем хешируемых данных может достигать 239 32- х разрядных слов, что перекрывает широких диапазон практических приложений. При этом вероятность коллизии ограничивается значением 10-3 (2-10). Снижение вероятности коллизии возможно путем увеличения q. Так при q=264 вероятность коллизии снижается по асимптотической границе не меньше чем на 5 порядков до 10-8.
Коды Эрмита являются конструктивными, реализуются относительно просто в той же арифметике что и RS коды. Универсальные хеш- функции с кодами Эрмита обеспечивают меньшую вероятность коллизии по сравнению с RS кодами.
Утверждение 2.5 []. Основная алгеброгеометрическая граница для вероятности коллизии хеш класса построенного с использованием алгеброгеометрического кода имеет вид
Ркол, (2.8)
где -скорость кода.
Связь вероятности коллизии с алгеброгеометрическими параметрами кривых устанавливает утверждение 2.6 [].
Утверждение 2.6. Вероятность коллизии при хешировании на основе алгеброгеометрического кода при , где -род алгебраической кривой,определяется границей
. (2.14)
Замечание 2.3.
1.Вероятность коллизииуниверсального хеширования по алгеброгеометрическим кодам определяется алгеброгеометрическими параметрами кривых, а именно отношением рода кривой к числу рациональных точек кривой. Наименьшая верхняя граница вероятности коллизии реализуется по алгеброгеометрическим кодам на кривых, которые удовлетворяют границе Дринфельда-Влэдуца.
2. Оценки вероятности коллизии для низкоскоростного кодирования не являются точными, так как параметры алгеброгеометрических кодов точно определяются при размерности .
Универсальное хеширование по рациональным функциям алгебраических кривых снимает ограничение на точность оценок параметров хеширования по параметрам алгеброгеометрических кодов.