Криптография, 02 лекция (от 08 октября)

Материал из eSyr's wiki.

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

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

Современные алгоритмы шифрования делятся на симметричное и асимметричное шифрование.

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

В случае асимметричной схемы ключ зашифрования не равен ключу расшифрования.

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

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

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

[править] Шифр Цезаря

Для шифрования своих сообщений Цезарь выбирал букву, отстоящую на три от той, которую хотел зашифровать. A=D, B=E, C=F... Эта система работала для Цезаря достаточно хорошо, потому что в первом веке до нашей эры криптография не была развита. Как бы мы ломали сейчас? Частотный анализ. Частотный анализ это слишком сложно. Расшифровывается путем обратной подстановки.

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

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

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

[править] Шифр случайной подстановки

Табличка случайного соответствия одних букв другим. Пространство ключей 26!. Это очень большое число. Даже на современной технике за время такого перебора практически любая информация устареет. Как ломать? Все-таки частотный анализ. Анализируем базу текстов на нужном языке и ищем самую популярную букву. Смотрим самую частую букву в шифротексте. С высокой вероятностью это будет табличная пара. С практической точки зрения использовать частоты одной буквы не всегда удобно. Вашим первым заданием будет частотный анализ.

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

У подхода есть естественное развитие --смотреть самые распространенные биграммы и триграммы. В англичйском языке самая распространенная триграмма the, кроме текстов Хэммингуэя, где это and, которое призвано иллюстрировтаь унылость будней.

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

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

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

[править] Полиалфавитные шифры

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

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

Таблица 26х26, фактически все варианты шифра Цезаря.

Далее выбиралось какое-либо слово, которое выписывалось над открытым текстом.

abcabc
gethim

Каждый столбец используем в качестве отдельного варианта шифра Цезаря. a -- первая строчка таблицы, b -- вторая, c -- третья.

abcabc
gethim
gfvhjo

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

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

abcgethim
gethimnow
gfvkorhcf

Как же это ломать? Ломать первые символы не получится, потому что они самые стойкие. Может попробовать угадать длину ключа? Ну допустим угадали, что дальше?

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

Ещё варианты? Практически применявшийся вариант состоял в следующем -- понятно, что донесения обычно начинаются с "Ваше величество", что является весьма длинным.

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

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

[править] Шифр перестановки

Берем многострадальный текст, и выписываем столбцами

get
him
now

ghneiotmw

Ломается оно очень просто -- достаточно угадать длину.

Как можно усложнить систему?

Переставить столбцы.

Перестановка по ключу.

the
---
get
him
now

eht
---
teg
mih
won

Теперь простое угадывание нам уже не поможет.

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

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

Что это значит?

Шифр сотоит из некоей простой функции, которая применяется несколько раз. Каждое применение называется раундом.

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

Примером такого шифра будет являться DES.

[править] DES

Разработан в комании IBM. NIST, тогда ещё ANSI, объявила конкурс на создание шифра для использования коммерческими организациями.

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

Рекомендации были следующими -- уменьшить эффективную длину ключа, и, возможно(точно неизвестно) s-box были заменены на рекомендованные анб. Шифр DES является сетью Фейстеля, вы видите ее на слайде.

Какова польза от сети Фейстеля в таком виде? Во-перввых такой дизайн шифра позволяет не заботиться о том, как устроена раундовая функция F. Она не обязана быть симметричной, мы ее вычисляем всегда только в одну сторону, потому что чтобы расшифровать раунд достаточно повторить его в другую сторону. Чтобы изменить шифр достаточно изменить раундовую функцию, и это потом использовалось, например, в Blowfish.

Раундовая функция DES, на слайде.

s-box это таблица подстановки дл 6-битных векторов.

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

Чтобы разобраться в с-боксах, будет второе практическое задание.

В реальном des раундов 16.

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

Первое задание недели на 4, второе задание недель на 6, начиная с сегодняшнего дня.

[править] Дифференциальный криптоанализ

Изучение выхода функции шифрования при намеренном изменении входа.

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

s-box является фиксированным элементом?

Да, это часть стандарта.

То что мы в процессе сначала расширяем блок а потом сужаем, это хорошая практика?

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

Следующий вторник в 18.00