Кратчайший очерк
истории, основных понятий и методов
крипто

Бессвязные заметки и аннотированная библиография

Максим Отставнов <maksim@otstavnov.com>

1. Обзорная лекция

В обзорной лекции мы рассмотрим складывание и смену понятийного аппарата крипто в связи с задачами практики и развитием теории.

Криптография в Древнем мире и Средних веках

• идея: задача конфиденциальной коммуникации

• идея: три пути ее решения: надежный канал, сокрытие канала (факта коммуникации), сокрытие смысла сообщения (шифры, коды, сигналы)

Подстановки в египетских иероглифах

1500 г. до н.э. Месопотамия

IV в. до н.э. Арта-шастра. Кама-сутра.

Библия: “Шешах” (Вавилон) в книге Иеремии

• античность, арабское средневековье. Подстановки и перестановки. Коды

Греция: Скиталы

Рим: “Шифр Цезаря”, “Шифр Августа”

Арабы: коды

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

• криптография, криптанализ и криптология

Шифрование, расшифровка, дешифровка (криптанализ)

• случайный характер применения крипто

• Ф. Бэкон. “Крипто --- оккультная наука”

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

Эпоха ручных шифров (XIV-XIX вв.)

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

Коды/номенклаторы

XV в. Леон Баттиста Альберти: шифрдиск

Иоганн Тритемий (многоалфавитные шифры), Джованни Баттиста Порта

• идея: разделение “системы” и “ключа”

XVI в. Джован Батиста Белазо (ключ)

Джироламо Кардано (отец теории вероятностей, матстатистики). Начала научной криптологии

Блез де Виженер

• XVI-XVIII вв. номенклаторы против многоалфавитных шифров

• середина XVIII в. популяризация: Джованни Джакомо Казанова

• XIX в.: ручной шифратор Томаса Джефферсона, “криптограф” Чарлза Уитстоуна

• Плейфер, Бэббидж. Сочетания подстановки и перестановки

• XIX в.: популяризация: По и Конан Дойл. Поп-крипто

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

Эпоха роторных шифров (первая половина XX в.)

• массовое применение шифраторов: тактическая военная связь

• принципы Керкхоффса

• автоматизация криптографии: механические и электромеханические шифраторы. Роторные шифры. Энигма

• крипто и телеграфия. Вернам.

• Драки в эфире. “Энигма”, “Пёрпл”

• автоматизация криптанализа: компьютеры (“бомбы”, “Колосс”...)

• криптанализ и теория чисел, теория сложности вычислений. Избыточность. Вклад Шеннона, Тьюринга.

• отсутствие популярности: эпоха мировых войн и холодной войны. Крипто в СССР --- закрытая тема. Торжество криптанализа, постфактум известное военной истории

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

2. Обзорная лекция

Компьютерная эпоха (вторая половина XX в.)

• автоматизация криптографии: компьютеры. Телеграфизация безналичных расчетов (аутентификация!) и банковские коммуникации

• спрос на истинно массовую криптографию

• социализация: возникновение академического сообщества.

• Дэвид Кан (1967). Криптофобия: NSA и цензура. Уотергейт (1971-4)

• простейшие протоколы. Стандарт DES (1975)

• потоковое шифрование/гаммирование (что не обсуждается американцами)

• проблема распределения ключей в массовой криптографии

• новая задача: идентификация/аутентификация (“подпись”)

• асимметрия. Ральф Меркл (1974), Уитфилд Диффи, Мартин Хеллман (1976). Джеймс Эллис (1969). Рон Ривест, Ади Шамир, Леонард Эддлмен (1977).

• Джим Безос и RSA Security, Inc. (1985), Фил Зиммерманн (1991).

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

• Крипто (с 1981)

• понятие протоколов

• тезаурус примитивов: блоки, потоки, . Крипто и некрипто-примитивы

• проблематизация предмета криптологии: протокол как обобщение алгоритма

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

Заключение

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

• ситуация в России. Закрытость тематики в советское время. ИКСИ. Военная “восьмерка”. Начала науки в середине 90х. Криптофобия в России: противодействие ФАПСИ. Саботаж законодательства. Публикации и образование. Ближайшие перспективы.

• Социология криптографического знания. Массовая криптограмотность как часть компьютерной грамотности. Понимание устройства крипто как часть компьютерной инженерии. Построение и ломка шифров.

• Криптография и “защита информации”. Паракриптография

3. Формализация

Примитивы

• одноключевые примитивы: симметричные шифры (блочные, потоковые). Фиксированные длины блоков и ключей. Полиномиальная (первой степени) производительность. Взаимозаменяемость потоковых и блочных шифров

• двухключевые примитивы: асимметричные шифры и ЦП. Фиксированные длины блоков и ключей. Полиномиальная (квадратичная, кубическая) производительность

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

• служебные примитивы: генерация случайных чисел, проверка чисел на простоту (стохастическая), проверка пар чисел на взаимную простоту

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

• мера абстрагирования от свойств материала.

Протоколы

• несводимость вопроса о стойкости протоколов к вопросу о стойкости примитивов

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

• гибридное шифрование

• гибридная ЦП

• сертификация (заверение) ключей

Формализация

Модульная арифметика и конечные поля (поля Галуа). Алфавит, аддитивная операция (с нулем и обратной операцией), мультипликативная операция (с обратной операцией (кроме “деления” на ноль) и единицей).

RSA

Генерация ключа:

простые p и q

n := pq

e; 3 < e < (p-1)(q-1); e взаимно просто с (p-1)(q-1)

d := e^-1 mod ((p-1)(q-1))

<n, e> -- открытый ключ; <n, d> -- закрытый ключ

Шифруются/подписываются сообщения m<n

Шифрование: c := m^e (mod n)

Расшифровка: m := c^d (mod n)

Наложение подписи: c := m^d (mod n)

Проверка подписи: m := c^e (mod n)

Примеры

Свободный криптографический пакет общего назначения GPG (http://www.gnupg.org); библиотека LAN-Crypto (свободная версия в составе ALT Linux (http://www.altlinux.ru)); свободная библиотека и язык быстрых теоретико-численных вычислений PARI/GP (http://www.math.u-psud.fr/~belabas/pari.html); свободный пакет символьной математики .

Аннотированная библиография

Источники по истории криптографии

Kahn, The Codebreakers (N.Y.: Scribner, 1996) [имеется сокращенный перевод: Кан, “Взломщики кодов” (М.: “Центрполиграф”, 2000)]

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

Levy, Crypto (N.Y.: Viking, 2001)

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

Соболева, "Тайнопись в истории России" (М.: “Международные отношения”, 1994)

Популярное изложение истории криптографии в России XVIII-нач. XX в.

Соболева, История шифровального дела в России (М.: “ОЛМА-Пресс”, 2002)

Жельников, “Криптография от папируса до компьютера” (М.: ABF, 1996)

Одна из первых книг на русском языке, посященная криптографии.

Журнал Cryptologia (с1 977)

Журнал Cryptologia, издающийся Военной академией США, остается единственным в мире реферируемым изданием статей по истории криптологии и криптографии. Периодически публикуются тематические сборники статей из этого журнала.

Источники по математическим основам криптографии и связанным вопросам

Кормен, Лейзерсон, Ривест, “Алгоритмы: построение и анализ” (М.: МЦНМО, 1999)

Грэм, Кнут, Паташник, “Конкретная математика” (М.: “Мир”, 1998)

Ноден, Китте, “Алгебраическая алгоритмика” (М.: “Мир”, 1999)

Виноградов, “Основы теории чисел” (М.: “Наука”, 1972)

Кнут, “Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы” (М.: “Мир”, 1977) [имеется второе издание (К.: “Williams”, 2001)]

Источники по методам криптографии

Шнайер, “Прикладная криптография” (М.: “Триумф”, 2002)

“Прикладная криптография” Брюса Шнайера --- самая читаемая книга по криптографии в мире. Она представляет собой “тезаурус” алгоритмов и протоколов, для многих из которых приведена реализация (на C). Материал ограничен концом девяностых годов, и некоторые позднее полученные результаты в книгу не вошли.

Саломаа, “Криптография с открытым ключом” (М.: “Мир”, 1996)

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

Зима, Молдовян, Молдовян, “Компьютерные сети и защита передаваемой информации” (СПб.: Издательство СПб. университета, 1998)

Основы теории и практики приложения криптографии к организации современных компьютерных сетей.

Молдовян, Молдовян, Гуц, Изотов, “Криптография: скоростные шифры” (СПб.: “БХВ”, 2002)

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

Баричев, Гончаров, Седов, “Основы современной криптографии” (М.: “Горячая линия --- Телеком”, 2001)

Самое компактное практическое введение в предмет.

Брассар, “Современная криптология” (М,: “Полимед”, 1999)

Компактное неформальное введение в предмет.

Бернет, Пэйн, “Криптография. Официальное руководство RSA Security” (М.: “Бином”, 2002)

(Я не читал перевода, поэтому могу оценить лишь оригинал.)

Неплохой справочник по вопросам практического применения методов криптографии в форме FAQ (“вопрос---ответ”). В книге наблюдается некоторый крен в сторону методов, реализованных в разработках компании RSA Security.

Журнал Journal of Cryptology (издается с 1988 г.)