Криптография, 04 лекция (от 22 октября)

Материал из eSyr's wiki.

Сегодня про другие шифры, хоть и относящиеся к криптосистемам с секретным ключом. Называются иногда поточными, иногда потоковыми.

Что такое потоковый шифр? Если блочный шифр оперирует большим объемом информации и шифрует целый блок, то потоковый шифр оперирует битами. Очень редко он оперирует байтами.

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

Он работает так -- у вас есть поток открытого тектса и поток ключа, потоки складываются побитово по модулю два и получаем поток шифротекста.

Было доказано таким человеком как Клод Шеннон, который первый начал изучать шифры и математизировал всю эту теорию. И он доказал, что если в шифре Вернона используется ключ, равный по длине открытому тексту и ключ выбирается _абсолютно_ случайно, и ключ используется ровно один раз, то он является абсолютно стойким.

Но это только модель, как Машина Тьюринга.

Но в реальных системах не бывает ничего абсолютно случайного. Если выбирать ключ равный длине открытого текста еще можно, то вот выбрать абсолютно случайно тяжело.

И хотелось бы иметь детерминированный алгоритм, порождающий ключевую гамму.

Возникает вопрос, а что же нам делать? Как бы нам модифицировать шифр вернона, что бы получить практическую криптосистему.

Любой классический потоковый шифр преддставляет из себя ключевой поток. Дальше этот ключевой поток складывается по модулю два с открытым текстом и получается шифрованный текст.

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

Есть ящик, кладете туда ключ, жмете кнопку, он выдает один бит. Эти биты вы используете как гамму.

Потоковый шифр вырабатывает только гамму, никаких хитрых операций с открытым текстом, как в блочных шифрах нет.

У потоковых шифров имеется небольшой недостаток -- сам по себе никак не защищает от намеренных искажений. Потоковые шифры обеспечивают только конфиденциальность. В блочных же режимах есть режимы в которые поддерживают защиту от искажений.

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

Регистры сдвига, у которых функция обратной связи является линейной называются регистрами сдвига с линейной обратной связью.

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

Старшая степень полинома равна длине регистра сдвига.

Раз регистр сдвига выраюатывает нам ключевую гамму, может так случится, что в силу конечности нашего регистра, последовательность будет периодической.

А вдруг последовательность повторится через мало тактов? Тогда наш ключ будет очень плохой, мы получим неслучайную последовательность.

Нам бы хотелось иметь такой регистр сдвига, чтобы период этой последовательности был максимальный. И тут возникает вопрос -- а как сделать так, чтобы период был максимальный? Как вообзе определить период регистра сдвига?

Чтобф ответить на вопрос о максимальном, обратимся к состояниям регистра. С какого момента гамма начинает повторяться? Когда вы попадете в сотояние, в которое уже попадали. Максимальный период вашей последовательности может быть какой? 2^(lдлина регистра) - 1.

Посмотрим на пример s0*s1 + s2. Характеристический многочлен 1 + x² + x³ 000 -> 000

В случае нелинейного ристра период мало предсказуем.

Зато в случе линейного есть предположение -- для того, чтобы он имел максимальный период, его характеристический многочлен должен быть неприводим над гф2.

F(x) = x² + x³

001->011->111->111

а если такое F(x) = x² + x³ + 1

001->011->111->110->101->010->100->001

На самом деле, непривоимости многочленов недостаточно.

Надо, чтобы многочлен был примитивен.

Докажите, что 1+x+x^4 не будет иметь максимального периода.

Чтоже такое примтивный полином?

Сначала нужно дать такое определение -- задать порядок многочлена. Порядок многочлена -- такое минимальнео число н, что многчлен x^n - 1 делится на F(x).

Мы не вдаемся в дебри конечны полей, но там этот порядок -- достаточно важная характеристика.

Многочлен называется примитивным, елси его порядок равен 2^n - 1.

Можно доказать, что любой неприводимый многочлен делит многочлен ....

GF(p) = 1,2,3,...,p − 1

p - простое

a+b mod p a*b mod p

deg f(x) = n

И пусть у него не будет корней в этом поле.

GF(2) \or \alpha = {\a + b \a + c \a^2 + d \a^3}

Полином называется примитивным, если через вот это альфа можно выразить все сотавшиеся элементы поля.

Если вы возьмете полином, который не примитивный, то все не выстроится в цепочку.

Взяли регистр сдвига, забабахали нолики и единички, взяли примтивный многочлен, он задал правила функционирования.

Можно доказать, что последовательность образующаяся на одном регистре сдвига почти случайная.

Если вы возьмете н=256, то период будет 2^256. То есть пи маленькой длине регистра можно получить случайную последовательность нереальной длины. Но тут имеется подвох.

Полином, фактически, является ключом.

Все было бы хорошо, если бы два еловека нам не нагадили, и не придумали адлгоритм, который бы по небольшому куску последовтельности восстаналивал регистр. Звали их Берлекэмп и Месси.

Алгоритм Берлекэмп-Месси.

Он классика, используется много где.

Демонстрация работы алгоритма берлекампа месси.

Наконец мы пришли к самому интересному.

Идея использовать регистры с обратной связью провалилась. Что делать? Как жить дальше?

В чем проблема в нашем регистре? Он почти везде линеен. Надо ввести нелинейность.

Давайте фделаем фильтр. Будем выдавать не саму гамму, а некую нелинейную функцию от гаммы. Другая идея -- использовать другие виды нелинейности

В чем идея?

У нас есть любимый линейный регистр сдвига, но гамма не выбрасиывается из левой ячейки, а является некоей нелинейной функцией от состояния. То есть, из состони в состояние переходим линейно, но гамму считаем нелинейной функцией от состояния. Есть развитие этой идеи.

Есть нелинейная функция от эн переменных. И каждая из переменных продуцируется отдельным регистром сдвига.

Можно доказать, что первый вариант сводится ко второму.

Итак, когда был просто регистр, последовательность была почти случайной. Пустили через фильтр. Кто сказал, что последовательность будет случайной?

Какие требования надо предъявить к филььтрующей функции, ятобы фильт был хорош?

1. У нее должно быть одинаковое число единиц и нулей.
1. Кроме того, эта функция не должна быть линейной. Хначит она должна задаваться полиномом достаточно выской степени. Можно обощить понятие линейности. Вектора булевых функций можно сравнивать и считать
расстояний между ними. Можем определить расстояние некоторой функции до множества линейных функций. Нам нужно обеспечить, чтобы это расстояние было максимальным. Функции, которые максимально удалены от
линейных называются максимально нелинейными, или, как их иногда называют бент-функции (для функций с четным числом входов).

Какое может быть максимальное расстояние?

max = ρ(f,A) Рассмотрим преобразование Молоша Адамара -- разложение по базису ортогональных функций.

Максимум расстояния 2ⁿ − 2⁽n / 2) если н четное. Функции, на которых достигается максимум, называются бент-функциями.

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

Давайте в функции вместо переменных подставим константу. Если новая функция будет неуравновешена, то вы можете провести атаку, подставив на нужные переменные нули и пытаясь вытащить корелляции.

Например, если в виде фильтрующей функции такая x*y \xor x*z \xor z. z = 1 = > !x&y

f(x,y,z) = z с вероятностью 3/4. И с той же веротяностью равна иксу.

А это означает, что вы можете перебрать значения только икса. И у вас есть детектор угадывания -- веротяность 3/4 совпадений. Так же можете восстановить регистр z. Комбинированием потом можно восстановить игрек.

Таки атаки называются корелляционными. Сложность там очень сильно падает. Если мощностьи регистров были н1 н2 н3, то полным перебором будет 2⁽n1 + n2 + n3), то тут перебор будет2ⁿ1 + 2ⁿ2 + 2ⁿ3

Плохие шифры можно псомтреть зайдя на https:\\mail.ru

Если пользоваться хромом, то оно показывает замочек, и там в описании сказано, что соединение защищено rc4 128. Шифр rc4 является потоковым, егонедавно ломанули и сейас он является небезопасным.