Rating@Mail.ru

Дискретные функции в криптографии

Сохранить в закладки
3380
25
Сохранить в закладки

Математик Юрий Таранников о линейных и афинных функциях, полиноме Жегалкина и алгебраических атаках

Дискретная функция — это отображение множества наборов какой-то длины каким-то алфавитом в значения из того же алфавита. Всякая информация в компьютерах, как правило, представлена конечным алфавитом. Очень часто это двоичный алфавит, поэтому рассматриваются двоичные функции как важный частный случай произвольных дискретных функций. Двоичные функции называются булевыми.

Поскольку часто при шифровании надо отображать информацию какой-то длины в информацию примерно такой же длины, часто рассматривают не одну функцию, а совокупность булевых функций. Например, совокупность из m булевых функций от n переменных. Такое отображение называется дискретным оператором или в частном случае булевым оператором. Приведу пример наиболее часто распространяющихся алгоритмов шифрования, криптосистем, которые используют дискретные функции, — это симметричное шифрование. В нем шифрование и дешифрование осуществляются одним и тем же алгоритмом.

Начнем с поточных шифров. В них генерируется псевдослучайная последовательность тем же самым алфавитом, на котором идет информация, которую надо зашифровать. Есть много способов породить псевдослучайную последовательность. Я расскажу о том, что чаще всего используется, — регистре сдвига с линейной обратной связью. Можно представить себе либо устройство, либо набор ячеек в программе — они используются и на механическом уровне как устройства, и как программная реализация. Число ячеек — это длина регистра, в начальный момент времени в них находятся элементы алфавита. Набор начальных значений ячеек регистра называется секретным ключом. На каждом такте времени все эти значения смещаются на одну позицию вправо. Самое правое идет на выход — это элемент псевдослучайной последовательности. В самую левую ячейку, которая полностью освободилась, помещается значение, определяемое как линейная функция от остальных ячеек регистра, может быть, и от нее самой. Такой регистр сдвига с линейной обратной связью порождает псевдослучайную последовательность, которая идет на выход и складывается с последовательностью, которую надо зашифровать.

Если противник полностью определит псевдослучайную последовательность, перехватит какой-то ее кусок, например совпадающий с длиной регистра, то он будет знать всю дальнейшую псевдослучайную последовательность. Тогда ее можно расшифровать, что плохо. Можно подавать значения ячеек регистра на вход булевой функции (в общем случае дискретной функции). Если эта функция будет линейной, то все равно порождаемая на выходе этой функции последовательность будет линейной функцией от начальных значений регистра в начальный момент времени. Поэтому если противник перехватит какой-то кусок псевдослучайной последовательности, то он решит систему линейных уравнений, найдет начальные значения ячеек и будет знать, как расшифровать всю последовательность.

И для того, чтобы он этого не сделал, используются криптографические булевы функции, то есть булевы функции со специальными свойствами. Значит, надо булеву функцию брать не линейной, а более сложно устроенной. Причем-то, насколько более сложно устроенной, зависит от типов атак, которые противник может предпринимать на описываемую нами криптосистему.

Я описал только самый простой способ: есть один регистр, и какие-то ячейки регистра выдаются на входы булевой функции. Естественно, на практике много таких схем поточных шифров. Может использоваться несколько регистров, они комбинируются, там не одна функция, а несколько. Архитектура может быть более сложной, и в таком случае ее труднее изучать. Но это палка о двух концах, потому что если система сложная, то ее сложно изучать не только с точки зрения взлома, но и с точки зрения синтеза. Самые простейшие примитивы, регистры сдвига с одной функцией, — это важная простая модель для изучения того, что может быть в более сложных случаях.

В регистрах сдвига начальные значения выдаются на входы булевой функции. Есть много самых разных атак, которые может предпринимать противник, и все они используют разные свойства булевых функций. Например, противник может аппроксимировать эту функцию линейной: вместо этой функции в моделях исследования подставить афинную функцию, то есть в степени один (линейная плюс константа). Естественно, будет выдаваться уже другая последовательность. Но вопрос, на скольких наборах будет отличие. Потому что если отличие будет на относительно небольшом числе наборов, то, значит, на большинстве наборов будет выдаваться правильное значение. И если противник правильно определит начальное значение ячеек, например, перебором или другими методами, то он увидит корреляцию между совсем псевдослучайной последовательностью и тем, что он предположил. Эта корреляция позволяет ему предположить, что угадал он правильно. Отсюда возникает свойство булевой функции в шифрах такого типа — нелинейность.

Нелинейностью называется расстояние между функцией и классом афинных функций в степени один. Расстояние между двумя функциями — это число наборов, на которых они принимают разные значения. Значит, нелинейность — это общее число наборов, на которых функция принимает значение, отличное от данной.

Плохо, если функцию можно аппроксимировать хоть какой-то функцией в степени один, поэтому берется минимум расстояния между этой функцией и классом всех афинных функций. Этот минимум называется нелинейностью булевой функции. Поскольку важно не только число наборов, но и общее количество переменных в функции, вместо нелинейности часто используется относительная нелинейность, то есть нелинейность, делящаяся на два в степени число переменных в функции, а это и есть число наборов, на которых функция полностью определена. Относительная нелинейность — это доля наборов, на которых функция отличается от ближайшей к ней афинной функции. Чтобы не проходили известные сейчас атаки на криптосистемы, использующие булевы функции, желательно, чтобы относительная нелинейность функции была не ниже 0,45.

Важна не просто нелинейность функции, а еще и степень функции, которую часто называют алгебраической степенью. У всякой булевой функции есть полином, в данном случае он уже задан — просто представляем функцию в виде суммы мономов, произведения некоторых переменных. В русскоязычной литературе это называется полиномом Жегалкина, в англоязычной литературе — алгебраической нормальной формой. Всякая булева функция имеет единственное представление полинома Жегалкина, а значит, важный параметр — степень этой функции. Степень функции — это длина самого длинного монома в полиноме Жегалкина. Афинная функция имеет степень один, поэтому получающаяся система уравнений, если противник хочет найти начальные значения ячеек регистра, имеет степень, равную степени этой функции.

Но если степень функции не очень велика, то можно провести атаку линеаризации. Получается система уравнений, в которой каждый моном заменяется на новую переменную. Число новых переменных — это число всех возможных мономов длины, не превосходящей степени функции. Даже если функция зависит от какого-то небольшого числа переменных, то, поскольку надо установить начальное значение регистра сдвига, через несколько тактов получается уравнение, завязанное на все ячейки регистра. Поэтому практически получаются новые функции в два числа переменных, равных длине регистра. Если мы ограничимся какой-то степенью, то надо смотреть на мономы, длина которых не больше, чем степень функции. Общее число таких мономов — это сумма биномиальных коэффициентов из длины регистра по всем значениям, не превосходящим степени функции.

Получается система уравнений. Достаточно ли велика сумма биноминальных коэффициентов? Даже если функция обладает достаточно высокой степенью, то все равно эту степень можно понизить. Для этой цели пятнадцать лет назад были придуманы алгебраические атаки. Самый простой вид основывается на том, что булева функция, которая используется в регистре, домножается на другую функцию невысокой степени, при этом получается либо ноль, либо другая функция невысокой степени. Можно домножать не на саму функцию, а на ее отрицание, потому что если мы знаем функцию, то мы знаем ее отрицание.

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

Итак, я рассказал про несколько свойств: нелинейность функции, высокую алгебраическую степень, высокую алгебраическую иммунность. Есть еще несколько свойств. Например, корреляционная иммунность — это свойство, когда выход функции статистически не зависит от некоторой совокупности ее входов. Она часто применяется в случаях, когда есть не один регистр сдвига, а несколько, и каждый регистр сдвига подается на свой вход. В таком случае противник может применить атаку «разделяй и властвуй», то есть нужно в каждом регистре по отдельности перебирать начальные значения, и если угадает, то корреляция проявит себя, и это будет видно.

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

Над материалом работали

Читайте также

Внеси свой вклад в дело просвещения!
visa
master-card
illustration