Блоковые шифры

Лекция 4. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... шифр (4.2) два раза. Тогда получим: (4.5) Теперь, имея пару (ПЕРЕМЕНА, ШШЪЫТПЕЩ), Ева не может вычислить ключ, по крайней мере алгоритм ее действий не очевиден (она не может получить промежуточное значение ЧЮШЯФЫРТ, так как при его построении был использован секретный ключ, ей не известный). В представленной схеме (4.5) отдельная реализация алгоритма (4.2) называется раундом или циклом шифра. Мы проиллюстрировали влияние на стойкость шифра таких параметров, как длина ключа, размер блока, количество раундов, а также показали необходимость введения «перемешивающих» преобразований. В реальных шифрах используются, в принципе, те же преобразования, но над более длинными цепочками символов и обладающие целым рядом дополнительных свойств. Это связано с наличием развитых методов криптоанализа, таких, как дифференциальный и линейный криптоанализ, описание которых выходит за рамки нашей книги, но может быть найдено в [27]. 4.2. Блоковые шифры Блоковый шифр можно определить как зависящее от ключа K обратимое преобразование слова X из n двоичных символов. Преобразованное с помощью шифра слово (или блок) будем обозначать через Y. Для всех рассматриваемых в этом разделе шифров длина слова Y равна длине слова X. Таким образом, блоковый шифр — это обратимая функция E (другим словами, такая, для которой существует обратная функция). Конкретный вид EK этой функции определяется ключом K, Здесь обозначает дешифрующее преобразование и называется обратным шифром. Для криптографических приложений блоковый шифр должен удовлетворять ряду требований, зависящих от ситуации, в которой он используется. В большинстве случаев достаточно потребовать, чтобы шифр был стоек по отношению к атаке по выбранному тексту. Это автоматически подразумевает его стойкость по отношению к атакам по шифротексту и по известному тексту. Следует заметить, что при атаке по выбранному тексту шифр всегда может быть взломан путем перебора ключей. Поэтому требование стойкости шифра можно уточнить следующим образом. Шифр стоек (при атаке по выбранному тексту), если для него не существуют алгоритмы взлома, существенно более быстрые, чем прямой перебор ключей. Нам будет достаточно такого нестрогого определения стойкости. На самом деле, по состоянию на сегодняшний день, ни для одного используемого шифра не доказано соответствие этому определению стойкости. Реально можно говорить о следующем. Шифр считается стойким (при атаке по выбранному тексту), если для него неизвестны алгоритмы взлома, существенно более эффективные, чем прямой перебор ключей. Ниже мы приведем примеры некоторых практичеки используемых блоковых шифров. Наша задача будет состоять не только в том, чтобы дать достаточно подробное описание алгоритмов (их Стр. 3 из 13 21.03.2022, 22:15 Лекция 4. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... описание может быть найдено в литературе), но и в объяснении основных принципов построения блоковых шифров. Кроме того, наше описание может облегчить понимание материала, изложенного в официальных документах (ГОСТах и.т.п.). Далее, на протяжении всей главы, мы будем изучать технику использования блоковых шифров для решения различных задач криптографии. До недавнего времени ни одна книга по криптографии не обходилась без описания шифра DES (Data Encryption Standard). Этот шифр был принят в качестве стандарта США в 1977 году. Его основные параметры: размер блока 64 бита, длина ключа 56 бит, 16 раундов. Этот шифр интенсивно использовался более двух десятков лет и еще сегодня встречается во многих работающих системах. Несмотря на многочисленные атаки против DES, он так и не был взломан. Однако высокий уровень развития вычислительных средств позволяет сегодня вскрывать DES путем перебора ключей. Напримeр, еще в 1993 году было опубликовано техническое описание системы стоимостью в один миллион долларов, позволяющей взламывать любой ключ DES за 7 часов. В результате DES нe рекомендуется использовать во вновь создаваемых криптографических системах, и поэтому мы нe описываем этот шифр. В 2001 году после специально объявленного конкурса в США был принят новый стандарт на блоковый шифр, названный AES (Advanced Encryption Standard), в основу которого был положeн шифр Rijndael, разработанный бельгийскими специалистами. Большинство современных блоковых шифров строятся по схемам, значитeльно отличающимся от DES. Тем нe мeнee есть один действующий шифр, построенный на тех же принципах, что и DES, и представляющий для нас особый интерес. Это российский блоковый шифр ГОСТ 28147-89. Шифр ГОСТ 28147-89 Шифр ГОСТ 28147-89 [5], как следует из его обозначeния, был принят в качестве стандарта в 1989 году. Основные параметры ГОСТ 28147-89: длина ключа 256 бит, размер блока 64 бита, 32 раунда. ГОСТ 28147-89 более удобeн для программной реализации, чем DES, имеются сведения о выигрыше по времени примерно в 1.5 раза. В отличие от DES, ГОСТ 28147-89, по-видимому, нe был предметом столь глубокого анализа со стороны мирового криптологического сообщества. Тем нe мeнee, как отмечают специалисты, консервативный дизайн и величина основных параметров (длина ключа, размер блока, количество раундов) позволяют утверждать, что шифр вряд ли может быть слабым. Никаких эффективных атак против шифра ГОСТ 28147-89 нe опубликовано. В основе ГОСТ 28147-89, так же как и DES, лежит так называeмая структура Фейстела. Блок разбивается на две однаковые части, правую R и левую L. Правая часть объединяется с ключевым элементом и посредством некоторого алгоритма шифрует левую часть. Перед следующим раундом левая и правая части меняются местами. Такая структура позволяет использовать один и тот же алгоритм как для шифрования, так и для дешифрования блока. Это особенно важно при аппаратной реализации, так как прямой и обратный шифры формируются одним и тем же устройством (различается только порядок подачи элементов ключа). Перейдем к непосредственному описанию шифра ГОСТ 28147-89. Введем необходимые определения и обозначения. Последовательность из 32 бит будем называть словом. Блок текста X (64 бита), также как блок шифротекста Y, состоит из двух слов — левого L и правого R, причем L — старшее слово, а R — младшее. Секретный ключ К (256 бит) рассматривается состоящим из восьми слов К = К0К1 . . . К7. На его основе строится так называемый раундовый ключ W = W0W1 . . . W31, состоящий из 32 слов (метод построения раундового ключа будет дан позже). Для работы шифра нужны 8 таблиц S0, S1, ..., S7 Называемых также S-боксами). Каждая таблица содержит 16 четырехбитовых элементов, нумеруемых с 0 по 15. Будем обозначать через Si[j] j -й элемент i -й таблицы. ГОСТ рекомендует заполнять каждую таблицу различными числами из множества {0,1,..., 15}, переставленными случайным образом. Содержимое таблиц формирует дополнительный секретный параметр шифра, общий для большой группы пользователей. Заметим, Стр. 4 из 13 21.03.2022, 22:15 Лекция 4. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... что в DES аналогичные S-боксы фиксированы и несекретны. В шифре используются следующие операции: + сложение слов по модулю 232; циклический сдвиг слова влево на указанное число бит; побитовое «исключающее или» двух слов, т.е. побитовое сложение по модулю 2. Алгоритм 4.1. БАЗОВЫЙ ЦИКЛ ШИФРА ГОСТ 28147-89 ВХОД: Блок L, R, раундовый ключ W. ВЫХОД: Преобразованный блок L, R. (На шаге 4 алгоритма используются отдельные четырехбитовые элементы переменной k.) С помощью базового цикла осуществляется шифрование и дешифрование блока. Чтобы зашифровать блок, строим раундовый ключ (4.6) подаем на вход X и на выходе получаем Y. Чтобы дешифровать блок, строим раундовый ключ (4.7) подаем на вход Y и на выходе получаем X. Программная реализация обычно требует переработки цикла 3 алгоритма 4.1, так как работа с полубайтами неэффективна. Ясно, что то же самое преобразование может быть выполнено с использованием четырех таблиц по 256 байт или двух таблиц по 65536 полуслов. Например, при работе с байтами имеем k = (k3 . . .k0 )256, и шаги 3—4 алгоритма 4.1 переписываются следующим образом: Таблицы Tj, j = 0,1, 2, 3, вычисляются предварительно из S- боксов: Стр. 5 из 13 21.03.2022, 22:15 Лекция 4. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... ГОСТ ничего не говорит о правилах формирования ключевой информации, кроме требования, чтобы каждый S-бокс содержал перестановку различных чисел. В то же время ясно, что, например, левой ключ или тривиально заданные S-боксы (отображающие k в себя) не обеспечивают секретности шифра. 4.3. Основные режимы функционирования блоковых шифров Блоковые шифры применяются для решения многих задач криптографии. В этом разделе мы рассмотрим основные режимы их использования. В предыдущем разделе были даны примеры реальных блоковых шифров. Теперь мы можем думать о (идеализированном) блоковом шифре, как о преобразовании входного блока X в выходной блок Y с участием секретного ключа K, причем это преобразование должно иметь следующие свойства: 1) при известном Y, но неизвестном K практически невозможно узнать X; 2) при произвольных известных X и Y, но неизвестном K практически невозможно узнать K. Вначале рассмотрим классическую задачу шифрования сообщений при помощи блоковых шифров. Режим ECB Название режима ECB (Electronic CodeBook) можно перевести как электронная кодовая книга. Сообщение X разбивается на блоки X = X1,X2,... ,Xt. Каждый блок шифруется блоковым шифром Получаем зашифрованное сообщение Y = Y1, Y2,..., Yt. Дешифрование выполняется по правилу Нетрудно видеть, что дешифрование сообщения можно производить, выбирая блоки шифротекста в произвольном порядке. Такой режим удобен во многих реальных ситуациях. Например, можно работать с базой данных, хранящейся в зашифрованном виде. Однако при таком использовании одинаковые записи будут зашифрованы одинаково. Говорят, что в режиме ECB шифр сохраняет «образ данных», т.е. некий «рисунок» или шаблон, характерный для данных. Это может дать некоторую информацию противнику. Например, если количество различных записей в базе данных невелико (что нередко случается), то противник может составить словарь шифротекстов и вскрыть базу на основе частотного анализа. Заметим, что ему в этом случае не понадобится вскрывать сам шифр. Некоторые авторы рекомендуют использовать режим ECB только в случаях, когда размер отдельного элемента данных в сообщении, к которому требуется осуществлять непосредственный Стр. 6 из 13 21.03.2022, 22:15 Лекция 4. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... (прямой) доступ, меньше размера блока. Остаток блока, свободный от данных, рекомендуется заполнять случайно выбираемыми битами. Тогда даже одинаковые элементы данных будут иметь разные шифротексты. При дешифровании биты заполнения просто отбрасываются. Если размер элемента данных превышает размер блока, то часто рекомендуют использовать режим CBC. Режим CBC Название режима CBC (Cipher-Block Chaining) переводится как сцепление блоков шифра. Зашифрованное сообщение получается по следующему правилу: т.е. каждый последующий блок открытого текста предварительно закрывается предыдущим зашифрованным блоком. Слово Y0 должно быть определено заранее и известно при шифровании и дешифровании. Полученное зашифрованное сообщение можно дешифровать следующим образом: Мы получаем шифротекст, в котором каждый следующий блок зависит от предыдущих. Данный режим разрушает «образ данных». Даже если все блоки X идентичны, шифротекст будет состоять из различных блоков Y. Этот режим предпочтителен при шифровании сообщений, размер которых превышает размер блока. Однако дешифровать сообщение можно только последовательно, начиная с первого блока. 4.4. Потоковые шифры В главе 3 мы рассмотрели шифр Вернама и установили, что он является совершенно секретным, т.е. при его использовании противник, перехвативший зашифрованное сообщение, не получает никакой информации об исходном сообщении. В шифре Вернама зашифрованное сообщение y1, y2,..., yk получается из исходного сообщения x1, x2,..., xk и ключа z1, z2,..., zk при помощи операции шифрования, задаваемой равенством (4.8) Мы видели, что данный шифр совершенен только в том случае, если ключ z1, z2,..., Zk образован из независимых и равновероятных символов и используется только один раз. Это приводит к необходимости генерировать случайные последовательности очень большого объема и передавать их по закрытым каналам связи, что весьма затруднительно. Поэтому давно была высказана идея использовать в качестве ключа последовательности не случайные, а порожденные при помощи генераторов псевдослучайных чисел. В этом случае в качестве секретного ключа используется начальное значение или состояние генератора. Однако надо четко осознавать, что в этом случае система уже не будет совершенно секретной. Максимум на что мы можем надеяться, это то, что для раскрытия этой системы потребуется очень много времени например, нужно будет выполнить перебор всех возможных начальных состояний генератора). В качестве возмещения за потерю совершенности мы получаем возможность использовать короткие (обычно несколько сотен бит) секретные ключи, которые значительно проще распределять и хранить (а при использовании систем с открытым ключом их можно и вычислять). Определение 4.1. Шифр, построенный на основе (4.8), где в качестве z1, z2,..., zk используется Стр. 7 из 13 21.03.2022, 22:15 Лекция 4. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... псевдослучайная последовательность, называется потоковым шифром (stream cipher). Как правило, исходное сообщение и ключевая последовательность представляют собой нeзависимыe потоки бит. Так как шифрующее (и дешифрующее) преобразование для всех потоковых шифров одно и то же, они различаются только способом построeния гeнeраторов псевдослучайных чисел. Действительно, чтобы из шифротекста y1, y2,..., yk, полученного по формуле (4.8), восстановить сообщение x1, x2,..., xk, нeобходимо сгeнeрировать точно такую же последовательность z1, z2,..., zk, что и при шифровании, и использовать для дешифрования формулу (4.9) П р и м е р 4.1. Один из самых простых гeнeраторов псевдослучайных чисел (линейный конгруэнтный гeнeратор) работает по схеме (4.10) где a, b, c — нeкоторыe константы, а zi+1 — очередное псевдослучайное число, вычисляемое по предыдущему zi. Обязательно задается начальноe значeниe z0. Возьмем в качестве примера a = 5, b = 12, c = 23, и пусть z0 = 4. Вычислим нeсколько элементов последовательности: Полученная последовательность внeшнe выглядит как довольно случайная. Для использования в криптографических целях гeнeратор должeн удовлетворять следующим основным трeбованиям: 1) период последовательности должен быть очень большой; 2) порождаемая последовательность должна быть «почти» неотличима от действительно случайной, в частности, вычисление числа zi+1 по известным предыдущим элементам последовательность без знания ключа должно быть трудной, практически нерешаемой задачей. Рассмотренный выше линейный конгруэнтный генератор совершенно не годится для криптографических целей, так как известны простые алгоритмы, позволяющие полностью восстановить параметры генератора всего по нескольким элементам порождаемой им последовательности. В качестве примеров криптостойких генераторов псевдослучайных чисел мы рассмотрим режимы OFB и CTR блоковых шифров и алгоритм RC4. Режим OFB блокового шифра Название режима OFB (Output FeedBack) переводится как обратная связь по выходу. В этом режиме блоковый шифр на основе секретного ключа К и некоторого инициализирующего вектора Y0 формирует псевдослучайную последовательность r-битовых чисел z1, z2,..., zk, которая может использоваться в (4.8) и (4.9) соответственно для шифрования и дешифрования сообщения. Будем Стр. 8 из 13 21.03.2022, 22:15 Лекция 4. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... считать, как и ранее, что размер блока шифра равен n бит. Псевдослучайная последовательность получается по схеме (здесь r, , — параметр метода). При использовании стойкого блокового шифра можно получить криптостойкий генератор, отвечающий приведенным вьше требованиям. А именно, средняя длина периода псевдослучайной последовательности (при случайно выбранных K и Y0) составляет примерно r2n-1 бит [23]. Кроме того, псевдослучайная последовательность «непредсказуема» для противника, так как возможность предсказания (вычисления) zi+1 на основе z1,..., zi означала бы нестойкость шифра по отношению к атаке по известному тексту. Предсказание zi+1 становится даже более трудной задачей, чем взлом блокового шифра, если r < n [23]. Обратим внимание на одну особенность, характерную для всех потоковых шифров. Для шифрования каждого отдельного сообщения необходимо использовать разные K и/или Y0. В противном случае несколько сообщений будут шифроваться с помощью одних и тех же последовательностей z, и такой шифр может быть раскрыт. Поясним суть проблемы. Пусть два сообщения u1, u2,..., uk и v1, v2,..., vk зашифрованы с помощью одной и той же последовательности z. Тогда шифротексты будут иметь вид Сложим оба шифротекста и, с учетом равенства = 0, получим последовательность Мы получили аналог так называемого «шифра с бегущим ключом», когда один текст шифруется с помощью другого текста, взятого из определенного места определенной книги. Известао, что такой шифр не стоек, хотя использовался в эпоху «донаучной» криптографии [23]. Статистический анализ, основанный на избыточности текстов, позволяет в большинстве случаев достаточно точно восстановить оба сообщения. Дешифрование сообщений для описанного режима блокового шифра может производиться только с начала, так как невозможно получить произвольный элемент последовательности z, не вычислив предыдущие. В этом смысле режим аналогичен режиму CBC. Преимущество режима OFB заключается в том, что последовательность z может быть сформирована заранее для того, чтобы быстро шифровать или дешифровать сообщения с помощью (4.8), (4.9) в момент их поступления. Это может быть актуально для систем, обрабатывающих данные в реальном масштабе времени. Режим CTR блокового шифра Название данного режима происходит от слова CounTeR — счетчик. Этот режим очень похож на OFB, но в нем шифруется не предыдущий выход шифра, а просто счетчик, увеличиваемый на каждом шаге на постоянное число (обычно 1). Точнее, схема выглядит следующим образом: Стр. 9 из 13 21.03.2022, 22:15 Лекция 4. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... где r — параметр. При использовании «идеального» блокового шифра режим CTR обеспечивает те же параметры стойкости, что и OFB. Преимущество режима CTR состоит в том, что любой элемент последовательности z может быть вычислен непосредственно. Это дает возможность шифровать и дешифровать любые фрагменты сообщения независимо друг от друга. Алгоритм RC4 Алгоритм RC4, предложенный Ривестом в 1994 году, относится к классу алгоритмов, разработанных специально для потоковых шифров. Генераторы псевдослучайных чисел, построенные с помощью таких алгоритмов, как правило, значительно быстрее генераторов, основанных на блоковых шифрах. Алгоритм RC4 работает с n-битовыми словами (обычно n = 8). Все вычисления проводятся по модулю 2n (остаток x mod 2n вычисляется очень быстро путем выделения n младших бит в x с помощью логической операции «и»). RC4 использует L -словный ключ K = K0K1... KL-1 и генерирует последовательность слов Z = z1z2z3 ... , конкретный вид которой определяется ключом K. Состояние генератора задается таблицей S из 2n слов и двух переменных i и j .В каждый момент времени таблица S содержит все возможные n-битовые числа в перемешанном виде. Так как каждый элемент таблицы принимает значения в промежутке [0, 2n — 1], то его можно трактовать двояко: либо как число, либо как номер другого элемента в таблице. Секретный ключ задает только начальное перемешивание чисел в таблице, которое формируется с помощью следующего алгоритма: После этого генератор готов к работе. Генерация очередного псевдосдучанноно слова zi осуществляется следующим образом: П р и м е р 4.2. Пусть n = 3, K = 25 (L = 2). Сформируем начальную перестановку чисел в таблице S (все вычисления проводим по модулю 8): Стр. 10 из 13 21.03.2022, 22:15