SWIFFT

Криптографическая</br>хеш-функция
Название	SWIFFT
Разработчики	Вадим Любашевский, Даниель Мичьянчио, Крис Пейкерт, Алон Розен
Создан	2008
Опубликован	2008
Тип	хеш-функция

SWIFFT — это набор криптографических хеш-функций с доказанной стойкостью. Они основываются на быстром преобразовании Фурье (БПФ, англ. Fast Fourier Transform, FFT) и используют алгоритм LLL-редуцированных базисов. Криптографическая стойкость SWIFFT (в асимптотическом смысле) математически доказана при использовании рекомендуемых параметров. Поиск коллизий в SWIFFT в худшем случае требует не меньше временных затрат, чем нахождение коротких векторов в циклических/идеальных решётках. Практическое применение SWIFFT будет ценно именно в тех случаях, когда стойкость к коллизиям особенно важна. Например, цифровые подписи, которые должны оставаться надёжными длительное время.

Данный алгоритм обеспечивает пропускную способность порядка 40 Мб/с на процессоре Intel Pentium 4 с тактовой частотой 3,2 ГГц. Было проведено исследование, направленное на ускорение БПФ, которое используется в SWIFFT. Как результат, скорость работы алгоритма удалось увеличить более чем в 13 раз. Данная реализация SWIFFT оказалась быстрее, чем реализации широко распространенных хэш-функций.

На конкурсе Национального института стандартов и технологий США 2012 года был предложен SWIFFTX (модификация SWIFFT) в качестве SHA-3 (на замену более старых SHA-2 и особенно SHA-1), но был отклонён в первом раунде.

Описание работы

Функции SWIFFT могут быть описаны как простое алгебраическое выражение над некоторым кольцом многочленов <math>R</math>. Семейство функций зависит от трёх основных параметров: пусть <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>.

Алгоритм работы следующий:

1. Берётся <math>\alpha</math> — неприводимый многочлен над <math>\mathbb{Z}[\alpha]</math>
2. На вход подаётся сообщение <math>M</math> длины <math>mn</math>
3. <math>M</math> преобразуется в набор из <math>m</math> полиномов <math>p_i</math> в определённом кольце многочленов <math>R</math> с двоичными коэффициентами
4. Рассчитываются коэффициенты Фурье для каждого <math>p_i</math>
5. Задаются фиксированные коэффициенты Фурье <math>a_i</math> в зависимости от семейства SWIFFT
6. Попарно перемножаются коэффициенты Фурье <math>p_i</math> с <math>a_i</math> для каждого <math>i</math>
7. Используется обратное преобразование Фурье для того, чтобы получить <math>m</math> многочленов <math>f_i</math> степени не более <math>2n</math>
8. Рассчитается <math>f = \sum_{i=1}^m (f_i)</math> по модулю <math>p</math> и <math>\alpha^n+1</math>.
9. <math>f</math> преобразуется в <math>n\log(p)</math> битов и отправляются их на выход

• Операцию быстрого преобразования Фурье на 4 шаге легко обратить. Она проводится для того, чтобы добиться путаницы — смешивания битов, поданных на вход.
• Линейная комбинация на 6 шаге приводит к путанице, потому как она сжимает входные данные.

Пример

Конкретные значения для параметров n, m и p выбраны следующим образом: n = 64, m= 16, p= 257. Для данных параметров любая фиксированная сжимающая функция семейства примет на вход сообщение длины 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>. Быстрый способ вычислить данное произведение — это использовать теорему о свёртке, которая утверждает, что при определённых условиях выполнено:

<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>. Алгоритм перемножения следующий: мы рассчитываем все коэффициенты Фурье для всех многочленов сразу с помощью БПФ. Затем мы попарно перемножаем соответствующие коэффициенты Фурье двух многочленов. После мы используем обратное БПФ, после чего получим многочлен степени не выше <math> 2n</math>.

Дискретное преобразование Фурье

Вместо обычного преобразования Фурье в SWIFFT используется дискретное преобразование Фурье (ДПФ). Оно использует корни из единицы в <math>\mathbb{Z}_p</math> вместо комплексных корней из единицы. Это будет справедливо, если <math>\mathbb{Z}_p</math> — конечное поле, и его 2n^th простых корня из единицы существуют в данном поле. Данные условия будут выполнены, если взять такое простое число <math>p</math>, что <math>p-1</math> делится на <math>2n</math>.

Выбор параметров

Параметры m,p,n должны удовлетворят следующим требованиям:

• n должен быть степенью двойки
• p должен быть простым числом
• p-1 должно делиться на 2n
• <math>\log(p)<</math>m

Можно взять, например, такие параметры: n=64, m=16, p=257. Мы берём пропускную способность на уровне 40Мб/с, защищённость от поиска коллизий — <math>2^{106}</math> операций.

Статистические свойства

• Универсальное хэширование. Семейство функций SWIFFT является универсальным. Иными словами, для любых различных фиксированных <math>x, x*</math> и случайно выбранной функции <math>f</math> из семейства вероятность, что выполнится равенство <math>f(x) = f(x*)</math>, обратно пропорциональна величине выбранного диапазона.
• Регулярность. Функции из семейства сжимающих функций SWIFFT — регулярные.
• Генератор энтропии. SWIFFT является генератором энтропии. Для хэш-таблиц и приложений, связанных с ними, желательно, чтобы ключи для значений, поданных в функцию, были распределены равномерно (или близко к равномерному распределению), даже если входные значения распределены неравномерно. Хэш-функции, которые ведут себя подобным образом, называются генераторами энтропии, потому как они могут представить неравномерно распределённые параметры (почти) равномерными на выходе. Формально, данным свойством обычно обладает семейство функций, из которого была выбрана одна функция случайным образом.

Криптографический свойства и безопасность

• SWIFFT не является псевдослучайной функцией из-за линейности. Для произвольной функции <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 также устойчиво к атаке нахождения второго прообраза.

Теоретическая стойкость

SWIFFT — криптографические функции с доказанной стойкостью. Как и в большинстве случаев, доказательство стойкости функций основывается на том, что математическую задачу, используемую в функциях, нельзя решить за полиномиальное время. Это значит, что стойкость SWIFFT заключается только в том, что в основе лежит сложная математическая задача.

В случае SWIFFT доказанная стойкость заключается в задаче поиска коротких векторов в циклических/идеальных решётках. Можно доказать, что справедливо следующее утверждение: предположим, у нас есть алгоритм, который может найти коллизии функции <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>, для решения которой существуют только экспоненциальные алгоритмы.

Практическая стойкость

Авторы данной хэш-функции исследовали её на уязвимости к различным атакам и установили, что атака «дней рождения» требует меньше всего операций подсчёта хэша (2¹⁰⁶) для поиска коллизий.. Атаки с перестановками требуют 2⁴⁴⁸ операций подсчёта для стандартных параметров. Полный перебор возможных значений потребует 2⁵²⁸ операций подсчёта хэша. Этого, как правило, достаточно для того, чтобы сделать нападение противника невозможным.

См. также

• Быстрое преобразование Фурье

Литература

Книги

• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.

Отрывок, характеризующий SWIFFT

На другой день князь Андрей поехал к Ростовым обедать, так как его звал граф Илья Андреич, и провел у них целый день.
Все в доме чувствовали для кого ездил князь Андрей, и он, не скрывая, целый день старался быть с Наташей. Не только в душе Наташи испуганной, но счастливой и восторженной, но во всем доме чувствовался страх перед чем то важным, имеющим совершиться. Графиня печальными и серьезно строгими глазами смотрела на князя Андрея, когда он говорил с Наташей, и робко и притворно начинала какой нибудь ничтожный разговор, как скоро он оглядывался на нее. Соня боялась уйти от Наташи и боялась быть помехой, когда она была с ними. Наташа бледнела от страха ожидания, когда она на минуты оставалась с ним с глазу на глаз. Князь Андрей поражал ее своей робостью. Она чувствовала, что ему нужно было сказать ей что то, но что он не мог на это решиться.
Когда вечером князь Андрей уехал, графиня подошла к Наташе и шопотом сказала:
– Ну что?
– Мама, ради Бога ничего не спрашивайте у меня теперь. Это нельзя говорить, – сказала Наташа.
Но несмотря на то, в этот вечер Наташа, то взволнованная, то испуганная, с останавливающимися глазами лежала долго в постели матери. То она рассказывала ей, как он хвалил ее, то как он говорил, что поедет за границу, то, что он спрашивал, где они будут жить это лето, то как он спрашивал ее про Бориса.
– Но такого, такого… со мной никогда не бывало! – говорила она. – Только мне страшно при нем, мне всегда страшно при нем, что это значит? Значит, что это настоящее, да? Мама, вы спите?
– Нет, душа моя, мне самой страшно, – отвечала мать. – Иди.
– Все равно я не буду спать. Что за глупости спать? Maмаша, мамаша, такого со мной никогда не бывало! – говорила она с удивлением и испугом перед тем чувством, которое она сознавала в себе. – И могли ли мы думать!…
Наташе казалось, что еще когда она в первый раз увидала князя Андрея в Отрадном, она влюбилась в него. Ее как будто пугало это странное, неожиданное счастье, что тот, кого она выбрала еще тогда (она твердо была уверена в этом), что тот самый теперь опять встретился ей, и, как кажется, неравнодушен к ней. «И надо было ему нарочно теперь, когда мы здесь, приехать в Петербург. И надо было нам встретиться на этом бале. Всё это судьба. Ясно, что это судьба, что всё это велось к этому. Еще тогда, как только я увидала его, я почувствовала что то особенное».
– Что ж он тебе еще говорил? Какие стихи то эти? Прочти… – задумчиво сказала мать, спрашивая про стихи, которые князь Андрей написал в альбом Наташе.
– Мама, это не стыдно, что он вдовец?
– Полно, Наташа. Молись Богу. Les Marieiages se font dans les cieux. [Браки заключаются в небесах.]
– Голубушка, мамаша, как я вас люблю, как мне хорошо! – крикнула Наташа, плача слезами счастья и волнения и обнимая мать.
В это же самое время князь Андрей сидел у Пьера и говорил ему о своей любви к Наташе и о твердо взятом намерении жениться на ней.

В этот день у графини Елены Васильевны был раут, был французский посланник, был принц, сделавшийся с недавнего времени частым посетителем дома графини, и много блестящих дам и мужчин. Пьер был внизу, прошелся по залам, и поразил всех гостей своим сосредоточенно рассеянным и мрачным видом.
Пьер со времени бала чувствовал в себе приближение припадков ипохондрии и с отчаянным усилием старался бороться против них. Со времени сближения принца с его женою, Пьер неожиданно был пожалован в камергеры, и с этого времени он стал чувствовать тяжесть и стыд в большом обществе, и чаще ему стали приходить прежние мрачные мысли о тщете всего человеческого. В это же время замеченное им чувство между покровительствуемой им Наташей и князем Андреем, своей противуположностью между его положением и положением его друга, еще усиливало это мрачное настроение. Он одинаково старался избегать мыслей о своей жене и о Наташе и князе Андрее. Опять всё ему казалось ничтожно в сравнении с вечностью, опять представлялся вопрос: «к чему?». И он дни и ночи заставлял себя трудиться над масонскими работами, надеясь отогнать приближение злого духа. Пьер в 12 м часу, выйдя из покоев графини, сидел у себя наверху в накуренной, низкой комнате, в затасканном халате перед столом и переписывал подлинные шотландские акты, когда кто то вошел к нему в комнату. Это был князь Андрей.
– А, это вы, – сказал Пьер с рассеянным и недовольным видом. – А я вот работаю, – сказал он, указывая на тетрадь с тем видом спасения от невзгод жизни, с которым смотрят несчастливые люди на свою работу.
Князь Андрей с сияющим, восторженным и обновленным к жизни лицом остановился перед Пьером и, не замечая его печального лица, с эгоизмом счастия улыбнулся ему.
– Ну, душа моя, – сказал он, – я вчера хотел сказать тебе и нынче за этим приехал к тебе. Никогда не испытывал ничего подобного. Я влюблен, мой друг.
Пьер вдруг тяжело вздохнул и повалился своим тяжелым телом на диван, подле князя Андрея.
– В Наташу Ростову, да? – сказал он.
– Да, да, в кого же? Никогда не поверил бы, но это чувство сильнее меня. Вчера я мучился, страдал, но и мученья этого я не отдам ни за что в мире. Я не жил прежде. Теперь только я живу, но я не могу жить без нее. Но может ли она любить меня?… Я стар для нее… Что ты не говоришь?…
– Я? Я? Что я говорил вам, – вдруг сказал Пьер, вставая и начиная ходить по комнате. – Я всегда это думал… Эта девушка такое сокровище, такое… Это редкая девушка… Милый друг, я вас прошу, вы не умствуйте, не сомневайтесь, женитесь, женитесь и женитесь… И я уверен, что счастливее вас не будет человека.
– Но она!
– Она любит вас.
– Не говори вздору… – сказал князь Андрей, улыбаясь и глядя в глаза Пьеру.
– Любит, я знаю, – сердито закричал Пьер.
– Нет, слушай, – сказал князь Андрей, останавливая его за руку. – Ты знаешь ли, в каком я положении? Мне нужно сказать все кому нибудь.
– Ну, ну, говорите, я очень рад, – говорил Пьер, и действительно лицо его изменилось, морщина разгладилась, и он радостно слушал князя Андрея. Князь Андрей казался и был совсем другим, новым человеком. Где была его тоска, его презрение к жизни, его разочарованность? Пьер был единственный человек, перед которым он решался высказаться; но зато он ему высказывал всё, что у него было на душе. То он легко и смело делал планы на продолжительное будущее, говорил о том, как он не может пожертвовать своим счастьем для каприза своего отца, как он заставит отца согласиться на этот брак и полюбить ее или обойдется без его согласия, то он удивлялся, как на что то странное, чуждое, от него независящее, на то чувство, которое владело им.
– Я бы не поверил тому, кто бы мне сказал, что я могу так любить, – говорил князь Андрей. – Это совсем не то чувство, которое было у меня прежде. Весь мир разделен для меня на две половины: одна – она и там всё счастье надежды, свет; другая половина – всё, где ее нет, там всё уныние и темнота…
– Темнота и мрак, – повторил Пьер, – да, да, я понимаю это.
– Я не могу не любить света, я не виноват в этом. И я очень счастлив. Ты понимаешь меня? Я знаю, что ты рад за меня.
– Да, да, – подтверждал Пьер, умиленными и грустными глазами глядя на своего друга. Чем светлее представлялась ему судьба князя Андрея, тем мрачнее представлялась своя собственная.


Для женитьбы нужно было согласие отца, и для этого на другой день князь Андрей уехал к отцу.
Отец с наружным спокойствием, но внутренней злобой принял сообщение сына. Он не мог понять того, чтобы кто нибудь хотел изменять жизнь, вносить в нее что нибудь новое, когда жизнь для него уже кончалась. – «Дали бы только дожить так, как я хочу, а потом бы делали, что хотели», говорил себе старик. С сыном однако он употребил ту дипломацию, которую он употреблял в важных случаях. Приняв спокойный тон, он обсудил всё дело.
Во первых, женитьба была не блестящая в отношении родства, богатства и знатности. Во вторых, князь Андрей был не первой молодости и слаб здоровьем (старик особенно налегал на это), а она была очень молода. В третьих, был сын, которого жалко было отдать девчонке. В четвертых, наконец, – сказал отец, насмешливо глядя на сына, – я тебя прошу, отложи дело на год, съезди за границу, полечись, сыщи, как ты и хочешь, немца, для князя Николая, и потом, ежели уж любовь, страсть, упрямство, что хочешь, так велики, тогда женись.
– И это последнее мое слово, знай, последнее… – кончил князь таким тоном, которым показывал, что ничто не заставит его изменить свое решение.
Князь Андрей ясно видел, что старик надеялся, что чувство его или его будущей невесты не выдержит испытания года, или что он сам, старый князь, умрет к этому времени, и решил исполнить волю отца: сделать предложение и отложить свадьбу на год.
Через три недели после своего последнего вечера у Ростовых, князь Андрей вернулся в Петербург.

На другой день после своего объяснения с матерью, Наташа ждала целый день Болконского, но он не приехал. На другой, на третий день было то же самое. Пьер также не приезжал, и Наташа, не зная того, что князь Андрей уехал к отцу, не могла себе объяснить его отсутствия.
Так прошли три недели. Наташа никуда не хотела выезжать и как тень, праздная и унылая, ходила по комнатам, вечером тайно от всех плакала и не являлась по вечерам к матери. Она беспрестанно краснела и раздражалась. Ей казалось, что все знают о ее разочаровании, смеются и жалеют о ней. При всей силе внутреннего горя, это тщеславное горе усиливало ее несчастие.
Однажды она пришла к графине, хотела что то сказать ей, и вдруг заплакала. Слезы ее были слезы обиженного ребенка, который сам не знает, за что он наказан.
Графиня стала успокоивать Наташу. Наташа, вслушивавшаяся сначала в слова матери, вдруг прервала ее:
– Перестаньте, мама, я и не думаю, и не хочу думать! Так, поездил и перестал, и перестал…
Голос ее задрожал, она чуть не заплакала, но оправилась и спокойно продолжала: – И совсем я не хочу выходить замуж. И я его боюсь; я теперь совсем, совсем, успокоилась…
На другой день после этого разговора Наташа надела то старое платье, которое было ей особенно известно за доставляемую им по утрам веселость, и с утра начала тот свой прежний образ жизни, от которого она отстала после бала. Она, напившись чаю, пошла в залу, которую она особенно любила за сильный резонанс, и начала петь свои солфеджи (упражнения пения). Окончив первый урок, она остановилась на середине залы и повторила одну музыкальную фразу, особенно понравившуюся ей. Она прислушалась радостно к той (как будто неожиданной для нее) прелести, с которой эти звуки переливаясь наполнили всю пустоту залы и медленно замерли, и ей вдруг стало весело. «Что об этом думать много и так хорошо», сказала она себе и стала взад и вперед ходить по зале, ступая не простыми шагами по звонкому паркету, но на всяком шагу переступая с каблучка (на ней были новые, любимые башмаки) на носок, и так же радостно, как и к звукам своего голоса прислушиваясь к этому мерному топоту каблучка и поскрипыванью носка. Проходя мимо зеркала, она заглянула в него. – «Вот она я!» как будто говорило выражение ее лица при виде себя. – «Ну, и хорошо. И никого мне не нужно».