22234

Криптографическая система

Лекция

Информатика, кибернетика и программирование

Замыслом который стал определяющим при формировании настоящей программы Вашей подготовки стала задача ознакомления Вас с двумя наиболее сложными в теоретическом да и практическом отношении криптоаналитическими атаками позволившими в свое время найти слабости в широко известном и все еще применяемом до настоящего времени стандарте симметричного блочного шифрования США алгоритме DES. Поэтому хотя сегодня уже шифр DES можно считать уходящим со сцены представляется целесообразным изучение принципов выполнения указанных выше...

Русский

2013-08-04

256 KB

1 чел.

Лекция 1

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

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

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

Замыслом, который стал определяющим при формировании настоящей программы Вашей подготовки, стала задача ознакомления Вас с двумя наиболее сложными в теоретическом (да и практическом) отношении криптоаналитическими атаками, позволившими в свое время найти слабости в широко известном и все еще применяемом до настоящего времени стандарте симметричного блочного шифрования США алгоритме DES. Речь идет об атаках дифференциального и линейного криптоанализа, проверка устойчивости к которым сегодня считается обязательной для всех используемых и разрабатываемых шифров.

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

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

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

Тема 1. Шифр DES.

1. Общее описание алгоритма1

Стандарт шифрования данных (на английском языке Data Encrypting Standard DES) был разработан в 70-тых годах специалистами фирмы IBM по заказу NBS (Национальным бюро стандартов США), и после освидетельствования ANSI (Агенством национальной безопасности США) в 1977 году был принят в качестве федерального стандарта шифрования для защиты коммерческой и государственной информации, не связанной с национальной безопасностью. Несмотря на тщательные исследования в течение всего периода его существования и практического применения, криптосистема DES и до настоящего времени считается не скомпрометированной и широко используется для реализации различных служб безопасности в ИВС общего назначения.

Возможны четыре режима работы DES:

- ECB (Electronic Code Book) электронной кодовой книги;

- CBC (Cipherblock Chaining) сцепления блоков шифра;

- CFB (Cipher Feedback) обратной связи по криптотексту;

- OFB (Output Feedback) обратной связи по выходу.

Базовым является режим ECB. В этом режиме последовательность двоичных символов открытого текста разбивается на 64-битные блоки и затем осуществляется их независимое шифрование при помощи одного и того же 64 -битного ключа. Для шифрования используется 56 бит ключа из 64, остальные 8 используются для контроля искажений ключа.

1.2. Шифрование (режим ECB). Рассмотрим основные операции процедуры шифрования . Входной блок  из 64 двоичных символов разбивается на две равные части по 32 бита: левую  и правую . Затем осуществляется 16 циклов преобразования сообщения . Здесь запись  обозначает операцию конкатенации (объединения) блоков. Структура преобразований цикловой функции представлена на рис 1.

  

         (32 бита)             (32 бита)

                       

                        

           

               Kі

          

          

          

         СМ

       

           

     

             (32 бита)                 (32 бита)

     

левые и правые 32-битные полублоки;

48-битные двоичные последовательности (цикловые подключи), формируемые из ключа шифрования ;

  цикловая функция преобразования 32-битного слова в 32-битное;

СМ  побитный сумматор по модулю 2.

Рис 1. Цикловая функция DES.

Как следует из рис.1, в  i-том цикле слово  преобразуется в  по правилам

,

.

Здесь символ  обозначает операцию побитного суммирования по модулю 2. Схема выполнения преобразования  представлена на рис.2.

     (32 бита)

    Расширение при

помощи таблицы E

              (48 бит)

 S1    S2        S3  S4         S5   S6      S7  S8

        Перестановка

    (32 бита)

Рис.2. Схема вычисления преобразования .

Вычисление начинается с так называемого расширения, преобразующего 32 - битный полублок в 48 битный в соответствии с расширяющей таблицей  (фиксированного вида), которая фактически дополнительно вставляет копии 16 позиций. Полученные 48 бит гаммируются (побитно суммируются) с 48 битным подключем . Результат гаммирования разбивается на 8 блоков по 6 бит, поступающих на так называемые блоки . В каждом из блоков входные 6 бит заменяются на 4 выходных, причем взаимосвязи между входными и выходными символами определяется с помощью 8 фиксированных таблиц таблиц подстановок.

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

Для полного описания алгоритма DES остается отметить еще несколько деталей.

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

Из исходных 64 бит ключа  алгоритма DES для шифрования используется только 56. Практически 64 бита ключа  разбиваются на восемь 8-битных блоков. Восьмой бит каждого блока служит для контроля четности, который позволяет выявлять ошибки типа искажения нечетного числа битов (такие ошибки могут возникать при хранении или непосредственно в процессе формирования ключей) Эти контрольные биты в процессе формирования ключей не участвуют. Каждый из цикловых подключей  получается из оставшихся 56 битов ключа  с помощью операций перестановок и циклических сдвигов на соответствующее для каждого циклового подключа  число позиций.

Заметим также, что в самом конце выполнения всех 16 циклов алгоритма DES левый и правый полублоки меняются местами, так что результатом роботы алгоритма является .

1.2. Дешифрование. Алгоритм дешифрования DES достаточно очевиден: Достаточно прогнать DES с тем же ключом в обратном направлении. При этом

,

.

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

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

Наконец, алгоритм DES в режиме ECB обладает свойством так называемого размножения ошибок, которое состоит в том, что искажения одного бита криптограммы приводит к искажению нескольких (около половины) бит в открытом тексте, полученном в результате дешифрования.

1.3. Другие режимы использования DES. Для нейтрализации этих недостатков разработан специальный режим использования DES, называемый CBC (режим сцепления блоков шифра).

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

.

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

Дешифрование выполняется по алгоритму

или, что то же самое

.

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

В отличии от режимов ECB и CBC, оперирующих 64-битными блоками, режимы CFB и OFB оперируют с -битными блоками . Это, в частности, позволяет шифровать текстовые данные посимвольно (для кода EBCDIC достаточно взять , а для кода ASCII ).

Режим CFB (Обратная связь по криптотексту). В этом режиме базовый алгоритм  служит для порождения блоков псевдослучайных битов  длиной 64 бита: , , где произвольный инициирующий вектор, а  получается из  отбрасыванием (методом сдвига) первых  битов и приписыванием (заполнением) справа к блоку первых (левых)  бит блока . Блок зашифрованного сообщения передается в виде . Здесь  битов текста на і - том шаге шифрования;  соответствующие  битов открытого текста; левые  бит результата шифрования на і - том шаге; символ побитного суммирования по модулю 2.

Обратная связь по выходу. Этот режим похож на предыдущий, только для обновления  используется  вместо .

Как видно, оба рассмотренных режима использования DES с обратной связью, как и режим CBC, свободны от главного недостатка ECB: идентичным блокам открытого текста в общем случае соответствуют различные блоки криптотекста (что касается OFB, то данное утверждение верно по отношению к любым двум идентичным блокам, разделенных в открытом тексте блоками, количество которых не кратно периоду повторения, уменьшенному на единицу).

Существенным достоинством OFB является отсутствие явления размножения искажений, имевших место при передаче криптотекста в процессе дешифрования последнего. В то же время искажения одного бита -битного блока криптотекста, полученного в режиме CFB, будет влиять на -битные блоки открытого текста до тех пор, пока искаженный бит не будет вытолкнут за пределы входного 64-битного блока в результате последовательности сдвигов его содержимого, выполняемых в процессе дешифрования.

Таковы основные особенности алгоритма шифрования DES и различных режимов его использования. Кратко остановимся на вопросах применения указанных режимов для обеспечения безопасности информации, передаваемой и хранимой в ИВС. Обычно рассматриваются три области применения DES: передача данных по каналам связи (ИВС), хранение и доступ к файлам (базам данных) ИВС, а также организация системы платежей и обмена коммерческой информацией.

Считается, что для обеспечения безопасности каналов связи ИВС могут применяться все описанные выше режимы, хотя в большинстве аппаратных реализаций (плат криптографического закрытия) используется режим CFB c , обеспечивающий побитовое шифрование, Это объясняется его большей криптостойкостью по сравнению с OFB, особенно в плане криптографической поддержки бит-ориентированных протоколов, характерных для ИВС, функционирующих на основе высокоскоростных широкополосных каналов связи. Относительно недорогие платы, реализующие CFB с , обеспечивают скорость шифрования-дешифрования, достаточную для передачи данных со скоростью до 19,2 Кбит/с.

В приложения, связанных с хранением информации во внешней памяти ЭВМ, различают три основных направления применения DES: криптографическое закрытие файлов прямого и последовательного доступа, а также отдельных полей записи таких файлов.

2. Использование алгоритма DES для аутентификации сообщений.

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

Исходное сообщение  разбивается на 64-битные блоки  (если длина сообщения не кратна 64, оно дополняется справа недостающим количеством нулевых бит). Далее блок  шифруется алгоритмом DES с некоторым секретным ключом , а результат шифрования гаммируется со следующим блоком. 64-битовый блок  опять шифруется алгоритмом DES c тем же ключом  и т.д., пока не будет достигнут последний -й блок исходного сообщения. В качестве аутентификационного кода сообщения (Message Authentification Code), добавляемого к сообщению при передаче его в канал связи, используется левый полублок 64-битного блока, полученного в результате выполнения описанных операций.

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

Как можно видеть алгоритм стандарта X9.9 во многом подобен алгоритму режима CBC, однако отличается от последнего двумя особенностями. Во-первых, X9.9, имея на входе открытый текст длиной  блоков, не формирует криптотекста той же длины, как это делает CBC: из всего криптотекста берутся только левые 32 бита последнего блока. Во-вторых, X9.9 не использует начального вектора , роль которого играет первый блок исходного сообщения.

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

1 Описание шифра DES взято из работы  Барсуков В.С., Дворянкин С.В., Шеремет И.А. Безопасность связи в каналах телекоммуникаций. - М.: Россия, 1993. - Т.20, - 123 с

2 Произведение преобразований есть последовательное их выполнение одно за другим.


 

А также другие работы, которые могут Вас заинтересовать

14524. Исследование симметричных и несимметричных режимов работы трёхфазного трансформатора 567.06 KB
  Лабораторная работа По дисциплине Электроснабжение На тему Исследование симметричных и несимметричных режимов работы трёхфазного трансформатора Цель работы: Исследовать характеристики работы единичного трёхфазного трансформатора по мгновенным значениям т
14525. ИНСТИТУТЫ ЕС. ОБЩАЯ ХАРАКТЕРИСТИКА 57.11 KB
  Институты ЕС. Общая характеристика Термин Институты ЕС обозначает руководящие органы данной организации на которые возложена осуществление её основных задач. Институты ЕС одновременно выступают в качестве институтов каждого из Европейских Сообществ ЕОУС ЕЭС Евр
14526. Единая сельскохозяйственная политика Европейского союза 76 KB
  Единая сельскохозяйственная политика Европейского союза 1.Необходимость и цели ЕСХП 2.Начало ЕСХП 3.Современные реформы ЕСХП 4. Реформа сахарного режима 2005 2006 Единая сельскохозяйственная политика Европейского союза англ. Common Agricultural Policy система сельскохозя
14527. Образование Европейских сообществ и становление европейского Союза 113 KB
  Образование Европейских сообществ и становление европейского Союза 1.Исторические предпосылки и основные этапы становления Европейских сообществ Формирование Европейских сообществ и европейского права это единовременный и тесно взаимосвязанный процесс. Создани...
14528. Сущность, предпосылки, цели и эффекты интеграции 50.5 KB
  Понятие МЭИ. Объективная необходимость и историческая неизбежность МЭИ В условиях интернационализации мировой экономики растет зависимость развития каждой национальной экономики от внешних факторов. Это подтверждается ростом мирового товарооборота объемов ...
14529. Сущность, предпосылки, цели и эффекты интеграции 155.5 KB
  Сущность предпосылки цели и эффекты интеграции 1.Сущность предпосылки цели и эффекты интеграции 2.Теории международной экономической интеграции 3.Главные интеграционные группировки мира 4.Особенности интеграции в Североамериканском регионе 5.Экономическая ин
14530. Теории европейской интеграции 110 KB
  ТЕМА 1. Теории европейской интеграции 1.Понятие интеграции: проблемы дефиниции 2.Теории политической интеграции 3.Социологический подход к изучению европейской интеграции 4.Экономикотеоретический подход к изучению европейской интеграции 5.Правовой подход к изу...
14531. Европейский Суд 127.5 KB
  Европейский Суд Экономический и социальный комитет 3.Комитет регионов Европейского Союза КОР 1.Европейский Суд Европейский Суд без натяжек можно признать стержневым органом в системе институтов ЕС. Но он бы не смог стать таковым если бы не была проявлен
14532. Европейская счетная палата 127.5 KB
  I. Европейская счетная палата 1.СозданииЕвропейской счетной палаты 2.Мандатчленов Европейской счетной палаты. Полномочия. 3.СоставЕвропейской счетной палаты. 4.Организационная структура Европейской счетной палаты 5.Сотрудничествос другими институтами и организ...