Электронная библиотека
Программисту веб-дизайнеру
Другие материалы
Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
С.Г. Баричев, Р.Е. Серов, Основы современной криптографии
• Бесплатно скачать книгу, объем 446 Кб, формат .djvu
1. КРИПТОГРАФИЧЕСКИЕ СИСТЕМЫ
1.1. История криптографии
1.2. Основные понятия и определения
1.2. Требования к криптографическим системам
1.3. Краткие сведения о криптоанализе
2. СИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ
2.1. Основные классы симметричных криптосистем
2.2. Общие сведения о блочных шифрах
2.3. Генерирование блочных шифров
2.4. Алгоритмы блочного шифрования
2.4.1. Алгоритм DES и его модификации
2.4.2. Стандарт AES. Алгоритм Rijndael
2.4.3. Алгоритм RC6
2.4.4. Российский стандарт шифрования ГОСТ 28147-89
2.4.5. Алгоритмы SAFER+, SAFER++
2.5. Режимы применения блочных шифров
2.6. Потоковые шифры
2.6.1. Общие сведения о потоковых шифрах
2.6.2. Самосинхронизирующиеся шифры
2.6.3. Синхронные шифры
2.6.4. Примеры потоковых шифров
Алгоритм RC4
Алгоритм SEAL
Алгоритм WAKE
3. АСИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ
.1. Общие положения
3.2. Односторонние функции и функции-ловушки
3.3. Асимметричные системы шифрования
3.3.1. Криптосистема Эль-Гамаля
3.3.2. Криптосистема, основанная на проблеме Диффи-Хеллмана
3.3.3. Криптосистема Ривеста-Шамира-Адлемана
3.3.4. Криптосистемы Меркля-Хеллмана и Хора-Ривеста
3.3.5. Криптосистемы, основанные на эллиптических кривых
4. ЭЛЕКТРОННЫЕ ЦИФРОВЫЕ ПОДПИСИ
4.1. Постановка задачи
4.2. Алгоритмы электронной цифровой подписи
4.2.1. Цифровые подписи, основанные на асимметричных
криптосистемах
4.2.2. Стандарт цифровой подписи DSS
4.2.3. Стандарт цифровой подписи ГОСТ Р 34.10-94
4.2.4. Стандарт цифровой подписи ГОСТ Р 34.10-2001
4.2.5. Цифровые подписи, основанные на симметричных
криптосистемах
4.3. Функции хэширования
4.3.1. Функция хэширования SHA
4.3.2. Функции хэширования SHA-256, SHA-512 и SHA-384116
4.3.3. Функция хэширования ГОСТ Р 34.11-94
4.3.4. Функция хэширования MD5
5. УПРАВЛЕНИЕ КРИПТОГРАФИЧЕСКИМИ КЛЮЧАМИ ...128
5.1. Обычная система управления ключами
5.2. Управление ключами, основанное на системах с открытым ключом
5.3. Протокол обмена секретным ключом
5.4. Использование сертификатов
5.5. Протоколы аутентификации
5.6. Анонимное распределение ключей
Краткая аннотация книги
1. КРИПТОГРАФИЧЕСКИЕ СИСТЕМЫ
1.1. История криптографии
Проблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом, волновала человеческий ум с давних времен. История криптографии - ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была своеобразной криптографической системой, так как в древних обществах ею владели только избранные. Священные книги древнего Египта, древней Индии тому примеры.
История криптографии условно можно разделить на 4 этапа.
1. Наивная криптография.
2. Формальная криптография.
3. Научная криптография.
4. Компьютерная криптография.
Для наивной криптографии (до нач. XVI века) характерно использование любых (обычно примитивных) способов запутывания противника относительно содержания шифруемых текстов. На начальном этапе для защиты информации использовались методы кодирования и стеганографии, которые родственны, но не тождественны криптографии.
Большинство из используемых шифров сводились к перестановке или моноалфавитной подстановке. Одним из первых зафиксированных примеров является шифр Цезаря, состоящий в замене каждой буквы исходного текста на другую, отстоящую от нее в алфавите на определенное число позиций. Другой шифр, полибианский квадрат, авторство которого приписывается греческому писателю Полибию, является общей моноалфавитной подстановкой, которая проводится с помощью случайно заполненной алфавитом квадратной таблицей (для греческого алфавита размер составляет 5x5). Каждая буква исходного текста заменяется на букву, стоящую в квадрате снизу от нее.
Этап формальной криптографии (кон. XV века - нач. XX века) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. В европейских странах это произошло в эпоху Возрождения, когда развитие науки и торговли вызвало спрос на надежные способы защиты информации. Важная роль на этом этапе принадлежит Леону Батисте Альберти, итальянскому архитектору, который одним из первых предложил многоалфавитную подстановку. Данный шифр, получивший имя дипломата XVI века Блеза Вижинера, состоял в последовательном "сложении" букв исходного текста с ключом (процедуру можно облегчить с помощью специальной таблицы). Его работа "Трактат о шифре" (1466) считается первой научной работой по криптологии.
Одной из первых печатных работ, в которой обобщены и сформулированы известные на тот момент алгоритмы шифрования является труд "Полиграфия" (1508 г.) немецкого аббата Иоганна Трисемуса. Ему принадлежат два небольших, но важных открытия: способ заполнения полибианского квадрата (первые позиции заполняются с помощью легко запоминаемого ключевого слова, остальные - оставшимися буквами алфавита) и шифрование пар букв (биграмм).
Простым но стойким способом многоалфавитной замены (подстановки биграмм) является шифр Плейфера, который был открыт в начале XIX века Чарльзом Уитстоном1. Уитстону принадлежит и важное усовершенствование - шифрование "двойным квадратом". Шифры Плейфера и Уитстона использовались вплоть до первой мировой войны, так как с трудом поддавались ручному криптоанализу.
В XIX веке голландец Керкхофф сформулировал главное требование к криптографическим системам, которое остается актуальным и поныне: секретность шифров должна быть основана на секретности ключа, но не алгоритма.
Наконец, последним словом в донаучной криптографии, которое обеспечили еще более высокую криптостойкосить, а также позволило автоматизировать (в смысле механизировать) процесс шифрования стали роторные криптосистемы.
Одной из первых подобных систем стала изобретенная в 1790 году Томасом Джефферсоном, будущим президентом США механическая машина. Многоалфавитная подстановка с помощью роторной машины реализуется вариацией взаимного положения вращающихся роторов, каждый из которых осуществляет "прошитую" в нем подстановку.
Практическое распространение роторные машины получили только в начале XX века. Одной из первых практически используемых машин, стала немецкая Enigma, разработанная в 1917 году Эдвардом Хеберном и усовершенствованная Артуром Кирхом. Роторные машины активно использовались во время второй мировой войны. Помимо немецкой машины Enigma использовались также устройства Sigaba (США), Турех (Великобритания), Red, Orange и Purple2 (Япония). Роторные системы -вершина формальной криптографии так как относительно просто реализовывали очень стойкие шифры. Успешные криптоа-таки на роторные системы стали возможны только с появлением ЭВМ в начале 40-х годов.
Главная отличительная черта научной криптографии (30-е - 60-е годы XX века) - появление криптосистем со строгим математическим обоснованием криптостойкости. К началу 30-х годов окончательно сформировались разделы математики, являющиеся научной основой криптологии: теория вероятностей и математическая статистика, общая алгебра, теория чисел, начали активно развиваться теория алгоритмов, теория информации, кибернетика. Своеобразным водоразделом стала работа Клода Шеннона "Теория связи в секретных системах" (1949), где сформулированы теоретические принципы криптографической защиты информации. Шеннон ввел понятия "рассеивание" и "перемешивание", обосновал возможность создания сколь угодно стойких криптосистем.
В 60-х годах ведущие криптографические школы подошли к созданию блочных шифров, еще более стойких по сравнению с роторными криптосистемами, однако допускающие практическую реализацию только в виде цифровых электронных устройств.
Компьютерная криптография (с 70-х годов XX века) обязана своим появлением вычислительным средствам с производительностью, достаточной для реализации критосистем, обеспечивающих при большой скорости шифрования на несколько порядков более высокую криптостойкость, чем "ручные" и "механические" шифры.
Первым классом криптосистем, практическое применение которых стало возможно с появлением мощных и компактных вычислительных средств, стали блочные шифры. В 70-е годы был разработан американский стандарт шифрования DES (принят в 1978 году). Один из его авторов, Хорст Фейстел (сотрудник IBM), описал модель блочных шифров, на основе которой были построены другие, более стойкие симметричные криптосистемы, в том числе отечественный стандарт шифрования ГОСТ 28147-89.
С появлением DES обогатился и криптоанализ, для атак на американский алгоритм был создано несколько новых видов криптоанализа (линейный, дифференциальный и т.д.), практическая реализация которых опять же была возможна только с появлением мощных вычислительных систем.
В середине 70-х годов произошел настоящий прорыв в современной криптографии - появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь отправной точкой принято считать работу, опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 году под названием "Новые направления в современной криптографии". В ней впервые сформулированы принципы обмена шифрованной информацией без обмена секретным ключом. Независимо к идее асимметричных криптосистем подошел Ральф Меркли. Несколькими годами позже Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, стойкость которой была основана на проблеме факторизации больших простых чисел. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы электронной цифровой подписи (ЭЦП) и электронных денег.
В 80-90-е годы появились совершенно новые направления криптографии: вероятностное шифрование, квантовая криптография и другие. Осознание их практической ценности еще впереди. Актуальной остается и задача совершенствования симметричных криптосистем. В 80-90-х годах были разработаны нефейстеловские шифры (SAFER, RC6 и др.), а в 2000 году после открытого международного конкурса был принят новый национальный стандарт шифрования США - AES.
Более подробно об увлекательной истории криптографии можно прочитать в книге [18].
1.2. Основные понятия и определения
Наукой, изучающей математические методы защиты информации путем ее преобразования, является криптология (крюттск; - тайный, Хсуск; - наука (слово) (греч.)). Криптология разделяется на два направления - криптографию и криптоанализ.
Криптография изучает методы преобразования информации, обеспечивающие ее конфиденциальность и аутентичность.
Под конфиденциальностью понимают невозможность получения информации из преобразованного массива без знания дополнительной информации (ключа). Аутентичность информации состоит в подлинности авторства и целостности.
Криптоанализ объединяет математические методы нарушения конфиденциальности и аутентичности информации без знания ключей.
Существует ряд смежных, но не входящих в криптологию отраслей знания. Так обеспечением скрытности информации в информационных массивах занимается стеганография. Обеспечение целостности информации в условиях случайного воздействия находится в ведении теории помехоустойчивого кодирования. Наконец, смежной областью по отношению к крип-тологии являются математические методы сжатия информации.
В этой книге будут рассматриваться только основы криптографии. Современная криптография включает в себя четыре крупных раздела:
Симметричные криптосистемы.
Криптосистемы с открытым ключом.
Системы электронной подписи.
Управление ключами.
Основные направления использования криптографических методов - передача конфиденциальной информации по каналам связи (например, электронная почта), установление подлинности передаваемых сообщений, хранение информации (документов, баз данных) на носителях в зашифрованном виде.
В качестве информации, подлежащей шифрованию и расшифрованию, а также электронной подписи будут рассматриваться тексты (сообщения), построенные на некотором алфавите. Под этими терминами понимается следующее.
Алфавит - конечное множество используемых для кодирования информации знаков.
Текст (сообщение) - упорядоченный набор из элементов алфавита.
В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:
алфавит - 32 буквы русского алфавита (исключая "ё") и пробел;
алфавит - символы, входящие в стандартные коды ASCII и КОИ-8;
двоичный алфавит - Z2 = {0,1} ;
восьмеричный или шестнадцатеричный алфавит.
Зашифрование - процесс преобразования открытых данных в зашифрованные при помощи шифра.
Вместо термина "открытые данные" часто употребляются термины открытый текст и исходный текст, а вместо "зашифрованные данные" - шифрованный текст.
Расшифрование - процесс, обратный зашифрованию, т.е процесс преобразования зашифрованных данных в открытые при помощи ключа. В некоторых источниках отдельно выделяют термин дешифрование, подразумевая под этим восстановление исходного текста на основе шифрованного без знания ключа, то есть методами криптоанализа. Мы в дальнейшем будем считать расшифрование и дешифрование синонимами.
Под шифрованием понимается процесс зашифрования или расшифрования. Также термин шифрование (в узком смысле) используется как синоним зашифрования. Однако неверно в качестве синонима шифрования использовать термин "кодирование" (а вместо "шифра" - "код"), так как под кодированием обычно понимают представление информации в виде знаков (букв алфавита).
Криптографическая система, или шифр представляет собой семейство Т обратимых преобразований открытого текста в шифрованный. Членам этого семейства можно взаимно однозначно сопоставить число к называемое ключом. Преобразование Т^ определяется соответствующим алгоритмом и значением ключа к.
Ключ - конкретное значение некоторых параметров алгоритма криптографического преобразования, обеспечивающее выбор одного преобразования из семейства. Секретность ключа должна обеспечивать невозможность восстановление исходного текста по шифрованному.
Пространство ключей К - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита. Следует отличать понятия ключ и пароль. 77а-ролъ также является секретной последовательностью букв алфавита, однако используется не для шифрования (как ключ), а для аутентификации субъектов.
Криптосистемы подразделяются на симметричные и асимметричные (или с открытым (публичным) ключом).
В симметричных криптосистемах для зашифрования и для расшифрования используется один и тот же ключ.
В системах с открытым ключом используются два ключа -открытый (публичный) и закрытый (секретный), которые математически связаны друг с другом. Информация зашифровывается с помощью открытого ключа, который доступен всем желающим, а расшифровывается с помощью закрытого ключа, известного только получателю сообщения.
Термины распределение ключей и управление ключами относятся к процессам системы обработки информации, содержанием которых является выработка и распределение ключей между пользователями.
Электронной (цифровой) подписью называется присоединяемое к тексту его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и целостность сообщения.
1.2. Требования к криптографическим системам
Процесс криптографического закрытия данных может осуществляться как программно, так и аппаратно. Аппаратная реализация отличается существенно большей стоимостью, однако ей присущи и преимущества: высокая производительность, простота, защищенность и т.д. Программная реализация более практична, допускает известную гибкость в использовании.
Независимо от способа реализации для современных криптографических систем защиты информации сформулированы следующие общепринятые требования:
1. Знание алгоритма шифрования не должно синжатъ криптостойскости шифра. Это фундаментальное требование было сформулировано в XIX веке Керкхоффом и разделяет криптосистемы общего использования (алгоритм доступен по тенциальному нарушителю) и ограниченного использования (алгоритм держится в секрете). Безусловно все массово исполь зуемые криптосистемы должны отвечать этому требованию. Взлом шифров в системе сотовой связи GSM или защите дисков DVD от незаконного воспроизведения - наглядные примеры последствий, к которым может привести несоблюдение этого требования.
2. Зашифрованное сообщение должно поддаваться чтению только при наличии ключа. Используемое в программе MS Word 6.0/95 "шифрование" документа на самом деле только запреща ло его открытие в данной программе. Сам же текст не шифро вался и был доступен для чтения в любом текстовом редакторе.
3. Шифр должен быть стойким даже в случае если нару- щителю известно достаточно большое количество исходных данных и соответствующих им зашифрованных данных.
4. Число операций, необходимых для расшифровывания ин формации путем перебора всевозможных ключей должно иметь строгую нижнюю оценку и должно либо выходить за пределы возможностей современных компьютеров (с учетом возможности организации сетевых вычислений) или требовать создания использования дорогих вычислительных систем.
5. Незначительное изменение ключа или исходного текста должно приводить к существенному изменению вида зашифро ванного текста. Этому требованию не соответствуют практи чески все шифры донаучной криптографии.
6. Структурные элементы алгоритма шифрования должны быть неизменными.
7. Длина шифрованного текста должна быть равной длине исходного текста.
8. Дополнительные биты, вводимые в сообщение в процессе шифрования, должен быть полностью и надежно скрыты в шифрованном тексте.
9. Не должно быть простых и легко устанавливаемых зави симостей между ключами, последовательно используемыми в процессе шифрования.
10. Любой ключ из множества возможных должен обеспе чивать равную криптостойкостъ. В этом случае принято гово рить о линейном (однородном) пространстве ключей.
1.3. Краткие сведения о криптоанализе
Криптоанализ как наука выходит за рамки данной книги, однако знание некоторых его положений необходимо для глубокого понимания криптографии. Главным действующим лицом в криптоанализе выступает нарушитель (или криптоаналитик). Под ним понимают лицо (группу лиц), целью которых является прочтение или подделка защищенных криптографическими методами сообщений.
В отношении нарушителя принимается ряд допущений, которые как правило кладутся в основу математических или иных моделей:
1. Нарушитель знает алгоритм шифрования (или выработки ЭЦП) и особенности его реализации в конкретном случае, но не знает секретного ключа.
2. Нарушителю доступны все зашифрованные тексты. Нару шитель может иметь доступ к некоторым исходным текстам, для которых известны соответствующие им зашифрованные тексты.
3. Нарушитель имеет в своем распоряжении вычислитель ные, людские, временные и иные ресурсы, объем которых оп равдана потенциальной ценностью информации, которая будет добыта в результате криптоанализа.
Попытку прочтения или подделки зашифрованного сообщения, вычисления ключа методами криптоанализа называют криптоатакой или атакой на шифр. Удачную криптоатаку называют взломом.
Криптостойкостъю называется характеристика шифра, определяющая его стойкость к расшифрованию без знания ключа (т.е. криптоатаке). Показатель криптостойкости - главный параметр любой криптосистемы. В качестве показателя крипто-стойкости можно выбрать: количество всех возможных ключей или вероятность подбора ключа за заданное время с заданными ресурсами; количество операций или время (с заданными ресурсами), необходимое для взлома шифра с заданной вероятностью; стоимость вычисления ключевой информации или исходного текста.
Все эти показатели должны учитывать также уровень возможной криптоатаки. Однако следует понимать, что эффективность защиты информации криптографическими методами зависит не только от криптостойкости шифра, но и от множества других факторов, включая вопросы реализации криптосистем в виде устройств или программ. При анализе криптостойкости шифра необходимо учитывать и человеческий фактор. Например, подкуп конкретного человека, в руках которого сосредоточена необходимая информация, может стоить на несколько порядков дешевле, чем создание суперкомпьютера для взлома шифра
Современный криптоанализ опирается на такие математические науки как теория вероятностей и математическая статистика, алгебра, теория чисел, теория алгоритмов и ряд других. Все методы криптоанализа в целом укладываются в четыре направления.
1. Статистический криптоанализ. Исследует возможности взлома криптосистем на основе изучения статистических зако номерностей исходных и зашифрованных сообщений. Его при менение осложнено тем, что в реальных криптосистемах ин формация перед шифрованием подвергается сжатию (превра щая исходный текст в случайную последовательность симво лов), или в случае гаммирования используются псевдослучай ные последовательности большой длины.
2. Алгебраический криптоанализ. Он занимается поиском математически слабых звеньев криптоалгоритмов. К примеру в 1997 году в эллиптических системах был выявлен класс ключей, которые существенно упрощали криптоанализ. 3. Дифференциальный (или разностный) криптоанализ. Основан на анализе зависимости изменения шифрованного тек ста от изменения исходного текста. Впервые использован Мерфи, улучшен Бихэмом и Шамиром для атаки на DES.
4. Линейный криптоанализ. Метод, основанный на поиске линейной аппроксимации между исходным и шифрованным текстом. Предложенный Мацуи, также впервые был применен при взломе DES. Как и дифференциальный анализ в реальных криптосистемах может быть применен только для анализа отдельных блоков криптопреобразований.
Опыт взломов криптосистем (в частности, конкурсов, которые регулярно устраивает RSA Data Security) показывает, что главным методом остается "лобовая" атака - проба на ключ. Также как показывает опыт криптосистемы больше страдают от небрежности в реализации.
Принято различать несколько уровней криптоатаки в зависимости от объем информации, доступной криптоаналитику. Грубо можно выделить три уровня криптоатаки по нарастанию сложности.
Атака по шифрованному тексту (Уровень КА1). Нарушителю доступны все или некоторые зашифрованные сообщения.
Атака по паре "исходный текст - шифрованный текст". (Уровень КА2). Нарушителю доступны все или некоторые зашифрованные сообщения и соответствующие им исходные сообщения.
Атака по выбранной паре "исходный текст - шифрованный текст". (Уровень КАЗ). Нарушитель имеет возможность выбирать исходный текст, получать для него шифрованный текст и на основе анализа зависимостей между ними вычислять ключ.
Все современные криптосистемы обладают достаточной стойкостью даже к атакам уровня КАЗ, то есть когда нарушителю доступно по сути шифрующее устройство.
Примечание. Сохраняйте книги на мобильный телефон и скачивайте их с Вашего телефона на компьютер. Удобное скачивание книг через мобильный телефон (в память телефона) и на Ваш компьютер через мобильный интерфейс. Быстрый Интернет без излишних тэгов. Материал носит неофициальный характер и приведен для ознакомления. Прямые ссылки на файлы книг запрещены.