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 Произведение преобразований есть последовательное их выполнение одно за другим.


 

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

6378. Захисник при перегляді судових рішень в порядку виключного провадження 77.5 KB
  Захисник при перегляді судових рішень в порядку виключного провадження План: Загальна характеристика та підстави перегляду судових рішень в порядкувиключного провадження. Поняття нововиявлених обставин та їххарактеристика. Захис...
6379. Бізнес-план в умовах ринкової системи господарювання 33.15 KB
  Бізнес-план в умовах ринкової системи господарювання Цілі: Особливості господарювання виноробних підприємств З'ясувати сутність і призначення бізнес-плану Визначити цілі розробки бізнес-плану Визначити види та о...
6380. Структура, послідовність розробки та оформлення бізнес-пл 25.77 KB
  Структура, послідовність розробки та оформлення бізнес-плану Цілі лекції: Ідентифікувати чинник, що впливають на зміст бізнес-плану. Визначити логіку опрацювання бізнес-плану. Засвоїти основні правила оформлення бізнес-плану. ...
6383. Продукт та ринок 101 KB
  Продукт та ринок З'ясувати цілі складання і визначити структуру розділу Галузь, підприємство та його продукція. Охарактеризувати зміст параграфів розділу Галузь, підприємство та його ...
6384. Маркетинг-план. Основні підрозділи маркетинг-плану 158.5 KB
  У попередньому розділі бізнес-плану був охарактеризований ринок майбутнього бізнесу і визначені його можливості. У маркетинг-плані необхідно висвітлити, як саме підприємство використовуватиме ці можливості...
6385. Виробничий план, його структура та зміст 161.5 KB
  Головне завдання виробничого плану як розділу бізнес-плану підприємства виробничого спрямування полягає в тому, щоб переконати заінтересованих фізичних та юридичних осіб (потенційних інвесторів), що підприємство...
6386. Організаційно-юридичний план 26.77 KB
  Індивідуальна підприємницька діяльність: одна особа є власником бізнесу та провадить підприємницьку діяльність без створення юридичної особи. Приватне підприємство: одна особа є власником бізнесу, веде його із залученням найманих робітників, зареєструвавшись, як юридична особа.