close

Вход

Забыли?

вход по аккаунту

?

OVSYAN Burova 1

код для вставкиСкачать
Федеральное агентство связи
Государственное федеральное образовательное учреждение
высшего профессионального образования
ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ
ЭЛЕКТРОННАЯ
БИБЛИОТЕЧНАЯ СИСТЕМА
Самара
3
Федеральное агентство связи
Государственное образовательное учреждение высшего профессионального
образования
«Поволжский государственный университет телекоммуникаций и
информатики»
____________________________________________________________________
_______
Кафедра информационных систем и технологий
А.С.Овсянников
М.А.Бурова
ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ И ЗАЩИТА ИНФОРМАЦИИ В
КОМПЬЮТЕРНЫХ СИСТЕМАХ
Часть 1
Основы криптографии
УЧЕБНОЕ ПОСОБИЕ
САМАРА 2011
4
УДК 681.3.06
ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ И ЗАЩИТА ИНФОРМАЦИИ В
КОМПЬЮТЕРНЫХ СИСТЕМАХ. ЧАСТЬ 1 Основы криптографии: Учебное
пособие / А.С. Овсянников, М.А. Бурова. - Самара: ПГУТИ, 2011. – 113 с.
Приведены основные понятия и определения информационной
безопасности в компьютерных системах.
Изложены классические методы блочного и потокового шифрования,
рассмотрены стандарты шифрования DES; ГОСТ 28147-89 и система
криптозащиты сообщений PGP.
Рассчитано на студентов ФИСТ ПГУТИ очной и заочной форм обучения,
обучающихся по специальности ―Информационные системы и технологии‖ и
изучающих дисциплину ―Информационная безопасность и защита информации
в компьютерных системах‖ в рамках лекционных и лабораторных занятий.
Разработано на кафедре информационных систем и технологий.
Может быть рекомендовано для студентов, обучающихся по
направлениям ―Информационные системы‖ и ―Информатика и вычислительная техника‖
Рецензенты:
Д.т.н., проф., зав. кафедрой ИСТ СамГУПС А.М. Косолапов
к.т.н, доцент кафедры СС ПГУТИ И.И. Корнилов
УДК 681.3.06
© ПГУТИ, 2011
5
ПРЕДИСЛОВИЕ
Предварительно, в первой лекции приводятся основные понятия и положения информационной безопасности: предмет и объект защиты; ценность и
стоимость информации, категории конфиденциальности государственной и
коммерческой информации. Даны основные методы оценки количества информации: энтропийный (по Шеннону); тезаурусный и практический. Дают-ся
определения фундаментальным понятиям теории и практики информа-ционной
безопасности: компьютерная система и система защиты информа-ции.
В материалах последующих лекций рассматриваются: традиционные
методы блочного шифрования; основы поточного (потокового) шифрования:
одноключевые и двухключевые (с открытым ключом) криптосистемы.
Приводятся основы построения симметричных криптосистем – принцип
итерирования и конструкция Фейстеля. Достаточно подробно рассмотрены
американский стандарт шифрования DES и стандарт России ГОСТ 28147-89.
Глубоко представлены режимы шифрования блочных шифров и в частности
шифров стандарта DES.
Рассмотрены основные атаки на блочные шифры: классический
дифференциальный криптоанализ и дифференциальный криптоанализ на основе отказов устройств. Приводится суть и результаты силовой атаки на основе
распределѐнных вычислений.
Даѐтся определение понятия надѐжности криптосистем и рассматриваются причины ненадѐжных криптосистем.
6
1 Основные понятия и определения
Вступление человечества в XXI век знаменуется бурным развитием
информационных технологий во всех сферах общественной жизни.
Информация все в большей мере становится стратегическим ресурсом
государства, производительной силой и дорогим товаром. Это не может не
вызывать стремления государств, организаций и отдельных граждан получить
преимущества за счет овладения информацией, недоступной оппонентам, а
также за счет нанесения ущерба информационным ресурсам противника (конкурента) и защиты своих информационных ресурсов.
Значимость обеспечения безопасности государства в информационной
сфере подчеркнута в принятой в сентябре 2000 года «Доктрине
информационной безопасности Российской Федерации» [1]: "Национальная
безопасность Российской Федерации существенным образом зависит от
обеспечения информационной безопасности, и в ходе технического прогресса
эта зависимость будет возрастать".
Остроту межгосударственного информационного противоборства можно
наблюдать в оборонной сфере, высшей формой которой являются
информационные войны. Элементы такой войны уже имели место в локальных
военных конфликтах на Ближнем Востоке и на Балканах. Так, войскам НАТО
удалось вывести из строя систему противовоздушной обороны Ирака с
помощью информационного оружия. Эксперты предполагают, что войска альянса использовали программную закладку, внедренную заблаговременно в
принтеры, которые были закуплены Ираком у французской фирмы и
использовались в АСУ ПВО.
Не менее остро стоит вопрос информационного противоборства и на
уровне организаций, отдельных граждан. Об этом свидетельствуют
многочисленные попытки криминальных элементов получить контроль над
компьютерными технологиями для извлечения материальной выгоды.
Достаточно привести в качестве примера случаи шантажа английских фирм
преступной международной группой. За 1993-1996 годы преступники получили
400 миллионов фунтов стерлингов. Жертвам приходилось выплачивать до 13
миллионов фунтов стерлингов единовременно после демонстрации
шантажистами своих возможностей остановить все сделки или получить доступ
к новейшим разработкам фирм. Деньги переводились в банки, расположенные в
оффшорных зонах, откуда преступники снимали их в считанные минуты.
Важно также обеспечить конституционные права граждан на получение
достоверной информации, на ее использование в интересах осуществления
законной деятельности, а также на защиту информации, обеспечивающую
личную безопасность.
Противоборство государств в области информационных технологий,
стремление
криминальных
структур
противоправно
использовать
информационные ресурсы, необходимость обеспечения прав граждан в
7
информационной сфере, наличие множества случайных угроз вызывают острую
необходимость обеспечения защиты информации в компьютерных системах
(КС), являющихся материальной основой информатизации общества.
Проблема обеспечения информационной безопасности на всех уровнях
может быть решена успешно только в том случае, если создана и
функционирует комплексная система защиты информации, охватывающая весь
жизненный цикл компьютерных систем от разработки до утилизации и всю
технологическую цепочку сбора, хранения, обработки и выдачи информации.
Вопросы построения и организации функционирования такой системы защиты
рассматриваются в настоящем учебном пособии. Оно позволит выработать у
читателей целостный, системный взгляд на проблему защиты информации в
компьютерных системах.
Предметом защиты является информация.
В Федеральном законе РФ «Об информации, информатизации и защите
информации», принятом 25 января 1995года Государственной Думой [2],
определено, что «информация - сведения о лицах, предметах, фактах, событиях,
явлениях и процессах, независимо от формы их представления» Информация
имеет ряд особенностей:
♦ она нематериальна;
♦ информация хранится и передается с помощью материальных носителей;
♦ любой материальный объект содержит информацию о самом себе или о
другом объекте.
Нематериальность информации понимается в том смысле, что нельзя
измерить ее параметры известными физическими методами и приборами.
Информация не имеет массы, энергии и т. п.
Информация хранится и передается на материальных носителях. Такими
носителями являются мозг человека, звуковые и электромагнитные волны,
бумага, машинные носители (магнитные и оптические диски, магнитные ленты
и барабаны) и др.
Информации присущи следующие свойства.
1. Информация доступна человеку, если она содержится на материальном
носителе. Поэтому необходимо защищать материальные носители
информации, так как с помощью материальных средств можно защищать
только материальные объекты.
2. Информация имеет ценность. Ценность информации определяется степенью
ее полезности для владельца. Обладание истинной (достоверной) информацией
дает ее владельцу определенные преимущества. Истинной или достоверной
информацией является информация, которая с достаточной для владельца
(пользователя) точностью отражает объекты и процессы окружающего мира в
определенных временных и пространственных рамках.
Информация,
искаженно
представляющая
действительность
(недостоверная информация), может нанести владельцу значительный
материальный и моральный ущерб. Если информация искажена умышленно, то
ее называют дезинформацией.
8
Законом «Об информации, информатизации и защите информации»
гарантируется право собственника информации на ее использование и защиту
от доступа к ней других лиц (организаций). Если доступ к информации
ограничивается, то такая информация является конфиденциальной.
Конфиденциальная информация может содержать государственную или
коммерческую тайну. Коммерческую тайну могут содержать сведения,
принадлежащие частному лицу, фирме, корпорации и т. п. Государственную
тайну могут содержать сведения, принадлежащие государству (государственному учреждению). В соответствии с законом «О государственной тайне»
[3] сведениям, представляющим ценность для государства, может быть
присвоена одна из трех возможных степеней секретности. В порядке
возрастания ценности (важности) информации ей может быть присвоена
степень (гриф) «секретно», «совершенно секретно» или «особой важности». В
государственных учреждениях менее важной информации может присваиваться
гриф «для служебного пользования».
Для обозначения ценности конфиденциальной коммерческой информации
используются три категории:
♦ «коммерческая тайна - строго конфиденциально»;
♦ «коммерческая тайна - конфиденциально»;
♦ «коммерческая тайна».
Используется и другой подход к градации ценности коммерческой
информации:
♦ «строго конфиденциально - строгий учет»;
♦ «строго конфиденциально»;
♦ «конфиденциально».
Как правило, со временем ценность информации уменьшается.
Зависимость ценности информации от времени приближенно определяется в
соответствии с выражением:
C(t) = С0 е -2,3 t/
(1.1)
где
Со - ценность информации в момент ее возникновения (получения);
t - время от момента возникновения информации до момента определения
ее стоимости;
 - время от момента возникновения информации до момента ее
устаревания.
Время, через которое информация становится устаревшей, меняется в
очень широком диапазоне. Так, например, для пилотов реактивных самолетов,
автогонщиков информация о положении машин в пространстве устаревает за
доли секунд. В то же время информация о законах природы остается
актуальной в течение многих веков.
Информацию правомочно рассматривать как товар, имеющий определенную цену. Цена, как и ценность информации, связаны с полезностью
информации для конкретных людей, организаций, государств. Информация
9
может быть ценной для ее владельца, но бес полезной для других. В этом
случае информация не может быть товаром, а, следовательно, она не имеет и
цены. Например, сведения о состоянии здоровья обычного гражданина
являются ценной информацией для него. Но эта информация, скорее всего, не
заинтересует кого-то другого, а, следовательно, не станет товаром, и не будет
иметь цены.
Информация может быть получена тремя путями:
♦ проведением научных исследований;
♦ покупкой информации;
♦ противоправным добыванием информации.
Как любой товар, информация имеет себестоимость, которая
определяется затратами на ее получение. Себестоимость зависит от выбора
путей получения информации и минимизации затрат при добывании
необходимых сведений выбранным путем. Информация добывается с целью
получения
прибыли
или
преимуществ
перед
конкурентами,
противоборствующими сторонами. Для этого информация:
продается на рынке;
 внедряется в производство для получения новых технологий и товаров,
приносящих прибыль;
 используется в научных исследованиях;
 позволяет принимать оптимальные решения в управлении.
Существует несколько подходов к измерению количества информации.
А. Энтропийный подход.
В прикладной теории информации количество информации оценивается
мерой уменьшения у получателя неопределенности (энтропии) выбора или
ожидания событий после получения информации. Количество информации тем
больше, чем ниже вероятность события. Энтропийный подход широко
используется при определении количества информации, передаваемой по
каналам связи. Выбор при приеме информации осуществляется между
символами алфавита в принятом сообщении. Пусть сообщение, принятое по
каналу связи, состоит из N символов (без учета связи между символами в
сообщении) какого либо языка. Тогда количество информации в сообщении
может быть подсчитано по формуле Шеннона [4]:
k
I   N  pi log pi ,
(1.2)
i 1
где
pi - вероятность появления в сообщении символа i;
- количество символов в алфавите языка.
Анализ формулы Шеннона показывает, что количество информации в
двоичном представлении (в битах или байтах) зависит от двух величин:
количества символов в сообщении и частоты появления того или иного символа
в сообщениях для используемого алфавита. Этот подход абсолютно не
отражает насколько полезна полученная информация, а позволяет определить
лишь затраты на передачу сообщения.
k
10
Б. Тезаурусный подход.
Этот подход предложен Ю.А. Шрейдером [5]. Он основан на
рассмотрении информации как знаний. Согласно этому подходу количество
информации, извлекаемое человеком из сообщения, можно оценить степенью
изменения его знаний.
Структурированные знания, представленные в виде понятий и
отношений между ними, называются тезаурусом.
Структура тезауруса иерархическая. Понятия и отношения, группируясь,
образуют другие, более сложные понятия и отношения.
Знания
отдельного
человека,
организации,
государства
образуют
соответствующие тезаурусы. Тезаурусы организационных структур образуют
тезаурусы составляющих их элементов. Так тезаурус организации образуют,
прежде всего, тезаурусы сотрудников, а также других носителей информации,
таких как документы, оборудование, продукция и т. д.
Для передачи знаний требуется, чтобы тезаурусы передающего и
принимающего элемента пересекались. В противном случае владельцы
тезаурусов не поймут друг друга.
Тезаурусы человека и любых организационных структур являются их
капиталом. Поэтому владельцы тезаурусов стремятся сохранить и увеличить
свой тезаурус. Увеличение тезауруса осуществляется за счет обучения, покупки
лицензии, приглашения квалифицированных сотрудников или хищения
информации.
В обществе наблюдаются две тенденции: развитие тезаурусов отдельных
элементов (людей, организованных структур) и выравнивание тезаурусов
элементов общества.
Выравнивание тезаурусов происходит как в результате целенаправленной
деятельности (например, обучения), так и стихийно. Стихийное выравнивание
тезаурусов происходит за счет случайной передачи знаний, в том числе и
незаконной передачи.
В. Практический подход.
На практике количество информации измеряют, используя понятие
«объем информации». При этом количество информации может измеряться в
количестве бит (байт), в количестве страниц текста, длине магнитной ленты с
видео- или аудиозаписью и т.п. Однако очевидно, что на одной странице
информации может содержаться больше или меньше, по крайней мере, по двум
причинам. Во-первых, разные люди могут разместить на странице различное
количество сведений об одном и том же объекте, процессе или явлении
материального мира. Во-вторых, разные люди могут извлечь из одного и того
же текста различное количество полезной, понятной для них информации. Даже
один и тот же человек в разные годы жизни получает разное количество
информации при чтении книги.
В результате копирования без изменения информационных параметров
носителя количество информации не изменяется, а цена снижается. Примером
11
копирования без изменения информационных параметров может служить
копирование текста с использованием качественных копировальных устройств.
Текст копии, при отсутствии сбоев копировального устройства, будет содержать точно такую же информацию, как и текст оригинала. Но при
копировании изображений уже не удастся избежать искажении. Они могут
быть только большими или меньшими.
В соответствии с законами рынка, чем больше товара появляется, тем он
дешевле. Этот закон полностью справедлив и в отношении копий информации.
Действие этого закона можно проследить на примере пиратского
распространения программных продуктов, видеопродукции и т. п.
В качестве предмета защиты рассматривается информация, хранящаяся,
обрабатываемая и передаваемая в компьютерных системах. Особенностями
этой информации являются:
♦
двоичное представление информации внутри системы, независимо от
физической сущности носителей исходной информации;
♦ высокая степень автоматизации обработки и передачи информации;
♦ концентрация большого количества информации в КС.
Объектом защиты информации является компьютерная система или
автоматизированная система обработки данных (АСОД). В работах,
посвященных защите информации в автоматизированных системах, до
последнего времени использовался термин АСОД, который все чаще
заменяется термином КС. Что же понимается под этим термином?
Компьютерная система - это комплекс аппаратных и программных
средств, предназначенных для автоматизированного сбора, хранения,
обработки, передачи и получения информации. Наряду с термином
«информация» применительно к КС часто используют термин «данные».
Используется и другое понятие - «информационные ресурсы». В соответствии
с законом РФ «Об информации, информатизации и защите информации» под
информационными ресурсами понимаются отдельные документы и отдельные
массивы документов в информационных системах (библиотеках, архивах,
фондах, банках данных и других информационных системах).
Понятие КС очень широкое и оно охватывает следующие системы:
♦ ЭВМ всех классов и назначений;
♦ вычислительные комплексы и системы;
♦ вычислительные сети (локальные, региональные и глобальные).
Такой широкий диапазон систем объединяется одним понятием по двум
причинам: во-первых, для всех этих систем основные проблемы защиты
информации являются общими; во-вторых, более мелкие системы являются
элементами более крупных систем. Если защита информации в каких-либо
системах имеет свои особенности, то они рассматриваются отдельно.
Предметом защиты в КС является информация. Материальной основой
существования
информации
в
КС
являются
электронные
и
электромеханические устройства (подсистемы), а также машинные носители. С
помощью устройства ввода или системы передачи данных (СПД) информация
12
попадает в КС. В системе информация хранится в запоминающих устройствах
(ЗУ) различных уровней, преобразуется (обрабатывается) процессорами (ПЦ) и
выводится из системы с помощью устройств вывода или СПД. В качестве
машинных носителей используются бумага, магнитные ленты, диски
различных типов. Ранее в качестве машинных носителей информации
использовались бумажные перфокарты и перфоленты, магнитные барабаны и
карты. Большинство типов машинных носителей информации являются
съемными, т.е. могут сниматься с устройств и использоваться (бумага) или
храниться (ленты, диски, бумага) отдельно от устройств.
Таким образом, для защиты информации (обеспечения безопасности
информации) в КС необходимо защищать устройства (подсистемы) и
машинные носители от несанкционированных (неразрешенных) воздействий на
них.
Однако такое рассмотрение КС с точки зрения защиты информации
является неполным. Компьютерные системы относятся к классу человекомашинных систем. Такие системы эксплуатируются специалистами
(обслуживающим персоналом) в интересах пользователей. Причем, в последние
годы пользователи имеют самый непосредственный доступ к системе. В
некоторых КС (например, ПЭВМ) пользователи выполняют функции
обслуживающею персонала. Обслуживающий персонал и пользователи являются также носителями информации. Поэтому от несанкционированных
воздействий необходимо защищать не только устройства и носители, но также
обслуживающий персонал и пользователей. При решении проблемы защиты
информации в КС необходимо учитывать также противоречивость
человеческого фактора системы. Обслуживающий персонал и пользователи
могут быть кик объектом, так и источником несанкционированного воздействия на информацию.
Понятие «объект защиты» или «объект» чаще трактуется в более
широком смысле. Для сосредоточенных КС или элементов распределенных
систем понятие «объект» включает в себя не только
информационные
ресурсы, аппаратные, программные средства, обслуживающий персонал,
пользователей, но и помещения, здания, и даже прилегающую к зданиям
территорию. Одними
из основных понятий теории защиты информации
являются понятия «безопасность информации» и «защищенные КС».
Безопасность (защищенность) информации в КС - это такое состояние всех
компонент компьютерной системы, при котором обеспечивается защита
информации от возможных угроз на требуемом уровне. Компьютерные
системы, в которых обеспечивается безопасность информации, называются
защищенными.
Безопасность информации в КС (информационная безопасность) является
одним из основных направлений обеспечения безопасности государства,
отрасли, ведомства, государственной организации или частной фирмы.
Информационная безопасность достигается проведением руководством
соответствующего уровня политики информационной безопасности. Основным
13
документом, на основе которого проводится политика информационной
безопасности, является программа информационной безопасности. Этот
документ разрабатывается и принимается как официальный руководящий документ высшими органами управления государством, ведомством,
организацией. В документе приводятся цели политики информационной
безопасности и основные направления решения задач защиты информации в
КС. В программах информационной безопасности содержатся также общие
требования и принципы построения систем защиты информации в КС.
Под системой защиты информации в КС понимается единый
комплекс правовых норм, организационных мер, технических,
программных
и
криптографических
средств,
обеспечивающий
защищенность информации в КС в соответствии с принятой политикой
безопасности.
Этапы передачи информации
Рассмотрим рисунок [4].
I I
Информация
Источник
II
Сообщение
Преобразо
ватель I
Преобразо
ватель II
III
Сигнал
III
Поме хи
Сигнал
Канал
II
Cообщение
Преобразо
ватель II
*
II
Информация
Преобразователь I
Получатель
Рис. 1.1  Основные преобразования информации при ее передаче
от источника к получателю
Источником информации может быть природа, человек, ЭВМ и т.д. С
помощью преобразователя, функции которого выполняет «Преобразователь I»
(кодирующее ―устройство‖ источника), информация преобразуется в сообщение
в виде данных (символах какого-либо ―языка‖, алфавита). Сообщение может
представлять собой результаты наблюдения естественного явления, устные или
письменные фразы, последовательность двоичных символов и т.д. Часть
информации может быть несущественна (не нужна) получателю. Допустимы
также небольшие искажения, которые являются критерием точности работы
преобразователя I (а также выбора алфавита, языка).
Источник и получатель
разделены в пространстве (при передаче
информации на расстояние) или во времени (при хранении информации).
Система передачи, способная преодолеть это разделение, называется каналом
связи.
Процесс передачи или хранения информации в канале может быть основан
на самых разнообразных физических принципах (электромагнитных явлениях,
механических законах и т.д.). Поэтому для согласования источника (или
преобразователя I) c каналом сообщение преобразуется преобразов-ателем II
в сигнал той природы, на которой основана передача или хранение
14
информации. Сигнал «несет» сообщение, содержащее информацию. Кроме
того, в этом преобразователе, для защиты информации, может осуществляться
шифрование сообщения.
Сформированный таким образом сигнал поступает на вход канала, по
которому он доставляется к получателю. При прохождении канала сигнал
подвергается воздействию помех и искажается в силу неидеальности самого
канала, что приводит к искажению сигнала и, в конечном счѐте, к потере части
информации. Канал, по определению, распределѐнная в пространстве система,
что позволяет злоумышленникам с наименьшими потерями перехватить сигнал,
преобразовать и получить информацию. Следовательно, передача сигнала по
каналу является наиболее уязвимым этапом с точки зрения информационной
безопасности.
После прохождения канала сигнал подвергается преобразованиям в
обратном порядке с целью представления информации получателю в
необходимом для его восприятия виде.
Контрольные вопросы
1. Охарактеризуйте информацию и ее свойства.
2. Что является объектом и предметом защиты информации?
3. Дайте краткую характеристику основных способов оценки информации.
4. Перечислите градации конфиденциальности информации для государственных и частных предприятий
5. Какой этап передачи информации от источника к получателю является
наиболее уязвимым для перехвата информации злоумышленником.
15
2 БЛОЧНЫЕ ШИФРЫ.
2.1 Определение блочного шифра
В настоящее время особенно быстрыми темпами, но все еще отставая от
мирового уровня, осуществляется компьютеризация всей нашей страны в целом
и, в том числе, многочисленных государственных и коммерческих организаций,
учреждений и банков, эффективная деятельность которых немыслима без
использования вычислительной техники. Однако, кроме очевидных выгод,
компьютеризация принесла с собой целый ряд проблем. Одна из таких
проблем, причем наиболее сложная, состоит в обеспечении безопасности конфиденциальной информации в системах обработки и передачи данных.
Для решения этой проблемы широко применяются криптографические
методы защиты информации, к которым относятся — специальное
шифрование, кодирование или иное преобразование данных, в результате
которого их содержимое становится недоступным для получения информации
без предъявления некоторого специального ключа и обратного преобразования.
Криптографическое преобразование защищаемых данных является наиболее
эффективным и универсальным, а при передаче по протяженным линиям связи
— единственно реальным средством предотвращения несанкционированного
доступа к ней. Сообщение от одного абонента к другому посылается по
незасекреченному каналу связи, в котором оно может быть перехвачено
злоумышленником с помощью подслушивания, изъятия корреспонденции и т.
п. Практически невозможно обеспечить безопасность такого канала связи, и,
следовательно, возможен перехват всех передаваемых сообщений. Картина
будет одинаковой, пересылаем ли мы сообщение с курьером, почтальоном или
по электронной почте. Первоочередные цели злоумышленника при этом —
нарушить секретность связи и извлечь, выгоду из тайной информации. При
этом он преследует далеко идущие цели, которые могут быть выполнены
следующим образом.
 Изменение сообщения, запутав при этом получателя недостоверным
текстом.
 Обман получателя, назвав имя ложного отправителя
 Обман отправителя, идентифицировав себя в качестве получателя,
захватив все сообщение, например, и не переслав его законному получателю.
16
Рис. 2.1 - Криптографические системы с использованием ключей.
Во всех этих случаях большим преимуществом пользователей было бы то
обстоятельство, если бы противоборствующая сторона не понимала смысла
перехваченных сообщений. Для этих целей может быть использован некоторый
метод шифрования.
Сообщение в его оригинальной форме может быть представлено им как
исходный текст. Затем отправитель зашифровывает данный текст. Результатом
этого будет криптотекст, который теперь может быть послан через ненадежный
(обычный) канал связи. Наконец, получатель расшифровывает поступивший к
нему криптотекст, после чего он получает исходное сообщение. Таким образом,
действия отправителя: зашифрование исходного текста и получение
криптотекста, а действия получателя обратные: расшифрование криптотекста и
получение исходного текста.
Построение современных криптографических систем защиты информации основано на использовании различных методов шифрования информационных сообщений. Эти методы, в свою очередь, подразделяются по характеру применения ключей шифрования. При этом под ключом понимается
секретное состояние (значение) некоторых параметров алгоритма
криптопреобразования конфиденциальных сообщений.
По характеру использования ключа криптографические системы
подразделяются (рис. 2.2) на одноключевые (симметричные, с секретным
ключом), двухключевые (несимметричные, с открытым или несекретным
ключом) и составные (комбинация симметричных и несимметричных).
Поскольку представленные на рис. 2.2 криптографические системы существенным образом отличаются друг от друга принципами функционирования,
остановимся на них более подробно.
17
Одноключевые криптографические системы являются классическими
системами защиты информации. Для шифрования и расшифрования текста
информационных сообщений в них используется один и тот же секретный ключ
Zc, сохранение которого в тайне обеспечивает надежность защиты информации.
Структурная схема одноключевой криптографической системы представлена на
рис. 2.3.
Процесс шифрования и расшифрования в данной системе можно
представить следующим образом:
Y=Ezc(X), X=Dzc(Y)=Dzc(Ezc(X))
(2.1)
где X — открытый текст (до шифрования и после расшифрования);
Y — зашифрованный текст;
Zc — секретный ключ, известный отправителю и получателю сообщения;
Ezc — функция шифрования;
Dzc — функция расшифрования.
Рис. 2.3 - Структурная схема одноключевой криптографической системы
При этом для взаимной однозначности шифрования и расшифрования
необходимо выполнение равенства:
Ezc Dzc=e,
(2.2)
где е — единичное преобразование.
Все известные одноключевые криптографические системы подразделяются по
методам шифрования на блочные (блоковые), поточные (потоковые) и
комбинированные (рис. 2.4).
18
Рис. 2.4 - Методы шифрования в одноключевых криптографических системах
В связи с тем, что открытый текст сообщения обычно имеет
произвольную длину, иногда достаточно большую, то он разбивается на более
мелкие блоки фиксированной длины. Тексты этих блоков шифруются отдельно
и независимо друг от друга.
Криптографическое преобразование составляет основу любого блочного
шифра Прямое криптографическое преобразование (шифрование) переводит
блок открытого текста в блок шифротекста той же длины. Обратное
криптографическое преобразование (дешифрование) переводит блок
шифротекста в исходный блок открытого текста. Необходимое условие выполнения как прямого, так и обратного криптографического преобразования
наличие секретного ключа.
Шифры, в которых прямое и обратное преобразования выполняются
над блоками фиксированной длины, называются блочными.
Для многих блочных шифров разрядность блока составляет 64 бита.
Прямое криптографическое преобразование обладает следующим свойством:
различные блоки открытого текста отображаются в различные блоки
шифротекста. При обратном преобразовании соответствие сохраняется. Прямое
преобразование можно рассматривать как перестановку на множестве
сообщений с фиксированным размером блока. Результат перестановки носит
секретный характер, что обеспечивается секретным компонентом - ключом.
Одноключевые блочные шифры подразделяются на 3 группы:
 Шифры перестановки.
 Шифры замены (подстановки).
 Составные шифры.
19
При использовании шифров перестановки, которые предназначены
для устранения смысла сообщения путем изменения порядка чередования
его символов, знаки открытого текста переставляются по некоторому
правилу (ключу) в пределах заданного блока. В результате этого нарушается
нормальный порядок их следования и сам смысл информационного сообщения.
При этом различают шифры простой и сложной перестановки.
2.2 Шифры простой и сложной перестановок
Шифр простой перестановки переупорядочивает группу букв текста
регулярным образом в соответствии с выбранным ключом (правилом) перестановки. Из истории известно множество примеров использования таких шифров
для ручного шифрования. При этом часто использовались специальные
таблицы, которые давали простые шифрующие процедуры (ключи), согласно
которым производились перестановки букв в сообщении. Ключом у таких таблиц служили размеры таблицы, фраза, задающая перестановку или другие
специальные особенности таблицы.
Пример простейшего шифра перестановки представлен на рис. 2.5.
Рис. 2.5 - Простейший шифр перестановки.
Как видно из рис. 2.5, для того чтобы зашифровать сообщение «ЮСТАС
АЛЕКСУ ВСТРЕЧАЙТЕ СВЯЗНОГО», последнее необходимо записать в виде
таблицы, состоящей, например, их 5 строк и 6 столбцов. Текст сообщения
записывается по столбцам, исключая пробелы. Если последний столбец
оказывается неполным, он заполняется произвольно любыми буквами. Для
20
получения зашифрованного сообщения исходный текст считывается построчно
(слева направо) и записывается группами, например, по 5 цифр. Последняя
процедура не относится к процессу шифрования и делается только для того,
чтобы было удобнее записывать текст, лишенный всякого смысла. Для расшифрования такого текста необходимо знать ключ, а именно количество строк
и столбцов в таблице или иными словами, ее размер.
Более практический метод шифрования, очень похожий на предыдущий,
описывается ниже. Он отличается лишь тем, что колонки таблицы
переставляются по ключевому слову, фразе или набору чисел длиной в строку
таблицы.
При шифровании простой перестановкой шифруемый текст последовательными строками записывается под символами ключевого слова, которые не
должны повторяться. Для упрощения запоминания ключа используют ключевое
слово, буквы которого, пронумерованные в порядке их расположения в
алфавите, задают правило перестановки. Зашифрованный текст выписывается
колонками в той последовательности, в которой располагаются в алфавите
буквы ключа или в порядке следования цифр в натуральном ряду, если ключ
цифровой. Наглядно процесс шифрования с использованием шифра простой
перестановки представлен на рис. 2.6. Предположим, что необходимо
зашифровать информационное сообщение
«ЗАСЕДАНИЕ СОСТОИТСЯ ЗАВТРА ЮСТАС».
Для шифрования этого открытого текста запишем его без пробелов (участие последних в процедуре шифрования, из-за их высокой частоты повторения, значительно ослабляет криптостойкость шифра) и выберем ключ
шифрования, например, 245 136. Согласно этому ключу, состоящему из 6 цифр,
поделим все информационное сообщение на блоки, каждый из которых будет
содержать по 6 букв текста. После деления на блоки у нас получилось 4 блока,
содержащих по 6 букв в каждом, и 1 блок — по 5 букв. В таких случаях
последняя группа букв исходного сообщения произвольно дополняется
различными символами до получения полного блока. В нашем случае не
достает только одной буквы, поэтому выбираем любую букву, например Ъ, и
добавляем ее в конце пятого блока.
21
Рис. 2.6 - Шифр простой перестановки
Далее, используя ключ 245 136, производится перестановка букв
исходного открытого текста. Например, первая цифра ключа — 2, указывает на
то, что в новом блоке первой буквой зашифрованного текста будет вторая буква
блока открытого текста, вторая цифра ключа — 4, показывает, что вторая буква
шифротекста — это четвертая буква в блоке открытого текста и т. д.
В конечном итоге, после проведения перестановок во всех блоках, получаем зашифрованный текст. Прочитав его, мы видим, что он полностью
лишен какого-либо смыслового содержания.
Для упрощения запоминания ключа обычно используется ключевое
слово. В данном случае — это слово «КОРЕНЬ». В нем цифре 1 ключа соответствует буква Е, так как она первой из всех букв этого слова встречается в
нашем алфавите, цифре 2 — буква К (по той же причине) и т. д.
То же сообщение можно зашифровать с использованием таблицы, состоящей, например, из 5 строк и 6 столбцов (по длине ключевого слова). Исходный
текст записывается по столбцам и образует таблицу (рис. 2.7). Ключевое слово
задает правило перестановки столбцов. Если в ключевом слове встречаются
одинаковые буквы, то они нумеруются по порядку слева направо. Полученный
второй шифротекст, как это видно из рис. 2.7, совершенно не похож на первый.
Рис. 2.7 - Шифрование с помощью таблицы
Основным недостатком данного шифра является его невысокая
криптостойкость. Разложив зашифрованный текст на множители (не так уж
22
много получается вариантов), можно легко определить вероятную длину кодового слова, которое использовалось при шифровании.
Для повышения криптостойкости полученного выше шифрованного текста можно попробовать зашифровать его еще раз. Этот способ шифрования
известен под названием двойная перестановка. Суть этого способа заключается
в следующем. Полученный после первого шифрования текст шифруется
вторично с использованием таблицы с другой размерностью (длины строк и
столбцов подбираются другими). Кроме того, в одной таблице можно переставлять строки, а в другой столбцы. Заполнять таблицу исходным текстом
можно разными способами: зигзагом, змейкой, по спирали и т. п.
Шифр простой перестановки с использованием свойств таблиц, называемых магическими квадратами (рис. 2.8), использовался еще в средние века.
Магическими квадратами называются равносторонние таблицы, все клетки
которых заполнены натуральными числами, начиная от 1. Причем эти числа в
сумме дают по каждому столбцу, по каждой строке и по диагоналям
магического квадрата одно и тоже число (в нашем случае — это число 34).
Исходный текст — ЖДУ ВСТРЕЧИ ЮСТАС, при заполнении магического
квадрата, вписывается по порядку следования натуральных чисел, например,
число 1 заменялось 1 буквой исходного текста (Ж), число 12 — 12 буквой
сообщения (С) и т.п. После записи открытого текста содержимое таблицы
считывается по строкам в результате чего и получался шифротекст с
перестановкой букв.
Рис. 2.8 - Магический квадрат
Число магических квадратов быстро возрастает с увеличением размера
квадрата. Существует только один магический квадрат размером 3x3 (если не
23
учитывать его повороты). Количество магических квадратов 4x4 составляет уже
880, а количество магических квадратов 5x5 - около 250000.
Магические квадраты средних и больших размеров могли служить
хорошей базой для обеспечения нужд шифрования в средние века, поскольку
практически нереально выполнить вручную перебор всех вариантов для такого
шифра.
Кроме шифров простой перестановки существуют шифры с двойной
перестановкой столбцов и строк таблицы с исходным сообщением. Выполнение
шифрования может быть произведено различными способами (вариантами).
В случае использования шифра сложной перестановки группы символов
открытого текста подвергаются перестановкам не только по строкам (как в
шифре простой перестановки), но и по столбцам. Это удобнее делать, используя вышеприведенную таблицу (рис. 2.7). В таблицу записывается открытое
исходное сообщение, причем, как уже говорилось выше, это можно сделать
различными вариантами. В данном случае запишем текст сообщения построчно
слева направо. Относительно двух сторон таблицы запишем ключевое слово и
его числовой эквивалент, согласно которым произведем перестановку
столбцов, расположив их в порядке возрастания цифр. После этого, по тому же
закону, произведем перестановку строк таблицы. Зашифрованное сообщение
получится при считывании текста таблицы по строкам. Полученный
шифротекст, как видим, лишен смыслового содержания. Число вариантов
двойной перестановки достаточно велико и зависит от размерности
используемой шифровальной таблицы (рис. 2.9). Но даже использование
таблиц большой размерности не делает этот шифр достаточно криптостойким.
Произведем шифрование вышеприведенного сообщения, используя несколько иной метод шифрования и тот же самый ключ (рис. 2.10). Шифротекст
образуется при этом путем считывания переупорядоченных, в соответствии с
выбранным ключом, строк открытого текста. При этом порядок считывания
строк определяется ключевым словом, размещаемым по вертикали рядом со
строками шифротекста. При шифровании открытого текста большого объема
ключевое слово может повторяться по вертикали необходимое число раз.
Сначала производится шифрование открытого текста методом простой
перестановки. Полученное зашифрованное сообщение записывается блоками
построчно соответственно номерам (строка 1 — блок 1 и т. д.). Слева от этих
строк по вертикали (в столбик) записывается ключевое слово или ключ, согласно которым выбирается порядок следования строк (блоков). Последние
записываются друг за другом и образуют окончательный зашифрованный
текст.
Шифр сложной перестановки, кроме вышеописанного способа, может
формироваться путем считывания шифротекста по диагонали с изменением
порядка считывания на обратный для соседних диагоналей. Наглядно этот
способ представлен на рис. 2.11. В качестве исходного используется зашифрованный текст, блоки которого расположены по строкам (рис. 2.10).
24
Порядок считывания букв показан цифрами, а изменение направления
считывания соседних диагоналей — стрелками.
Еще один метод шифрования заключается в использовании специальных
решеток, трафаретов или палеток (рис. 2.12). Он основан на применении для
шифрования квадратных таблиц, у которых четверть ячеек (квадратиков) вырезана так, чтобы после 4 поворотов они покрывали весь квадрат. Поворачивать
квадрат можно как по часовой, так и против часовой стрелки.
Рис. 2.9 - Шифр сложной перестановки с использованием таблицы
25
Рис. 2.10 - Шифр сложной перестановки
Рис. 2.11 - Шифр сложной перестановки со считыванием по диагонали
Зашифруем исходное сообщение ЗАСЕДАНИЕ СОСТОИТСЯ ЗАВТРА
ЮСТАС с помощью трафарета (квадратная таблица размерностью 4x4),
26
Рис. 2.12 - Шифрование с использованием трафарета
имеющего по одному вырезанному окну в каждой строке. Наложим трафарет на
чистый лист бумаги, очертим его и начнем вписывать в вырезанные квадратики
(окошки) буквы исходного текста. После записи первых 4 букв произведем
поворот трафарета по часовой стрелке на 90° (для удобства пользования на
трафарете имеется ключ-метка). Снова запишем 4 буквы и произведем поворот
трафарета, и так до тех пор пока последний не вернется в свое первоначальное
положение или не закончится шифруемый текст. В последнем случае трафарет
можно заполнить любыми буквами. Убираем трафарет и записываем текст
таблицы построчно, в результате получается необходимый шифротекст.
2.3 Шифры замены
Шифры замены (подстановки) образуются с помощью замены знаков
открытого текста другими знаками или символами в соответствии с определенным правилом (ключом). С одним из таких шифров многие из нас впервые
познакомились еще в детском возрасте, когда зачитывались захватывающими
расследованиями знаменитого сыщика Шерлока Холмса. В рассказе А. КонанДойля «Пляшущие человечки», например, описывается как шифруются и
расшифровываются тексты с помощью шифра замены. В этом шифре каждой
букве алфавита соответствует изображение пляшущего человечка. Используя
27
этот шифр можно произвести шифрование открытого текста, приведенного
выше. В результате мы получим целый ансамбль пляшущих человечков, который изображен на рис. 2.13. Такой шифр имеет невысокую криптостойкость и,
как видно из текста книги мастера детективов, может быть быстро расшифрован даже без использования какой-либо вычислительной техники.
В отличии от этого простейшего шифра, большинство современных шифров практически невозможно расшифровать, то есть не существует вычислительных средств, способных в приемлемые сроки осуществить перебор возможных вариантов или эффективных алгоритмов, позволяющих значительно
сократить указанные переборные алгоритмы.
Рис. 2.13 - Открытый текст, закодированный шифром
«Пляшущие человечки»
Шифрование на основе замены использует принцип шифроалфавита —
перечня эквивалентов, применяемых для преобразования открытого текста в
зашифрованный. В том случае, когда для шифрования используется всего один
28
шифроалфавит, шифр называется одноалфавитным (моноалфавитным). Когда
же используются два и более шифроалфавитов, шифр называется
многоалфавитным (полиалфавитным).
Рис. 2.14 - Шифрование с использованием двоичного кода
Для увеличения скорости шифрования и использовании при этом вычислительной техники удобно использовать цифровое представление текстовой
информации, при котором символы текста заменяются некоторыми цифровыми
эквивалентами или представляются в виде двоичного кода. В этом случае, при
шифровании, символы шифруемого текста последовательно складываются с
символами некоторой специальной последовательности (ключом), называемой
гаммой. Процедуру наложения ключа (гаммы) на исходный текст можно
осуществить двумя способами.
При первом способе символы исходного текста, замененные цифровыми
эквивалентами, (например, А — 32, Б — 27, В — 22 и т. д.), складываются по
модулю К, где К — число символов в алфавите, с ключом (гаммой).
При втором способе символы исходного открытого текста и ключа (гаммы) представляются в виде двоичного кода, а затем складываются поразрядно
друг с другом по модулю 2. Наглядно это представлено на рис. 2.14. Допустим,
что необходимо зашифровать слово «КРОНА», каждая буква которого имеет
эквивалент в виде двоичного кода. Используя ключ (гамму), например 1001,
произведем его сложение по модулю 2 с двоичными кодами букв. В результате
получается последовательность, состоящая только из 0 и 1. Восстановление
исходной последовательности заключается в обратном сложении по модулю 2
исходного ключа и полученной шифропос-ледовательности.
Вместо сложения по модулю 2 можно использовать и другие логические
операции, например, преобразование по правилу логической эквивалентности,
что равносильно введению еще одного ключа, которым является выбор правила
формирования символов зашифрованного сообщения из символов исходного
текста и ключа. Шифрование по данному методу аналогично шифрованию
методом многоалфавитной подстановки при условии, что длина ключа
превышает длину шифруемого текста.
2.4 Одноалфавитные шифры
Примером одноалфавитного шифра является шифр Цезаря, в котором
каждая буква исходного открытого текста заменялась третьей по счету
буквой (от этой буквы исходного текста) латинского алфавита (с учетом
циклического сдвига). Вскрытие такого шифра осуществляется путем перебора
возможных ключей, в качестве которых используется величина сдвига букв
сообщения в алфавите до появления осмысленного текста.
При простой моно алфавитной подстановке каждый знак mi текста,
принадлежащего алфавиту А, заменяется соответствующим знаком hi ,
29
принадлежащим к алфавиту шифротекста В. Соответствие между знаками
алфавитов А и В задается с помощью кодовой таблицы или выражения.
Например, при использовании обобщенного «шифра Цезаря» выражение,
устанавливающее связь между алфавитами А и В, имеет вид
(2.3)
где К — количество знаков в алфавитах;
h — постоянная величина сдвига.
Каждому знаку алфавитов, которые в рассматриваемом случае состоят из
одних и тех же символов, ставится в соответствие число. Переход к
шифротексту осуществляется в результате суммирования с некоторым
постоянным числом h. Шифрование данным способом эквивалентно сдвигу
алфавита на фиксированное число позиций h. Если сдвиг h=l, то, например, для
русского алфавита буква А заменяется на букву Б, буква Б — на букву В, буква
Я — на букву А и т. п. соответственно (рис. 2.15).
В качестве примера зашифруем вышерассмотренное информационное
сообщение
ЗАСЕДАНИЕ СОСТОИТСЯ ЗАВТРА ЮСТАС.
После шифрования получим новое сообщение, которое имеет вид
ИБТЁЕБОЙЁ ТПТУПЙУТА ИБГУСБ ЯТУБТ
Увеличить надежность такого шифра можно путем использования перемешанного алфавита (см. рис. 2.15). Исходное сообщение после применения
такого алфавита будет иметь вид:
ЩЙПНЕЙДЗН ПЛПАЛЗАПЁ ЩЙУАРЙ ЮПАЙП
Рис. 2.15 - Пример одноалфавитного шифра
Однако, не смотря на то, что количество возможных перестановок букв
алфавита равно 33!, шифры моноалфавитной замены не являются высокостойкими и могут быть вскрыты с использованием вычислительной техники
достаточно быстро.
2.5 Многоалфавитные шифры
В шифрах многоалфавитной замены, в отличие от описанных выше, для
шифрования применяются несколько перемешанных алфавитов, поочередно
используемых при замене букв исходного шифруемого сообщения.
30
К многоалфавитным шифрам относятся шифр Вижинера, шифр
«Энигма», цилиндр Джефферсона и др. Использование шифра Вижинера,
например, сводится к следующему. Множество, например, из 33 алфавитов
(циклических сдвигов) русского языка формируется путем последовательного
сдвига букв исходного алфавита, подобно рассмотренному выше шифру
Цезаря.
Совокупность всех алфавитов, сведенных в одну таблицу, образует так
называемую шифровальную таблицу Вижинера (рис. 2.16). При шифровании в
этом случае также имеется кодовое слово, буквы которого определяют выбор
конкретного алфавита, используемого при замене соответствующей буквы
открытого текста. Процесс шифрования может быть описан, в данном случае,
как суммирование номеров соответствующих друг другу букв открытого текста
и ключевого слова по модулю 33.
Рассмотрим пример формирования шифра Вижинера для использованных
выше информационного сообщения и ключевого слова, повторяющегося необходимое число раз.
Исходное сообщение разбивается на блоки с использованием ключевого
слова «КОРЕНЬ», которое записывается над исходным открытым текстом 5 раз
подряд (для нашего текста). Выбираем строку с алфавитом, который начинается
с буквы К (первая буква ключевого слова) в первом столбце шифровальной
таблицы Вижинера (см. рис. 2.16). Первая буква шифрованного текста
находится на пересечении этой строки и столбца таблицы, начинающегося с
первой буквы открытого текста (первая строка таблицы), в данном случае это
буква Т. Следующая буква шифротекста находится на пересечении строки
таблицы, начинающейся со второй буквы ключевого слова — буквы О, и
столбца, начинающегося со второй буквы открытого текста. Это буква — О.
Аналогично производится шифрование остальных букв. В итоге, получается
шифротекст, по количеству символов совпадающий с исходным открытым
текстом:
ТОВЙСЬ ШУХЦЬН ЭЭЩЧЯЫ ТОТЧЮЬ ИАГЕЯЦ
Для облегчения процессов шифрования и расшифрования обычно используется специальная шифровальная линейка, состоящая из неподвижной и
подвижной частей (рис. 2.17). При шифровании соответствующая буква
ключевого слова, например первая — К, путем перемещения подвижной части
устанавливается напротив буквы А неподвижной части линейки. В этом случае
над соответствующей буквой открытого текста, расположенной на
неподвижной части линейки, находится находящаяся на подвижной части
соответствующая буква шифротекста.
Для увеличения криптостойкости в шифре Вижинера может использоваться переменный ключ, в качестве которого применяется некоторый текст,
заранее известный отправителю и получателю сообщения.
31
Рис. 2.16 - Шифровальная таблица Вижинера для русского алфавита
ЗАСЕДА НИЕСОС ТОИТСЯ ЗАВТРА ЮСТАС
КОРЕНЬ КОРЕНЬ КОРЕНЬ КОРЕНЬ КОРЕНЬ
32
Рис. 2.17 - Пример формирования шифра Вижинера с
использованием шифровальной линейки
Шифр сложной замены, называемый шифром Гронсфельда, представляет
собой модификацию шифра Цезаря числовым ключом. Для этого под буквами
исходного сообщения записывают цифры числового ключа. Если ключ короче
сообщения, то его запись циклически повторяют. Шифртекст получают
примерно, как в шифре Цезаря, но отсчитывают по алфавиту не третью букву
(как это делается в шифре Цезаря), а выбирают ту букву, которая смещена по
алфавиту на соответствующую цифру ключа. Например, применяя в качестве
ключа группу из четырех начальных цифр числа е (основания натуральных
логарифмов), а именно 2718, получаем для исходного сообщения
ВОСТОЧНЫЙ ЭКСПРЕСС следующий шифртекст:
Чтобы зашифровать первую букву сообщения В, используя первую цифру
ключа 2 , нужно отсчитать вторую по порядку букву от В в алфавите В-Г-Д;
получается первая буква шифртекста Д.
Следует отметить, что шифр Гронсфельда вскрывается относительно
легко, если учесть, что в числовом ключе каждая цифра имеет только десять
значений, а значит, имеется лишь десять вариантов прочтения каждой буквы
шифртекста. С другой стороны, шифр Гронсфельда допускает дальнейшие
модификации, улучшающие его стойкость, в частности двойное шифрование
разными числовыми ключами.
Шифр Гронсфельда представляет собой по существу частный случай
системы шифрования Вижинера.
2.6 Составные шифры
На практике для повышения криптостойкости шифрования обычно
используют
два
общих
принципа
шифрования:
рассеивание
и
перемешивание.
Принцип рассеивания состоит в распространении влияния одного символа
открытого текста на некоторое, иногда большое, количество символов
33
шифротекста, что позволяет скрыть статистические свойства открытого
текста. Развитием этого принципа является распространение влияния
одного символа ключа на много символов шифрограммы, что позволяет
исключить восстановление ключа по частям.
Принцип перемешивания состоит в использовании таких
шифрующих преобразований, которые исключают восстановление
взаимосвязи статистических свойств открытого и шифрованного текста.
Распространенный способ шифрования, при котором достигается хорошее рассеивание и перемешивание, состоит в использовании составного шифра.
Этот шифр строится на основе совместного использования простых шифров
замены и перестановки, каждый из которых вносит некоторый вклад в
значительное суммарное рассеивание и перемешивание.
Одним из наглядных примеров криптоалгоритма, разработанного в
соответствии с принципами рассеивания и перемешивания, может служить
принятый в 1977 году Национальным бюро стандартов США стандарт
шифрования данных DES. Несмотря на интенсивные и тщательные
исследования алгоритма специалистами, пока не найдено уязвимых мест
алгоритма, на основе которых можно было бы предложить метод
криптоанализа, существенно лучший полного перебора ключей. В июле 1991
года в нашей стране введен в действие подобный отечественный
криптоалгоритм шифрования — ГОСТ 28147-89.
В то же время, несмотря на широкое распространение блочного шифрования, ему присущи следующие недостатки:
 Одиночная ошибка в шифротексте вызывает искажение примерно
половины открытого текста при дешифровании, что требует применения
мощных кодов, исправляющих ошибки
 Из двух одинаковых блоков открытого текста получаются одинаковые блоки шифрованного текста.
Избежать этих недостатков позволяют поточные (потоковые)
шифры.
Контрольные вопросы
1.
2.
3.
4.
5.
6.
7.
8.
9.
Дайте определение блочного щифра.
Что является ключом при шифровании таблицей.
Привести структуру и пояснить работу одноключевой криптосистемы.
Перечислить методы шифрования в одноключевых криптографических
системах.
Шифры сложной перестановки, алгоритмы шифрования и дешифрации.
Алгоритмы шифрования и дешифрации с использованием трафарета.
Шифры подстановки, алгоритмы шифрования и дешифрации.
Шифровальная таблица Вижинера для русского алфавита, алгоритмы
шифрования.
Пояснить суть принципов шифрования: рассеивание и перемешивание.
34
3 ПОТОЧНЫЕ ШИФРЫ.
3.1 Идеальный поточный шифр
В современных системах шифрования данных широкое применение
нашли системы поточного (потокового) шифрования. Поточные (потоковые)
шифры, в отличие от блочных, осуществляют поэлементное шифрование
потока данных без задержки в криптосистеме. В общем случае каждый символ
открытого текста шифруется, передается и дешифруется независимо от других
символов. Иными словами, шифрующее преобразование элемента открытого
текста меняется от одного элемента к другому, в то время как для блочных
шифров шифрующее преобразование каждого блока остается неизменным. В
некоторых случаях символ открытого текста может шифроваться с учетом
ограниченного числа предшествующих ему символов.
Важным достоинством поточного шифрования является высокая скорость
преобразования данных, соизмеримая со скоростью поступления открытого
текста, что обеспечивает шифрование и расшифрование передаваемой информации больших объемов практически в реальном масштабе времени.
Системы поточного шифрования обладают высокой криптостойкостью, так как
вскрытие такой системы предполагает точное определение структуры
генератора ключевой последовательности (ГКП) и его начальной фазы. Перечисленные положительные качества поточного шифрования в совокупности с
простой и низкой по стоимости технической или программной реализацией
поставили его в ряд наиболее перспективных систем шифрования.
Поточные (потоковые) шифры основываются на использовании ключевой
последовательности с заданными свойствами случайности и двоичном
(цифровом) представлении информационных сообщений. Шифрование и
расшифрование осуществляется, как правило, с использованием операции
сложения по модулю 2 элементов открытого текста и псевдослучайной
ключевой последовательности. Последние состоят из сгенерированных
определенным образом последовательностей символов с заданными свойствами
непредсказуемости (случайности) появления очередного символа.
Рис.3.1 - Шифр Вернама
35
Исторически первым поточным шифром стал шифр Вернама, в котором в
качестве ключевой последовательности использовалась уникальная случайная
гамма. При этом размер ключевой последовательности соответствовал длине
открытого текста. Принцип шифрования и расшифрования данных изображен
на рис. 3.1.
Отличительной особенностью шифра Вернама является шифрование гаммы ключевых последовательностей, каждая из которых представляет собой
шифр. Практическая реализация этого шифра из-за сложности реализации
сверхдлинных ключевых последовательностей и неудобства их хранения оказалась затруднительной.
Более удобными оказались поточные шифры, в которых в качестве
ключевых используются псевдослучайные последовательности (ПСП),
формируемые генераторами ПСП. В этом случае секретный ключ определяется
начальным состоянием генератора ПСП, а его размер значительно меньше
размера открытого текста, что существенным образом упрощает решение задач
технической реализации, хранения и передачи ключа.
В настоящее время существует достаточно большое количество поточных
шифров, отличающихся друг от друга некоторыми отличительными признаками. Например, по способу синхронизации поточные шифры подразделяются на
синхронные и самосинхронизирующиеся.
3.2 Синхронные поточные фильтры
В синхронных поточных шифрах ключевая последовательность или, как ее
еще называют, гамма, формируется независимо от последовательности
символов открытого текста и каждый символ этого текста шифруется
независимо от других символов, а ключом Z является начальная установка
генератора ПСП. Процесс шифрования и расшифрования при этом описывается
выражениями:
Yi = Xi Е Fi (Z) — шифрование;
(3.1)
Xi = Yi Е Fi (Z) — расшифрование,
(3.2)
где Yi , Xi — двоичные символы зашифрованного и открытого текста,
Fi (Z) — i-й символ ПСП, вырабатываемый генератором с функцией обратной связи F и начальным состоянием Z;
Е – оператор объединения символов зашифрованного и открытого текста.
Синхронные поточные шифры можно классифицировать по
способам построения ПСП, по соотношению размеров открытого текста и
периода ключевой ПСП, по способам технической реализации (рис. 3.2).
По способам построения ПСП для синхронного шифрования различают:
• Метод комбинирования ПСП
36
• Метод функциональных отображений.
Суть первого метода заключается в построении комбинированных схем,
представляющих собой совокупность регистров сдвига с линейными обратными связями. Примерами таких схем являются схема Джеффа (рис. 3.3 а) и
схема Брюс (рис. 3.3 б).
Отличие этих двух схем состоит в использовании для формирования ПСП
различных логических устройств. Так, в схеме Джеффа применяется операция
логического умножения и сложения по модулю 2. Схема Брюс использует
пороговое устройство, работающее по правилу: на выходе 1, если порог
превышен, иначе — 0.
Более сложным является метод функциональных отображений, суть которого заключается в следующем. Пусть дано некоторое векторное пространство GF(2m) с числом координат m в каждом векторе, причем каждая
координата вектора принадлежит множеству скалярных величин GF(2)={0,l}.
Очевидно, что общее число векторов, принадлежащих пространству GF(2m),
равно 2т. Пусть задано некоторое функциональное отображение f, которое
каждому вектору из векторного пространства GF(2m) ставит в соответствие
вектор из пространства GF(2k). При этом обязательным является выполнение
условия k<=m. Далее пусть задано некоторое функциональное отображение g,
которое каждому вектору из GF(2k) ста вит в соответствие скаляр из множества
GF(2). В этом случае получим ПСП с использованием вышеприведенных
функциональных отображений. Например, ПСП, полученная по схеме,
изображенной на рис. 3.4 (m = 4, k = 2), построена по методу двухступенчатых
отображений.
37
Рис. 3.2 - Классификация синхронных поточных шифров
Метод ступенчатого отображения GF(2m) — GF(2k) — GF(2) впервые был
использован при построении последовательностей Гордона-Милса-Велга. Для
порождения векторного пространства GF(2m) использовались регистры сдвига с
линейными обратными связями длины m с обратной связью.
Рис. 3.3 - Схема Джеффа (а) и схема Брюс (б)
38
Следует заметить, что на практике имеет место различное число
функциональных отображений. С возрастанием используемых ступеней
уровень криптостойкости шифрования повышается.
По отношению размера открытого текста и периода ключевой ПСП
различают схемы:
 С «бесконечной» ключевой ПСП (период ПСП больше размера открытого
текста)
 С конечной ключевой ПСП или с режимом «бегущего кода» (период ПСП
равен размеру открытого текста).
Рис. 3.4 - Принцип формирования ПСП по методу
двухступенчатых отображений
Схемы с «бесконечной» ключевой ПСП обладают более высокой
криптостойкостью относительно вскрытия их структуры при известном открытом тексте. Однако при вскрытии структуры ПСП по частично известному
тексту схема «бегущий код» не позволяет вскрывать весь текст, а только его
небольшую часть, поэтому, например, разработчики спутниковой системы «Навстар» в качестве криптостойкой ПСП P-кода использовали сегменты длительностью 7 суток, выделенные случайным образом из нелинейной ПСП с
периодом 267 суток.
По способам технической реализации синхронных поточных шифров
можно выделить схемы, представленные на рис. 3.5:
 с нелинейной внешней логикой;
 с нелинейной внутренней логикой.
39
Рис. 3.5 - Схема с нелинейной внешней (а) и внутренней (6) логикой
При использовании нелинейной внешней логики основу генератора ПСП
составляет регистр сдвига с линейными обратными связями, который порождает все ненулевые элементы векторного пространства GF(2n).
В схеме с нелинейной внутренней логикой генератор ПСП представляет
собой регистр с нелинейными обратными связями. Такой генератор вырабатывает последовательности де Брейна с периодом 2n. Такие последовательности обладают одними из самых высоких показателей криптостойкости
из всех классов ПСП, так как каждая серия из n-символов встречается на
периоде ПСП только один раз.
3.3 Самосинхронизирующиеся поточные шифры
В самосинхронизирующихся поточных шифрах (рис. 3.6) символы открытого текста шифруются с учетом ограниченного числа предшествующих nсимволов, которые принимают участие в формировании ключевой
последовательности. При этом секретным ключом Z является функция обратной связи генератора ПСП.
Используя математические выражения, принцип самосинхронизирующегося поточного шифрования можно представить следующим образом:
(3.3)
(3.4)
где xi, yi – двоичные символы открытого и зашифрованного текста;
40
Fz(…) – функция обратной связи, соответствующая ключу Z;
n – количество регистров генератора ПСП.
Рис. 3.6 - Принцип самосинхронизирующегося поточного шифрования
Системы потокового шифрования близки по своим параметрам к криптосистемам с «одноразовым ключом», в которых размер ключа равен размеру
шифруемого текста, что существенным образом повышает криптостойкость
зашифрованных сообщений. Следовательно, потоковые шифры, в отличие от
других криптосистем, обладают значительно большей анализируемой
секретностью. В силу сказанного, а также благодаря высокой скорости
шифрования и ограниченности размножения ошибок поточное шифрование
является на сегодняшний день наиболее перспективным и вызывает большое
доверие многих потребителей и специалистов.
Примером поточных шифраторов, используемых в высокоскоростных линиях связи, являются такие как SEC-15, SEC-17, SDE-100 и др. Устройство
SEC-17, например, обеспечивает скорость шифрования от 256 Кбит/с до 2304
Кбит/с, его ключ состоит из 72 шестнадцатиричных цифр; а устройство SEC-15
позволяет иметь более 10000000000000000000000000000000000 статистически
независимых ключей. В устройстве потокового шифрования CSD 807 в
генераторе ключевой последовательности применен 31-разрядный регистр
сдвига, в генераторе устройства потокового шифрования SDE-100 используются 2 регистра сдвига. Принципы потокового шифрования используются также в устройствах аппаратуры шифрования MSDS MARCRYP.
На основании сравнительного анализа поточных шифров можно сделать
следующие выводы:
 В синхронных поточных шифрах, в отличие от самосинхронизирующихся,
отсутствует эффект размножения ошибок, то есть количество ошибок в
шифротексте соответствует количеству в расшифрованном получателем тексте;
 При использовании синхронных поточных шифров необходимо решить
задачу синхронизации генераторов ключевых ПСП у отправителя и получателя
сообщений. Вставка или выпадение одного двоичного символа в шифротексте
приведет к неправильному расшифрованию остальных символов из-за
нарушения синхронизации;
 В самосинхронизирующихся поточных шифрах восстановление режима
синхронизации осуществляется автоматически через n-символов шифротекста.
41
4 КРИПТОГРАФИЧЕСКИЕ КРИПТОСИСТЕМЫ
4.1 Одноключевые криптографические системы
Двухключевые криптографические системы характеризуются на использовании двух ключей: открытого (несекретного) и закрытого (секретного).
Особенность двухключевых систем состоит в возможности получения двух
разновидностей шифрования в зависимости от вариантов применения открытого и секретного ключей.
Рис. 3.7 - Система шифрования с открытым ключом
Так, если открытый ключ используется для шифрования, а секретный
ключ — для расшифрования, то имеет место система шифрования с открытым
ключом. В этом случае каждый владелец открытого ключа может зашифровать
текст, а расшифровать его сможет только владелец секретного ключа. Этот
способ используется, например, в системах сотовой подвижной связи стандарта
GSM. Структурная схема системы шифрования с открытым ключом
представлена на рис. 3.7.
Процесс шифрования и расшифрования для систем с открытым ключом,
проиллюстрированный на рис. 3.7, может быть представлен выражениями:
Y=Ezo(X), X=Dzc(Y)=Dzc(Ezo(X)),
(3.5)
где X — открытый текст;
Y — зашифрованный текст;
ZQ — открытый ключ;
Zc — секретный ключ;
Ezo — функция шифрования;
Dzc — функция расшифрования.
Если же секретный ключ используется для шифрования, а открытый для
расшифрования, то имеет место система электронной цифровой подписи
(ЭЦП). В данном случае только владелец секретного ключа может правильно
42
зашифровать текст, то есть подписать его, а проверить подпись (расшифровать
текст) может любой пользователь, имеющий в своем распоряжении открытый
ключ. Реализацию процесса шифрования и расшифрования для системы ЭЦП
можно представить с помощью следующих выражений:
Y=Ezc(X), X=Dzo(Y)=Dzo(Ezc(X)),
где
(3.6)
X — открытый текст;
Y — зашифрованный (подписанный) текст;
Zo — открытый ключ;
Zc — секретный ключ;
Ezc — функция шифрования ЭЦП;
Dz0 — функция расшифрования ЭЦП.
При этом для взаимной однозначности выражений, описывающих процессы шифрования и расшифрования с открытым и секретным ключами,
необходимо выполнение условия
EzoDzc=EzcDzo=e,
(3.7)
где е — единичное преобразование.
4.2 Криптографические системы с открытым ключом
В криптосистемах с открытым (общедоступным) ключом используются
некоторые аналитические преобразования и два различных, но взаимосвязанных друг с другом ключа — один (открытый — доступный любому лицу)
для шифрования, другой (секретный — доступный только одному лицу) для
дешифрирования.
Стойкость криптосистем с открытым ключом определяется вычислительной сложностью алгоритмов. В этом случае предполагается, что даже при наличии всей доступной информации для дешифрирования сообщения оно не
сможет быть восстановлено за требуемое время из-за чрезвычайно большого
объема необходимых вычислений.
В криптосистемах с открытым ключом, в алгоритмах шифрования и расшифрования используются разные ключи, каждый из которых не может быть
получен из другого (с приемлемыми затратами).
Желательно, чтобы методы шифрования обладали минимум двумя свойствами:
 Законный получатель сможет выполнить обратное преобразование и
расшифровать сообщение
 Злоумышленник или криптоаналитик противника, перехвативший
сообщение, не сможет восстановить по нему исходное сообщение без таких
затрат времени и средств, которые сделают эту работу нецелесообразной.
43
Один ключ используется для шифрования, другой — для расшифрования.
Односторонние функции не могут быть непосредственно использованы в
качестве криптосистемы, так как даже законный получатель не сможет
расшифровать полученное сообщение. Односторонняя функция должна иметь
«потайную дверь (лазейку)», то есть должен существовать эффективный способ
ее вычисления в обоих направлениях, при этом знание прямого преобразования
не позволяет легко найти обратное преобразование. Двухключевые системы
(рис. 3.8), в основном, используют блочные методы шифрования и основаны на
применении односторонних (необратимых) функций с потайным ходом
(лазейкой). Эти функции обладают важным свойством: при заданном значении
x относительно просто вычислить значение функции f(x). Однако, если
известна функция y=f(x), то для вычисления х очень трудно рассчитать
значение обратной функции l / f(y).
Рис. 3.8 - Двухключевые криптографические системы
Односторонние функции с потайной дверью (лазейкой) являются
теоретической основой криптосистем с открытым ключом. Примером подобной
функции является перемножение простых чисел (простое число, как известно
из школьной программы, — это целое число, которое делится без остатка только на единицу и на само себя). Например, сравнительно несложно
перемножить два простых 100-значных числа, однако для разложения на
множители получившегося 200-значного числа потребуется десятки лет непрерывной работы мощного компьютера. Примером криптоалгоритма на
основе умножения простых чисел является широко известный алгоритм
RSA (Райвест, Шамир, Адлеман). Криптостойкость алгоритма RSA
находится в прямой зависимости от сложности разложения простых чисел
на множители.
44
Вычисление ключей в таких системах осуществляется получателем сообщений, который оставляет у себя тот ключ, который он будет потом использовать для расшифрования, то есть секретный ключ. Другой ключ — открытый,
он высылает отправителю сообщений любым доступным способом, не опасаясь
его огласки. Используя этот открытый ключ, любой пользователь может
зашифровать свой открытый текст и послать его получателю, который
сформировал данный открытый ключ (рис. 2.26). Все используемые алгоритмы
этого процесса являются общедоступными. Особенность этого метода
заключается в том, что функции шифрования и расшифрования являются
обратимыми только тогда, когда они обеспечиваются с помощью строго
определенной пары ключей (открытого и секретного), причем открытый ключ
должен представлять собой необратимую функцию от секретного ключа.
Рис. 3.9 - Пример реализации системы с открытым ключом
В результате исследований односторонних (необратимых) функций с
использованием решений определенных классов математических задач появились следующие направления в построении двухключевых криптографических алгоритмов:
 Умножение простых чисел
 Дискретное возведение в степень
 Задача об укладке (упаковки) рюкзака (ранца)
 Использование кодовых конструкций, исправляющих ошибки.
Недостатком этих систем является то, что в системах с открытым ключом, также как и в блочных шифрах, необходим большой размер шифруемого
блока, хотя, возможно, и не больше чем в алгоритме DES. А это препятствует,
наряду с низкой скоростью шифрования, использованию алгоритмов с
открытым ключом в потоковых шифрах. На настоящий момент
высокоэффективные системы с открытым ключом пока не найдены. Почти
45
повсеместно принято ограничение использования криптосистем с открытым
ключом — только для управления ключами и цифровой подписи.
4.2.1 Метод возведения в степень
Известно несколько методов шифрования, разработанных на основе дискретного возведения в степень. Наиболее распространенным из них является
метод дискретного возведения в степень в конечных полях. К ним относятся
криптоалгоритмы Диффи-Хелмана (DH) и Месси-Омура. Задача дискретного
возведения в степень в аддитивной абелевой группе положена в основу
построения алгоритмов на алгеброических кривых.
Идея криптографии с открытым ключом тесно связана с идеей односторонних функций. По заданному аргументу х легко вычислить значение функции f(x), тогда как определение х из f(x) трудновычислимо. Здесь «трудновычислимость» понимается в смысле теории сложности. Ситуация изображена
на рис. 3.10.
Мы говорим о f(x), как о функции. Определение х из f(x) трудновычислимо только для криптоаналитика. Законный получатель информации имеет
подходящую лазейку. Далее такие односторонние функции будем называть
криптографическими.
Упомянем по этому поводу, что ни одного примера криптографической
односторонней функции не известно. Зато существует много криптографических функций f(x), таких, что:
• Легко вычислить f(x) из х
• Определение x из f(x), вероятно, будет трудновычислимым.
Рис. 3.10 - Смысл теории сложности
для односторонней функции
С точки зрения криптографии с открытым ключом вполне подходят функции, удовлетворяющие этим двум требованиям. В типичных криптосистемах с
открытым ключом только прямой криптоанализ основан на вычислении x из
^x). Могут существовать и другие, более гениальные криптоаналитические
методы, избегающие этого вычисления. Таким образом, криптоаналитик может
достичь успеха даже в том случае, когда доказано, что нахождение x из f(x)
трудно вычислимо.
Функция f(x) будет односторонней, если перевод x в f(x) легок, а обратный перевод из f(x) в x трудновычислим. Второе требование часто
заменяется более слабым условием: обратный перевод, вероятно, будет
трудновычислимым.
46
Можно выделить две основные группы методов криптографической
защиты информации с открытым ключом, использующих ту или иную одностороннюю функцию с «потайной лазейкой». В качестве такой функции может
быть использовано модульное возведение в степень с фиксированным
показателем степени m и модулем n:
f(x)=xmmod (n)
(3.8)
Эффективный алгоритм для обратной операции — извлечения корня t-ой
степени по модулю n для произвольных t и n неизвестен. Это так называемая
проблема дискретного логарифмирования для больших чисел. Один из методов
использует эффективный алгоритм извлечения корня при известном
разложении числа n на простые множители. Это и позволяет отнести функцию
вида f(x) к классу односторонних функций с «потайной лазейкой».
4.2.2 Метод укладки (упаковки) рюкзака (ранца)
Реализацией задачи об укладке рюкзака является криптоалгоритм Меркле
и Хелмана. Рассмотрим этот криптоалгоритм на примере. Пусть задан набор
чисел
(а,,а2,...ап) = А.
Задачей является нахождение таких чисел а|5 если это возможно, сумма
которых равна числу к. В простейшем случае это число к указывает размер
рюкзака, а каждое из чисел а. указывает размер предмета, который может быть
упакован в рюкзак. Задачей является нахождение такого набора предметов,
чтобы рюкзак был полностью заполнен.
В качестве примера возьмем число к=3231 и набор из 10 целых чисел:
43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523.
Заметим, что число k получается при сложении только некоторых чисел а:
3231 = 129+ 473 + 903 + 561 + 1165
Таким образом, сложив эти числа, мы нашли решение, то есть заполнили
рюкзак. Ситуация наглядно проиллюстрирована на рис. 3.11.
47
Рис. 3.11 - Метод укладки рюкзака
В принципе решение всегда может быть найдено полным перебором
подмножеств А и проверкой, какая из сумм равна числу к. В нашем случае это
означает перебор 210=1024 подмножеств (включая при этом и пустое
множество). Это вполне осуществимо.
Но что будет, если существует несколько сотен чисел а/? В нашем
примере n=10, чтобы не усложнять положение и расчеты. В реальных условиях
пример будет иметь, скажем, 300 чисел а… Суть здесь в том, что неизвестны
алгоритмы, имеющие существенно меньшую сложность по сравнению с
полным перебором. Поиск правильного решения среди 2300 подмножеств не
поддается обработке.
4.2.3 Кодовые конструкции
Алгоритм преобразований на основе кодовых конструкций с исправлением ошибок различаются по способам маскирования исходного кода. Наиболее известными являются криптоалгоритмы Мак-Элайса, использующие
исправляющие ошибки коды Гоппы, Нидеррайгера, Крука, Габидулина и др.
Сравнительные характеристики некоторых известных двухключевых
криптоалгоритмов приведены в табл. 3.2.
48
Таблица 3.2. Характеристики двухключевых криптоалгоритмов
Алгоритм
RSA
Длина
ключа, бит
до 1
DHE (алгоритм Диффи-Хелмана в до 4
версии Эль-Гамаля)
DSS
до 2
Примечание
Используется
шифрования и
формирования ЭЦП
Используется
шифрования
Используется
формирования ЭЦП
для
для
для
4.3 Комбинированные и составные криптографические системы
В системах комбинированного шифровании реализуются принципы как
блочного, так и поточного шифрования. При этом возможно использование
блочного шифра в поточном режиме (гаммирование, шифрование с обратной
связью) и поточного шифра в блочном режиме (шифрование блоков).
Комбинированное шифрование применяется на практике в различных
режимах стандартов шифрования ГОСТ 28147-89 и DES.
Одноключевые криптографические алгоритмы наиболее хорошо известны в огромном мире криптографии.
Сравнительный анализ показателей эффективности используемых в настоящее время криптографических систем показывает, что алгоритм шифрования двухключевых систем значительно медленнее классического алгоритма с секретным ключом. В то же время шифрование сообщений с открытым
ключом обладает рядом преимуществ, которые невозможно реализовать в
одноключевых системах.
Данное обстоятельство побудило многих специалистов по криптографии
к поиску криптосистем, сочетающих в себе достоинства как одноключевых, так
и двухключевых систем.
В 1991 году американский криптолог Ф. Зиммерманн предложил использовать так называемые составные криптографические системы, основанные
на совместном применении систем с открытым и секретным ключами. В
качестве конкретной реализации такого подхода был разработан и опубликован
для широкого круга пользователей криптографический алгоритм PGP (Pretty
Good Privacy). Принцип работы этого криптоалгоритма показан на рис. 3.12.
Для шифрования открытого текста X используется качественный и быстрый алгоритм симметричного шифрования с секретным ключом. В качестве
секретного ключа применяется случайное число, используемое как сеансовый
ключ Z. Кроме того, сеансовый ключ Z шифруется с помощью открытого
ключа получателя Zo при использовании несимметричного шифрования.
Зашифрованный текст в виде Y=Ez(X) и сеансовый ключ в виде K=
(Z)
отправляются получателю.
49
Процесс расшифрования является обратным по отношению к шифрованию. Секретный ключ получателя Zc используется для восстановления сеансового ключа Z, который, в свою очередь, служит ключом симметричного
расшифрования Dz(Y) получаемого текста.
Рис. 3.12 - Криптоалгоритм PGP
Практические разработки криптоалгоритма PGP и последующий анализ
его криптостойкости показывают, что он становится все более популярным в
мире. Более того, рабочая группа по стандартам Интернета (IETF)
рассматривает алгоритм PGP как возможный официальный стандарт этой
глобальной сети, который будет рекомендован всем производителям программного обеспечения.
4.4 Основной принцип и конструкция современных криптосистем
Принцип итерирования [6] является основным при разработке криптографических преобразований и заключается в многократной, состоящей из
нескольких циклов обработке одного блока открытого текста. На каждом цикле
данные подвергаются специальному преобразованию при участии
вспомогательного ключа, полученного из заданного секретного ключа. Выбор
числа циклов определяется требованиями криптостойкости и эффективности
реализации блочного шифра. Как правило, чем больше циклов, тем выше
криптостойкость и ниже эффективность реализации (больше задержка при
шифровании/дешифровании) блочного шифра, и наоборот. Так, например, в
случае DES (федеральный криптостандарт США) для того, чтобы все биты
шифротекста зависели от всех битов ключа и всех битов открытою текста,
необходимо 5 циклов криптографического преобразования. DES с 16 циклами
обладает
высокой
криитостойкостыо
по
отношению
к
ряду
криптоаналитических атак.
50
Конструкция Фейстеля [6] (Н. Feistel) или сеть Фейстеля пред-ставляет
собой разновидность итерированного блочного шифра. При шифровании блок
открытого текста разбивается на две равные части правую и левую. Очевидно,
что длина блока при этом должна быть четной. На каждом цикле одна из частей
подвергается преобразованию при помощи функции f и вспомогательного
ключа ki полученного из исходного секретного ключа. Результат операции
суммируется по модулю 2 (операция XOR) с другой частью. Затем левая и
правая части меняются местами. Схема конструкции Фейстеля представлена на
рисунке 3.5. Преобразования на каждом цикле идентичны, но на последнем не
выполняется перестановка. Процедура дешифрования аналогична процедуре
шифрования, однако ki выбираются в обратном порядке. Конструкция
Фейстеля хороша тем, что прямое и обратное криптографические
преобразования для какого блочного шифра имеют идентичную структуру.
Конструкция Фейстеля применяется в криптоалгоритмах DES, ГОСТ
28147-89, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, CAST, Blowfish и др.
Блочный шифр, использующий такую конструкцию, является обратимым и
гарантирует возможность восстановления входных данных функции f на
каждом цикле. Сама функция f не обязательно должна быть обратимой. При
задании произвольной функции f не потребуется реализовывать две различные
процедуры - одну для шифрования, а другую для дешифрования. Структура
сети Фейстеля автоматически позаботится об этом.
Рис. 4.1 Схема конструкции Фейстеля
51
Существует еще одно объяснение идеи конструкции Фейстеля. В
своих лекциях известный криптограф Дж. Мэсси (J. L. Massey) вводит
понятие инволютивного оюбражения. Так, неко-торая функция f является
инволюцией, если f (f(x)) = х для всех х. Для такой функции область
определения (множество аргументов х) и область значений (множество
значений f(x)) совпадают. Например, функция f (х) = х является
инволюцией, так как f (f (х)) = f (х) =  (х) = х. Другой пример
инволюции: f(x) = х  с, где с - некоторая константа. Действительно, f (f
(х)) = f (хс) = х  с  с = х.
Рис. 4.2 - Шифрование композиционного блочного шифра
Инволюция является полезным свойством при конструировании
блочных шифров. Рассмотрим композиционный блочный шифр,
включающий n последовательных криптографических преобразований
ЕiK(), 1  i  n на ключе К (рис. 4.2).
Рис. 4.3 - Дешифрование композиционного блочного шифра
Тогда шифротекст С получается в результате преобразования
С = ЕnK(Еn-1K (…Е2K (Е1K (P))…)),
(4.1)
где Р — открытый текст (рисунок 3.7). Если функция ЕiK является
инволюцией, открытый текст может быть восстановлен в результате
преобразования
P = Е1K(Е2K (…Еn-1K (ЕnK (С))…)).
(4.2)
52
Действительно, согласно описанному выше свойству имеем:
P = Е1K(Е2K (…Еn-1K (ЕnK (ЕnK(Еn-1K (…Е2K (Е1K (P))…))))…))
(4.3)
Так как ЕnK (ЕnK()) =  , Еn-1K (Еn-1K()) =  ; и так далее вплоть до получения
тождества
P  P.
(4.4)
4.5 Режимы шифрования блочных шифров
При использовании блочных шифров применяются различные схемы
шифрования, известные под названием рабочих режимов шифрования для
блочных шифров. Очевидно, что применение того или иного режима
шифрования не должно отрицательно сказываться на эффективности и тем
более криптостойкости блочного шифра. Режимы шифрования позволяют
реализовать дополнительные, отсутствующие в исходной конструкции
блочного шифра функции.
Шифрование в режимах ЕСВ и СВС
Стандарт режимов шифрования для блочных
шифров
(применительно
к криптоалгоритму DES) опубликован в материалах
Национального института стандартов
США и ANSI X3.106. В более
общем виде, применительно к произвольному блочному шифру с
переменной длинной блока, стандарт опубликован в материалах и
включает шифрование в следующих режимах: Электронной кодовой книги
(Electronic Code Book, ЕСВ), Сцепления блоков шифра (Cipher Block
Chaining, СВС), Обратной связи по шифротексту (Cipher Feedback, CFB) и
Обратной связи по выходу (Output Feedback, OFB). В режиме ЕСВ (рис.
4.4) шифрование/дешифрование i -го блока открытого текcта/шифротекста
выполняется независимо:
mi = Dk (ci),
ci, = Е k (mi),
(4.5)
где через Е k и Dk обозначены процедуры шифрования/дешифрования на
секретном ключе k.
Криптостойкость режима ЕСВ не ниже, чем криптостойкосгь
используемого блочного шифра. Недостаток заключается в том, что
фиксированные блоки открытого текста (например, последовательность
53
нулей длины l = nb бит, где b длина блока) будут соответствовать
фиксированным блокам шифротекста.
Рис. 4.4 – Шифрование в режиме ECB
Следовательно, открытый текст может быть легко изменен путем
удаления, реплицирования и перестановки блоков шифротекста Скорость
обработки блоков в режиме ЕСВ фиксирована и определяется
эффективностью реализации блочного шифра. Режим ЕСВ допускает
эффективное распараллеливание вычислений. Однако конвейерная
обработка блоков в данном режиме невозможна.
В режиме СВС каждый i-й блок открытого текста суммируется по
модулю 2 (операция XOR) с (i-1)-м блоком шифротекста и затем
шифруется (рис. 4.5).
Начальное значение (в наших обозначениях со) задается вектором
инициализации.
Рис. 4.5 – Шифрование в режиме CBC
54
Криптостойкость режима СВС определяется криптостойкостью
используемого блочного шифра. Применение режима СВС позволяет
устранить недостаток режима ЕСВ: каждый блок открытого текста
«маскируется» блоком шифротекста, полученным на предыдущем этапе.
Таким образом, возможность изменения открытого текста при
использовании режима СВС весьма ограничена - любые манипуляции с
блоками шифротекста, за исключением удаления первого и последнего
блоков, будут обнаружены. Скорость обработки в данном режиме не
ниже производительности блочного шифра - задержка при выполнении
операции XOR пренебрежимо мала Процедура шифрования в режиме СВС
c трудом поддается распараллеливанию, процедуру дешифрования
распараллелить значительно проще.
Шифрование в режимах CFB и OFB
В режиме CFB i-й блок шифротекста формируется путем
шифрования (i-1)-го блока шифротекста и его суммированием (операция
XOR) с i-м блоком открытого текста (рис. 4.6).
Рис. 4.6 – Шифрование в режиме CFB
Режим CFB можно задать таким образом, что обратная связь будет
захватывать не целый n-битный блок, а только k бит предыдущего блока, k
 n Начальное значение со так же, как в режиме СВС, задается при
помощи вектора инициализации
Криптостойкость
CFB
определяется
криптостойкостью
используемого шифра. Фиксированные блоки открытого текста
«маскируются» блоками шифротекста. Возможности изменения открытого
текста те же, что и в режиме СВС. Если в режиме CFB с полноблочной
55
обратной связью имеется два идентичных блока шифротекста, результат,
например, DES-шифрования на следующем шаге будет тем же. Скорость
шифрования CFB-режима с полноблочной обратной связью та же, что и у
блочного шифра, причем возможности распараллеливания процедуры
шифрования ограничены
Режим OFB аналогичен CFB, за исключением того, что суммируемые с
открытым текстом биты генерируются независимо от открытого текста и
шифротекста Вектор инициализации so задает начальное значение
последовательности блоков si, и каждый блок si, получается путем
шифрования предыдущею блока si-1,. Открытый текст шифруется
суммированием (операция XOR) i-го блока открытою текста с si, из
независимой последовательности блоков (рис. 4.7).
Обратная связь по выходу на k разрядов не рекомендуется из
соображений криптостойкости. Режим OFB имеет следующее
преимущество по сравнению с режимом CFB: ошибки, возникающие в
результате передачи по каналу с шумом, при дешифровании не
«размазываются» по всему шифротексту, а локализуются в пределах
одною блока. Однако открытый текст может быть изменен путем
определенных манипуляций с блоками шифротекста. Скорость шифрования в режиме OFB также, что и у блочного шифра. Несмотря на то, что
OFB-шифрование не поддается распараллеливанию, эффективность
процедуры может быть повышена за счет предварительной генерации
независимой последовательности блоков.
Рис. 4.7 – Шифрование в режиме OFB
Шифрование в режимах усовершенствованного OFB и РСВС
Известные недостатки привели к появлению усовершенствованного
варианта шифрования в режиме OFB [189]. Основные изменения касаются
метода генерации независимой последовательности блоков: для получения
очередного блока предлагается шифровать не si, a si + IV(mod 264), где IV
— некоторый вектор инициализации.
56
Режим шифрования РСВС (Propagating Cipher Block Chaining)
применяется в протоколе Kerberos (версия 4) и позволяет обнаруживать
ошибки. Данный режим шифрования не является федеральным или
международным стандартом. Режим РСВС  вариант режима СВС,
обладающий специфическим свойством, — в результате дешифрования
единичная ошибка распространяется на весь шифротекст (решается
обратная задача с точки зрения режима OFB). Данное свойство позволяет с
высокой надежностью обнаруживать ошибки, возникающие при передаче
сообщений по каналам с шумом. Шифрование в режиме РСВС
выполняется по правилу:
ci = Ek (mi  mi-1  ci-1 ),
(4.6)
дешифрование:
m i = Dk (ci)  ci-1  mi-1 ,
(4.7)
где m 0  c0  вектор инициализации.
Контрольные вопросы
1.
Понятие поточного шифра.
2.
Шифр Вернама, шифрование, требования к элементам структуры.
3.
Привести классификация синхронных поточных шифров, дать краткую
характеристику.
4.
Схема Джеффа и схема Брюс формирования ПСП, принципы работы.
5.
Принцип формирования ПСП по методу двухступенчатых отображений.
6.
Схема с нелинейной внешней и внутренней логикой, работа.
7.
Принцип самосинхронизирующегося поточного шифрования.
8.
Схема конструкции Фейстеля,работа.
9.
Перечислите режимы шифрования блочных шифров.
10. Привести основные характеристики стандарта DES.
11. Схема DES – преобразования, работа.
12. Перечислите режимы работы стандарта DES
57
5 СТАНДАРТЫ БЛОЧНОГО ШИФРОВАНИЯ
5.1 Федеральный стандарт США - DES
Стандарт шифрования данных DES [6] (Data Encryption Standard),
который ANSI называет алгоритмом шифрования данных DEA (Data
Encryption Algorithm), a ISO — DEA-1, за 20 лет стал мировым
стандартом. За годы своего существования он выдержал натиск
различных атак и при известных ограничениях все еще считается
криптостойким.
DES представляет собой блочный шифр, шифрующий данные 64битовыми блоками. С одного конца алгоритма вводится 64-битовый блок
открытого текста, а с другого конца
выходит 64-битовый блок
шифротекста.
DES является симметричным алгоритмом: для шифрования и дешифрования используются одинаковые алгоритм и ключ (за исключением небольших различий в использовании ключа). Длина ключа равна
56 битам. (Ключ обычно представляется 64-битовым числом, но каждый
восьмой бит используется для проверки четности и игнорируется. Биты
четности являются наименьшими значащими битами байтов ключа.)
Ключ, который может быть любым 56-битовым числом, можно изменить
в любой момент времени.
Криптостойкость
полностью
определяется
ключом.
Фундаментальным строительным блоком DES является комбинация
подстановок и перестановок. DES состоит из 16 циклов (рис. 5.1).
В общем виде цикл преобразования представлен на риc. 5.2.
Если Li и Ri - левая и правая половины, полученные в результате i-й
итерации, Кi — 48-битный ключ для цикла i, а f - функция,
выполняющая все подстановки, перестановки и XOR с ключом, то один
цикл преобразования можно представить как
(Li , Ri) = (Ri-1 , Li-1  f(Ri-1 , Кi)).
(5.1)
Учитывая подстановку Fi () и перестановку Ti (), цикл
преобразования можно представить так, как это сделано на рисунке 5.1.
Из рисунка 5.1 видно, что каждый цикл DES представляет собой
композиционный шифр с двумя последовательными преобразованиями —
подстановкой Fi () и перестановкой Ti () (за исключением последнего,
шестнадцатого цикла, где перестановка опускается).
58
Рис. 5.1 - Схема DES - преобразования
Рис. 5.2 – Общий вид цикла DES - преобразования
59
Рис. 5.3 – Цикл DES с учѐтом перестановки и подстановки
Подстановка
Fi (Li-1 , Ri-1) = (Ri-1 , Li-1  f(Ri-1 , Кi))
(5.2)
является инволюцией, так как
Fi (Fi (Li-1 , Ri-1)) = Fi ((Ri-1 , Li-1  f(Ri-1 , Кi)))=
= ((Ri-1 , Li-1  f (Ri-1 , Кi))  ( f(Ri-1 , Кi))= (Li-1 , Ri-1)
(5.3)
В свою очередь, подстановка T(L‘i , Ri’ ) = (Ri’ , L‘i) также является
инволюцией,
поскольку
T(T(L‘i , Ri’ )) = T(Ri’ , L‘i) = (L‘i , Ri’ )
(5.4)
Если обозначить начальную и завершающую перестановки как (IP)
и (IP )-1, то прямое DES-преобразование (шифрование) реализует
функцию
DES = (IP)F1TF2T...F15TF16 (IP)-1
(5.5)
а обратное DES-преобразование (дешифрование) реализует функцию
DES -l = (IP)-lFl6TF15T...F2TF1(IP)
(5.6)
Таким образом, DES является шифром Фейстеля и сконструирован
так, чтобы выполнялось полезное свойство: для шифрования и
дешифрования используется один и тот же алгоритм. Единственное
отличие состоит в том, что ключи должны использоваться в обратном
порядке.
60
Рис. 5.4 – Один цикл DES – преобразования
То есть если при шифровании использовались ключи К1, К2,
К3,…К16 ,
то ключами дешифрования будут K16,K15, К14, …, К1 Алгоритм использует
только стандартную арифметик 64-битовых чисел и логические операции, поэтому легко реализуется на аппаратном уровне.
DES работает с 64-битовым блоком открытого текста. После
первоначальной перестановки блок разбивается на правую и левую
половины длиной по 32 бита. Затем выполняется 16 преобразований
(функция f), в которых данные объединяются с ключом. После
шестнадцатого цикла правая и левая половины объединяются, и
алгоритм завершается заключительной перестановкой (обратной по
отношению к первоначальной). На каждом цикле (см. рисунок 5.4) биты
ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов.
Правая половина данных увеличивается до 48 битов с помощью
перестановки с расширением, объединяется посредством XOR с 48
битами смещенного и переставленного ключа, проходит через 8 S-блоков,
образуя 32 новых бита, и переставляется снова. Эти четыре операции и
выполняются функцией f.
Затем результат функции f объединяется с левой половиной с
помощью другого XOR. В итоге этих действий появляется новая правая
половина, а старая правая становится новой левой половиной. Эти
действия повторяются 16 раз образуя 16 циклов DES.
Начальная перестановка выполняется еще до первого цикла, при
этом входной блок переставляется так, как показано в таблице 5.1.
61
Таблица 5.1 - DES — начальная перестановка
58
62
57
61
50
54
49
53
42
46
41
45
34
38
33
37
26
30
25
29
18
22
17
21
10
14
9
13
2
6
1
5
60
64
59
63
52
56
51
55
44
48
43
47
36
40
35
39
28
32
27
31
20
24
19
23
12
16
11
15
50
3
54
5
42
60
46
28
34
52
38
20
26
44
30
12
18
36
22
4
4
8
3
7
Таблица 5.2 - DES — преобразование ключа
57
10
63
14
49
2
55
6
41
59
47
61
33
51
39
53
25
43
31
45
17
35
23
37
9
27
15
29
1
19
7
21
58
11
62
13
Эту и все другие таблицы настоящей главы следует читать слева
направо и сверху вниз. Например, начальная перестановка перемещает
бит 58 в позицию 1, бит 50 — в позицию 2, бит 42
в позицию 3 и так
далее.
Начальная перестановка и соответствующая заключительная
перестановка не влияют на криптостойкость DES (перестановка в первую
очередь служит для облегчения побайтной загрузки данных открытого
текста и шифротекста в микросхему DES).
Процедура преобразования ключа сводится к следующим
действиям. Сначала 64-битовый ключ DES уменьшается до 56-битового
ключа отбрасыванием каждого восьмого бита, как показано в таблице
5.2. Эти биты используются только для контроля четности, позволяя проверять правильность ключа. После извлечения 56-битного ключа для
каждого из 16 циклов генерируется новый 48-битный подключ. Эти
подключи, К2, определяются следующим образом. Сначала 56-битный
ключ делится на две 28-битные половины. Затем половины циклически
сдвигаются влево на один или два бита в зависимости от номера цикла.
Этот сдвиг показан в таблице 5.З.
Таблица 5.З. DES — сдвиг ключа в зависимости от номера цикла
Номер цикла 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Сдвиг (бит) 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
После сдвига выбирается 48 из 56 битов. Так как при этом не только
выбирается подмножество битов, но и изменяется их порядок, эта
операция получила название перестановка со сжатием. Ее результатом
является набор из 48 битов. Перестановка со сжатием определена в табл.
62
5.4. Например, бит сдвинутого ключа в позиции 33 перемещается в
позицию результата, а 18-й бит сдвинутого ключа отбрасывается.
Таблица 5.4 - DES — перестановка со сжатием
14
23
41
44
17
19
52
49
11
12
31
39
24
4
37
56
1
26
47
34
5
8
55
53
3
16
30
46
28
7
40
42
15
27
51
50
6
20
45
36
21
13
33
29
10
2
48
32
Из-за сдвига для каждого подключа используются различные
подмножества бит ключа. Каждый бит используется приблизительно в
четырнадцати из шестнадцати подключей, при этом не все биты
используются одинаковое число раз.
Операция перестановки с расширением правой половины данных, Ri,
от 32 до 48 битов и изменением их порядка, называется перестановкой
с расширением. У этой операции две задачи: привести размер правой
половины в соответствие с ключом для операции XOR и получить более
длинный результат, который можно будет сжать в ходе операции
подстановки.
Однако криптографический смысл данной операции состоит в том,
что за счет влияния одного бита на две подстановки быстрее возрастает
зависимость битов результата от битов исходных данных. Данная
зависимость называется лавинным эффектом. DES спроектирован так,
чтобы как можно быстрее добиться зависимости каждого бита
шифротекста от каждого бита открытого текста и каждого бита ключа.
Перестановка с расширением показана на рисунке 5.5.
Рис 5.5 - DES — схема перестановки с расширением
Иногда она называется E-блоком (от expansion). Для каждого 4битного входного блока первый и четвертый биты представляют собой
два бита выходного блока, а второй и третий биты — один бит
выходного блока. В табл. 5.5 показано соответствие позиций результата и
исходных данных. Например, бит входного блока в позиции 3
63
переместится в позицию 4 выходного блока, а бит входного блока в
позиции 21 — в позиции 30 и 32 выходного блока.
Таблица 5.5 - DES — перестановка с расширением
32
8
16
24
1
9
17
25
2
10
18
26
3
11
19
27
4
12
20
28
5
13
21
29
4
12
20
28
5
13
21
29
6
14
22
30
7
15
23
31
8
16
24
32
9
17
25
1
Хотя выходной блок больше входного, каждый входной блок
генерирует уникальный выходной блок.
После объединения сжатого блока с расширенным блоком с
помощью XOR над 48-битным результатом выполняется операция
подстановки. Подстановки производятся в восьми блоках подстановки,
или S-блоках (от substitution). У каждого S-блока есть 6-битный вход и
4-битный выход, всего используется восемь различных S-блоков
(для восьми S-блоков DES потребуется 256 байтов памяти). 48 битов
делятся на восемь 6-битных подблоков. Каждый отдельный подблок
обрабатывается отдельным S-блоком: первый подблок - первым Sблоком, второй
- вторым S-блоком и так далее (см. рис. 5.6).
Рис. 5.6 - DES — подстановка при помощи S-блоков
64
Таблица 5.6 - DES — S-блок 1
14
0
4
15
4
15
1
12
13
7
14
8
1
4
8
2
2
14
13
4
15
2
6
9
11
13
2
1
8
1
11
7
3
10
15
5
10
6
12
11
6
12
9
33
12
11
7
14
5
9
3
10
9
5
10
0
0
3
5
6
7
8
0
13
4
14
1
2
9
12
5
11
7
0
8
6
2
1
12
7
13
10
6
12
12
6
9
0
0
9
3
5
5
11
2
14
10
5
15
9
5
10
0
7
1
2
11
4
13
8
1
15
12
5
2
14
7
14
12
3
11
12
5
11
4
11
10
5
2
15
14
2
8
1
7
12
10
3
13
8
1
4
15
9
2
7
1
4
8
2
3
5
5
12
14
11
11
1
5
12
12
10
2
7
4
14
8
2
15
9
4
14
6
1
8
13
8
5
15
6
5
0
9
15
3
15
12
0
15
10
5
9
13
3
6
10
0
9
3
4
14
8
0
5
9
6
14
3
Таблица 5.7 - DES — S-блок 2
15
3
0
13
1
13
14
8
8
4
7
10
14
7
11
1
6
15
10
3
11
2
4
15
3
8
13
4
Таблица 5.8 - DES — S-блок 3
10
13
13
1
0
7
6
10
9
0
4
13
14
9
9
0
6
3
8
6
3
4
15
9
15
6
3
8
Таблица 5.9 - DES — S-блок 4
7
13
10
3
13
8
6
15
14
11
9
0
3
5
0
6
0
6
12
10
6
15
11
1
9
0
7
13
Таблица 5.10 - DES — S-блок 5
2
14
4
11
12
11
2
8
4
2
1
12
1
12
11
7
7
4
10
1
10
7
13
14
11
13
7
2
Таблица 5.11 - DES — S-блок 6
12
10
9
4
1
15
14
3
10
4
15
2
15
2
5
12
9
7
2
9
2
12
8
5
6
9
12
15
8
5
3
10
0
6
7
11
13
1
0
14
3
13
4
1
4
14
10
7
14
0
1
6
7
11
13
0
5
3
11
8
11
8
6
13
13
10
14
7
3
14
10
9
12
3
15
5
9
5
6
0
7
12
8
15
5
2
0
14
10
15
5
2
6
8
9
3
1
6
2
12
1
4
2
13
10
12
0
15
9
5
6
12
3
6
10
9
14
11
13
0
5
0
15
3
0
14
3
5
12
9
5
6
7
2
8
11
23
21
19
17
63
61
59
57
31
29
27
25
Таблица 5.12 - DES — S-блок 7
4
13
1
6
11
0
4
11
2
11
11
13
14
7
13
8
15
4
12
1
0
9
3
4
8
1
7
10
Таблица 5.13 - DES — S-блок 8
13
1
7
2
2
15
11
1
8
13
4
14
4
8
1
7
6
10
9
4
15
3
12
10
11
7
14
8
Таблица 5.14 - DES — перестановка с помощью Р-блоков
16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25
Таблица 5.15 - DES — заключительная перестановка
40
38
36
34
8
6
4
2
48
46
44
42
16
14
12
10
56
54
52
50
24
22
20
18
64
62
60
58
32
30
28
26
39
37
35
33
7
5
3
1
47
45
43
41
15
13
11
9
55
53
51
49
Входные биты особым образом определяют элемент S-блока.
Рассмотрим 6-битовый вход S-блока: b1, b2, b3, b4, b5, и b6. Биты b1 и b6
объединяются, образуя 2-битное число от нуля до трех, соответствующее
строке таблицы. Средние четыре бита, с b2 по b5, объединяются, образуя 4битное число от нуля до пятнадцати, соответствующее столбцу таблицы.
Например, пусть на вход шестого S-блока (то есть биты функции XOR с 31
66
по 36) попадает 110011. Первый и последний биты, объединяясь, образуют
11, что соответствует строке три шестого S-блока. Средние четыре бита
образуют 1001, что соответствует столбцу девять того же S-блока. Элемент
шестого S-блока, находящийся на пересечении строки три и столбца девять, это 14 (строки и столбцы нумеруются с нуля, а не с единицы). Вместо 110011
подставляется 1110. Намного легче реализовать S-блоки программно в виде
массивов с 64 элементами. Для этого потребуется переупорядочить элементы.
Такой способ описания S-блоков помогает понять, как они работают. Каждый
S-блок можно рассматривать как функцию подстановки 4-битного элемента:
b2 по b5 являются входом, а некоторое 4-битное число - результатом. Биты b1 и
b6 определяются соседними блоками, они определяют одну из четырех
функций подстановки, возможных в данном S-блоке. Подстановка с помощью
S-блоков является ключевым этапом DES. Другие действия алгоритма
линейны и легко поддаются анализу. S-блоки нелинейны, и именно они в
большей степени, чем всѐ остальное, обеспечивают криптостойкость DES. В
результате этой подстановки получаются восемь 4-битных блоков, которые
вновь объединяются в единый 32-битный блок. Этот блок поступает на вход
следующего этапа — перестановки с помощью Р-блоков.
32-битовый выход подстановки с помощью S-блоков перетасовывается в
соответствии с Р-блоком. Эта перестановка перемещает каждый входной бит в
другую позицию, ни один бит не используется дважды, и ни один бит не
игнорируется. Этот процесс называется прямой перестановкой, или просто
перестановкой. Позиции, в которые перемещаются биты, показаны в таблице
5.14. Например, двадцать первый бит перемещается в позицию четыре, а
четвертый бит — в позицию тридцать один.
Наконец, результат перестановки с помощью Р-блока объединяется
посредством XOR с левой половиной первоначального 64-битового блока.
Затем левая и правая половины меняются местами, и начинается следующий
цикл криптографического преобразования.
Заключительная перестановка является обратной по отношению к
начальной перестановке и описана в таблице 5.15. Отметим, что левая и правая
половины не меняются местами после завершения последнего цикла DES,
вместо этого объединенный блок R16, L16
используется как вход
заключительной перестановки. Перестановка половин с последующим
циклическим сдвигом привела бы к точно такому же результату. Это сделано
для того, чтобы алгоритм можно было использовать как для шифрования,
так и для дешифрования.
Алгоритм, который создает ключ для каждого цикла, также цикличен.
Ключ
сдвигается
направо,
а
число
позиций
сдвига
равно
0,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1.
Режимы работы стандарта DES
67
FIPS PUB 81 (Federal Information Standards Publication) определяет
четыре режима работы: ЕСВ, СВС, OFB и CFB. Банковские стандарты ANSI
определяют для шифрования ЕСВ и СВС, а для проверки подлинности СВС и
n-битовый CFB. Из-за простоты реализации в большинстве существующих
коммерческих программ используется ЕСВ, хотя этот режим наиболее уязвим.
СВС используется редко, несмотря на то, что он лишь незначительно более
сложен, чем ЕСВ и обеспечивает большую криптостойкость.
Криптостандарт DES стал объектом скрупулезных криптоаналитических исследований с момента его публикации в 1977 г. В том же году
Диффи и Хеллман предложили вариант специализированного компьютера
стоимостью двадцать млн. долл., гарантирующего раскрытие ключа DES
методом силовой атаки в течение одних суток. В 1993 г. Винер (М. J.
Wiener) спроектировал специализированную компьютерную архитектуру
стоимостью в один млн. долл., позволяющую раскрывать ключ DES в
среднем за 3,5 час. Реализация идей Винера на современном
технологическом уровне позволяет раскрывать ключ DES в среднем за 35
мин. Силовая атака на основе метода распределенных вычислений обеспечивает раскрытие ключа в течение 90 и даже 40 календарных дней. В 90-е
годы были разработаны и применены для атаки на DES методы
дифференциального и линейного криптоанализа.
Однако известны и другие разновидности атак, позволяющие при
заданном шифротексте получать открытый текст, не раскрывая при этом
секретного ключа. Примером являемся атака на основе сопоставления
образцов шифротекста (matching ciphertext attack), эффективность которой
зависит исключительно от длины блока шифра. Основная идея атаки
заключается в поиске одинаковой пары среди заданного набора блоков
шифротекста. В случае использования режима ЕСВ последнее означает, что
соответствующие блоки открытого текста также являются идентичными.
Атака возможна при использовании режимов СВС и CFB.
Рассмотрим режим СВС. Обозначим через Рi и Сi блоки открытого
текста и шифротекста соответственно. Тогда Сi = Ек (Рi  Сi-1) - перед
шифрованием текущий блок открытого текста суммируется (по модулю 2,
операция XOR) с полученным на предыдущем шаге блоком шифротекста. Из
равенства Сi = Сj следует, что Рi  Сi-1 = Рj  Сj-1. Для дальнейших
рассуждений необходимо ввести понятие расстояния Хэмминга.
Расстояние Хэмминга dist (x,y) между двумя двоичными векторами х
= х 1 ,... ,х n и у = y1 ,…,yn , равно числу позиций, в которых они различаются.
Например. dist(10111,00101) = 2. Вес Хэмминга wt (x) вектора х = х1 ,... ,хn
равен числу ненулевых компонентов хi, например wt(101110) = 4.
Очевидно, что dist(x,y) = wt (x  y), где х  у покомпонентная сумма по
модулю 2 (операция XOR) векторов х и у.
Таким образом, расстояние Хэмминга i-го и j-ro блоков открытого
текста равно расстоянию Хэмминга (i - 1)-го и (j - 1)- го блоков шифротекста,
68
поскольку Рi  Рj = Сi-1  Сj-1. При длине блока n совпадения пары можно
ожидать на множестве из 2 n / 2 блоков шифротекст. Для DES это 232 блоков.
Для обеспечения высокого уровня криптостойкости рекомендуют
применять тройное DES-шифрование на трех или на двух различных ключах.
Такие режимы известны под общим названием EDE (encrypt-decrypt-encrypt).
Так, при двух различных ключах блок открытого текста сначала шифруется
на ключе К1 , дешифруется на ключе К2 и затем опять шифруется на ключе
К1 . При трех различных ключах данный метод позволяет увеличить размер
ключевого пространства до 2168, при двух до 2 112. Однако угроза атаки на
основе сопоставления образцов шифротекста при этом сохраняется, так как
длина блока DES фиксирована (64 бита).
В течение ряда лет комитет X9.F.1 Американского национального
института стандартов (National Institute of Standards and Technology, NIST)
занимался исследованием различных режимов для метода тройного DESшифрования. Основу предложенной NIST разработки составили известные
режимы ЕСВ, СВС, OFB и CFB с заменой базовой операции однократного
шифрования на тройное DES-шифрование.
Рис. 6.1 – DES – режим TCBC
В режиме Обратной связи но шифротексту для тройного DES (Triple
DES Cipher Block Chaining, ТСВС) блок шифротекста, суммируемый с блоком
открытого текста, получается в результате тройного DES-шифрования. ТСВС
называют также внешним СВС-режимом (outer-CBC mode), подразумевая
под этим, что блок шифротекста берется с выхода тройного DESшифратора. Схема режима ТСВС представлена на рис. 6.1. Данный режим
уязвим с точки зрения атаки на основе сопоставления образцов шифротекста
69
и по очевидным причинам в три раза менее производителен, чем однократный
DES. Недостатки ТСВС стали причиной разработки внутреннего СВС-режима
(inner-CBC mode, 1СВС) (рис. 6.2).
Рис. 6.2 - DES – режим ICBC
В этом режиме обратная связь реализуется при помощи блоков
шифротекста с выхода одиночного DES-шифратора. Режим ICBC можно
интерпретировать как трехкратное применение стандартного СВС-режима на
трех различных ключах. Разработчики предполагали, что режим ICBC
обеспечивает высокую криптостойкость при атаке на основе сопоставления
образцов шифротекста и не менее криптостоек, чем режим трехкратного DESшифрования на трех различных ключах. Результаты последних исследований
показали, что объем перебора для режима EDE не превосходит 2109. Кроме
того, режим ICBC допускает эффективную конвейерную аппаратную
реализацию и позволяет достичь той же производительности, что и
однократный DES.
Тем не менее, проанализировав большое число различных режимов
шифрования, Бихам (Е. Biham) продемонстрировал уязвимость режима
ICBC. Трудоемкость атаки Бихама лишь незначительно превышает
трудоемкость атаки на однократный DES. Исходное предположение
заключается в возможности контроля обратных связей со стороны
криптоаналитика. Атакующий выбирает шифротекст вида (С,С,С,С), где все
четыре блока идентичны. После дешифрования на одном СВС-уровне
исходный шифротекст принимает вид (?,Х,Х,Х), где блоки X идентичны, но
не известны криптоаналитику. После дешифрования на двух уровнях
получаем (?, ?,У, У), где блоки У идентичны, а после дешифрования на всех
70
трех уровнях получаем (?, ?, ?, Z) для некоторого Z. Для успешного
осуществления атаки необходимо 2 33 шифротекстов для различных С.
Вероятность того, что два шифротекста, например С1 и С2, приведут к одному
и тому же значению X и, следовательно, одним и тем же значениям У и Z,
достаточно велика (парадокс «дня рождения» - разновидность силовой атаки,
основанной на следующем известном факте: вероятность совпадения дней
рождения двух и более человек в группе из 23 человек превышает 1/2. Так. если
на вход некоторой функции подается случайное значение, а на выходе
наблюдается одно из к возможных независимых значений с равномерным
распределением, то, подавая на вход различные значения, можно ожидать
появления одинаковых значений на выходе функции с вероятностью 1,2k ).
При заданной паре С1 и С2 криптоаналитик может раскрыть ключ Кз
методом силовой атаки, используя в качестве критерия условие DK3 (C1)  C1
= DK3 (C2)  C2. При заданном К3 оставшиеся ключи раскрываются
аналогичным образом. Общая трудоемкость атаки всего в несколько раз
выше, чем трудоѐмкость силовой атаки на однократный DES и не сравнима с
трудоемкостью атаки на DES в режиме EDE.
В статьях Копперсмит (D. Coppersmith), Джонсон (D. В. Johnson) и
Матиас (S. M. Matyas) предложили тройное DES-шифрование в режиме СВС
с OFB-маскированием (СВС with OFB Masking, СВСМ). Основная цель при
проектировании
СВСМ
заключалась
в
обеспечении
адекватной
криптостойкости при атаках, описанных в атаке на основе сопоставления
образцов шифротекста и ряда других.
Режим СВСМ аналогичен СВС с базовой операцией трехкратного
шифрования на двух различных ключах, при этом промежуточные блоки
шифротекста между первым и вторым, а также вторым и третьим уровнями
маскируются блоками шифротекста, полученными в результате DESшифрования на третьем ключе в режиме OFB (рис. 6.3, где М1,М2,... и т.д. —
выходные блоки OFB-режима, полученные в результате шифрования на
ключе К3, и IV1 — вектор инициализации).
71
Рис. 6.3 - DES – режим CBCМ
Основной недостаток режима — низкая производительность; на один
64-битный блок открытого текста приходится четыре DES-шифрования на
трех различных ключах. Анализируя варианты использования внутренней
обратной связи с учетом возможностей описанной выше атаки Бихама,
авторы статей приходят к выводу о бесперспективности дальнейших
разработок режимов шифрования с внутренней обратной связью. При этом
применение только внешней обратной связи также нельзя признать
удовлетворительным. Приведенные аргументы стали причиной разработки
режима СВСМ, включающего как внешние, так и внутренние обратные
связи, причем последние не могут контролироваться криптоаналитиком, так
как являются выходом DES-шифратора в OFB-режиме.
Криптостойкость СВСМ при различных атаках,
описанных
в
доказана в статье .
В результате режим СВСМ был принят в качестве стандарта и
включен в документ. Однако сразy же вслед за принятием стандарта Бихам и
Кнудсен (L. R. Knudsen) предложили оригинальный вариант атаки на режим
СВСМ .
Суть предложенной атаки заключается в том, что вместо контроля
обратных связей можно воспользоваться их структурой. Для этого вводится
понятие фиксированной точки в криптографическом преобразовании.
72
Фиксированная точка функции f есть значение x, такое что f(x) = х. Важное
наблюдение заключается в том, что, когда вход среднего дешифратора
является фиксированной точкой, результаты дешифрования и маскирования на
втором (среднем) уровне взаимно уничтожаются и трехкратное шифрование
сводится к двухкратному с использованием одного и того же ключа дважды.
При большом количестве блоков открытого текста и шифротекста вероятность
обнаружения преобразований с фиксированной точкой достаточно велика.
Основная задача заключается в определении блоков с фиксированной точкой.
Следующее наблюдение указывает на то, что для большинства функций f
существует в точности одна фиксированная точка х. Для реализации атаки
необходимо огромное количество выборочных блоков шифротекста,
превышающее период OFB потока. В качестве исходного материала было
выбрано 264 фиксированных блоков шифротекста С1 и столько же блоков С2,
С2  С1. При заданном открытом тексте можно определить период OFBпотока. Поиск ключа К1 выполняется путем дешифровании блоков С1 и C2 на
ключе К, при этом претенденты выбираются из ключевого пространства 256.
Блоки с фиксированной точкой определяются путем сравнения результатов с
блоками открытого текста. Поскольку фиксированная точка уникальна, пара
шифрований на втором уровне имеет одинаковые данные, что позволяет
установить различие между двумя дополнительными блоками с одинаковыми
масками. Дополнительные блоки используются затем для проверки ключапретендента К. Детальное описание атаки приводится в статье. Для
осуществления атаки достаточно 265 блоков выборочного шифротекста, в ходе
атаки необходимо выполнить 2 58 попыток трехкратного DES-шифрования,
кроме того, необходима дополнительная память для хранения блоков
открытого текста. Описанная атака имеет теоретический характер и вряд ли
будет реализована на практике. Однако ее трудоемкость значительно ниже
трудоемкости известных атак на режим EDE.
Существует несколько простых способов модификации СВСМ-режима.
позволяющих противостоять описанной выше атаке. Однако нет полной
уверенности в том, что эти модификации гарантируют адекватную
криптостойкость.
Один из очевидных способов заключается в замене ключа К1 на
третьем уровне на ключ К4, К4  K1. При этом авторы атаки не рекомендуют
изменять способ OFB-маскирования между вторым и третьим уровнями, так
как существует эффективная атака. Возможное решение заключается также в
разработке нового режима шифрования. Например, Бихам предложил
следующее преобразование — OFB{CBC,CBC,CBC-l} (открытый текст
суммируется по модулю 2 (операция XOR) с OFB-потоком, генерируемым
однократным DES, затем шифруется в режиме СВС на третьем ключе, снова
суммируется с тем же OFB-потоком, дешифруется в режиме СВС на
четвертом ключе и опять суммируется с тем же OFB-потоком), вектор
инициализации вычисляется как КАС от некоторого начального значения,
передаваемого в открытом виде от отправителя к получателю.
73
Криптостойкость этого режима шифрования пока не скомпрометирована,
трудоемкость атаки оценивается как 2112 попыток дешифрования, даже при
условии, что криптоаналитик может получить неограниченное количество
выборочных шифротекстов с фиксированным вектором инициализации.
Данный режим допускает эффективную аппаратную реализацию по
конвейерному принципу и может гарантировать то же быстродействие, что и
однократный DES при аппаратной реализации и режим СВСМ при
программной реализации.
Еще одно решение заключается в разработке нового блочного шифра. В
статье Кнудсен предложил новый блочный шифр DEAL и выполнил анализ
его криптостойкости. По оценкам автора трудоемкость любой атаки на DEAL
оценивается как 2120 попыток дешифрования в худшем случае. DEAL имеет
простую конструкцию. Цикл криптографического преобразования сводится к
следующему: открытый текст делится на блоки по 128 бит каждый; левая и
правая половины поступают на вход DES и шифруются на ключе К1,
результат шифрования суммируется по модулю 2 (операция XOR) с правой
половиной, затем половины меняются местами. Результирующий шифротекст
получается после шести циклов преобразования, причем на каждом цикле
используется новый ключ. Таким образом DEAL является шифром Фейстеля
с шестью циклами и криптоалгоритмом DES в качестве функции f (рис. 6.3).
Для получения двух 64-битных блоков шифротекста необходимо выполнить
шесть DES-шифрований, поэтому DEAL имеет ту же производительность, что
и режим EDE. Шесть 56-битных подключей генерируются из секретного
ключа длиной 128, 192 или 256 бит.
Все рассмотренные выше режимы шифрования и другие методы
являются попыткой компенсации известных недостатков DES, связанных с
коротким ключом и блоком. В настоящее время стало ясно, что
принципиальное решение заключается в разработке нового блочного
стандарта шифрования с большей длиной ключа и блока, обеспечивающего
высокую криптостойкость по отношению ко всем известным атакам на
блочные шифры. Американский национальный институт стандартов выступил
с инициативой по разработке нового альтернативного стандарта AES
(Advanced Encryption Standard, AES). NIST выражает надежду, что стандарт
AES обеспечит высокий уровень криптостойкости на ближайшие 20 - 30 лет.
В своем проекте NIST выдвигает ряд требований: так, например,
предлагаемый в качестве кандидата блочный шифр должен иметь 128-битный
блок и оперировать с ключами длиной 128, 192 и 256 бит. Как отмечается в
комментарии NIST, блочный шифр с указанными параметрами «должен
гарантировать адекватную криптостойкость — не ниже, чем DES в режиме
EDE, и обеспечивать высокое быстродействие». Действительно, при 128битном блоке для реализации атаки на основе сопоставления образцов
шифротекста понадобится около 264 блоков шифротекста. Еще одно
требование заключается в представлении трех различных программных
реализаций шифра-кандидата на двух языках программирования, а также
74
оценке числа логических элементов, необходимых для его аппаратной
реализации. После отбора претендентов NIST готов представить их для
широкого обсуждения и сравнения по ряду параметров - быстродействию,
криптостойкости, простоте реализации, модульности и т.д. Ожидается, что
при сравнимом с DES быстродействии криптостойкость AES будет на
несколько порядков выше.
Контрольные вопросы
1.
2.
3.
4.
5.
Схема конструкции Фейстеля, работа.
Перечислите режимы шифрования блочных шифров.
Привести основные характеристики стандарта DES.
Схема DES – преобразования, работа.
Перечислите режимы работы стандарта DES
5.2 Стандарт России — ГОСТ 28147-89.
ГОСТ 28147-89 — это блочный шифр с 256-битным ключом и 32
циклами преобразования, оперирующий 64-битными блоками [7]. В
криптоалгоритме также используется дополнительный ключ, который
рассматривается ниже. Для шифрования открытый текст сначала разбивается
на левую и правую половины L и R. На i-м цикле используется подключ Кi:
Li = Ri-1 ,
Ri = Li-1  (f (Ri-1, Ki))
(7.1)
(7.2)
Один цикл криптографического преобразования показан на рис. 7.1.
Рис.
7.1.
Один
цикл
преобразования
ГОСТа
28147-89
75
Функция f реализована следующим образом. Сначала правая половина и
i-й подключ складываются по модулю 2 32. Результат разбивается на восемь 4битовых подпоследовательностей, каждая из которых поступает на вход
своего S-блока. ГОСТ использует восемь различных S-блоков, первые 4 бита
попадают в первый S-блок, вторые 4 бита — во второй S-блок и т.д. Каждый
S-блок представляет собой перестановку чисел от 0 до 15. Например, S-блок
может выглядеть как: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. В этом случае, если
на входе S-блока 0, то на выходе 7. Если на входе 1, на выходе 10 и т.д. Все
восемь S -блоков различны, они фактически являются дополнительным
ключевым материалом. Выходы всех восьми S -блоков объединяются в 32битовое слово, затем все слово циклически сдвигается влево на 11 битов.
Наконец, результат объединяется с помощью операции XOR с левой
половиной, и получается новая правая половина, а правая половина становится
новой левой половиной. Для генерации подключей исходный 256-битный
ключ разбивается на восемь 32-битных блоков: k1,k2,…,k8.
На каждом цикле,
как показано в табл. 3.16, используется свой подключ. Дешифрование
выполняется так же, как и шифрование, но инвертируется порядок подключей
ki. Стандарт не определяет способ генерации S -блоков.
Таблица 7.1. Использование подключей в ГОСТе 28147-89
Цикл
Подключ
Цикл
Подключ
1
1
17
1
2
2
18
2
3
3
19
3
4
4
20
4
5
5
21
5
6
6
22
6
7
7
23
7
8
8
24
8
9
1
25
8
10
2
26
7
11
3
27
6
12
4
28
5
13
5
29
4
14
6
30
3
15
7
31
2
16
8
32
1
14
10
2
15
8
13
9
4
6
2
14
14
4
3
0
9
11
3
15
4
10
6
10
2
1
8
12
6
9
8
14
3
12
1
7
12
14
5
7
14
7
0
6
11
0
9
6
6
15
7
0
2
3
12
8
11
5
5
9
5
11
15
2
8
3
9
11
3
2
14
12
12
Таблица 7.2. S-блоки ГОСТа 28147-89
S-блок 1:
S-блок 2:
S-блок 3:
S-блок4:
S-блок5:
S-блок6:
S-блок7:
S-блок8:
4
14
5
7
6
4
13
1
10
11
8
13
12
11
11
15
9
4
1
10
7
10
4
13
2
12
13
1
1
0
1
0
13
6
10
0
5
7
3
5
8
13
3
8
15
2
15
7
0
15
4
9
13
1
5
10
Набор S -блоков, указанный в табл. 7.1, рекомендуется стандартом
ГОСТ Р 34.11-94.
Главные различия между DES и ГОСТом заключаются в следующем:
- DES использует сложную процедуру для генерации подключей из ключей.
В ГОСТе эта процедура очень проста;
76
- в DES 56-битный ключ, а в ГОСТе - 256-битный. Если добавить секретные
перестановки S -блоков, то полный объем секретной информации ГОСТа
составит примерно 610 бит;
- у S -блоков DES 6-битные входы и 4-битные выходы, а у S -блоков ГОСТа
4-битные входы и выходы. В обоих алгоритмах используется по восемь S блоков, но размер S-блока ГОСТа равен четверти размера S -блока DES;
- в DES используются нерегулярные перестановки, названные Р-блоком, а в
ГОСТе используется 11-битный циклический сдвиг влево;
- в DES 16 циклов, а в ГОСТе – 32.
Силовая атака на ГОСТ абсолютно бесперспективна. ГОСТ
использует 256-битовый ключ, а если учитывать секретные S -блоки, то
длина ключа будет еще больше. ГОСТ, по-видимому, более устойчив к
дифференциальному и линейному криптоанализу, чем DES. Хотя случайные S
-блоки ГОСТа при некотором выборе не гарантируют высокой
криптостойкости по сравнению с фиксированными S -блоками DES, их
секретность увеличивает устойчивость ГОСТа к дифференциальному и
линейному
криптоанализу.
К
тому
же
эффективность
этих
криптоаналитических методов зависит от количества циклов преобразования
- чем больше циклов, тем труднее криптоанализ. ГОСТ использует в два
раза больше циклов, чем DES, что, возможно, приводит к несостоятельности
дифференциального и линейного криптоанализа. ГОСТ не использует
существующую в DES перестановку с расширением Удаление этой
перестановки из DES ослабляет его из-за уменьшения лавинного эффекта:
разумно предположить, что отсутствие такой операции в ГОСТе
отрицательно сказывается на его криптостойкости. С точки зрения
криптостойкости операция арифметического сложения, используемая в
ГОСТе, не хуже, чем операция XOR в DES. Основным различием
представляется использование в ГОСТе циклического сдвига вместо
перестановки. Перестановка DES увеличивает лавинный эффект. В ГОСТе
изменение одного входного бита влияет на один S -блок одного цикла
преобразования, который затем влияет на два S -блока следующего цикла,
затем на три блока следующего цикла и т.д. Потребуется восемь циклов,
прежде чем изменение одного входного бита повлияет на каждый бит
результата; в DES для этого нужно только пять циклов. Однако ГОСТ
состоит из 32 циклов, a DES только из 16. Разработчики ГОСТа пытались
достигнуть равновесия между криптостойкостью и эффективностью. Взяв за
основу конструкцию Фейстеля, они разработали криптоалгоритм, который
лучше, чем DES, подходит для программной реализации. Для повышения
криптостойкости введен сверхдлинный ключ и удвоено количество циклов.
Однако вопрос, увенчались ли усилия разработчиков созданием более
криптостойкого, чем DES, криптоалгоритма, остается открытым.
77
6 ОСНОВЫ КРИПТОАНАЛИЗА
6.1 Дифференциальный криптоанализ
Метод дифференциального криптоанализа впервые был применен для
атаки на блочный шифр FEAL-4 [8]. Впоследствии метод был
усовершенствован и успешно применен для криптоанализа DES. Метод
дифференциального криптоанализа позволил получить ответ на вопрос о
числе циклов криптографического преобразования стандарта DES. Этот ответ
важен с точки зрения разработки эффективных методов криптоанализа произвольных итерированных блочных шифров конструкции Фейстеля. Вопрос
формулировался следующим образом: почему число циклов преобразования
равно шестнадцати, не больше и не меньше? Известно, что после пяти циклов
каждый бит шифротекста является функцией всех битов открытого текста и
ключа. После восьми циклов наблюдается пик лавинного эффекта —
шифротекст представляет собой случайную функцию всех битов открытого
текста и ключа. Успешные атаки на DES с тремя, четырьмя и шестью циклами
подтвердили результаты исследований лавинного эффекта. На первый взгляд,
криптографическое преобразование с большим числом циклов (> 8)
представляется необоснованным с точки зрения эффективности реализации.
Однако успешный дифференциальный криптоанализ DES доказал:
трудоемкость (объем перебора) атаки на открытом тексте для DES с любым
количеством циклов, меньшим шестнадцати, ниже, чем трудоемкость силовой
атаки. При этом необходимо отметить, что вероятность успеха при силовой
атаке выше, чем при атаке методом дифференциального криптоанализа. Тот
факт, что метод дифференциального криптоанализа был известен в момент
разработки DES, но засекречен по очевидным соображениям, подтвержден
публичными заявлениями самих разработчиков.
Ядро метода составляет атака на основе выборочного открытого текста.
Идея заключается в анализе процесса изменения несходства для пары
открытых текстов, имеющих определенные исходные различия, в процессе
прохождения через циклы шифрования с одним и тем же ключом. Не
существует каких-либо ограничений на выбор открытых текстов. Достаточно
различия в некоторых позициях. В качестве меры несходства, как правило,
используют расстояние Хэмминга.
Исходя из различий в получившихся шифротекстах ключам
присваиваются различные вероятности. Истинный ключ определяется в
процессе дальнейшего анализа пар шифротекстов — это наиболее вероятный
ключ среди множества претендентов. Для пояснения рассмотрим один цикл
криптографического преобразования DES (рис. 7.2).
Пусть задана пара входов, X и X, с несходством Х.. Выходы, Y и Y, —
известны, следовательно, известно и несходство Y. Известны перестановка с
расширением Е и Р-блок, следовательно, известны А и С. Значения на
выходе сумматора по модулю 2 не известны, однако их несходство В известно
78
и равно А. Доказано, что для любого заданного А не все значения С
равновероятны. Комбинация А и С позволяет предположить значения битов
для Е(Х)  Кi, и Е(Х')  Кi . To, что Е(X) и Е(Х') известны, дает нам информацию о Кi .
На каждом цикле в преобразовании участвует 48-битный подключ
исходного 56-битного секретного ключа. Таким образом, раскрытие К16
позволяет восстановить 48 бит ключа. Остальные восемь можно восстановить
при помощи силовой атаки.
Рис. 7.2 – Один цикл DES-преобразования для двух входных блоков X и X
Несходство различных пар открытых текстов приводит к несходству
получаемых шифротекстов с определенной вероятностью. Вероятности можно
оценить, построив таблицу, строки которой представляют собой возможные
входы сумматора по модулю 2 (XOR двух различных наборов входных битов),
столбцы — возможные результаты операции XOR, а элемент на пересечении
строк и столбцов — частота появления конкретного результата суммирования
для заданного входа. Таблицу можно построить для каждого из восьми Sблоков DES. Различные несходства на отдельных циклах можно объединять.
Кроме того, при условии, что циклы независимы, вероятности могут
перемножаться.
Пара открытых текстов, соответствующих несходству с более высокой
вероятностью, подсказывает правильный ключ последнего цикла. Правильный
ключ цикла определяется статистически — один из подключей будет
встречаться чаще, чем все остальные. Очевидно, что для успешного раскрытия
необходимо достаточное количество данных — помимо статистического
материала необходимо хранить частотную таблицу; для этого понадобится не
более 253 бит памяти. В ходе дифференциального криптоанализа DES был
использован ряд приемов, позволивших сократить объем памяти и
оптимизировать некоторые вычисления.
79
Таблица 7.3 Дифференциальный криптоанализ: результаты атаки на DES
Кол-во Выборочные Известные Проанализированные Трудоемкость
циклов открытые
открытые открытые тексты
атаки
тексты
тексты
14
8
2
238
4
29
24
44
9
2
2
2
232t
10
224
243
214
215
11
231
247
2
232t
12
231
247
221
221
13
239
252
2
232t
14
239
251
229
229
15
247
256
27
237
16
227
255
236
237
tТрудоемкость может быть значительно снижена за счет четырехкратного
увеличения числа открытых текстов и метода группировок.
В табл. 7.3 приводится обзор наилучших результатов успешного
дифференциальною криптоанализа DES с различным количеством циклов.
Первый столбец содержит количество циклов. Два следующих столбца
содержат нижнюю оценку числа выборочных или заданных (известных)
открытых текстов, необходимых для осуществления атаки. Четвертый
столбец содержит количество действительно проанализированных
открытых текстов. В последнем столбце приведена оценка трудоемкости
атаки после обнаружения требуемой пары.
Наилучший известный результат успешного дифференциального
криптоанализа DES с шестнадцатью циклами требует 247 выборочных
открытых текстов. Можно воспользоваться атакой на известном открытом
тексте, но для этого потребуется уже 255 известных образцов. Трудоемкость
атаки — 237 DES-шифрований. Дифференциальный криптоанализ эффективен против DES и аналогичных алгоритмов с постоянными S-блоками.
Трудоемкость атаки зависит от структуры S-блоков. Для всех режимов
шифрования ЕСВ, СВС, CFB и OFB атака имеет одинаковую трудоемкость.
Криптостойкость DES может быть повышена путем увеличения числа циклов.
Трудоемкость дифференциального криптоанализа DES с семнадцатью или
восемнадцатью циклами эквивалентна трудоемкости силовой атаки. При
девятнадцати и более циклах дифференциальный криптоанализ невозможен
в принципе - для его реализации потребуется более 264 выборочных
открытых текстов (DES оперирует блоками по 64 бита, следовательно,
существует 2 различных открытых текстов). В общем случае доказательство
криптостойкости по отношению к атаке методом дифференциальною
криптоанализа заключается в оценке числа открытых текстов, необходимых
для выполнения атаки. Атака невозможна, если полученная оценка
превышает 2b, где b - разрядность блока в битах.
80
6.2 Дифференциальный криптоанализ на основе отказов устройства
В сентябре 1996 г. группа специалистов из компании Bellcore объявила о
новом методе криптоанализа, позволяющем эффективно раскрывать
секретный
ключ,
хранящийся
в
памяти
портативного
шифрующего/дешифрующего устройства, например Smart Card или PCMCIA
[8]. Сохранность ключа в подобных устройствах обеспечивается за счет
уникальных характеристик технологии TEMPEST. Впервые метод был
успешно применен для раскрытия ключа криптосистемы RSA. Дальнейшие
исследования нового метода, получившего название дифференциального
криптоанализа на основе сбоев устройства (Differential Fault Analysis, DFA),
продемонстрировали его эффективность при атаке на DES и другие блочные
шифры. Так, для раскрытия ключа DES понадобилось проанализировать
двести шифротекстов. полученных в результате шифрования открытых
текстов, хранящихся в памяти устройства. Показано, что применение
тройного DES-шифрования не влияет на трудоемкость атаки.
Известно, что некоторые виды излучения (например, ионизирующее
или радиоактивное) приводят к сбоям в работе электронного оборудования.
Именно эта идея и легла в основу криптоаналитической атаки, разработанной
криптоанали-тиками компании Bellcore. Предполагается, что криптоаналитик
имеет неограниченный доступ к шифрующему/дешифрующему устройству.
Открытый текст и секретный ключ хранятся в памяти устройства и
недоступны. Криптоаналитик искусственно вызывает сбои в работе
устройства, подвергая его облучению. Облучение приводит к инверсии бита
(или битов) в одном из регистров на некотором промежуточном этапе
криптографического преобразования. Для блочных шифров конструкции
Фейстеля инверсия возникает на одном из циклов преобразования. Позиция
инвертированного бита и номер цикла криптоаналитику также неизвестны.
Сбой в работе приводит к искажению шифротекста на выходе устройства.
Криптоаналитик пытается раскрыть секретный ключ, анализируя
искаженные и неискаженные шифротексты.
Рассмотрим описанный метод на примере криптоанализа DES.
Предположим, что имеется два различных шифротекста, полученных при
шифровании одного и того же открытого текста на фиксированном ключе.
Известно, какой шифротекст получен в результате инверсии одиночного бита
в процессе шифрования. Под инверсией подразумевается следующее: бит
правой половины входного блока на одном из 16 циклов DES-преобразования
меняет исходное значение 0 на значение 1, или наоборот. Причем позиция бита
и номер цикла преобразования выбираются случайно и имеют равномерное
распределение.
На первом этапе атаки необходимо установить номер цикла
преобразования, на котором произошла инверсия. Предположим, что инверсия
произошла на последнем, шестнадцатом цикле DES-преобразования. Если
инверсия произошла в правой половине блока (до заключительной
81
перестановки), то два шифротекста будут различаться в одном бите,
локализованном в правой половине блока. Различие левых половин блоков
шифротекста определяется выходами тех S-блоков (одного или двух), на входе
которых
появился
инвертированный
бит.
Применение
метода
дифференциального криптоанализа позволяет раскрыть шесть бит ключа для
каждого такого S-блока.
Рассмотрим случай, когда инверсия возникает на пятнадцатом цикле.
Для раскрытия бит ключа необходимо участие более двух S-блоков в
последнем цикле преобразования: различие в правой половине блоков
шифротекста эквивалентно различиям на выходе F-функции предпоследнего
цикла. По зафиксированным выходным изменениям можно установить
позицию одиночного инвертированного бита. Кроме того, можно определить,
какое изменение правой половины блока шифротекста приводит к
соответствующему изменению выхода F-функции на последнем цикле (суммы
по модулю 2 левой половины шифротекста и инвертированного бита).
Для раскрытия подключа последнего цикла преобразования
достаточно проанализировать менее двухсот шифротекстов. Дальнейшее
развитие атаки возможно в двух направлениях. Первый вариант - поиск
секретного ключа путем исчерпывающей проверки 28 = 256 кандидатов при
заданном подключе (напомним, что разрядность подключа — 48 бит).
Альтернативный вариант заключается в использовании знания о подключе,
полученного на последнем цикле, для анализа предшествующих циклов.
Последний вариант позволяет успешно атаковать DES в режиме EDEшифрования на трех различных ключах.
Описанный метод работает и в тех случаях, когда инверсия возникает
внутри F-функции или процедуры генерации подключей.
Метод дифференциального криптоанализа на основе отказов
устройства можно применять для атаки на такие блочные шифры, как IDEA,
RC5 и Feal. Некоторые блочные шифры, например Khufu, Khafre и Blowfish,
используют заданный секретный ключ для генерации S-блоков. В этом случае
описанный метод позволяет раскрывать не только ключи, но и сами S-блоки.
Рассмотренный
выше
криптоаналитический
метод
позволяет
эффективно раскрывать секретный ключ, хранящийся в памяти устройства,
даже тогда, когда сам алгоритм криптографического преобразования
неизвестен. Так, например, детали криптоалгоритма Skipjack составляют
государственную тайну и засекречены Агентством национальной безопасности
США. Однако аппаратная реализация криптоалгоритма в виде микросхемы
Clipper входит в состав многих коммерческих устройств шифрования,
например Fortezza PCMCIA.
Предполагается, что криптографические ключи хранятся в памяти с
асимметричной динамикой сбоев. Это означает, например, что переход из
состояния 1 в состояние 0 происходит с большей вероятностью, чем
противоположное событие. Ячейки CMOS имеют симметричную динамику
сбоев — все переходы равновероятны. Однако для некоторых видов
82
энергонезависимой памяти это не так. Например, при воздействии
ультрафиолетового излучения ячейки EEPROM памяти принимают значение
0 с большей вероятностью, чем значение 1.
Предполагается также, что в криптографическое устройство можно
вводить некоторый открытый текст m и в результате шифрования на ключе k,
хранящемся в энергонезависимой памяти, получать на выходе шифротекст с.
Поскольку память открыта на запись (но закрыта на чтение), в устройство
можно ввести новый n-битный ключ k' вместо старого ключа k. Еще раз
отметим, что основная задача криптоаналитика сводится не к дешифрованию
некоторого шифротекста (сделать это очень просто, так как имеется доступ к
соответствующему устройству), а к раскрытию секретного ключа,
хранящегося в памяти устройства шифрования/дешифрования.
Криптоаналитическая атака включает два этапа:
1)
на первом этапе неизвестный секретный ключ k, хранящийся в памяти
устройства, используется для серии шифрований фиксированного открытого
текста m0. После каждого шифрования устройство подвергается облучению. В
результате последовательность шифротекстов на выходе устройства будет
состоять из нескольких различных подпоследовательностей co,c1,c2,...,cf.
Изменение шифротекста - переход от сi к ci+1 - обусловлено направленной
инверсией (из 1 в 0) некоторых бит ключа, иными словами - заменой ключа
ki на ki+1, ki  ki+1. Поскольку wt(k)  n/2, можно предположить что f  n/2 и
шифротекст cf представляет собой результат шифрования m0 на нулевом
ключе kf. Отсутствие изменений в шифротексте после облучения —
естественный
признак вырождения ключа до нулевого состояния;
2)
на втором этапе выполняется восстановление исходного секретного
ключа k0 по нулевому ключу kf. Пусть известен некоторый промежуточный
ключ ki+1, тогда, согласно модели сбоев, разумно предположить, что ключ kf,
отличается от ki+1 в одной позиции, wt(ki  ki+1) = 1. Тогда для раскрытия
ключа ki достаточно зашифровать m0 на последовательности ключей k‗i+1,
получаемых из ki+1, последовательной заменой единиц на нули. Если
результат шифрования равен сi - ключ восстановлен.
Так как алгоритм шифрования неизвестен, то для проверки ключей
придется воспользоваться устройством шифрования. Как было отмечено
выше, устройство позволяет вводить различные ключи. Следовательно, для
восстановления неизвестного ключа k0 по известному kf понадобится
проверить О(n) ключей на каждом из О(n) шагов. Таким образом, трудоемкость метода оценивается как О(n2) операций шифрования.
Помимо раскрытия секретного ключа, хранящегося в памяти устройства
шифрования/дешифрования, можно попытаться решить и более сложную
задачу - идентифицировать неизвестный криптоалгоритм, включая
определение функций цикла, 5-блоки и подключи.
83
Рассмотрим метод идентификации исходя из предположения, что
реализованный в устройстве криптоалгоритм соответствует конструкции
Фейстеля.
Вначале необходимо установить, какие биты шифротекста получены в
результате обработки правого, а какие — левого подблока на последнем цикле
криптографического преобразования. Для этого необходимо выполнить серию
шифрований некоторого открытого текста В процессе шифрования устройство
подвергают облучению, что приводит согласно описанной выше модели сбоев
к инверсии некоторых битов. Анализ расстояния Хэмминга пары
шифротекстов — искаженного и неискаженного — позволяет установить
позиции бит, инвертированных на последнем или предпоследнем цикле
преобразования. В качестве критерия для выбора шифротекстов используется
некоторое пороговое значение, как правило, не превышающее четверти
размера блока. Таким образом, искаженные шифротексты, для которых
расстояние Хэмминга пары не превышает заданного порогового значения,
получены в результате сбоя на последнем или предпоследнем цикле
преобразования. Сбой на последнем цикле приводит к изменению одного бита
в правом и нескольких бит в левом подблоке. В 32-битном подблоке возможно
не более 32 инверсий. Следовательно, для анализа понадобится не более 32
искаженных шифротекстов. Искаженные шифротексты, полученные в
результате сбоя на последнем цикле, будут различаться в одном бите в
правом подблоке и нескольких битах в левом подблоке.
После определения бит правого и левого подблоков можно установить
их функциональную зависимость. Предположим, что в криптоалгоритме
применяется F-функция, состоящая из набора S-блоков. Некоторые биты
правого подблока поступают на вход S-блока: выходное значение формирует
биты левого подблока. Для определения входных и выходных бит, а также
номера каждого S-блока достаточно выбрать все пары шифротекстов,
различающихся в одном бите в правом подблоке. Информации о различиях в
левых подблоках для каждого номера позиции в правом подблоке достаточно
для определения номеров S-блоков, их размеров, а также входных и
выходных битов.
Содержимое S-блоков можно восстановить, построив таблицу Т(х) =
S(x  k)  u, где k — подключ, а неизвестное значение u получено из правого
подблока предыдущего цикла. Например, если в качестве неизвестного
криптоалгоритма используется DES, можно восстановить содержимое Sблоков, за исключением 6 + 4 = 10 из 64 х 4 = 256 неизвестных бит в каждом
блоке. Для LOKI удается восстановить 2 12 х 8 - (12 + 8) = 32 748 неизвестных
бит в каждом блоке. Недостающие биты могут быть восстановлены в
результате обработки данных, полученных на последнем цикле
преобразования. Описанный метод позволяет восстановить не сами S-блоки,
а их сумму по модулю 2 (операция XOR) с подключами. Восстановление Sблоков и подключей возможно путем анализа отличий результатов
шифрования на нескольких ключах и данных из таблицы Т. Описанный метод
84
был успешно применен для реконструкции S-блоков и алгоритма генерации
подключей для DES и LOKI.
В некоторых блочных шифрах нелинейная функция F может быть
реализована не в виде набора констант — S-блоков (как в DES и LOKI), а
как последовательность различных арифметических операций, сдвигов,
логических операций И, ИЛИ, НЕ и т.д. Подобные функции также поддаются
восстановлению. Можно восстановить F-функцию более общего вида с
произвольно заданной операцией суммирования (XOR) правой половины бит
подключа и некоторой функцией на выходе. В целях упрощения анализа
можно интерпретировать такую F-функцию как один большой S-блок.
Несмотря на высокую трудоемкость, задача восстановления такого S-блока
практически реализуема — число входных и выходных бит S-блока не
превышает половины размера блока шифротекста. Эффективность такого
подхода очевидна — другой метод идентификации блочного шифра на основе
исчерпывающего перебора известных шифров и возможных ключей имеет
практически неограниченную трудоемкость. Описанная атака применялась
для идентификации DES в качестве неизвестного блочного шифра. Для
идентификации бит правой половины, а также входных и выходных бит и
содержимого S-блоков потребовалось проанализировать около пятисот и пяти
тысяч искаженных шифротекстов соответственно. Для восстановления
входных значений S-блоков потребовалось проанализировать около десяти
тысяч искаженных шифротекстов.
Отметим, что трудоемкость восстановления содержимого S-блоков
существенно зависит от их размеров. Поскольку S-блок DES имеет 6-битный
вход, то для его реконструкции достаточно проанализировать не более 64
входных значений, полученных из искаженных блоков шифротекста.
Трудоемкость аналогичной реконструкции для LOKI значительно выше — S блоки имеют 12-битный вход (4096 различных значений).
6.3 Линейный криптоанализ
Метод линейного криптоанализа впервые был применен для атаки
блочного шифра FEAL и затем DES [9]. Данный метод использует линейные
приближения. Это означает, что, если выполнить операцию XOR над
некоторыми битами открытого текста, затем над некоторыми битами
шифротекста, а затем выполнить XOR результатов предыдущего
суммирования, можно получить бит, который равен сумме некоторых бит
ключа. Это называется линейным приближением, которое может быть
верным с некоторой вероятностью р. Если р  0,5, то этот факт можно
использовать для раскрытия бит ключа.
Рассмотрим данный метод подробнее. Пусть в общем виде линейное
выражение задается уравнением:
85
(7.3)
где i1, i2,…, ia, j1, j2,…, jb, и l1, l2,…, lc, позиции некоторых бит открытого текста Р,
шифротекста С и ключа К. (Напомним, что суммирования в (7.3)
выполняется по модулю 2) Для случайно выбранного открытого текста Р и
соответствующего шифротекста С уравнение (7.3) выполняется с
вероятностью р  1/2. Величина |р-1/2| определяет эффективность уравнения
(7.3).
Таким образом, при заданном эффективном линейном выражении
можно определить один бит ключа К, воспользовавшись следующим
алгоритмом максимума правдоподобия:
Алгоритм 1.
Шаг 1. Пусть T задает число открытых текстов, таких, что левая часть
уравнения (7.4) равна нулю.
Шаг 2. Тогда, если T > N/2 (N — общее число открытых текстов),
угадываем
Угадываем
(7.4)
Или угадываем
Вероятность успеха увеличивается с ростом N или |р — 1/2|.
Рассмотрим криптоалгоритм DES с n-циклами криптографического
преобразования. С учетом 48-битного ключа Кn и F-функции линейное
выражение принимает следующий вид:
(7.5)
где через СR обозначена правая половина блока шифротекста.
Оценивая эффективность уравнения (7.5) при подстановке различных
кандидатов, можно восстановить Кn и
. Для этого следует
воспользоваться следующим алгоритмом максимального правдоподобия:
Алгоритм 2.
Шаг 1. Пусть Т задает число открытых текстов, таких, что левая часть
уравнений (7.6) и (7.7) равна нулю для каждого кандидата Кn (i) (i = 1,2,...).
86
Шаг 2. Обозначим через Т mах и Т min максимальное и минимальное
значения средиT i .
Тогда
Если
угадываем
воспользовавшись кандидатом для Tmax
(7.6)
Если
угадываем
воспользовавшись кандидатом для Tmin
(7.7)
Рассмотрим линейные приближения для S-блоков. Задача заключается в
исследовании вероятности того, что некоторый бит на входе S-блока равняется
некоторому биту на выходе. Однако в более общем случае полезно рассмотреть
зависимости сумм бит на некоторых входных и выходных позициях.
Для заданного S-блока Sa(a = 1,2,..., 8) и чисел 1    6 3 и 1    1 5
определим NSa( ,  ) - число выходных значений для 64 возможных значений
на входе Sа, таких, что результат логической операции «И» суммы по модулю
2 некоторых бит значения на входе Sа и числа  равен результату логической
операции «И» суммы по модулю 2 некоторых бит значения на выходе Sа и числа
 . Данное условие можно записать в виде:
(7.8)
где S(x)t — t-й бит выходного значения S при заданном на входе значении х.
Если NSa( ,  ) не равно 32, можно сделать вывод о корреляционной
зависимости входных и выходных бит S. Например, уравнение 7.9 показывает,
что четвертый бит входных значений S5 равен сумме всех бит выходных
значений с вероятностью 12/64 = 0,19:
NS5(1 6 , 1 5 )=12.
(7.9)
Следующее уравнение выполняется с вероятностью 0,19 для случайно
выбранного X и зафиксированного К (с учетом перестановки в Е- и Р-блоках):
87
(7.10)
В усеченной табл. 7.4 представлены значения NS5( ,  ) - 32 для
всевозможных значений  (номер строки) и  (номер столбца). Исследование
полной таблицы показывает, что уравнение (7.4) является наилучшим
линейным приближением во всех S-блоках (то есть величина |NS5( ,  )|
принимает максимальное значение). Следовательно, уравнение (7.10) является
наилучшим линейным приближением для F-функции.
Из определения S-блоков вытекает, что
NSa( ,  ) четно;
если  = 1,32 или 33, то NSa( ,  ) = 32 для всех Sa и Sa.
Рассмотрим криптоалгоритм DES с тремя циклами преобразования.
Следующее уравнение выполняется для первого цикла с вероятностью 12/64:
(7.11)
где через PR и PL обозначены правая и левая половины открытого текста.
Аналогичное уравнение выполняется для последнего третьего цикла
преобразования:
(7.12)
где через CR и CL обозначены правая и левая половины шифротекста.
Таблица 7.4 - Криптоанализ DES: усеченная таблица значений NS5( ,  ) - 32
88
1
2
3
4
5
6
7
8
9
10
11
12 13 14 15
1
0
0
0
0
0
0
0
0
0
0
0
0
0
2
4
-2 2
-2 2
-4 0
4
0
2
-2
2
3
0
-2 6
-2 -2
4
0
0
-2
4
2
-2 0
0
2
-2 0
0
2
2
5
2
2
10
-6 -4
0
2
-10 0
6
-2 -4 -6 -2 -4
2
0
0
-2 0
7
2
0
2
-2 8
6
0
-4 6
8
0
2
6
0
0
-2 -6
-2 2
9
-4 6
-4
-6 -6
6
2
-4 0
-2 0
-4
0
1
-2 0
-4
2
6
-2 -2 4
-4
3
4
-4 -2 -2 0
4
4
-2 2
4
5
-2
-6 -8 2
0
6
0
-6
-2 0
4
-12 2
6
-2 0
-4
2
-6 -8 -4
9
2
-2
2
4
-4 -4 0
10
-8 -4 0
11
-6 -4
7
-4 4
8
10 4
0
0
-2 -6
2
11 4
4
4
6
2
-2 -2
-2 -2 -2
2
0
12 2
0
-2 0
2
4
10
-2 4
-2
-8
-2 4
-6 -4
12
13 6
0
2
-2
4
-10 -2 0
-2
4
-2 8
-6 0
13
-2 -4
14
0
2
0
14 -2 -2 0
-2 4
0
2
-2 0
4
2
-4 6
15 -2 -2 8
6
4
0
2
2
4
8
-2
8
-6 2
16 2
-2 0
0
-2
-6 -8
0
-2 -2
-4
0
2
17 2
-2 0
4
2
-2 -4
4
2
2
0
-8 -6 2
-4
-2 -8
4
6
4
6
-2 4
2
0
4
-6 4
0
0
0
18 -2 0
-2 2
19 -6 0
2
0
0
15
10 -20 16
4
17
-2 4
-6 0
18
2
-6 4
-2 0
19
-4 -4 4
4
0
4
-4 0
20
20 4
-4 0
21 4
0
-4 -4 4
-8 -8
0
0
-4
4
8
4
0
4
21
22 0
6
6
2
-2
4
0
4
0
6
2
2
2
0
0
22
23 4
-6 -2 6
-2
-4 4
4
-4 -6
2
-2 2
0
4
23
89
Таким образом, линейное приближение для третьего цикла выглядит
следующим образом:
(7.13)
Для случайно выбранного открытого текста Р и соответствующего
шифротекста С уравнение (7.13) выполняется с вероятностью (12/64) 2 + (1 12/64)2 = 0,70. Поскольку уравнение (7.11) является наилучшим линейным
приближением F-функции, уравнение (7.12) является наилучшим
приближением для DES с тремя циклами. Теперь, воспользовавшись Алгоритмом 1, можно решить уравнение (7.12) для того, чтобы получить значение
К122 К322.
Описанный метод можно обобщить на полный DES с шестнадцатью
циклами криптографического преобразования.
В конце января 1997 г. компания RSA Data Security, Inc. анонсировала
новый криптографический конкурс (табл. 8.1). Цель конкурса — оценка
криптостойкости федерального стандарта США DES [8] и симметричных
криптосистем с переменной длиной ключа на основе криптоалгоритма RC5.
Хорошо известно, что 56-битный ключ стандарта DES не гарантирует
адекватной криптостойкости в случае силовой атаки (исчерпывающий перебор
ключа). В 1993 г. Винер (М. J. Wiener) из Bell-Northen Research разработал
для силовой атаки на DES специализированный параллельный компьютер,
позволяющий раскрывать ключ в течение нескольких часов [9]. Попытки
устранения основного недостатка DES, связанного с коротким ключом,
привели к появлению различных DES-модификаций — метода тройного DESшифрования [9], метода DESX, предложенного Ривестом (R. Rivest), а также
ряда альтернативных криптосистем, таких, как IDEA и RC5. Известно
также, что кроме криптостойкости существуют и другие факторы,
оказывающие влияние на выбор длины ключа симметричной криптосистемы.
Таблица 8.1. Условия и результаты конкурса компании RSA Data Security,
Inc.
Приз
Начало
Криптосистема
Время
(тыс.
(9 a.m.
Длительность
DES, RC5
завершения
долл.)
PST)
17.06.97,
DES
10
28.01.97
10:40 p.m.
140 дней
PST
28.01.97,
RC5-32/12/5
1
28.01.97
12:30 p.m.
3.5 часа
PST
10.02.97,
RC5-32/12/6
5
28.01.97
313 часов
10:00 a.m.
90
RC5-32/12/7
10
28.01.97
RC5-32/12/8
RC5-32/12/9
RC5-32/12/10
RC5-32/12/11
RC5-32/12/12
RC5-32/12/13
RC5-32/12/14
RC5-32/12/15
RC5-32/12/16
10
10
10
10
10
10
10
10
10
28.01.97
28.01.97
28.01.97
28.01.97
28.01.97
28.01.97
28.01.97
28.01.97
28.01.97
PST
20.10.97,
11:18 a.m.
PST
-
210 дней
-
Так, например, в соответствии с законодательством длина ключа
для экспортируемых за пределы США и Канады криптографических
приложений на основе симметричного криптоалгоритма ограничена 40
битами. Необходимость теоретических обоснований в данном случае
отпадает, несостоятельность криптографии с 40-битным ключом
убедительно продемонстрирована первыми результатами криптосистема
RC5-32/12/5 была «взломана» через 3,5 часа после объявления в Internet
условий криптографического конкурса (см. табл. 8.1). Параметры
криптосистемы RC5 в табл. 11.20 обозначаются как RC5-X/Y/Z, где X разрядность блока в битах, Y - число циклов криптографического
преобразования, Z — длина ключа в байтах (Z*8—разрядность в битах).
Силовая атака сводится, по сути, к дешифрованию фиксированного
шифротекста на различных ключах при заданном векторе
инициализации. Так, для атаки на RC5-32/12/5 был задан шифротекст (в
шестнадцатеричном представлении):
12
6c
9b
43
35
b4
d4
75
13
bf
7f
9a
64 78
5b 00
la 8d
58 06
d3
38
48
2c
da
ff
fe
8b
08
44
b6
a5
d9
4e
63
9e
15
d9
dl
6a
ed
d4
d4
33
20
9b
c2
30
89
46
eb
c3
30
16
19
3e
5f 50
fb 12
Od 86
a8 ab
68
92
3f
24
5c
62
f4
25
и вектор инициализации 8а 16 2f 69 e8 37 98.
Секретный ключ считается раскрытым, если результат
дешифрования на текущем ключе приводит к содержательному тексту на
английском языке. Условия конкурса, а также все необходимые
исходные данные могут быть получены с Web-сервера компании RSA
Data Security, Inc. но адресу http://www.rsa.com.
91
Все результаты табл. 8.1 в отличие от идеи Винера получены при
помощи программной реализации криптоалгоритма и массированной
параллельной атаки с привлечением десятков, а иногда и тысяч рабочих
станций. Сеть Internet, пример практического приложения идеи
распределенных вычислений, стала мощным инструментом силовой
атаки в руках криптоаналитиков и хакеров. Силовая атака на основе
распределенных вычислений имеет свою динамику, связанную с
активностью сетевых пользователей. Проанализируем возможности
распределенной силовой атаки на примере криптосистем RC5-32/12/5 и
RC5-32/12/6 [9].
Для решения ряда задач практической криптографии необходимы
значительные вычислительные ресурсы. При этом некоторые из этих
задач поддаются распараллеливанию. Таким образом, Internet,
объединяющий многие тысячи рабочих станций, позволяет эффективно
решать трудоемкие задачи путем координированной и одновременной
работы большого числа компьютеров. Такой подход, реализующий
возможности компьютерных сетей, известен под названием метода
распределенных вычислений. Одна из первых успешных попыток
использования Internet для факторизации RSA-модуля из 129
десятичных разрядов была предпринята в 1994 г. [10]. Объединенные
усилия 600 человек и 1600 компьютеров, включая две факс-машины,
координировались при помощи электронной почты. Успешная
факторизация
RSA-модуля
из
130
десятичных
разрядов
продемонстрировала
исключительную
эффективность
решения,
основанного на объединении метода распределенных вычислений,
алгоритма обобщенного числового решета и координации работы
компьютеров в рамках Web-технологии.
Проблема поиска ключа симметричной криптосистемы путем
исчерпывающего перебора относится к классу задач, допускающих
распараллеливание. В настоящее время Internet обладает достаточными
ресурсами для успешной силовой атаки на DES (или любую другую
криптосистему, сравнимую с DES по длине ключа) в течение нескольких
недель. Таким образом, анализ потенциальных возможностей метода
распределенных вычислений при решении криптографических задач
интересен как для криптоаналитиков, так и для разработчиков
криптографических приложений.
В 1992 г. Каронни (G. Caronni) и Алемсбергер (W. Alemsberger)
разработали программное обеспечение для координации одновременной
работы сетевых компьютеров при поиске «плохих» паролей локальных
UNIX-серверов. Программа позволила решить поставленную задачу
объединенными усилиями 350 рабочих станций. Объявленный в январе
1997 г. криптографический конкурс открыл новую область приложения
для программного обеспечения Каронни-Алемсбергера. В течение января
программа была переработана под новую задачу. Программная
92
реализация криптоалгоритма RC5, оптимизированная для компьютера
Ultra 1/170. позволяла проверять миллион ключей криптосистемы RC532/12/5 за 6,15 с. За неделю до начала атаки организаторы разослали в
ряд университетов США и Европы предложения об участии в проекте с
просьбой привлечения всех заинтересованных лиц. За три дня до начала
атаки стало ясно, что объединенное общей целью сетевое сообщество
обладает достаточным потенциалом для решения поставленной задачи.
Запуск проекта состоялся в 18:07 по западноевропейскому времени (9:07
PST). Ошибки в работе программного обеспечения сервера,
обнаруженные Шнайдером (С. Schneider) в 20:30. привели к перезапуску
40 серверов, участвовавших в проекте. Несмотря на сбои, задача была
решена объединенными усилиями 800 компьютеров в Швейцарии.
Германии, Норвегии и США. Секретный ключ криптосистемы RC532/12/5 найден за 231 мин после проверки 51% всех ключей со средней
производительностью 40 млн. ключей в секунду. Известно, что
аналогичная атака, предпринятая ранее Голдбергом (I. Goldberg) из
Университета Беркли, успешно завершилась после перебора 31% ключей
за 210 мин. Отметим, что с методологической точки зрения различия в
организации атаки Каронни и Голдберга мало существенны. В проекте
Голдберга было задействовано 259 компьютеров (287 процессоров):
97 UltraSPARC;
4 UltraSPARC (8 процессоров);
120 рабочих станций HP:
8 процессоров Pentium;
30 SPARCStation 20s.
Все ресурсы были полностью доступны к моменту запуска и
оставались неизменными в период осуществления проекта. Средняя
скорость проверки составляла 27 млн. ключей в секунду. Управление
перебором ключей осуществлялось при помощи центрального сервера.
Перед получением очередной порции ключей для проверки клиент
прогонял специальный тест, оценивающий текущую производительность
его компьютера, и сообщал результаты серверу. Сервер, в свою очередь,
передавал клиенту сегмент ключевого пространства, обеспечивающий
20-минутную загрузку с учетом текущей производительности
компьютера клиента. После завершения проверки сегмента клиент
извещал сервер о результатах, и цикл повторялся. При этом все
проверенные, а также непроверенные и находящиеся в работе ключи
учитывались сервером при организации дальнейшей проверки.
Клиент
Сервер
Регистрация/3апрос_задания
Задание/Сброс_задания/Остановка
Задание_выполнено/3апрос_задания
93
Задание/Сброс_задания/3апрос_регистрации/Остановка
Рис. 8.1. Протокол взаимодействия по технологии «клиент-сервер»
Молниеносная «расправа» с криптосистемой RC5-32/12/5 стала
безусловным стимулом для силовой атаки криптосистемы RC5-32/12/6 с
48-битным ключом (далее в тексте - проект RC5-32/12/6). Проект был
запущен 29 января в 18:00 по западноевропейскому времени после
переработки
программного
обеспечения
и
предварительного
шестичасового тестирования. Существует два подхода к организации
силовой атаки на основе метода распределенных вычислений. Первый —
централизованное управление процессом поиска при помощи сервера.
Второй — случайный и независимый выбор стартовой точки в ключевом
пространстве каждым из участвующих в проекте компьютером и
оповещение в случае раскрытия ключа. Первый подход более
предпочтителен, но связан с определенными трудностями. Так, не исключена возможность перегрузки сервера потоком запросов со стороны
клиентов. К тому же некоторые непреднамеренные действия клиентов
могут привести к сбоям в работе центрального сервера. Не исключен
также риск злонамеренного деструктивного воздействия. Для сведения к
минимуму указанных рисков необходимы дополнительные меры.
Известный метод обеспечения отказоустойчивости предполагает
введение дополнительной избыточности. Репликация серверов, а также
принцип иерархии в проектировании структуры связей позволяют
устранить некоторые риски и ограничить последствия сбоев и отказов.
Применение кода аутентификации гарантирует подлинность всех
сообщений при передаче как от клиента к серверу, так и в обратном
направлении. Ведение регистрационного журнала упрощает анализ и
отслеживание последствий отказов.
Организаторы проекта намеренно предложили упрощенную схему
взаимодействия по технологии «клиент-сервер» [10]. Для регистрации
клиента и получения очередного задания от сервера использовался
простейший протокол. Типичный протокол обмена между клиентом и
сервером представлен на рис. 8.1.
Запрос Регистрация включает номер версии, тип компьютера и
другую необходимую для начала работы информацию. Запрос_ задания
содержит сведения об объеме сегмента ключевого пространства и оценку
времени перебора сегмента указанного объема. Клиент может отказаться
от участия или приостановить выполнение задания. Факт отказа со
стороны клиента устанавливается по нулевому объему сегмента в
Запросе_задания. Сервер подтверждает отказ клиента сообщением
Сброс_ задания. В случае раскрытия ключа или возобновления работы
клиент уведомляет сервер с помощью специально предусмотренных
сообщений. Если сервер по каким-либо причинам завершает свою
94
работу и вместо него включается новый, то в ответ на сообщение
клиента Задание_ выполнено новый сервер отвечает сообщением
Запрос_ регистрации, чем инициирует регистрацию клиента на новом
сервере. Для немедленной остановки работы клиентов предусмотрено
сообщение Остановка. Сервер управляет сегментированием ключевого
пространства, периодически записывая текущее состояние на жесткий
диск, в целях оперативного восстановления программного обеспечения
в случае сбоя или перезагрузки операционной системы. Сервер
динамически отслеживает время работы всех зарегистрированных у него
клиентов. Если время перебора ключевого сегмента, указанное клиентом
в Запросе_задания, истекает, сервер передает сегмент другому клиенту
виртуальной сети. По завершении процедуры проверки текущего
ключевого сегмента клиенту, по соответствующему запросу, передается
новый сегмент.
Криптоалгоритм RC5 для программного обеспечения клиента
был реализован на языке ассемблера для процессоров Intel и RS6000.
Оптимизация на уровне компилятора языка С выполнялась для
следующих операционных систем: AIX. FreeBSD, HPUX, IRIX. Linux,
NEXTSTEP, NetBSD, OS2, OSF1, OpenBSD, SCO_SV, SunOS, ULTRIX,
Windows (NT& 95), AMIGA MacOS MIPS, Alpha, (Ultra) SPARC, 486/586
Intel, Pentium Pro, Paragons. ОС для компьютеров с параллельной
архитектурой (до 16 000 процессоров).
Лавинообразное вовлечение участников в силовую атаку на
криптосистему RC5-32/12/6 позволило задействовать значительные
сетевые ресурсы. Отметим, что пиковая производительность тестирования
ключей достигала 440 млн. ключей в секунду, а максимальное количество
одновременно работающих компьютеров - 4500 единиц.
Рис. 8.2 иллюстрирует закономерность роста производительности при
проверке ключей После медленного роста в течение первой недели
производительность удвоилась за два дня — с 4 по 6 февраля. Следующее
удвоение производительности произошло также через два дня - с 7 по 9
февраля.
Рост производительности в ходе силовой атаки на криптосистему
RC5-32/12/6 сравним с производительностью атаки Голдберга на
криптосистему RC5-32/12/5 (27 млн. ключей в секунду), в которой было
задействовано фиксированное число компьютеров.
95
Рис. 8.2. Рост производительности при проверке ключей
На рис. 8.3 представлена закономерность роста количества
проверенных ключей в процентах от объема ключевого пространства.
Более подробную информацию о развитии проекта можно получить
из различных сетевых источников. Например,
http://www.ee.ethz.ch/challenge/
http://www.42.org/challenge/
http://www.klammeraffe.org/challenge/.
Рассматриваемая организация силовой атаки на основе метода
распределенных вычислений порождает следующий вопрос. В состоянии
ли один-единственный центральный сервер справиться с возрастающим
потоком запросов, и в какой степени такой рост влияет на эффективность
распределенных вычислений? Исходя из данных о пиковой нагрузке
последних дней проекта можно предположить, что центральный сервер
обслуживал 5000 клиентов каждые 30 мин. Это, в свою очередь, означает,
что каждую секунду к серверу обращалось не более двух клиентов.
Производительность современных серверов позволяет легко справляться с
подобной нагрузкой при интенсивности трафика порядка 300 байт в
секунду. Так, сервер проекта RC5-32/12/6, сконфигурированный на Sun
Ultra 1/170, был загружен менее чем на 2%, при этом потребность в
оперативной памяти составила менее 6 Мбайт. Таким образом,
экспериментальные данные, полученные в ходе проекта, подтверждают,
что один сервер без перегрузки может обслужить миллион клиентов.
Отметим, что эффективность описанного подхода может быть
96
невысокой из-за дополнительных задержек, возникающих в связи с
низкой пропускной способностью каналов связи.
Оценим вычислительную производительность проекта. Поскольку
для проверки одного ключа по криптоалгоритму RC5 требуется порядка
2000 инструкций, то для нахождения ключа методом силовой атаки
понадобится 3.24 x 1017 инструкций. Так как принятая единица
измерения вычислительной производительности в один миллион
инструкций в секунду (MIPS/Year, MY) оценивается как 3.15 x 1013
инструкций, суммарная производительность проекта составила 104 MY в
течение 10 календарных дней. Это свидетельствует о росте
вычислительной
производительности
Internet.
Для
сравнения:
вычислительная производительность при факторизации 129-разрядного
RSA-модуля в 1994 г. составила 5 х 103 MY за девять календарных
месяцев.
По результатам проекта RC5-32/12/5 и RC5-32/12/6 в статье [11)
представлен прогноз будущего силовой атаки на основе распределенных
вычислений. В первую очередь отметим, что производительность
проверки ключей, достигнутая в последние дни проекта RC5-32/12/6 (330
млн. ключей в с.), недостаточна для эффективной силовой атаки на
криптосистему RC5-32/12/7. Учитывая производительность проекта
RC5-32/12/6, для силовой атаки криптосистемы RC5-32/12/7 по оценкам
[11] потребуется около 255/330 х 220 секунду - приблизительно три с
половиной года непрерывной работы. Однако экспериментальные данные
(рис. 8.3) свидетельствуют об удваивании производительности каждые
три дня. Таким образом, ожидаемая производительность при сохранении
тенденции может возрасти на порядок по сравнению с пиковой
производительностью проекта RC5-32/12/6. В этом случае для
осуществления атаки понадобится не более полугода.
При одинаковой длине ключа криптоалгоритм DES позволяет
проверять ключи в 2 - 4 раза быстрее (в зависимости от реализации), чем
RC5-32/12/7. Производительность некоторых программных реализаций
составляет 500 тысяч ключей в секунду на процессоре Pentium 120. С
учетом изложенных выше тенденций для поиска ключа DES методом
исчерпывающего перебора понадобится не более нескольких месяцев.
Отметим, что прогноз, представленный в статье [12], подтвердился
недавно опубликованными результатами (см. табл. 8.2).
97
Рис. 8.3. Рост числа проверенных ключей
Результаты распределенной силовой атаки на криптосистемы
RC5-32/12/5 и RC5-32/12/6 продемонстрировали слабость 40- и 48битных ключей. Известно, что в ходе обсуждения экспортного
законодательства США было предложено ограничить длину ключа в
экспортируемых криптографических приложениях 56 битами (см.
http://www.bxa.doc.gov/encstart.htm).
Однако,
учитывая
рост
производительности компьютеров (удваивается каждые 18 месяцев по
закону Мура) и динамику развития Internet. можно предположить, что
56-битный ключ также не гарантирует адекватной криптоетой-кости. По
оценкам ведущих криптографов и специалистов по компьютерным
технолот-ям, минимальная длина ключа симметричной криптосистемы,
гарантирующая криптостойкость по отношению к силовой атаке, должна
колебаться
от
75
до
90
бит
(см.
отчет
http://www.bsa.org/policy/encryption).
Многие
специалисты
с
консервативными вз!лядами придерживаются мнения, что длина ключа
должна быть не менее 128 бит.
98
7 НАДЕЖНОСТЬ КРИПТОСИСТЕМ
В компьютерном и околокомпьютерном мире все время появляется информация об ошибках или «дырах» в той или иной программе (в том числе
применяющей криптоалгоритмы), или о том, что такие программы были
взломаны. Это создает недоверие как к конкретным программам, так и к
возможности вообще защитить что-либо криптографическими методами не
только от спецслужб, но и от простых хакеров.
Эффективность любой криптосистемы зависит от ее стойкости к анализу
зашифрованной информации. А уровень криптостойкости системы зависит как
от ее разработчика, так и от возможностей криптоаналитиков, пытающихся ее
вскрыть. Поэтому знание истории атак и «дыр» в криптосистемах, а также
понимание причин, по которым они имели место, является одним из
необходимых условий разработки защищенных систем. Перспективным
направлением исследований в этой области является анализ успешно
проведенных атак или выявленных уязвимых мест в криптосистемах с целью их
обобщения, классификации и выявления причин и закономерностей их
появления и существования.
Рис. 3.13. Причины ненадежности криптосистем
На сегодняшний день существуют хорошо известные и апробированные
криптоалгоритмы (как с симметричными, так и несимметричными ключами),
криптостойкость которых либо доказана математически, либо основана на
необходимости решения математически сложной задачи (факторизации,
дискретного логарифмирования и т. п.). К наиболее известным из них относятся
DES, RSA, ГОСТ. Таким образом, они не могут быть вскрыты иначе, чем
99
полным перебором или решением указанной задачи. Но тем не менее, можно
выделить следующие основные
группы причин ненадежности криптографических систем [10]:
 Применение нестойких алгоритмов
 Ошибки в реализации криптоалгоритмов
 Неправильное применение криптоалгоритмовЧеловеческий фактор
При этом видна четкая параллель между ними и причинами нарушения
безопасности вычислительных систем. Более подробно причины ненадежности
криптосистем представлена на рис. 3.13. Из-за них имелись или имеются
проблемы безопасности у всех классов программных продуктов, использующих
криптоалгоритмы, будь то операционные системы; криптопротоколы; клиенты
и сервера, их поддерживающие; офисные программы; пользовательские
утилиты шифрования; популярные архиваторы.
Научный подход к анализу криптостойкости шифров приобрел стройность после публикации в 1949 году работы К. Шеннона «Теория связи в
секретных системах». Он предложил рассматривать криптостойкость систем с
двух точек зрения — теоретической (совершенной) и практической
(вычислительной) стойкости.
С точки зрения теоретической стойкости рассматривается насколько надежна некоторая криптосистема, если криптоаналитик, ее вскрывающий, не
ограничен временем и обладает всеми необходимыми средствами.
Теоретическая криптостойкость использует два допущения: криптоаналитику
известна только шифрованная информация и ключ используется только один
раз. Решение этого вопроса приводит к следующему выводу: объем секретного
ключа для построения теоритической стойкости шифра недопустимо велик для
большинства практических применений.
С точки зрения вычислительной стойкости рассматривается надежна ли
некоторая криптосистема, если криптоаналитик располагает ограниченным
временем и вычислительными возможностями для анализа шифрованной
информации.
Криптоанализ может быть основан на использовании как общих
математических методов, так и частных, полученных для конкретной
криптографической защиты. Поэтому для примера рассмотрим, как проводится
криптоанализ простейших шифров подстановок и перестановок. При этом
широко используется статистическое распределение символов в алфавите.
Например, в шифре моноалфавитной замены количество возможных
перестановок, для английского языка, равно 26!=4 1026. Но даже при таком
огромном количестве перестановок этот шифр не является стойким. Это
обусловлено следующими причинами:
 В шифротексте сохраняются статистические зависимости символов и
сочетаний символов исходного текста;Перемешанный относительный алфавит
может быть установлен постепенным подбором.
100
Рис. 3.14 - Частота использования букв:
а — английского и немецкого алфавитов;
б — русского алфавита
Для любого естественного языка частота встречаемости букв в тексте различна, вспомните, например, телеигру «Поле чудес». Частота встречаемости
101
букв в процентах от общего количества символов в сообщении для русского,
английского и немецкого алфавитов наглядно представлена на рис. 3.14.
Кроме того на основании анализа частоты встречаемости различных букв
шифротекста можно установить, на каком языке написано исходное сообщение.
Как видно из рис. 3.14, одни и те же буквы используются с различной частотой.
Например, буква Q очень редко встречается в английском и немецком языках, и
заметно чаще в итальянском и французском. Буква О активно используется в
русском, английском, итальянском, испанском и португальском языках, но
реже во французском и немецком. Все это позволяет достаточно быстро
расшифровывать простые шифры. Но вернемся к рис. 3.13.
Малая скорость стойких криптоалгоритмов — это основной фактор, затрудняющий применение хороших алгоритмов, например, в системах «тотального» шифрования или шифрования «на лету». В частности, программа
Norton DiskReet, хотя и имеет реализацию криптоалгоритма DES, при смене
пользователем ключа может не перешифровывать весь диск, так как это займет
слишком много времени. Аналогично, программа компрессии «на лету» Stacker
фирмы Stac Electronics имеет опцию закрытия паролем компрессируемых
данных. Однако она не имеет физической возможности зашифровать этим
паролем свой файл, обычно имеющий размеры в несколько сот мегабайт,
поэтому она ограничивается очень слабым алгоритмом и хранит хэш-функцию
от пароля вместе с защищаемыми данными. Величина криптостойкости этой
функции была исследована и оказалась равной 28, то есть пароль может быть
вскрыт быстро и просто.
Экспортные ограничения криптоалгоритмов приводят к тому, что при
межгосударственном общении возможно использование только весьма условно
защищенных алгоритмов, со временем перебора паролей в среднем около 4
месяцев.
Использование собственных криптоалгоритмов идет от незнания или нежелания использовать уже известные алгоритмы — такая ситуация, как ни
парадоксально, также имеет место быть, особенно в программах типа Freeware
и Shareware, например, архиваторах. Например, архиватор ARJ (до версии 2.60
включительно) использует (по умолчанию) очень слабый алгоритм
шифрования — простое гаммирование, что позволяет достичь скорости
перебора в 350000 паролей/сек, на машине класса Pentium. Аналогичная
ситуация имеет место и в случае с популярными программами из Microsoft
Office — для определения пароля там необходимо знать всего 16 байт файла
.doc или .xls, после чего достаточно перебрать всего 16 вариантов. В Microsoft
Office 97 сделаны значительные улучшения алгоритмов шифрования, в результате чего осталась возможность только полного перебора, но не везде. MS
Access 97 использует примитивнейший алгоритм, причем шифруются не
данные, а сам пароль операцией XOR с фиксированной константой. И таких
примеров можно привести еще великое множество.
В случае неправильной реализации криптоалгоритмов, несмотря на то,
что в этом случае применяются криптостойкие или сертифицированные
102
алгоритмы, эта группа причин приводит к нарушениям безопасности
криптосистем.
Такая причина, как уменьшение криптостойкости системы при генерации
ключа основана на том, что криптосистема либо обрезает пароль пользователя,
либо генерирует из него данные, имеющие меньшее количество бит, чем сам
пароль [11]. В старых версиях UNIX пароль пользователя обрезается до 8 байт
перед хэшированием. Любопытно, что, например, Linux 2.0, требуя от
пользователей ввода паролей, содержащих обязательно буквы и цифры, не
проверяет, чтобы 8-символьное начало пароля также состояло из букв и цифр.
Поэтому пользователь, задав, например, достаточно надежный пароль
passwordlsgoodl 9, будет весьма удивлен, узнав, что хакер вошел в систему под
его именем с помощью элементарного пароля password. Novell Netware
позволяет пользователям иметь пароли до 128 байт, что дает (считая латинские
буквы без учета регистра, цифры и спецсимволы) 68Ш или 2™ комбинаций. Но
при этом, во-первых, хэш-функция получает на входе всего лишь 32-байтовое
значение, что ограничивает эффективную длину пароля этой же величиной.
Более того, во-вторых, на выходе хэш-значение имеет длину всего 128 бит, что
соответствует 2128 комбинаций. Это дополнительно снижает эффективную
длину до 21 символа, то есть в 6 раз по сравнению с первоначальной.
Полностью аналогичная ситуация происходит с архиватором RAR версий 1.5х
— выбор пароля больше 10 символов не приводит к росту времени,
необходимого на его вскрытие.
Некоторые криптоалгоритмы (в частности, DES, IDEA) при шифровании
со специфическими ключами не могут обеспечить должный уровень
криптостойкости. Такие ключи называют слабыми (weak). Для DES известно 4
слабых и 12 полуслабых (semi-weak) ключей. И хотя вероятность попасть в них
очень мала, для серьезных криптографических систем пренебрегать ей нельзя.
Мощность множества слабых ключей IDEA составляет немного-немало — 251
(впрочем, из-за того, что всего ключей 2т, вероятность попасть в него в 3>107раз
меньше, чем у DES).
Недостаточная защищенность от компьютерных вирусов, «троянских
коней», программных закладок и прочих программ, способных перехватить
секретный ключ или сами нешифрованные данные, а также просто подменить
алгоритм на некриптостойкий, приводит к нарушению безопасности
криптосистемы. Особенно это актуально для операционных систем, не
имеющих встроенных средств защиты или средств разграничения доступа —
типа MS DOS или Windows 95. Как пример можно привести самый старый
способ похищения пароля, известный еще со времен больших ЭВМ, когда
программа-«фантом» эмулирует приглашение ОС, предлагая ввести имя
пользователя и пароль, запоминает его в некотором файле и прекращает работу
с сообщением «Invalid password». Для MS DOS и Windows существует
множество закладок для чтения и сохранения паролей, набираемых на
клавиатуре. Примером реализации подмены криптоалгоритма является
закладка, маскируемая под прикладную программу-«ускоритель» типа Turbo
103
Krypton. Эта закладка заменяет алгоритм шифрования ГОСТ 28147-89,
реализуемой платой «Krypton-З» (демонстрационный вариант), другим,
простым и легко дешифруемым алгоритмом. Последним примером служит
имевшие место в июне 1998 года попытки проникновения «троянского коня»
через электронную почту. В письмо были вложены порнографическая картинка
и ЕХЕ-файл FREECD.EXE, который за то время, пока пользователь развлекался
с письмом, расшифровывал пароли на соединение с провайдером (Dial-Up) и
отправлял их на адрес ispp@usa.net.
Сравнительно новый аспект недостаточно корректной реализации криптоалгоритмов заключается в наличии зависимости во времени обработки ключей. Многие криптосистемы неодинаково быстро обрабатывают разные входные данные. Это происходит как из-за аппаратных (разное количество тактов на
операцию, попадание в процессорный кэш и т.п.), так и программных причин
(особенно при оптимизации программы по времени). Время может зависеть как
от ключа шифрования, так и шифруемых или расшифруемых данных. Поэтому
злоумышленник,
обладая
детальной
информацией
о
реализации
криптоалгоритма, имея зашифрованные данные и будучи способным каким-то
образом измерять время обработки этих данных (например, анализируя время
отправки пакетов с данными), может попытаться подобрать секретный ключ.
Ясно, что пока программы будут писаться людьми, ошибки в программной реализации всегда будут иметь место. Хороший пример — ОС Novell
Netware 3.12, где, несмотря на достаточно продуманную систему аутентификации, при которой, по заявлениям фирмы Novell, «нешифрованный пароль
никогда не передается по сети», удалось найти ошибку в программе SYSCON v.
3.76, при которой пароль именно в открытом виде попадает в один из сетевых
пакетов. Этого не наблюдается ни с более ранними, ни с более поздними
версиями этой программы, что позволяет говорить именно о чисто
программистской ошибке. Этот ошибка проявляется только если супервизор
меняет пароль кому-либо (в том числе и себе). Видимо, каким-то образом в
сетевой пакет попадает клавиатурный буфер.
Причины наличия люков в криптосистемах очевидны: разработчик хочет
иметь контроль над обрабатываемой в его системе информацией и оставляет
для себя возможность расшифровывать ее, не зная ключа пользователя.
Возможно также, что они используются для отладки и по какой-то причине не
убираются из конечного продукта. Естественно, что это рано или поздно
становится известным достаточно большому кругу лиц и ценность такой
криптосистемы становится почти нулевой. Самыми известными примерами
здесь являются AWARD BIOS (до версии 4.51PG) с его универсальным паролем «A WARD_SW» и СУБД Paradox фирмы Borland International, также имеющая «суперпароли» «jIGGAe» и «пхббррх». Вплотную к наличию люков в
реализации (очевидно, что в этом случае они используют явно нестойкие
алгоритмы или хранят ключ вместе с данными) примыкают алгоритмы, дающие
возможность третьему лицу читать зашифрованное сообщение, как это сделано
104
в нашумевшем проекте CLIPPER, где третьим лицом выступает государство,
всегда любящее совать нос в тайны своих граждан.
Хороший, математически проверенный и корректно реализованный
датчик случайных чисел (ДСЧ) также важен для криптосистемы, как и
хороший, математически стойкий и корректный криптоалгоритм, иначе его
недостатки могут повлиять на общую криптостойкость системы. При этом для
моделирования ДСЧ на ЭВМ обычно применяют датчики псевдослучайных
чисел (ПСЧ), характеризующиеся периодом, разбросом, а также
необходимостью его инициализации (seed). Применение ПСЧ для криптосистем
вообще нельзя признать удачным решением, поэтому хорошие криптосистемы
применяют для этих целей физический ДСЧ (специальную плату), или, по
крайней мере, вырабатывают число для инициализации ПСЧ с помощью
физических величин (например, времени нажатия на клавиши пользователем).
Малый период и плохой разброс относятся к математическим недостаткам ДСЧ
и появляются в том случае, если по каким-то причинам выбирается
собственный ДСЧ. Иначе говоря, выбор собственного ДСЧ так же опасен, как и
выбор собственного криптоалгоритма. В случае малого периода (когда
псевдослучайных значений, вырабатываемых датчиком, меньше, чем
возможных значений ключа) злоумышленник может сократить время поиска
ключа, перебирая не сами ключи, а псевдослучайные значения и генерируя из
них ключи.
Такая группа причин, как неправильное применение криптоалгоритмов,
приводит к тому, что оказывается ненадежными криптостойкие и корректно
реализованные алгоритмы. Самая очевидная причина — это малая длина
ключа. Стойкие криптоалгоритмы могут иметь малую длину ключа вследствие
двух факторов:
 Некоторые алгоритмы могут работать с переменной длиной ключа,
обеспечивая разную криптостойкость,— и именно задача разработчика выбрать
необходимую длину, исходя из желаемой криптостойкости и эффективности.
Иногда на это желание накладываются и иные обстоятельства — такие, как
экспортные ограничения
 Некоторые алгоритмы разрабатывались весьма давно, когда длина
используемого в них ключа считалась более чем достаточной для соблюдения
нужного уровня защиты.
Ошибочный выбор класса алгоритма — это также весьма распространенная причина, при которой разработчик выбирает пусть и хороший, но совершенно неподходящий к его задаче алгоритм. Чаще всего это выбор шифрования
вместо хэширования или выбор симметричного алгоритма вместо алгоритма с
открытыми ключами. Примеров здесь масса — это почти все программы,
ограничивающие доступ к компьютеру паролем при его включении или
загрузке, например AMI BIOS, хранящий вместо хэша пароля его
зашифрованный вариант, который, естественно, легко дешифруется. Во всех
сетевых процедурах аутентификации естественно применять ассиметричную
криптографию, которая не позволит подобрать ключ даже при полном пере105
хвате трафика. Однако многие программы довольствуются (в лучшем случае!)
стандартной схемой «запрос-отклик», при которой можно вести достаточно
быстрый перебор по перехваченным значениям «запроса» и «отклика».
Уже классическим примером стала уязвимость в Windows 3.x и первых
версиях Windows 95, связанная с шифрованием. В этом случае программисты
фирмы Microsoft, хорошо известные своими знаниями в области безопасности,
применяли алгоритм RC4 (представляющем собой ни что иное, как шифрование гаммированием), не меняя гаммы, несколько раз к разным данным —
сетевым ресурсам, хранящимся в файлах типа .pwl. Оказалось, что один из
наборов данных файла.pwl представлял из себя более чем специфичный текст
—20-символьное имя пользователя (в верхнем регистре) и набор указателей на
ресурсы. Таким образом, угадав им пользователя (которое в большинстве
случаев к тому же совпадает с именем файла) можно вычислить по крайней
мере 20 байт гаммы. Так как гамма не меняется при шифровании других ресурсов (в этом состоит основная ошибка применения R.C4 в этом случае),
могут быть вычислены первые 20 байт всех ресурсов, в которые входит длина
каждого из них. Вычислив длину, можно найти значения указателей и тем самым прибавить еще несколько десятков байт к угаданной гамме.
Хранение ключа вместе с данными приводит к тому, что данные,
зашифрованные с помощью криптостойкого и корректно реализованного
алгоритма, могут быть легко дешифрованы. Это связано со спецификой
решаемой задачи, при которой невозможно вводить ключ извне и он хранится
где-то внутри в практически незашифрованном виде. Иначе говоря, здесь
наиболее уязвимым будет алгоритм шифрования не ключом, а ключа (с
помощью некоего вторичного ключа). Но так как (что опять-таки очевидно
следует из специфики задачи) этот вторичный ключ хранить извне нельзя, то
основные данные рано или поздно будут расшифрованы без использования
методов перебора. Типичным примером здесь будут все WWW-, ftp-, e-mailклиенты. Дело в том, что для базовой (наиболее часто встречающейся)
аутентификации в этих протоколах пароль должен передаваться серверу в
открытом виде. Поэтому клиентские программы вынуждены шифровать (а не
хэшировать) пароль, причем с фиксированным ключом, чтобы не надоедать
пользователю постоянными вопросами. Отсюда следует, что где-то внутри
любого броузера, почтового или ftp-клиента (будь то Netscape Communicator,
Eudora, Outlook, FAR и т. п.) лежат все ваши пароли в практически открытом
виде, и что расшифровать их не представляет труда. (Чаще всего, кстати,
пароль в таких программах даже не шифруется, а кодируется алгоритмом типа
base-64.)
В любой критической системе ошибки человека-оператора являются чуть
ли не самыми дорогостоящими и распространенными. В случае криптосистем
непрофессиональные действия пользователя сводят на нет самый стойкий
криптоалгоритм и самую корректную его реализацию и применение.
В первую очередь это связано с выбором паролей. Очевидно, что
короткие или осмысленные пароли легко запоминаются человеком, но они
106
гораздо проще для вскрытия. Использование длинных и бессмысленных
паролей безусловно лучше с точки зрения криптостойкости, но человек обычно
не может их запомнить и записывает на бумажке, которая потом либо теряется,
либо попадает в руки злоумышленнику. Именно из того, что неискушенные
пользователи обычно выбирают либо короткие, либо осмысленный.
 Атака полным перебором
 Атака по словарю.
В связи с резким ростом вычислительных мощностей атаки полным перебором имеют гораздо больше шансов на успех, чем раньше. Если для
системы UNIX функция crypt(), которая отвечает за хэширование паролей, была
реализована так, что выполнялась почти 1 секунду на машину класса PDP, то за
двадцать лет скорость ее вычисления увеличилась в 15 000 раз. Поэтому если
раньше хакеры (и разработчики, которые ограничили длину пароля 8
символами) и представить себе не могли полный перебор, то сегодня такая
атака в среднем приведет к успеху за 80 дней. Скорость перебора паролей для
различных криптосистем приведена в табл. 3.3.
Однако вернемся на несколько лет назад, когда вычислительной мощности для полного перебора всех паролей не хватало. Тем не менее, хакерами
был придуман остроумный метод, основанный на том, что в качестве пароля
человеком выбирается существующее слово или какая-либо информация о себе
или своих знакомых (имя, дата рождения и т. п.). Ну, а поскольку в любом
языке не более 100 000 слов, то их перебор займет весьма небольшое время, и
от 40 до 80% существующих паролей может быть угадано с помощью такой
простой схемы, называемой «атакой по словарю». (Кстати, до 80% этих
паролей может быть угадано с использованием словаря размером всего 1000
слов!). Даже вирус Морриса (в 1988 г.) применял такой способ, тем более что в
UNIX «под рукой» часто оказывается файл-словарь, обычно используемый
программами-корректорами. Что же касается «собственных» паролей, то файл
/etc/passwd может дать немало информации о пользователе: его входное имя,
имя и фамилию, домашний каталог. Вирус Морриса с успехом пользовался
следующими предположениями:
 В качестве пароля берется входное имя пользователя;
 Пароль представляет собой двойной повтор имени пользователя;
 То же, но прочитанное справа налево;
 Имя или фамилия пользователя;
 То же, но в нижнем регистре.
Таблица 3.3 - Скорость полного перебора на компьютере класса Pentium/166
107
Криптосистема
ARJ 2.50
RC5 - 56 бит
LM-хэш
Novell Netware 3.x
MS Office 97
UNIX - crypt()
RAR 2.0
UNIX -MD5
Скорость,
паролей / сек
350 000
150 000
50 000
25 000
15 000
15 000
1000
500
Пусть сегодня пользователи уже понимают, что выбирать такие пароли
нельзя, но до тех пор, пока с компьютером работает человек, эксперты по
компьютерной безопасности не дождутся использования таких простых и
радующих душу паролей, как 34jXs5U@bTa!6. Поэтому даже искушенный
пользователь хитрит и выбирает такие пароли, как hopel, user 1997, pAsSwOrD,
toor, roottoor, parol, gfhjkm, asxz. Видно, что все они, как правило, базируются
на осмысленном слове и некотором простом правиле его преобразования:
прибавить цифру, прибавить год, перевести через букву в другой регистр,
записать слово наоборот, прибавить записанное наоборот слово, записать
русское слово латинскими буквами, набрать русское слово на клавиатуре с
латинской раскладкой, составить пароль из рядом расположенных на
клавиатуре клавиш и т. п. Поэтому не надо удивляться, если такой «хитрый»
пароль будет вскрыт хакерами — они не глупее самих пользователей, и уже
вставили в свои программы те правила, по которым может идти преобразование
слов.
Контрольные вопросы
1. Основные условия организации и результаты силовой атаки на основе
распределенных вычислений.
2. Дать определение надежности криптосистем.
3. Перечислить и дать краткую характеристику причины ненадежности
криптосистем.
108
ЗАКЛЮЧЕНИЕ
По причине ограниченности курса информационной безопасности и
защите информации в компьютерных системах за пределами конспекта
остались многие блочные шифры (RC2; RC5; IDEA и др.), криптосистемы
(RSA; Эль-Гамаля и др.); стандарты США и России (SHS; DSS; ГОСТ Р 34.1194 и др.) и ряд других современных способов и методов информационной
безопасности и зашиты информации в криптосистемах. Более подробно
криптография изучается в рамках специальностей ―Криптография‖ и
―Организация и технология защиты информации‖
В современных информационно-вычислительных сетях
широко
применяется алгоритм стандарта DES, например, в виртуальных частных сетях
(VPN). Достаточно часто применяется программа для защиты сообщений,
посылаемых по электронной почте – PGP, основу которой составляет
криптосистема с открытым ключом, второй режим работы которой является
основой для электронной цифровой подписи.
Современные направления развития криптографии связаны, например, с
разработкой криптосистем с временным раскрытием и квантовой
криптографией.
Суть первого заключается в том, чтобы разработать такой шифр, чтобы он
был бы раскрыт не раньше заданной даты (через заданное время). Специфика
такого шифрования заключается в том, что секретный ключ уничтожается сразу
после шифрования и неизвестен ни отправителю, ни получателю сообщения.
Такая задача возникла в последние годы, например, в связи с потребностями
людей, пользующихся услугами криогенных депозитариев (заморозка тела
человека до уровня поддержания минимальных функций жизнедеятельности).
При этом замороженный человек должен иметь гарантии разморозки по
истечения заданного срока. Известны и другие практические приложения
криптографии с временным раскрытием.
Задача квантовой криптографии - создание секретного канала,
принципиальная проблема технологии защиты информации [6]. По сути,
секретный канал - это физическая среда распространения, гарантиирующая с определенной вероятностью невозможность считывания и
изменения информации во время ее передачи. Абсолютно надежный и
высокоскоростной секретный канал позволил бы решить проблему
конфиденциальности без применения криптографии. К сожалению,
традиционные каналы связи не обеспечивают секретности в силу своей
физической
природы.
Однако
невозможно
полностью
исключить
использование секретного канала при передаче, хранении и обработке
конфиденциальной информации. Один из основных подходов к развитию
криптографии заключается в создании адекватных методов защиты при
минимальном количестве и загрузке секретных каналов. Несмотря на
появление алгоритмов двухключевой криптографии, позволивших существенно
109
снять остроту проблемы, зависимость от секретного канала сохраняется на
этапе распределения открытых ключей.
С появлением квантовой криптографии, основанной на фундаментальных
принципах квантовой механики, наметился новый путь решения проблемы
секретного канала. Квантово-механический подход необходимо рассматривать
как одну из первых попыток построения канала со строгим теоретическим
обоснованием его секретности.
Основателем квантовой криптографии по праву считают физика С.
Уиснера (S. Wiesner), автора основополагающей работы под названием
«Сопряженное кодирование» (Conjugate Coding). По всей видимости, в конце
60-х годов идеи Уиснера выглядели слишком «сумасшедшими», и поэтому
статья была опубликована только в 1983 г. [6]. В ней Уиснер объяснял, как
принципы квантовой физики могут применяться для создания денежных знаков
- квантовыхбанкнот, которые невозможно подделать. Другая идея, изложенная
в статье Уиснера и относящаяся к области криптографических протоколов,
спустя десять лет была заново открыта Рабином (М. О. Rabin) и получила
название забывающая передача
(oblivious transfer). Криптографический
протокол передачи нескольких секретов от одного участника другому, когда
владелец секретов не может точно установить, какой из секретов получен
противоположной стороной. Например, сверхдержава желает купить некоторый
политический секрет. При этом раскрытие того факта, что данный
политический секрет ей неизвестен, может быть крайне нежелательно.
Рождение квантовой криптографии состоялось благодаря Беннетту (С. Н.
Bennett), лично знавшему Уиснера, и Брассару (G. Brassard), которые
сформулировали и опубликовали основные положения нового научного
направления в трудах симпозиума, организованного Институтом инженеров по
электротехнике и радиоэлектронике США в октябре 1979 г. Широкое
обсуждение идей Уиснера привело к публикации его статьи в журнале Sigact
News.
Вначале квантово-механический подход к защите информации
воспринимался как нечто, имеющее отношение к научной фантастике; уровень
технологий не допускал практической реализации идеи (например, для
создания квантовой банкноты необходимо хранить поляризованный фотон или
частицу со спином
в течение длительного времени без поглощения или
потери поляризации).
Советский математик А. С. Холево первым осознал, что фотон может
использоваться не для хранения, а для передачи информации (необходимо
отметить, что в работе Уиснера подобная возможность также рассматривалась).
Первая попытка «проращивания» идеи на криптографической почве привела к
появлению некоторой модификации шифра Вернама (или так называемого
одноразового блокнота) многократного использования. Позднее Беннетт
разработал квантовый протокол распределения ключей, а Брассар предложил
квантовый протокол подбрасывания монеты. В некоторых криптографических
приложениях требуется, чтобы участники, не обращаясь за помощью к третьей
110
стороне, путем двустороннего обсуждения породили какую-нибудь случайную
последовательность. Если участников двое, задача решается с помощью
криптографического протокола подбрасывания монеты. В настоящее время
квантовая криптография интенсивно развивается. Разработан квантовый
вариант протокола, известного под названием доказательство с нулевым
знанием, который позволяет одному из участников достоверно убедиться в том,
что другой участник знает некоторый секрет, причем секрет при этом не
раскрывается. Экерт (A. Ekert) предложил альтернативный вариант квантового
протокола распределения ключей на основе эффекта Эйнштейна-ПодольскогоРозена (EPR effect) и теоремы Белла. Упрощенный, однако не менее
криптостойкий вариант протокола Экерта, как показано в работе, эквивалентен
протоколу, предложенному ранее Беннеттом и Брассаром. Протоколы,
рассчитанные на практическую реализацию, описаны в статье. Вариант
протокола распределения ключей, построенный на фундаментальном
соотношении неопределенности для энергии-времени, предложен в статье.
Перечень библиографических ссылок по квантовой криптографии можно найти
в Internet по адресу
http://www.cs.mcgill.ca/~crepeau/CRYPTO/Biblio-QC.html.
С момента первых достижений в области практической реализации идей
квантовой криптографии были получены впечатляющие результаты.
Перечисленные перспективные направления работ в криптографии
далеко не все.
Криптография ждѐт своих молодых и пытливых исследователей, математиков и программистов.
111
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Российская газета, 28 сентября 2000 г.
2. Федеральный закон от 20.02.95 г. № 24-ФЗ ―Об информации,
информатизации и защите информации‖.
3. Закон Российской Федерации «О государственной тайне». 21.07.1993.
4. А.С.Овсянников. Теория информационных процессов и систем: Учеб-ное
пособие. В 2 ч. Ч. 1. Теоретические основы информационных процесссов / Самарск.гос. арх. – строит. ун-т, Самара, 2005. – 100 с.
5. Шрейдер Ю.А. О семантических аспектах теории информации.
Информация и кибернетика. - М.: Сов. радио, 1967.
6. Чмора А.Л. Современная прикладная криптография. 2-е изд., стер. –
М.:Гелиос АРВ, 2002. – 256 с.
7. ГОСТ 28147 - 89. Системы обработки информации. Защита
криптофафическая. Алгоритм криптографического преобразования.
8. Герасименко В. А., Размахнин М. К. Криптографические методы в
автоматизированных системах. — Зарубежная радиоэлектроника, 1982,
№8. — С. 97—124.
9. Диффи У. Первые десять лет шифрования с открытым ключом// ТИИЭР,
т. 76,1988. — №5.—С. 55—74.
10.Диффи У., Хелман Н. Защищенность и иммуностойкость: введение в
криптографию// ТИИЭР, т. 67, 1979. —№3.—С. 71—109.
11.Жельников В. Криптография от папируса до компьютера. — М.: ABF,
1997. — 336 с.
12.Ковалевский В. Э., Максимов В. А. Криптографические методы//
Компьютер Пресс:1993. — №5.—С, 31-34.
13.Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. М.: Мир,
1989. 544 с.
14.Блэк Ю. Сети ЭВМ: Протоколы, стандарты, интерфейсы: Пер. с англ.
М.: Мир, 1990. 506 с.
15.Гоноровский И.С. Радиотехнические цепи и сигналы. Ч.1 и 2.  М: Сов.
радио, 1966, 1968. 832 с.
16.Назаров М.В., Кувшинов Б.И., Попов О.В. Теория передачи сигналов. –
М:. Связь, 1970, 369 с.
112
Документ
Категория
Без категории
Просмотров
12
Размер файла
2 816 Кб
Теги
ovsyan, burov
1/--страниц
Пожаловаться на содержимое документа