foundations_chap_2 (1027396), страница 4
Текст из файла (страница 4)
Данные соображения позволяют прийти квыводу, что в большинстве случаев трудоемкость метода тотальногоопробования на качественном уровне не зависит от длины текста иопределяется только количеством возможных ключей.Не очень добросовестные производители средств шифрования данных, рекламируя свои продукты, сообщают время, необходимое длявзлома этих средств, исходя из того, что противник будет применятьименно метод тотального опробования. Однако этот метод далеко невсегда оказывается наилучшим.Вернемся к рассмотрению нашего алгоритма шифрования, длякоторого, как мы выяснили, трудоемкость дешифрования методомтотального опробования составляет несколько миллионов операций.Сделаем предположение, что противник знает значение несколькихсимволов зашифрованного сообщения (это может быть стандартныйзаголовок, адрес, обращение или служебная информация используемого редактора текстов).
В нашем примере будем считать известным,что первое слово сообщение начинается с приставки «при»: приказ,приказываю, приказание и т. д. Буквы «П», «Р», «И» идут под номерами «15», «16», «08». Следовательно, выполняются соотношения:(15 + Z1 ) mod 32 = 18, (16 + Z2 ) mod 32 = 30, (8 + Z3 ) mod 32 = 10, согласно которым первые три знака гаммы принимают значения Z1 = 3,Z2 = 14, Z3 = 2. Исходя из этой информации, криптоаналитик противника может составить систему уравнений:(Y1 + Y2 ) mod 32 = 3,(Y2 + Y3 ) mod 32 = 14,(Y3 + Y4 ) mod 32 = 2.Воспользовавшись для Y4 рекуррентным соотношением Yt = (Yt−1 +Yt−3 ) mod 32, получаем систему из трех уравнений с тремя неизвест-§ 2.1.ВВЕДЕНИЕ В ПРОБЛЕМЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ149ными:(Y1 + Y2 ) mod 32 = 3,(Y2 + Y3 ) mod 32 = 14,(Y1 + 2Y3 ) mod 32 = 2.Выразим Y1 и Y3 через Y2 , используя первое и второе уравнения:Y1 = (3 − Y2 ) mod 32,Y3 = (14 − Y2 ) mod 32.Затем, подставив результат в последнее уравнение, получим:(3 − Y2 + 28 − 2Y2 ) mod 32 = 2.Отсюда(3Y2 ) mod 32 = 29.Несложно убедиться, что последнее уравнение имеет единственное решение Y2 = 31 в диапазоне от 0 до 31.
Далее, подставив Y2 в соответствующие уравнения, получаемY1 = (−28) mod 32,Y3 = (−17) mod 32.Напомним, что для произвольного целого числа n и натурального mзначение d = n mod m определяется как такое целое число из множества {0, 1, . . . , m − 1}, что d = n + k × m при некотором целом k.Следовательно, Y1 = 4, а Y3 = 15.Таким образом, мы нашли секретный ключ Y1 = 4, Y2 = 31,Y3 = 15, проделав всего пару десятков операций вместо несколькихмиллионов, необходимых для опробования всех возможных ключей.Вернемся теперь к рассмотрению вопроса о способе измерениястойкости криптографических алгоритмов. Все алгоритмы шифрования можно разделить на три группы.К первой группе относятся совершенные шифры, заведомо неподдающиеся дешифрованию (при правильном использовании).
Примером такого шифра является шифр гаммирования случайной равновероятной гаммой.Во вторую группу входят шифры, допускающие неоднозначноедешифрование. Например, такая ситуация возникает, если зашифровать с помощью шифра простой замены, рассмотренного в начале параграфа, очень короткое сообщение.Третья группа состоит из шифров, криптограммы которых могутбыть однозначно дешифрованы. Сложность дешифрования шифра изэтой группы будет определяться трудоемкостью используемого алгоритма дешифрования. Следовательно, для оценки стойкости такогошифра необходимо рассмотреть все известные алгоритмы дешифрования и выбирать из них имеющий минимальную трудоемкость, то150КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫесть тот, который работает в данном случае быстрее всех остальных.Трудоемкость этого алгоритма и будет характеризовать стойкость исследуемого шифра.Удобнее всего измерять трудоемкость алгоритма дешифрованияв элементарных операциях, но более наглядным параметром является время, необходимое для вскрытия шифра (при этом необходимоуказывать технические средства, которые доступны криптоаналитику).
Не следует только забывать, что вполне возможно существование неизвестного на данный момент алгоритма, который может значительно снизить вычисленную нами стойкость шифра. К большому сожалению разработчиков шифрсистем, чрезвычайно редко удается строго доказать с помощью математических методов невозможность существования простых алгоритмов дешифрования. Очень хорошим результатом в криптографии является доказательство того,что сложность решения задачи дешифрования исследуемого шифраэквивалентна сложности решения какой-нибудь известной математической задачи.
Такой вывод хотя и не дает 100% гарантии, но позволяет надеяться, что в этом случае будет очень не просто существеннопонизить оценку стойкости шифра.§ 2.2. Системы блочного шифрования: DES и ГОСТВ данном параграфе мы проведем сравнительный анализ Российского стандарта на шифрование данных (ГОСТ 28147–89) и алгоритма DES (Data Encryption Standard), являвшегося на протяжении многих лет стандартом в США.В октябре 2000 года Национальным Институтом Стандартов иТехнологий (National Institute of Standards and Technologies, NIST) были подведены итоги конкурса на новый стандарт шифрования США(Advaced Encryption Standard, AES).
Победителем объявлен алгоритмРэйндал (Rijndael), созданный двумя криптографами из Бельгии —Винсентом Рэйменом (Vincent Rijmen) и Йоном Даменом (Joan Daemen). Имеются все основания полагать, что данный алгоритм получит широкое распространение в частном секторе, банковской инфраструктуре и государственных органах многих стран, став практически мировым стандартом. Однако еще довольно продолжительноевремя во всем мире будут эксплуатироваться программные и аппаратные средства защиты информации, реализующие DES.Рассматриваемые стандарты относятся к блочным шифрам, удобным для реализации на ЭВМ. В Российском стандарте шифрованияпредусмотрены 4 режима работы: шифрование данных в режиме простой замены, шифрование данных в режиме гаммирования, шифро-§ 2.2.СИСТЕМЫ БЛОЧНОГО ШИФРОВАНИЯ: DES И ГОСТ151вание данных в режиме гаммирования с обратной связью и режимвыработки имитовставки.Дадим краткое описание алгоритма шифрования в режиме простой замены Российского ГОСТа.
В этом режиме, как, впрочем, иво всех других, данные шифруются блоками по 64 бита в каждом.Шифрование заключается в 32-кратном применении процедуры, описываемой следующей общей схемой.Исходный текст разбивается на отрезки по 64 бита. Первые 32 бита заносятся в регистр N1 , а оставшиеся 32 бита заносятся в регистрN2 . Один такт работы состоит в следующем:1) производится суммирование очередного ключа из ключевогозапоминающего устройства (КЗУ) с содержимым регистра N1 по мо32дулю 2 ;2) результат суммирования преобразуется в блоке подстановки:32-х разрядный вектор разбивается на 8 последовательно идущих 4-хразрядных векторов, каждый из которых преобразуется в новый 4-хразрядный вектор соответствующим узлом замены, затем 4-х разрядные выходные векторы снова последовательно объединяются в 32-хразрядный вектор;3) полученный вектор циклически сдвигается на 11 шагов в сторону старших разрядов;4) результат сдвига складывается поразрядно по модулю два с152КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫсодержимым регистра N2 и заносится в регистр N1 , при этом содержимое регистра N1 помещается в N2 (в последнем, 32-м цикле результат суммирования заносится в регистр N2 , а значение регистра N1сохраняется старое).После 32-го цикла работы в регистрах N1 и N2 будет находитьсяблок шифрованных данных, соответствующий исходному блоку открытых данных.Длина исходного ключа в ГОСТе — 256 бит.
Из этих 256 битформируются 8 векторов по 32 бита в каждом, которые и хранятся вКЗУ. При шифровании ключи из КЗУ считываются сначала три разав прямом порядке (с нулевого по седьмой), а затем один раз в обратномпорядке.Рассмотрим теперь основные отличия шифрования по алгоритмуDES от шифрования по ГОСТу в режиме простой замены (подробноеописание DES на русском языке можно найти в [4] или [12]).Прежде всего, у алгоритма шифрования DES ключ состоит всегоиз 56 бит. Из них по определенному закону формируется 16 ключейпо 48 бит в каждом.Входной алфавит в алгоритме DES так же, как и в ГОСТе, состоит из слов длиной 64 бита.
Однако при использовании DES производится 16 циклов преобразования данных, вместо 32 в ГОСТе. Крометого, в DES используется другая функция преобразования данных (насхеме она обведена двойной рамкой). К тому же в DES эта функцияфиксирована, тогда как в тексте Российского стандарта узлы замены K1 , . . . , K8 , от которых зависит функция преобразования данных,никак не определены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
