Методы и средства криптографической защиты информации

1

1

Федеральное агентство по образованию

Сибирский государственный аэрокосмический университет

имени академика М. Ф. Решетнева

Методы и средства криптографической защиты информации

Рекомендовано в качестве учебного пособия

для студентов, обучающихся по специальностям

"Комплексное обеспечение информационной безопасности

автоматизированных систем"

"Информационная безопасность телекоммуникационных систем"

Красноярск 2007

1

УДК 004.042

ББК 32.973.26-018.2 З 80

РЕЦЕНЗЕНТЫ:

Зав. кафедрой высшей математики Сибирского государственного аэрокосмического университета, д.ф.-м.н., профессор А.М. Попов;

Профессор Кызыл-Кийского института технологий, экономики и права Баткенского государственного университета, к.ф.-м.н. Т.К. Юлдашев.

Жданов, О. Н., Золотарев, В. В.

З80 Методы и средства криптографической защиты информации: Учебное пособие / О.Н. Жданов, В. В. Золотарев; СибГАУ. - Красноярск, 2007. - 217 с.

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

Учебное пособие предназначено для студентов, обучающихся по специальностям 090105 "Комплексное обеспечение информационной безопасности автоматизированных систем", 090106 "Информационная безопасность телекоммуникационных систем" всех форм обучения.

УДК 004.042

ББК 32.973.26-018.2

© Сибирский государственный аэрокосмический

университет имени академика М. Ф. Решетнева, 2007

© О.Н. Жданов, В. В. Золотарев, 2007

Учебное издание

Жданов Олег Николаевич

Золотарев Вячеслав Владимирович

методы и средства Криптографической защиты информации

Учебное пособие

Редактор

Компьютерная верстка

Подп. в печать __________. Формат 6084/16. Бумага офисная.

Печать плоская. Усл. печ. л. 6,0. Уч.-изд. л. 6,0.

Тираж 100 экз. Заказ 410. С 70.

Санитарно-эпидемиологическое заключение № 24.04.953. П.000032.01.03. от 29.01.2003 г.

Редакционно-издательский отдел СибГАУ.

660014, г. Красноярск, просп. им. газ. "Красноярский рабочий", 31.

Отпечатано в типографии "Город".

660014, г. Красноярск, ул. Юности, 24а.

Оглавление

Предисловие

Список принятых сокращений

1. Криптография как научная дисциплина

1.1 основные понятия

1.1.1 предмет криптографии

1.1.2 односторонние функции

1.2.задачи криптографии

1.2.1 проблемы безопасности информации

1.2.2 управление секретными ключами

1.3.математические основы криптографии

1.3.1 формальные модели простых шифров

1.3.2 модели открытых текстов

1.3.3 классификация шифров по различным признакам

Контрольные вопросы и задания

2. Алгоритмы блочного шифрования и элементы криптоанализа

2.1 стандарт шифрования данных des

2.1.1 описание des

2.1.2 режимы работы блочных шифров

2.1.3 расшифрование des

2.1.4 дифференциальный и линейный криптоанализ

2.1.5 варианты des

2.2 алгоритм шифрования данных гост 28147-89

2.2.1 описание алгоритма

2.2.2 логика построения и структура ключевой

Информации алгоритма

2.2.3 основной шаг криптопреобразования

2.2.4 базовые циклы криптографических преобразований

2.2.5 основные режимы шифрования

2.2.6 криптографическая стойкость госта

2.2.7 требования к качеству ключевой информации и источники ключей

2.3 алгоритм idea

2.4 алгоритм aes

2.5 обзор некоторых современных блочных шифров

2.5.1 алгоритм lucifer

2.5.2 алгоритм madriga

2.5.3 алгоритмы khufu и khafre

2.5.4 алгоритм rc2

2.5.6 алгоритм ca-1.1

2.5.7 алгоритм skipjack

2.6 объединение блочных шифров

2.6.1 двойное шифрование

2.6.2 тройное шифрование

2.6.3 другие схемы многократного шифрования

2.6.4 многократное последовательное использование блочных алгоритмов

2.7 алгоритмы с открытыми ключами

2.7.1 алгоритм рюкзака

2.7.2 алгоритм rsa

2.7.3 алгоритм rohlige-hellman

2.7.4 алгоритм rabin

2.7.5 алгоритм elgamal

2.7.6 алгоритм mceliece

2.7.7 алгоритм luc

2.7.8 криптосистемы на базе конечных автоматов

2.8 криптосистемы на эллиптических кривых

2.8.1 эллиптические кривые

2.8.2 построение криптосистем на эллиптических кривых

2.8.3 примеры эллиптических кривых и их применение

2.8.4 безопасность криптографии с использованием

Эллиптических кривых

2.9 шифры совершенные и близкие к совершенным

2.9.1 шифры совершенные по к. Шеннону

2.9.2 шифры, близкие к совершенным

2.10 экстремальные шифры

2.10.1 понятие экстремальности

2.10.2 экстремальный шифр

2.10.3 процедура исследования

Контрольные вопросы и задания

3. Средства криптографической защиты информации

3.1 виды средств криптографической защиты информации

3.1.1 аппаратные средства

3.1.2 программные средства

3.1.3 программно-аппаратные комплексы

3.2 применение средств криптографической защиты информации

3.2.1 принципы использования ключей шифрования

3.2.2 виды шифрования с использованием средств

Криптографической защиты информации

3.2.3 цифровые подписи

3.3.инфраструктура открытых ключей

3.3.1 сертификаты

3.3.2 центры сертификации

3.4 виртуальные частные сети

3.4.1 классификация виртуальных частных сетей

3.4.2 технология построения виртуальной частной сети

3.5 новые направления в криптографии

3.5.1 мультибазисная криптография

3.5.2 квантовое распределение ключей

Контрольные вопросы и задания

Послесловие

Библиографический список

Приложение

Список принятых сокращений

АНБ - Агентство национальной безопасности США (National Security Agency, NSA)

АПК -

АРМ - автоматизированное рабочее место

БСШ - [шифр], близкий к совершенному

ГПК - генератор псевдослучайных чисел

ДНФ - дизъюнктивная нормальная форма

ИНФ - индуктивная нормальная форма

КАС - код аутентификации сообщения

КНФ - конъюнктивная нормальная форма

КШ - криптошлюз

МНФ - минимальная нормальная форма

НСД - несанкционированный доступ

НФ - нормальная форма

ПФК - полная функциональная константа

РГПЧ - рекуррентный генератор последовательных чисел

СБИС - сверхбольшая интегральная схема

СКЗИ - средство криптографической защиты информации

СНФ - совершенно нормальная форма

УКЗД - устройство криптографической защиты данных

УЦ - удостоверяющий центр

ЭЦП - электронная цифровая подпись

AES - Advanced Encryption Standard (улучшенный стандарт шифрования)

ANSI - American National Standards Institute (Американский национальный институт стандартов)

BSAFE

CBC

CDMF - Commercial Data Masking Facility (коммерческое средство маскирования данных)

CFS - Cryptographic File System (криптографическая файловая система)

CFB

DEA - Data Encryption Algorithm

DES - Data Encryption Standard

DESX

DMS - Defense Messaging System (система защиты сообщений)

ECB

EDE - encrypt-decrypt-encrypt

GDES - Generalized DES (обобщенный DES)

IDEA - International Data Encryption Algorithm (международный алгоритм шифрования данных)

IPES - Improved Proposed Encryption Standard

ISDN

IV - /////// (инициализирующий вектор)

FEE - Fast Elliptic Encryption (быстрое эллиптическое шифрование)

LFSR - Linear Feedback Shift Register (регистр сдвига с линейной обратной связью)

MMB - Modular Multiplication-based Block cipher

NBS - National Bureau of Standards (Национальное бюро стандартов, США)

NIST - National Institute of Standards and Technology (Национальный институт стандартов и техники, США)

OFB

PES - Proposed Encryption Standard

RDES

RSA - Rivest, Shamir, Aldeman

SHA

TEMK - Triple Encryption with Minimum Key (тройное шифрование с минимальным ключом)

VNP - /////// (виртуальная частная сеть)

Предисловие

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

Данное учебное пособие предназначено для оказания помощи студентам в изучении дисциплин "Криптографические методы защиты информации", "Средства криптографической защиты информации", подготовке к лабораторным и практическим работам, занятиям и итоговому контролю.

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

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

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

Учебное пособие соответствует Государственному образовательному стандарту подготовки специалистов по специальностям 090105 "Комплексное обеспечение информационной безопасности автоматизированных систем", 090106 "Информационная безопасность телекоммуникационных систем" всех форм обучения.

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

· исследование лавинного эффекта и теории экстремальных шифров совместно с Кулешом Александром Юрьевичем;

· исследование шифров, близких к совершенным, их классификация совместно с Егоровой Татьяной Михайловной;

· создание и применение подхода операционного анализа криптоалгоритмов совместно с Кукарцевым Анатолием Михайловичем;

· разработка направления мультибазисной криптографии совместно с Краковским Павлом Сергеевичем;

· изучение различных аспектов применения шифра RSA и создание тестирующих программ совместно с Чурмантаевым Динаром Мунировичем и Лубкиным Иваном Александровичем.

Авторы предлагают данное учебное пособие в качестве основы для теоретической подготовки студентов по курсам "Криптографические методы защиты информации", "Средства криптографической защиты информации" и близким дисциплинам. Работа будет также полезна аспирантам и научным работникам, исследующим аспекты разработки, применения и реализации криптографических методов и средств защиты информации.

1. Криптография как научная дисциплина

1.1 Основные понятия

Как передать нужную информацию нужному адресату в тайне от других? Нетрудно прийти к выводу, что есть три возможности.

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

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

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

Прокомментируем эти три возможности [14, гл. 1].

1. При современном уровне развития науки и техники сделать такой канал связи между удаленными абонентами для неоднократной передачи больших объемов информации практически нереально.

2. Разработкой средств и методов скрытия факта передачи сообщения занимается стеганография.

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

Из детективных произведений хорошо известны различные способы тайнописи между строк обычного, незащищаемого текста: от молока до сложных химических реактивов с последующей обработкой.

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

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

3. Разработкой методов преобразования (шифрования) информации с целью ее защиты от незаконных пользователей занимается криптография. Такие методы и способы преобразования информации называются шифрами.

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

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

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

1.1.1 Предмет криптографии

Что же является предметом криптографии?

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

- государственная тайна;

- военная тайна;

- коммерческая тайна;

- юридическая тайна;

- врачебная тайна и т. д.

Далее мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации:

- имеется строго определенный круг законных пользователей, которые имеют право владеть этой информацией;

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

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

Ситуацию можно изобразить следующей схемой (см. рис. 1).

1

Рис.1. Угроза разглашения информации

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

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

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

Вскрытие (взламывание) шифра -- процесс получения защищаемой информации из шифрованного сообщения без знания примененного шифра.

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

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

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

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

1) является ли она для противника более ценной, чем стоимость атаки;

2) является ли она для вас более ценной, чем стоимость защиты.

Именно перечисленные соображения и являются решающими при выборе подходящих средств защиты: физических, стеганографических, криптографических и др.

Некоторые понятия криптографии удобно иллюстрировать историческими примерами, поэтому сделаем небольшое историческое отступление.

Долгое время занятие криптографией было уделом чудаков-одиночек. Среди них были одаренные ученые, дипломаты, священнослужители. Известны случаи, когда криптография считалась даже чёрной магией. Этот период развития криптографии как искусства длился с незапамятных времён до начала ХХ века, когда появились первые шифровальные машины. Понимание математического характера решаемых криптографией задач пришло только в середине ХХ века - после работ выдающегося американского ученого К. Шеннона

История криптографии связана с большим количеством дипломатических и военных тайн и поэтому окутана туманом легенд.

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

Цезарь использовал в переписке шифр, который в историю вошёл как Шифр Цезаря. Этот шифр реализует следующее преобразование открытого текста: каждая буква открытого текста заменяется третьей после нее буквой в алфавите, который считается написанным по кругу, т.е. после буквы "я" следует буква "а". Цезарь заменял букву третьей после ней буквой, но можно заменять и какой-нибудь другой. Главное, чтобы тот, кому посылается шифрованное сообщение, знал эту величину сдвига. Класс шифров к которым относится шифр Цезаря, называется шифрами замены.

Поэтому класс шифров, к которым относится и шифр "Сцитала", называется шифрами перестановки.

Шифр Цезаря. Этот шифр реализует следующее преобразование открытого текста: каждая буква открытого текста заменяется третьей после нее буквой в алфавите, который считается написанным по кругу, т. е. после буквы "я" следует буква "а". Отметим, что Цезарь заменял букву третьей после нее буквой, но можно заменять и какой-нибудь другой. Главное, чтобы тот, кому посылается шифрованное сообщение, знал эту величину сдвига. Класс шифров, к которым относится и шифр Цезаря, называется шифрами замены.

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

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

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

Вернемся к формальному описанию основного объекта криптографии [14]. Теперь в него необходимо внести существенное изменение -- добавить недоступный для противника секретный канал связи для обмена ключами (рис. 2). Создать такой канал связи вполне реально, поскольку нагрузка на него, вообще говоря, небольшая.

1

Рис. 2. Формальное описание объекта криптографии

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

Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра.

Под атакой на шифр понимают попытку вскрытия этого шифра.

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

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

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

Из более специфических приведем еще три примера возможностей противника:

- противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов;

- противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты;

- противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию.

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

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

Криптология - наука, состоящая из двух ветвей: криптографии и криптоанализа.

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

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

1.1.2 Односторонние функции

В 1976 году была опубликована работа молодых американских математиков У.Диффи и М.Э.Хеллмана "Новые направления в криптографии", которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. Центральным понятием "новой криптографии" является понятие односторонней функции. [14, гл. 1]

Односторонней называется функция F: X --> Y, обладающая двумя свойствами:

а) существует полиномиальный алгоритм вычисления значений F(x);

б) не существует полиномиального алгоритма инвертирования функции F (т.е. решения уравнения F(x) = у относительно х).

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

Еще одним новым понятием является понятие функции с секретом. Иногда еще употребляется термин функция с ловушкой. Функцией с секретом К называется функция F_k : X -> Y, зависящая от параметра К и обладающая тремя свойствами:

а) существует полиномиальный алгоритм вычисления значения F_k(х)для любых К и х;

б) не существует полиномиального алгоритма инвертирования F_k при неизвестном К;

в) существует полиномиальный алгоритм инвертирования F_k при известном К.

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

Применение функций с секретом в криптографии позволяет:

1) организовать обмен шифрованными сообщениями с использованием только открытых каналов связи, т.е. отказаться от секретных каналов связи для предварительного обмена ключами;

2) включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;

3) решать новые криптографические задачи, отличные от шифрования (электронная цифровая подпись и др.).

Опишем, например, как можно реализовать п. 1). Пользователь А, который хочет получать шифрованные сообщения, должен выбрать какую-нибудь функцию F_k с секретом К. Он сообщает всем заинтересованным (например, публикует) описание функции F_k в качестве своего алгоритма шифрования. Но при этом значение секрета К он никому не сообщает и держит в секрете. Если теперь пользователь В хочет послать пользователю А защищаемую информацию xX, то он вычисляет у = F_k(х) и посылает у по открытому каналу пользователю А. Поскольку А для своего секрета К умеет инвертировать F_k , то он вычисляет х по полученному у. Никто другой не знает К и поэтому в силу свойства б) функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению F_k(x) вычислить защищаемую информацию х.

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

Описанную выше идею Диффи и Хеллман предложили использовать также для электронной цифровой подписи сообщений, которую невозможно подделать за полиномиальное время. Пусть пользователю А необходимо подписать сообщение х. Он, зная секрет К, находит такое у, что F_K(y)=х, и вместе с сообщением х посылает у пользователю В в качестве своей цифровой подписи. Пользователь В хранит у в качестве доказательства того, что А подписал сообщение х.

Сообщение, подписанное цифровой подписью, можно представлять себе как пару (х,у), где х -- сообщение, у -- решение уравнения F_K(у) = х, F_K: X --> Y -- функция с секретом, известная всем взаимодействующим абонентам. Из определения функции F_k очевидны следующие полезные свойства цифровой подписи: 1) подписать сообщение х, т.е. решить уравнение F_k(y) = х, может только абонент -- обладатель данного секрета К; другими словами, подделать подпись невозможно;

2) проверить подлинность подписи может любой абонент, знающий открытый ключ, т.е. саму функцию F_k;

3) при возникновении споров отказаться от подписи невозможно в силу ее неподделываемости;

4) подписанные сообщения (х, у) можно, не опасаясь ущерба, пересылать по любым каналам связи.

Кроме принципа построения криптосистемы с открытым ключом, Диффи и Хеллман в той же работе предложили еще одну новую идею -- открытое распределение ключей. Они задались вопросом: можно ли организовать такую процедуру взаимодействия абонентов А и В по открытым каналам связи, чтобы решить следующие задачи:

1) вначале у А и В нет никакой обшей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у А и В появляется, т. е. вырабатывается;

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

Диффи и Хеллман предложили решать эти задачи с помощью функции

F(x) = а^х mod р,

где р -- большое простое число, х -- произвольное натуральное число, а -- некоторый примитивный элемент поля GF(p). Общепризнанно, что инвертирование функции а^х mod p, т. е. дискретное логарифмирование, является трудной математической задачей.

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

Абоненты А и В независимо друг от друга случайно выбирают по одному натуральному числу -- скажем x_А и x_B. Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:

у_А = а^xА mod р, у_B = а^хВ mod p.

(Числа р и а считаются общедоступными.) Потом они обмениваются этими элементами по каналу связи. Теперь абонент А, получив у_B и зная свой секретный элемент x_А, вычисляет новый элемент:

у^х_B^А mod p = (a^xB)^xA mod р.

Аналогично поступает абонент В:

у^х_A^B mod p = (a^xA)^xB mod р.

Тем самым у А и B появился общий момент поля, равный а^хАхВ. Этот элемент и объявляется общим ключом А и В.

Из описания протокола видно, что противник знает р, а, а^хА, а^хВ, не знает х^А и х^В и хочет узнать а^xAxB. В настоящее время нет алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это -- трудная математическая задача.

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

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

Приведем еще несколько примеров задач, решаемых удаленными абонентами.

1. Взаимодействуют два не доверяющих друг другу абонента. Они хотят подписать контракт. Это надо сделать так, чтобы не допустить следующую ситуацию: один из абонентов получил подпись другого, а сам не подписался.

Протокол решения этой задачи принято называть протоколом подписания контракта.

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

Протокол решения этой задачи принято называть протоколом подбрасывания монеты.

Опишем один из простейших протоколов подбрасывания монеты по телефону (так называемая схема Блюма-Микали). Для его реализации у абонентов А и В должна быть односторонняя функция f: X --> У, удовлетворяющая следующим условиям:

1) X -- множество целых чисел, которое содержит одинаковое количество четных и нечетных чисел;

2) любые числа х₁,х₂ X, имеющие один образ f(x₁) = f(x₂), имеют одну четность;

3) по заданному образу f(x) "трудно" вычислить четность неизвестного аргумента х.

Роль подбрасывания монеты играет случайный и равновероятный выбор элемента хX, а роль орла и решки -- четность и нечетность х соответственно. Пусть А -- абонент, подбрасывающий монету, а В -- абонент, угадывающий результат. Протокол состоит из следующих шагов:

1) А выбирает х ("подбрасывает монету"), зашифровывает х, т.е. вычисляет у = f(x), и посылает у абоненту В;

2) В получает у, пытается угадать четность х и посылает свою догадку абоненту А;

3) А получает догадку от В и сообщает В, угадал ли он, посылая ему выбранное число х;

4) В проверяет, не обманывает ли А, вычисляя значение f(x) и сравнивая его с полученным на втором шаге значением у.

3. Взаимодействуют два абонента А и В (типичный пример: А -- клиент банка, В -- банк). Абонент А хочет доказать абоненту В, что он именно А, а не противник.

Протокол решения этой задачи принято называть протоколом идентификации абонента.

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

Эту задачу принято называть задачей о византийских генералах, а протокол ее решения -- протоколом византийского соглашения.

Осмысление различных протоколов и методов их построения привело в 1985-1986 г.г. к появлению двух плодотворных математических моделей -- интерактивной системы доказательства и доказательства с нулевым разглашением. Математические исследования этих новых объектов позволили доказать много утверждений, весьма полезных при разработке криптографических протоколов (подробнее об этом см. главу 2).

Под интерактивной системой доказательства (Р, V, S) понимают протокол взаимодействия двух абонентов: Р (доказывающий) и V (проверяющий). Абонент Р хочет доказать V, что утверждение S истинно. При этом абонент V самостоятельно, без помощи Р, не может проверить утверждение S (поэтому V и называется проверяющим). Абонент Р может быть и противником, который хочет доказать V, что утверждение S истинно, хотя оно ложно. Протокол может состоять из многих раундов обмена сообщениями между Р и V и должен удовлетворять двум условиям:

1) полнота - если S действительно истинно, то абонент P абонента V признать это;

2) корректность -- если S ложно, то абонент Р вряд ли убедит абонента V, что S истинно.

Здесь словами "вряд ли" мы для простоты заменили точную математическую формулировку.

Подчеркнем, что в определении системы (Р, V, S) не допускалось, что V может быть противником. А если V оказался противником, который хочет "выведать" у Р какую-нибудь новую полезную для себя информацию об утверждении S? В этом случае Р, естественно, может не хотеть, чтобы это случилось в результате работы протокола (Р, V, S). Протокол (Р, V, S), решающий такую задачу, называется доказательством с нулевым разглашением и должен удовлетворять, кроме условий 1) и 2), еще и следующему условию:

3) нулевое разглашение -- в результате работы протокола (Р, V, S) абонент V не увеличит свои знания об утверждении S или, другими словами, не сможет извлечь никакой информации о том, почему S истинно.

1.2 Задачи криптографии

Целью настоящего раздела является определение основных понятий и задач криптографии. При написании данного раздела мы использовали учебное пособие [15].

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

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

Обеспечение целостности -- гарантирование невозможности несанкционированного изменения информации. Для гарантии целостности необходим простой и надежный критерий обнаружения любых манипуляций с данными. Манипуляции с данными включают вставку, удаление и замену.

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

Обеспечение невозможности отказа от авторства -- предотвращение возможности отказа субъектов от некоторых из совершенных ими действий. Рассмотрим средства для достижения этих целей более подробно.

1.2 Проблемы безопасности информации

Конфиденциальность

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

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

1

Рис.3. Передача шифрованной информации [15, c.57]

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

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

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

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

Если обозначить через М открытое, а через С шифрованное сообщения, то процессы зашифрования и расшифрования можно записать в виде равенств

E_k1(M)=C

D_k2(C)=M

которых алгоритмы зашифрования Е и расшифрования D должны удовлетворять равенству

D_k2(E_k1(M))=M

Различают симметричные и асимметричные криптосистемы. В симметричных системах знание ключа зашифрования k₁ позволяет легко найти ключ расшифрования k₂ (в большинстве случаев эти ключи просто совпадают). В асимметричных криптосистемах знание ключа k₁, не позволяет

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

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

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

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

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

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

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

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

Целостность

Наряду с конфиденциальностью не менее важной задачей является обеспечение целостности информации, другими словами, -- неизменности ее в процессе передачи или хранении [см. 15, с. 62-68]. Решение этой задачи предполагает разработку средств, позволяющих обнаруживать не столько случайные искажения (для этой цели вполне подходят методы теории кодирования с обнаружением и исправлением ошибок), сколько целенаправленное навязывание противником ложной информации. Для этого в передаваемую информацию вносится избыточность. Как правило, это достигается добавлением к сообщению некоторой проверочной комбинации, вычисляемой с помощью специального алгоритма и играющей роль контрольной суммы для проверки целостности полученного сообщения. Главное отличие такого метода от методов теории кодирования состоит в том, что алгоритм выработки проверочной комбинации является "криптографическим", то есть зависящим от секретного ключа. Без знания секретного ключа вероятность успешного навязывания противником искаженной или ложной информации мала. Такая вероятность служит мерой имитостойкости шифра, то есть способности самого шифра противостоять активным атакам со стороны противника.