Введение в криптографию. Общие вопросы, проблемы и решения. Обычная криптография

12.1. Введение. К истории стеганографии и криптографии.

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

Размышляя над задачей ТП, нетрудно прийти к выводу, что есть три возможности:

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

Прокомментируем эти три возможности.

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

Стеганография как наука сейчас находится в состоянии подъема, связанного с процессом стремительного развития Интернета. В переводе с греческого «стеганография» буквально означает «тайнопись» (steganos - тайна; graphy - писать). Целью стеганографии является сокрытие передачи информации; она не может заменить криптографию, но вместе с ней позволяет осуществлять максимально безопасную передачу сообщений.

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

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

Главная особенность компьютерной тайнописи - сокрытие файла- сообщения внутри файла-контейнера. В роли контейнера обычно выступают широко распространенные файлы графических форматов BMP, GIF, JPEG или звуковых WAV, хотя возможны и иные - все зависит от конкретной реализации. Современные компьютерные стеганографические системы используют в основном LSB-метод, или метод замены наименее значащего бита. Суть этого метода состоит в подмене значения бита наименьшей значимости. Предположим, мы хотим сокрыть сообщение внутри контейнера, в роли которого выступает черно-белая фотография. В стандартном восьмибитовом цифровом изображении значение яркости меняется от 0 до 255, изменение значения последнего бита может увеличить или уменьшить значение яркости на единицу. Таким образом, среднее изменение яркости пиксела не превысит одного процента. Добавим, что незначительному изменению подвергаются далеко не все элементы изображения, а значит, оно не будет внешне отличаться от оригинала. Из сказанного следует, что визуально отличить изменение файла-контейнера труднее, если он представляет собой изображение с равномерным контрастным шумом. Описанный выше метод применяют и для сокрытия сообщений в файлах звуковых форматов, при этом изменение оригинала-контейнера на слух практически неразличимо, а качественным контейнером может считаться файл с большими фоновыми шумами.

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

Несмотря на относительную молодость направления компьютерной стеганографии, с помощью поисковых систем в Интернете можно найти достаточное количество как профессиональных, так и любительских программ для тайнописи. Одним из наиболее удачных является пакет Steganos Security Suite 4. Эта программа является мощным набором утилит для обеспечения конфиденциальности информации. В ее состав входят средства для защиты дисков и доступа к компьютеру в целом, шифровки почтовых сообщений, обеспечения безопасности работы в Интернет, профессиональная утилита для гарантированно невосстановимого удаления файлов и, конечно же, качественная стенографическая система. Для интересующих нас целей предназначена утилита Steganos File Manager. С ее помощью возможно выбрать файл-контейнер из уже существующих на диске пользователя либо с помощью сканера или микрофона самостоятельно создать файл подходящего формата. Программа может не только надежно упрятать сообщение в выбранный контейнер, но и создать саморас- паковывающийся архив.

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

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

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

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

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

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

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

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

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

История криптографии связана с большим количеством дипломатических и военных тайн и поэтому окутана туманом легенд. Свои след в истории криптографии оставили многие хорошо известные исторические личности. Приведем несколько наиболее ярких примеров. Первые сведения об использовании шифров в военном деле связаны с именем спартанского полководца Лисандра (шифр «Сцитала»). Цезарь использовал в переписке шифр, который вошел в историю как «шифр Цезаря». В древней Греции был изобретен вид шифра, который в дальнейшем стал называться «квадрат Политая». Одну из первых книг по криптографии написал аббат И. Трителий (1462-1516), живший в Германии. В 1566 году известный математик Д. Кардано опубликовал работу с описанием изобретенной им системы шифрования («решетка Кардано»). Франция XVI века оставила в истории криптографии шифры короля Генриха IV и Ришелье. Имелось и много российских шифров, в том числе и «цифирная азбука» 1700 года, автором которой был Петр Великий.

Некоторые сведения о свойствах шифров и их применении можно найти и в художественной литературе, особенно в приключенческой, детективной и военной. Хорошее подробное объяснение особенностей одного из простейших шифров - шифра замены и методов его вскрытия содержится в двух известных рассказах: «Золотой жук» Э. По и «Пляшущие человечки» А. Конан Дойла.

Рассмотрим два примера.

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

Предмет криптографии.
Что же является предметом криптографии? Для ответа на этот вопрос вернемся к задаче ТП, чтобы уточнить ситуацию и используемые понятия.

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

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

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

Оглавление
Предисловия
Глава 1. Основные понятия криптографии
§1. Введение
§2. Предмет криптографии
§3. Математические основы
§4. Новые направления
§5. Заключение
Глава 2. Криптография и теория сложности
§1. Введение
§2. Криптография и гипотеза Р = NP
§3. Односторонние функции
§4. Псевдослучайные генераторы
§5. Доказательства с нулевым разглашением
Глава 3. Криптографические протоколы
§1. Введение
§2. Целостность. Протоколы аутентификации и электронной подписи
§3. Неотслеживаемость. Электронные деньги
§4. Протоколы типа «подбрасывание монеты по телефону»
§5. Еще раз о разделении секрета
§6. Поиграем в «кубики». Протоколы голосования
§7. За пределами стандартных предположений. Конфиденциальная передача сообщений
§8. Вместо заключения
Глава 4. Алгоритмические проблемы теории чисел
§1. Введение
§2. Система шифрования RSA
§3. Сложность теоретико-числовых алгоритмов
§4. Как отличить составное число от простого
§5. Как строить большие простые числа
§6. Как проверить большое число на простоту
§7. Как раскладывают составные числа на множители
§8. Дискретное логарифмирование
§9. Заключение
Глава 5. Математика разделения секрета
§1. Введение
§2. Разделение секрета для произвольных структур доступа
§3. Линейное разделение секрета
§4. Идеальное разделение секрета и матроиды
Глава 6. Компьютер и криптография
§1. Вместо введения
§2. Немного теории
§3. Как зашифровать файл?
§4. Поучимся на чужих ошибках
§5. Вместо заключения
Глава 7. Олимпиады по криптографии для школьников
§1. Введение
§2. Шифры замены
§3. Шифры перестановки
§4. Многоалфавитные шифры замены с периодическим ключом
§5. Условия задач олимпиад по математике и криптографии
§6. Указания и решения
Приложение А. Отрывок из статьи К. Шеннона «Теория связи в секретных системах»
Приложение Б. Аннотированный список рекомендованной литературы
Приложение В. Словарь криптографических терминов
Алфавитный указатель русскоязычных терминов
Алфавитный указатель англоязычных терминов.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Введение в криптографию, Ященко В.В., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.

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

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

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

Использованием «невидимых» носителей информации (микропленок);

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

Маскированием секретной информации обычным посланием и т.д.

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

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

1.1. Основные понятия и определения криптографии

Рассмотрим основные понятия, принятые в криптографии , и вначале определим, что такое криптография.

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

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

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

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

Классификация криптосистем представлена на рис. 1.1.

Рис. 1.1. Классификация криптосистем

Более полная классификация криптосистем приведена, например в .

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

Рис. 1.2. Упрощенная структурная схема симметричной криптосистемы

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

По виду криптографического преобразования – на шифры перестановки, шифры замены и композиционные шифры;

По конструктивным принципам – на поточные криптосистемы и блочные криптосистемы.

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

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

Рис. 1.3. Упрощенная структурная схема асимметричной криптосистемы

1.2. Из истории криптографии

По мнению ряда специалистов, криптография по возрасту – ровесник египетских пирамид. В документах древних цивилизаций (Индии, Египта, Месопотамии) есть сведения о системах и способах составления шифрованных писем.

В криптографии с древних времен использовались два вида шифров: замены (подстановки) и перестановки. Историческим примером шифра замены является шифр Цезаря (I век до н.э.), описанный историком Древнего Рима Светонием. Гай Юлий Цезарь использовал в своей переписке шифр собственного изобретения. Применительно к русскому языку он состоит в следующем. Выписывается алфавит, а затем под ним выписывается тот же алфавит, но с циклическим сдвигом на три буквы влево:

А	Б	В	Г	Д	Е	…	Э	Ю	Я
Г	Д	Е	Ё	Ж	З	…	А	Б	В

Зашифрование заключается в выборе буквы из первой строки и замену ее на букву второй строки, расшифрование представляет собой обратную операцию. Например, РИМ – УЛП. Ключом шифра Цезаря является величина циклического сдвига. Гай Юлий Цезарь всю жизнь использовал один и тот же ключ – сдвиг на 3 буквы. Приемник Юлия Цезаря – Цезарь Август использовал тот же шифр, но со сдвигом на одну букву. Светоний не приводит фактов дешифрования шифра Цезаря, однако в те времена, когда царила всеобщая неграмотность, даже обычное открытое послание могло остаться непрочитанным.

Одним из первых физических приборов, реализующих шифр перестановки является скитала . Он был изобретен в древней Спарте (V век до н.э.). Кроме Древней Греции прибор скитала использовался широко и в Древнем Риме. Скитала (в переводе - «жезл») представляет собой цилиндр заданного диаметра. На цилиндр наматывался ремень из пергамента, на который наносился текст сообщения вдоль оси цилиндра. Затем ремень сматывался и отправлялся получателю сообщения. Последний, имея аналогичный цилиндр, расшифровывал сообщение. Ключом шифра является диаметр скитала. Изобретение дешифровального устройства приписывается Аристотелю. Он предложил использовать для дешифрования конусообразное «копье», на которое наматывался перехваченный ремень, до тех пор, пока не появлялся осмысленный текст.

Одним из первых исторических имен, которое упоминается в связи с криптографией, это имя Энея - легендарного полководца, защитника Трои. В области тайнописи Энею принадлежат два изобретения. Первое из них – так называемый диск Энея . Его принцип прост. На диске размером 10-15 см и толщиной 1-2 см высверливались отверстия по числу букв алфавита. В центре диска закреплена катушка с нитью. При зашифровании нитка последовательно протягивалась через отверстия соответствующие буквам послания. Диск отсылался получателю, который вытягивал нитку из отверстий и получал сообщение в обратном порядке. Другим устройством является линейка Энея . Здесь вместо диска использовалась линейка с числом отверстий, равным числу букв в алфавите. Буквы по отверстиям располагались в произвольном порядке. К линейке прикреплялась катушка с нитью. При шифровании нить протягивалась через отверстие, соответствующее букве шифруемого послания, при этом на нити в месте прохождения отверстия завязывался узелок. Таким образом, зашифрованное послание представляло собой нить с узелками, в которой каждой букве ставилось в соответствие расстояние между узелками нити. Ключом шифра являлся порядок следования букв по отверстиям линейки. Аналогичное линейке Энея кипу (узелковое письмо) получило широкое распространение у индейцев Центральной Америки.

Еще оно изобретение древних греков – квадрат Полибия (Полибий – греческий государственный деятель, полководец, историк III века до н.э):

	A	B	C	D	E
A	A	B	C	D	E
B	F	G	H	I,J	K
C	L	M	N	O	P
D	Q	R	S	T	U
E	V	W	X	Y	Z

Применительно к современному латинскому алфавиту шифрование по этому квадрату заключалось в следующем. Шифруемая буква заменялась на координаты квадрата, в котором она записана. Так буква R заменяется на DB. При расшифровании каждая пара букв определяет соответствующую букву сообщения. Например, TABLE – DDAAABCAAE. Ключом этого шифра является сам квадрат. Усложненный вариант квадрата Полибия заключается в произвольном порядке записи букв в квадрате. При этом для запоминания такого произвольного порядка использовался лозунг, который представлял собой слово, записываемое без повтора букв в квадрат, а оставшиеся клетки квадрата заполнялись по порядку их следования остальными буквами алфавита. Например, THE APPLE соответствует THEAPL.

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

Во времена средневековья европейская криптография приобрела сомнительную славу, отголоски которой слышаться и в наши дни. Дело в том, что криптографию стали отождествлять с черной магией, астрологией, алхимией, к шифрованию призывались мистические силы. Для шифрования сообщений рекомендовалось использовать «магические квадраты» . Магия этих квадратов заключалась в том, что сумма чисел по строкам, столбцам и полным диагоналям равнялась одному числу. Шифрование по «магическому квадрату» заключалось в следующем. Буквы сообщения вписывались в квадрат согласно записанным в них числам, а в пустые клетки вставлялись произвольные буквы. Шифртекст выписывался в оговоренном заранее порядке. Например, сообщение ПРИЕЗЖАЮ СЕГОДНЯ зашифрованное с помощь «магического квадрата»:

16У	3И	2Р	13Д
5З	10Е	11Г	8Ю
9С	6Ж	7А	12О
4Е	15Я	14Н	1П

имеет вид УИРДЗЕГЮСЖАОЕЯНП. Данный шифр – обычный шифр перестановки, однако считалось, что особую стойкость ему придает волшебство «магического квадрата».

В XV веке аббат Тритемий сделал два новаторских предложения в области криптографии: он предложил шифр «Аве Мария» и шифр, основанный на периодически сдвигаемом ключе. Наиболее серьезное предложение Тритемия, дошедшее до наших дней, заключается в придуманной им таблице:

A	B	C	D	…	W	X	Y	Z
B	C	D	E	…	X	Y	Z	A
C	D	E	F	…	Y	Z	A	B
…	…	…	…	…	…	…	…	…
Y	Z	A	B	…	U	V	W	X
Z	A	B	C	…	V	W	X	Y

Первая буква текста шифруется по первой строке, вторая буква по второй строке и так далее. Первая строка одновременно является строкой букв открытого текста. Например, FIGHT – FJIKX. В первоначальном варианте в шифре Тритемия отсутствовал ключ. Секретом являлся сам способ шифрования. Дальнейшее усложнение шифра шло двумя путями: введением произвольного порядка расположения букв в таблице; усложнением порядка выбора строк таблицы при шифровании. Следует сказать, что шифр Цезаря является частным случаем шифра Тритемия.

Шифр «Аве Мария» основан на принципе замены букв шифруемого текста на целые слова, из которых составлялись внешне невинные сообщения. Например, Н – «Я», «ЗДЕСЬ»; Е – «ЖДУ», «БУДУ»; Т – «ДОМА», «ВЕЧЕРОМ». Тогда открытому сообщению НЕТ могут соответствовать послания «Я ЖДУ ДОМА», «ЗДЕСЬ БУДУ ВЕЧЕРОМ».

В XVII веке английский философ и ученый лорд-канцлер Френсис Бэкон выдвинул главные требования к шифрам: «Они не должны поддаваться дешифрованию, не должны требовать много времени для написания и чтения, не должны возбуждать никаких подозрений». Эти требования актуальны и сегодня.

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

А:	B:	C:	J.	K.	L.	S	T	U
D:	E:	F:	M.	N.	O.	V	W	X
G:	H:	I:	P.	Q.	R.	Y	Z

Например, APPLE соответствует криптограмме вида:

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

В XVI веке итальянец Альберти впервые выдвинул идею двойного шифрования, т.е. текст после первого шифрования подвергался повторному шифрованию. Альберти также принадлежит шифр, который он называл «шифром, достойным королей». Реализация шифра осуществлялась с помощью шифровального диска. На внешний неподвижный диск наносились буквы и цифры под которыми располагались буквы и цифры внутреннего подвижного диска. Процесс шифрования прост – буквам и цифрам открытого текста ставились в соответствие буквы и цифры внутреннего диска. После зашифровывания слова послания внутренний диск сдвигался на один шаг. Начальное положение дисков заранее оговаривалось. Диск Альберти с незначительными изменениями использовался вплоть до начала XX века.

В XVI веке заметный вклад в развитие криптографии внесли Матео Ардженти, Жовани Батиста Белазо, Джовани Батиста Порта, Кордано и др. Матео Ардженти был криптографом папы римского, именно ему принадлежит идея использования слова-лозунга для придания алфавиту легко запоминаемого смешанного вида. Ардженти также предложил вставлять в шифртекст большое количество букв «пустышек», устранять пунктуацию, не вставлять в шифртекст открытые слова («клер»), заменять буквы шифртекста на цифры. Белазо и Порта развили идеи Ардженти в своих трудах «Шифр сеньора Белазо» и «О тайной переписке».

Существенный вклад в развитие криптографии внес математик, врач и философ Кордано. Предложенный им шифр вошел в историю под названием «решетка Кордано». «Решетка Кордано» - это шифр перестановки, суть которого заключается в следующем. Брался лист плотного материала (картон, пергамент), представляющий собой квадрат в котором вырезаны «окна». При шифровании квадрат накладывался на лист бумаги и сообщение вписывалось в «окна», затем квадрат поворачивался на 90 градусов и сообщение продолжали записывать в «окна» повернутого квадрата. Такая процедура продолжалась до полного поворота квадрата на 360 градусов. Главное требование «решетки Кордано» - при всех поворотах «окна» не должны попадать на дно и тоже место, а при полном повороте квадрата все места в шифртексте оказываются занятыми. Шифртекст считывался по строкам из полученной таблицы. Предложенный Кордано шифр лежит в основе знаменитого шифра Ришелье , в котором шифрованный текст внешне имел вид обычного послания. Накладывая на лист с таким посланием прямоугольник прорезанными с окнами можно было прочесть сообщение. Шифр Ришелье не относиться ни к шифрам замены, ни к шифрам перестановки, он представлял собой стеганографический способ защиты информации. Такого рода шифром пользовался русский писатель и государственный деятель А.С. Грибоедов будучи послом в Персии.

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

Познакомившись в трудами Тритемия, Белазо, Кордано и Альберти французский государственный деятель Блез де Виженер разработал собственный шифр, который получил название шифр Виженера . Суть шифра заключалась в том, что выбирался секретное слово, которое являлось ключом шифра. Это слово выписывалось под открытым сообщением периодически. Верхняя буква открытого текста соответствовала столбцу таблицы Тритемия, а нижняя буква ключа – строке таблицы Тритемия, буква, стоящая на пересечение строки и столбца являлась буквой шифртекста. Шифр Виженера представляет собой шифр замены. В последующем этот шифр был несколько упрощен для практического использования начальником первого в Германии государственного дешифровального отдела графом Гронсфельдом. Шифр Виженера и шифр Гронсфельда являются по сути дела родоначальниками широко используемого в настоящее время шифра гаммирования. Шифр Виженера использовался в различных вариантах вплоть до XIX века. Одним из наиболее известных модификаций шифра Виженера является шифр английского адмирала Бофора. Достоинство шифра Бофора заключается в том, что правило зашифрования сообщений и их расшифрования совпадают.

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

В XIX веке появляются первые механические шифровальные устройства. Наиболее известными являются изобретения полковника американской армии Д. Уодсворта и английского инженера Ч. Уитстона. Устройство Уодсворта (1817 г.) представляло механический шифратор основными элементами которого были два шифровальных диска, на торце дного располагались буквы английского алфавита, а на торце второго буквы и цифры от 2 до 8. Литеры на втором диске били съемные, что позволяло менять алфавит шифрованного текста. Диски помещались в футляр с прорезанными в нем окнами. При вращении первого диска в верхнем окне выставлялась буква открытого сообщения. Диски были соединены шестеренчатой передачей, поэтому в нижнем окне появлялась соответствующая буква шифртекста. Устройство было снабжено специальной кнопкой для разъединения дисков. Это требовалось для того, чтобы обеспечивать установку устройства в заданное начальное положение. В устройстве Уодсворта просматриваются идеи Альберти, Тритемия, Виженера. Несмотря на то, что устройство было достаточно громоздким, к тому же в это время господствовали «ручные» шифры, которые не требовали специальных приспособлений, оно послужило толчком к развитию механических устройств для шифрования и расшифрования сообщений.

Интересное предложение по созданию механического устройства шифрования сделал Ч. Уитстон во второй половине XX века. В устройстве Уитстона просматриваются идеи Альберти, а также Уодсворта. Внешне устройство Уитстона напоминает диск Альберти, однако в нем реализована парадоксальная идея – алфавит открытого текста содержит большее количество знаков, чем шифрованного. Проблема неоднозначности в определении букв открытого сообщения решена Уитстоном блестяще. На рис. 1.4 представлен внешний вид устройства Уитстона.

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

Рис. 1.4. Внешний вид устройства Ч. Уитстона

В начале шифрования большая (длинная) стрелка указывает на знак "+". Малая стрелка, связанная с большой резьбовой шестеренкой, ставилась в то же положение, т.е. "часы" показывали "12.00". Набор букв открытого текста производился поворотом большой стрелки по направлению движения часовой. После такого поворота малая стрелка указывает знак шифрованного текста. Таким образом, при полном повороте большого диска малый диск смещался на единицу по отношению к исходному взаимному состоянию двух дисков, что приводило к сдвиговому изменению алфавита шифрованного текста по отношению к алфавиту открытого текста. По окончании каждого слова большая стрелка становилась на знак "+", буква, на которую при этом указывала короткая стрелка, записывалась как знак шифрованного текста. Во избежание неоднозначности расшифрования, удвоение букв в открытом тексте не допускается. Повторную букву следует либо пропустить, либо ставить вместо нее какую-нибудь редкую букву, например Q. Например, слово THE APPLE при шифровании записывается как +THE+APLE+ или +THE+APQLE+.

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

В начале XX века значительный вклад в развитие криптографии внес американец Г. Вернам. В 1917 году он, будучи сотрудником телеграфной компании, предложил идею автоматического шифрования телеграфных сообщений, суть которой заключается в следующем. Открытый текст представляется в коде Бодо (в виде пятизначных "импульсных комбинаций"). В этом коде, например, буква "А" имела вид (+ + - - -). На бумаге знак "+" означал отверстие, а знак "-" - его отсутствие. При считывании с ленты пятерка металлических щупов "опознавала" отверстия (при наличии отверстия щуп замыкал электрическую цепь). В линию связи посылались импульсы тока. Вернам предложил электромеханически покоординатно складировать импульсы знаков секретного текста с импульсами секретного ключа, представляющего из себя хаотический набор букв того же самого алфавита. Сложение, по современной терминологии, осуществлялось по модулю 2. Г. Вернам создал устройство, производящее операции шифрования автоматически, без участия шифровальщика, тем самым было положено начало так называемому "линейному шифрованию", когда процессы шифрования и передачи сообщения происходят одновременно. До той поры шифрование было предварительным, поэтому линейное шифрование существенно повышало оперативность связи. Шифр Вернама обладает исключительной криптографической стойкостью. В то же время очевиден и недостаток этой системы шифрования - ключ должна иметь ту же длину, что и открытый текст. Для расшифрования на приемном конце связи туда нужно передать (по тайным, защищенным каналам) ключ достаточной длины. При практической реализации это порождает проблемы, причем весьма существенные, что и предопределило скромное распространение шифров Вернама. Сам Вернам не был математиком-криптографом, тем не менее, он настаивал на том, что ключ шифра не должен повторяться при шифровании, и в этом, как показала история криптографии, он был прав. Его идеи породили новые подходы к надежной защите информации при передаче больших объемов сообщений.

Первая половина XX века стала «золотым веком» электромеханических шифровальных машин . Наибольшую известность получило семейство немецких электромеханических шифровальных машин Enigma. Различные модификации этой шифровальной машины использовались германскими войсками с конца 1923 года вплоть до 1945 года. В 1943 году союзникам по антигитлеровской коалиции удалось «взломать» машину Enigma, что сыграло большую роль в победе во Второй мировой войне. Для передачи наиболее секретных сообщений во время Второй мировой войне немцами использовалась шифровальная машина Lorenz. В американской армии с 1923 по 1943 год использовалась механическое устройство для шифрования М-94. В основу этого устройства положен диск Альберти. Для защиты дипломатической переписки в США использовалась машина Хеберна MarkII. Шведский криптограф Б. Хагелин разработал для французской секретной полиции шифровальное устройство СD-57, а для французских спецслужб – шифровальную машину М-209. Модификация этой машины использовалась также и американскими военными во Второй мировой войне. С 1939 года по 1952 год японцы использовали шифровальную машину для защиты дипломатической переписки под названием «Тип 97» и ее модификацию. В США эти машины получили красочное обозначение «Пурпурный код» и «Красный код». В СССР перед войной и в годы Великой Отечественной войны широко использовалась малогабаритная дисковая кодировочная машина К-37 «Кристалл». Только в 1940 году было выпущено 100 комплектов этой машины. После войны были подведены итоги эксплуатации К-37 и проводилась работа по ее дальнейшему совершенствованию.

Предисловие
Базовая терминология
Основные алгоритмы шифрования
Цифровые подписи
Криптографические хэш-функции

Предисловие

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

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

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

Базовая терминология

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

В криптографической терминологии исходное послание именуют открытым текстом (plaintext или cleartext ). Изменение исходного текста так, чтобы скрыть от прочих его содержание, называют шифрованием (encryption ). Зашифрованное сообщение называют шифротекстом (ciphertext ). Процесс, при котором из шифротекста извлекается открытый текст называют дешифровкой (decryption ). Обычно в процессе шифровки и дешифровки используется некий ключ (key ) и алгоритм обеспечивает, что дешифрование можно сделать лишь зная этот ключ.

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

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

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

Метод шифровки/дешифровки называют шифром (cipher ). Некоторые алгоритмы шифрования основаны на том, что сам метод шифрования (алгоритм) является секретным. Ныне такие методы представляют лишь исторический интерес и не имеют практического значения. Все современные алгоритмы используют ключ для управления шифровкой и дешифровкой; сообщение может быть успешно дешифровано только если известен ключ. Ключ, используемый для дешифровки может не совпадать с ключом, используемым для шифрования, однако в большинстве алгоритмов ключи совпадают.

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

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

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

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

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

Многие качественные криптографические алгоритмы доступны широко - в книжном магазине, библиотеке, патентном бюро или в Интернет. К широко известным симметричным алгоритмам относятся DES и IDEA, Наверное самым лучшим асимметричным алгоритмом является RSA. На страничке литературы приведен список хороших учебников по криптографии и смежным вопросам.

Цифровые подписи

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

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

Цифровые подписи также можно использовать для удостоверения (сертификации --- to certify ) того, что документ принадлежит определенному лицу. Это делается так: открытый ключ и информация о том, кому он принадлежит подписываются стороной, которой доверяем. При этом доверять подписывающей стороне мы можем на основании того, что ее ключ был подписан третьей стороной. Таким образом возникает иерархия доверия. Очевидно, что некоторый ключ должен быть корнем иерархии (то есть ему мы доверяем не потому, что он кем-то подписан, а потому, что мы верим a-priori, что ему можно доверять). В централизованной инфраструктуре ключей имеется очень небольшое количество корневых ключей сети (например, облеченные полномочиями государственные агенства; их также называют сертификационными агенствами --- certification authorities ). В распределенной инфраструктуре нет необходимости иметь универсальные для всех корневые ключи, и каждая из сторон может доверять своему набору корневых ключей (скажем своему собственному ключу и ключам, ею подписанным). Эта концепция носит название сети доверия (web of trust ) и реализована, например, в PGP.

Цифровая подпись документа обычно создается так: из документа генерируется так называемый дайджест (message digest ) и к нему добавляется информация о том, кто подписывает документ, штамп времени и прочее. Получившаяся строка далее зашифровывается секретным ключом подписывающего с использованием того или иного алгоритма. Получившийся зашифрованный набор бит и представляет собой подпись. К подписи обычно прикладывается открытый ключ подписывающего. Получатель сначала решает для себя доверяет ли он тому, что открытый ключ принадлежит именно тому, кому должен принадлежать (с помощью сети доверия или априорного знания), и затем дешифрует подпись с помощью открытого ключа. Если подпись нормально дешифровалась, и ее содержимое соответствует документу (дайджест и др.), то сообщение считается подтвержденным.

Свободно доступны несколько методов создания и проверки цифровых подписей. Наиболее известным является алгоритм RSA.

Криптографические хэш-функции

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

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

Много хороших криптографических хэш-функций доступно бесплатно. Широко известные включают MD5 и SHA.

Криптографические генераторы случайных чисел

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

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

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

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

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

Доступны несколько примеров криптографических генераторов случайных чисел.

Обеспечиваемая шифром степень защиты

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

Теоретически, любой шифровальный алгоритм с использованием ключа может быть вскрыт методом перебора всех значений ключа. Если ключ подбирается методом грубой силы (brute force ), требуемая мощность компьютера растет экспоненциально с увеличением длины ключа. Ключ длиной в 32 бита требует 2^32 (около 10^9) шагов. Такая задача под силу любому дилетанту и решается на домашнем компьютере. Системы с 40-битным ключом (например, экспортный американский вариант алгоритма RC4) требуют 2^40 шагов --- такие компьютерные мощности имеются в большинстве университетов и даже в небольших компаниях. Системы с 56-битными ключами (DES) требуют для вскрытия заметных усилий, однако могут быть легко вскрыты с помощью специальной аппаратуры. Стоимость такой аппаратуры значительна, но доступна для мафии, крупных компаний и правительств. Ключи длиной 64 бита в настоящий момент, возможно, могут быть вскрыты крупными государствами и уже в ближайшие несколько лет будут доступны для вскрытия преступными организацими, крупными компаниями и небольшими государствами. Ключи длиной 80 бит могут в будущем стать уязвимыми. Ключи длиной 128 бит вероятно останутся недоступными для вскрытия методом грубой силы в обозримом будущем. Можно использовать и более длинные ключи. В пределе нетрудно добиться того, чтобы энергия, требуемая для вскрытия (считая, что на один шаг затрачивается минимальный квантовомеханический квант энергии) превзойдет массу солнца или вселенной.

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

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

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

Чтобы дать представление о степени сложности вскрытия RSA, скажем, что модули длиной 256 бит легко факторизуются обычными программистами. Ключи в 384 бита могут быть вскрыты исследовательской группой университета или компании. 512-битные ключи находятся в пределах досягаемости крупных государств. Ключи длиной в 768 бит вероятно не будут надежны продолжительное время. Ключи длиной в 1024 бит могут считаться безопасными до тех пор, пока не будет существенного прогресса в алгоритме факторизации; ключи длиной в 2048 большинство считает надежными на десятилетия. Более подробную информацию о длинах ключей RSA можно почерпнуть из статьи Брюса Шнайера (Bruce Scheier).

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

Криптоанализ и атаки на криптосистемы

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

Атака со знанием лишь шифрованного текста (ciphertext-only attack ): Это ситуация, когда атакующий не знает ничего о содержании сообщения, и ему приходтся работать лишь с самим шифрованным текстом. На практике, часто можно сделать правдоподобные предположения о структуре текста, поскольку многие сообщения имеют стандартные заголовки. Даже обычные письма и документы начинаются с легко предсказумой информации. Также часто можно предположить, что некоторый блок информации содержит заданное слово.
Атака со знанием содержимого шифровки (known-plaintext attack ): Атакующий знает или может угадать содержимое всего или части зашифрованного текста. Задача заключается в расшифровке остального сообщения. Это можно сделать либо путем вычисления ключа шифровки, либо минуя это.
Атака с заданным текстом (chosen-plaintext attack ): Атакующий имеет возможнот получить шифрованный документ для любого нужного ему текста, но не знает ключа. Задачей является нахождение ключа. Некоторые методы шифрования и, в частности, RSA, весьма уязвимы для атак этого типа. При использовании таких алгоритмов надо тщательно следить, чтобы атакующий не мог зашифровать заданный им текст.
Атака с подставкой (Man-in-the-middle attack ): Атака направлена на обмен шифрованными сообщениями и, в особенности, на протокол обмена ключами. Идея заключается в том, что когда две стороны обмениваются ключами для секретной коммуникации (например, используя шифр Диффи-Хелмана, Diffie-Hellman), противник внедряется между ними на линии обмена сообщениями. Далее противник выдает каждой стороне свои ключи. В результате, каждая из сторон будет иметь разные ключи, каждый из которых известен противнику. Теперь противник будет расшифровывать каждое сообщение своим ключом и затем зашифровывать его с помощью другого ключа перед отправкой адресату. Стороны будут иметь иллюзию секретной переписки, в то время как на самом деле противник читает все сообщения.

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

Атака с помощью таймера

timing attack

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

Перевод статьи Tatu Ylonen "Introduction to Cryptography"

Введение в криптографию

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

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

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

Устойчивость шифра к поиску автокорреляций в сообщении называется криптостойкостью алгоритма. Даже при использовании удачных в этом смысле алгоритмов, если взломщик знает, что исходные (нешифрованные) данные удовлетворяют тому или иному требованию, например, содержат определенное слово или снабжены избыточным кодом, он может произвести полный перебор пространства ключей: перебирать все значения ключа, допускаемые алгоритмом, пока не будет получено удовлетворяющее требованию сообщение. При использовании ключей достаточно большой разрядности такая атака оказывается чрезмерно дорогой, однако прогресс вычислительной техники постоянно сдвигает границу "достаточности" все дальше и дальше. Так, сеть распределенных вычислений Bovine в 1998 году взломала сообщение, зашифрованное алгоритмом DES с 56-разрядным ключом за 56 часов работы. Простым и эффективным способом борьбы с такой атакой является расширение пространства ключей. Увеличение ключа на один бит приводит к увеличению пространства вдвое – таким образом, линейный рост размера ключа обеспечивает экспоненциальный рост стоимости перебора. Некоторые алгоритмы шифрования не зависят от разрядности используемого ключа – в этом случае расширение достигается очевидным способом. Если же в алгоритме присутствует зависимость от разрядности, расширить пространство можно, всего лишь применив к сообщению несколько разных преобразований, в том числе и одним алгоритмом, но с разными ключами. Еще один способ существенно усложнить работу взломщику – это упаковка сообщения перед шифрованием и/или дополнение его случайными битами. Важно подчеркнуть, впрочем, что количество двоичных разрядов ключа является лишь оценкой объема пространства ключей сверху, и во многих ситуациях эта оценка завышена. Некоторые алгоритмы в силу своей природы могут использовать только ключи, удовлетворяющие определенному условию – например, RSA использует простые числа. Это резко сужает объем работы по перебору, поэтому для обеспечения сопоставимой криптостойкости разрядность ключа RSA должна быть намного больше, чем у алгоритмов, допускающих произвольные ключи. Низкая криптостойкость может быть обусловлена. не только алгоритмом шифрования, но и процедурой выбора ключа: если ключ может принимать любые двоичные значения заданной разрядности, но реально для его выбора используется страдающий неоднородностью генератор псевдослучайных чисел, мы можем значительно сократить объем пространства, которое реально должен будет перебрать взломщик наших сообщений. Еще хуже ситуация, когда в качестве ключа используются легко запоминаемые слова естественного языка: в этом случае реальный объем пространства ключей даже довольно большой разрядности может измеряться всего лишь несколькими тысячами различных значений.

Современные алгоритмы шифрования делятся на два основных класса: с секретным и с публичным ключом.

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

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

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

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

Шифры с открытым ключом называются также двухключевыми. Если в алгоритмах со скрытым ключом для кодирования и декодирования сообщений используется один и тот же ключ, то здесь используются два ключа: публичный и приватный. Для прочтения сообщения, закодированного публичным ключом, необходим приватный, и наоборот. Помимо обычных соображений криптостойкости, к таким алгоритмам предъявляется дополнительное требование: невозможность восстановления приватного ключа по публичному иначе как полным перебором пространства ключей. Двухключевые схемы шифрования намного сложнее в разработке, чем схемы с секретным ключом: требуется найти преобразование, не поддающееся обращению при помощи применявшегося в нем публичного ключа, но такое, чтобы с применением приватного ключа его все-таки можно было обратить. Известные криптоустойчивые схемы основаны на произведениях простых чисел большой разрядности, дискретных логарифмах и эллиптических кривых. Наиболее широкое применение получил разработанный в 1977 г. алгоритм RSA. Известные двухключевые алгоритмы требуют соответствия ключей весьма специфическим требованиям, поэтому для достижения криптостойкости, сопоставимой с блочными алгоритмами, необходимо использовать ключи намного большей разрядности. Так, снятые в 2000 году ограничения Министерства торговли США устанавливали ограничения разрядности ключа, который мог использоваться в экспортируемом за пределы США программном обеспечении: для схем с секретным ключом устанавливался предел, равный 48 битам, а для схем с открытым – 480. Использование ключей большой разрядности требует значительных вычислительных затрат, поэтому двухключевые схемы чаще всего применяются в сочетании с обычными: обладатель публичного ключа генерирует случайную последовательность битов, кодирует ее и отправляет обладателю приватного ключа. Затем эта последовательность используется в качестве секретного ключа для шифрования данных. При установлении двустороннего соединения стороны могут сначала обменяться своими публичными ключами, а затем использовать их для установления двух разных секретных ключей, используемых для шифрования данных, передаваемых в разных направлениях. Такая схема делает практичной частую смену секретных ключей: так, в протоколе SSH ключ генерируется на каждую сессию, в протоколе виртуальных приватных сетей IPSEC время жизни ключа ограничено восемью часами. Еще более широкое применение двухключевые схемы нашли в области аутентификации и электронной подписи. Электронная подпись представляет собой контрольную сумму сообщения, зашифрованную приватным ключом отправителя. Каждый обладатель соответствующего публичного ключа может проверить аутентичность подписи и целостность сообщения. Это может использоваться для проверки аутентичности как сообщения, так и самого отправителя. Использование в качестве контрольной суммы обычного CRC невозможно, потому что генерация сообщения с заданным CRC не представляет вычислительной сложности. Для применения в электронной подписи были разработаны специальные алгоритмы вычисления контрольных сумм, затрудняющие подбор сообщения с требуемой суммой.

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

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

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

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

Некоторые системы предоставляют и более крупные структурные единицы, чем процесс. Например, в системах семейства Unix существуют группы процессов, которые используются для реализации логического объединения процессов в задания (job). Ряд систем имеют также понятие сессии – совокупности всех заданий, которые пользователь запустил в рамках одного сеанса работы. Впрочем, соответствующие концепции часто плохо определены, а их смысл сильно меняется от одной ОС к другой.

В более старых системах и в старой литературе называют результат загрузки задачей, а процессами – отдельные нити управления. Однако в наиболее распространенных ныне ОС семейств Unix и Win32, принято задачу называть процессом, а процесс – нитью (tread).