Русская Википедия:SWIFFT
Шаблон:Карточка хеш-функции SWIFFT — это набор криптографических хеш-функций с доказанной стойкостьюШаблон:SfnШаблон:SfnШаблон:Sfn. Они основываются на быстром преобразовании Фурье (БПФ, Шаблон:Lang-en, FFT) и используют алгоритм Шаблон:Нп5. Криптографическая стойкость функций SWIFFT (в асимптотическом смысле)Шаблон:Sfn математически доказана при использовании рекомендуемых параметровШаблон:Sfn. Поиск коллизий в SWIFFT в худшем случае требует не меньше временных затрат, чем нахождение коротких векторов в циклических/идеальных решётках. Практическое применение SWIFFT будет ценно именно в тех случаях, когда стойкость к коллизиям особенно важна. Например, цифровые подписи, которые должны оставаться надёжными длительное время.
Данный алгоритм обеспечивает пропускную способность порядка 40 Мб/с на процессоре Intel Pentium 4 с тактовой частотой 3,2 ГГцШаблон:SfnШаблон:Sfn. Было проведено исследование, направленное на ускорение БПФ, которое используется в SWIFFTШаблон:Sfn. Как результат, скорость работы алгоритма удалось увеличить более чем в 13 разШаблон:Sfn. Данная реализация SWIFFT оказалась быстрее, чем реализации широко распространенных хеш-функцийШаблон:Sfn.
На конкурсе Национального института стандартов и технологий СШАШаблон:Sfn 2012 года был предложен SWIFFTX (модификация SWIFFT) в качестве SHA-3 (на замену более старых SHA-2 и особенно SHA-1[1]), но был отклонён в первом раунде[2].
Описание работы
Функции SWIFFT могут быть описаны как простое алгебраическое выражение над некоторым кольцом многочленов <math>R</math>Шаблон:SfnШаблон:Sfn. Семейство функций зависит от трёх основных параметровШаблон:Переход: пусть <math>n</math> будет степенью числа 2, <math>m > 0</math> — небольшое целое число, и <math>p > 0</math> — не обязательно простое число, но лучше выбрать его простым. Определим <math>R</math> как кольцо вида <math>R = \mathbb{Z}_p[\alpha]/(\alpha^n + 1)</math>. Например, кольцо многочленов в <math>\alpha </math>, у которых коэффициенты — целые числа, <math>p</math> — число, на которое выполняем деление по модулю, и <math>\alpha^n +1</math>. Элемент из <math>R</math> может быть многочленом степени меньшей <math>n</math> с коэффициентами из <math>Z_p</math>.
Определённая функция в семействе SWIFFT задаётся как <math>m</math> фиксированных элементов <math>a_1,\ldots,a_m \in R</math> кольца <math>R</math>, называемых мультипликаторами. Данную функцию над кольцом <math>R</math> можно записать в следующем виде:
<math> \sum_{i=1}^m (a_i \cdot x_i) </math>,
где <math>x_1,\ldots, x_m \in R</math> — многочлены с двоичными коэффициентами, соответствующие двоичному входному сообщению длины <math>mn</math>.
Алгоритм работы следующий:Шаблон:SfnШаблон:SfnШаблон:Sfn
- Берётся <math>\alpha</math> — неприводимый многочлен над <math>\mathbb{Z}[\alpha]</math>
- На вход подаётся сообщение <math>M</math> длины <math>mn</math>
- <math>M</math> преобразуется в набор из <math>m</math> полиномов <math>p_i</math> в определённом кольце многочленов <math>R</math> с двоичными коэффициентами
- Рассчитываются коэффициенты Фурье для каждого <math>p_i</math>
- Задаются фиксированные коэффициенты Фурье <math>a_i</math> в зависимости от семейства SWIFFT
- Попарно перемножаются коэффициенты Фурье <math>p_i</math> с <math>a_i</math> для каждого <math>i</math>
- Используется обратное преобразование Фурье для того, чтобы получить <math>m</math> многочленов <math>f_i</math> степени не более <math>2n</math>
- Рассчитается <math>f = \sum_{i=1}^m (f_i)</math> по модулю <math>p</math> и <math>\alpha^n+1</math>.
- <math>f</math> преобразуется в <math>n\log(p)</math> битов и отправляются их на выход
- Операцию быстрого преобразования Фурье на 4 шаге легко обратить. Она проводится для того, чтобы добиться Шаблон:Нп5 — смешивания битов, поданных на вход.
- Линейная комбинация на 6 шаге приводит к Шаблон:Нп5, потому как она сжимает входные данные.
Пример
Конкретные значения для параметров n, m и p выбраны следующим образом: n = 64, m= 16, p= 257Шаблон:Sfn. Для данных параметров любая фиксированная сжимающая функция семейства примет на вход сообщение длины mn = 1024 бит(128 байт). Выходные данные лежат в диапазоне <math> \mathbb{Z}^n_p </math>, который имеет размер <math> p^n = 257^{64}</math>. Выходные данные в <math> \mathbb{Z}^n_p </math> могут быть представлены, используя 528 бит (66 байт).
Вычисление результата перемножения многочленов
Самое сложное в вычислении приведённого выше выражения — вычислить результат перемножения <math> a_i \cdot x_i </math>Шаблон:SfnШаблон:Sfn. Быстрый способ вычислить данное произведение — это использовать Шаблон:Нп5, которая утверждает, что при определённых условиях выполнено:
- <math>\mathcal{F}\{f*g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\}</math>
Здесь <math>\mathcal{F}</math> обозначает преобразование Фурье, а операция <math>\cdot</math> означает перемножение коэффициентов с одинаковым индексом. В общем случае теоремы о свёртке <math>*</math> имеет значение свёртки, а не перемножения. Однако, можно показать, что перемножение многочленов является свёрткой.
Быстрое преобразование Фурье
Для нахождения преобразования Фурье мы используем Быстрое преобразование Фурье (БПФ), которое выполняется за <math> O(n \log(n))</math>Шаблон:Sfn. Алгоритм перемножения следующийШаблон:Sfn: мы рассчитываем все коэффициенты Фурье для всех многочленов сразу с помощью БПФ. Затем мы попарно перемножаем соответствующие коэффициенты Фурье двух многочленов. После мы используем обратное БПФ, после чего получим многочлен степени не выше <math> 2n</math>.
Дискретное преобразование Фурье
Вместо обычного преобразования Фурье в SWIFFT используется дискретное преобразование Фурье (ДПФ)Шаблон:SfnШаблон:Sfn. Оно использует корни из единицы в <math>\mathbb{Z}_p</math> вместо комплексных корней из единицы. Это будет справедливо, если <math>\mathbb{Z}_p</math> — конечное поле, и его 2nth простых корня из единицы существуют в данном поле. Данные условия будут выполнены, если взять такое простое число <math>p</math>, что <math>p-1</math> делится на <math>2n</math>.
Выбор параметров
Параметры m,p,n должны удовлетворят следующим требованиямШаблон:Sfn:
- n должен быть степенью двойки
- p должен быть простым числом
- p-1 должно делиться на 2n
- <math>\log(p)<</math>m
Можно взять, например, такие параметры: n=64, m=16, p=257. Мы берём пропускную способность на уровне 40Мб/сШаблон:Sfn, защищённость от поиска коллизий — <math>2^{106}</math> операций.
Статистические свойства
- Универсальное хеширование. Семейство функций SWIFFT является универсальнымШаблон:Sfn. Иными словами, для любых различных фиксированных <math>x, x*</math> и случайно выбранной функции <math>f</math> из семейства вероятность, что выполнится равенство <math>f(x) = f(x*)</math>, обратно пропорциональна величине выбранного диапазона.
- Регулярность. Функции из семейства сжимающих функций SWIFFT — регулярныеШаблон:Sfn.
- Генератор энтропии. SWIFFT является Шаблон:Нп5Шаблон:Sfn. Для хеш-таблиц и приложений, связанных с ними, желательно, чтобы ключи для значений, поданных в функцию, были распределены равномерно (или близко к равномерному распределению), даже если входные значения распределены неравномерно. Хеш-функции, которые ведут себя подобным образом, называются генераторами энтропии, потому как они могут представить неравномерно распределённые параметры (почти) равномерными на выходе. Формально, данным свойством обычно обладает семейство функций, из которого была выбрана одна функция случайным образом.
Криптографический свойства и безопасность
- SWIFFT не является Шаблон:Нп5 из-за линейностиШаблон:Sfn. Для произвольной функции <math>f</math> из семейства SWIFFT справедливо следующее: для двух входных параметров <math>x_1</math>, <math>x_2</math> таких, что <math>x_1+x_2</math> тоже может быть входным параметром, выполнено <math>f(x_1)+f(x_2) = f(x_1+x_2)</math>. Выполнение данного соотношения не подходит к случайной функции, и злоумышленник сможет легко отличить нашу функцию от случайной.
- Для семейства функций SWIFFT доказана криптографическая стойкость к коллизиям (в асимптотическом смысле) при относительно умеренном предположении о сложности задачи нахождения коротких векторов в циклических/идеальных решётках в худшем случае. Это значит, что семейство функций SWIFFT также устойчиво к атаке нахождения второго прообразаШаблон:SfnШаблон:Sfn.
Теоретическая стойкость
SWIFFT — Шаблон:Нп5Шаблон:SfnШаблон:Sfn. Как и в большинстве случаев, доказательство стойкости функций основывается на том, что математическую задачу, используемую в функциях, нельзя решить за полиномиальное время. Это значит, что стойкость SWIFFT заключается только в том, что в основе лежит сложная математическая задача.
В случае SWIFFT доказанная стойкость заключается в задаче поиска коротких векторов в циклических/идеальных решёткахШаблон:Sfn. Можно доказать, что справедливо следующее утверждение: предположим, у нас есть алгоритм, который может найти коллизии функции <math>f</math> для случайной версии SWIFFT, полученной от <math>f</math>, за некоторое возможное время <math>T</math> с вероятностью <math>p</math>. Значит, алгоритм, работает только на небольшой, но заметной доле функций семейства. Тогда мы можем также найти алгоритм <math>f_2</math>, который сможет всегда находить короткий вектор на любой идеальной решётке над кольцом <math>\mathbb{Z}_p[\alpha]/(\alpha^n + 1)</math> за некоторое возможное время <math>T_2</math>, зависящее от <math>T</math> и <math>p</math>. Это значит, что нахождение коллизий в SWIFFT не менее сложное, задача нахождения коротких векторов в решётке над <math>\mathbb{Z}_p[\alpha]/(\alpha^n + 1)</math>, для решения которой существуют только экспоненциальные алгоритмы.
Практическая стойкость
Авторы данной хеш-функции исследовали её на уязвимости для различных атак и установили, что атака «дней рождения» требует меньше всего операций подсчёта хэша (2106) для поиска коллизий.Шаблон:SfnШаблон:Sfn. Атаки с перестановками требуют 2448 операций подсчёта для стандартных параметров. Полный перебор возможных значений потребует 2528 операций подсчёта хэша. Этого, как правило, достаточно для того, чтобы сделать нападение противника невозможным.
См. также
Примечания
Литература
Книги
Статьи
