Криптография: введение.

Leono 23 апреля 2017 в 15:17

Введение в криптографию и шифрование, часть первая. Лекция в Яндексе

• Блог компании Яндекс ,
• Алгоритмы ,
• Информационная безопасность ,
• Криптография

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

Я когда-то читал в МГУ лекции по крипте, и они занимали у меня по полгода. Я попытаюсь вам всё рассказать за два с половиной часа. Никогда этого не делал. Вот и попробуем.

Кто понимает, что такое DES? AES? TLS? Биноминальное отображение?

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

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

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

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

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

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

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

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

Первый криптографический примитив - симметричные шифры.


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


Какие здесь важные нюансы? В большинстве распространенных алгоритмов симметричного шифрования, с которыми можно столкнуться, размер шифротекста всегда равен размеру открытого текста. Современные алгоритмы шифрования оперируют размерами ключей. Размер ключей измеряется в битах. Современный размер - от 128 до 256 бит для алгоритмов симметричного шифрования. Об остальном, в том числе о размере блока, мы поговорим позже.


Исторически, в условном IV веке до нашей эры, существовало два метода дизайна шифров: шифры подстановки и перестановки. Шифры подстановки - алгоритм, где в те времена заменяли одну букву сообщения на другую по какому-то принципу. Простой шифр подстановки - по таблице: берем таблицу, где написано, что А меняем на Я, Б на Ю и т. д. Дальше по этой таблице шифруем, по ней же дешифруем.

Как вы считаете, с точки зрения размера ключа насколько это сложный алгоритм? Сколько вариантов ключей существует? Порядок факториала длины алфавита. Мы берем таблицу. Как мы ее строим? Допустим, есть таблица на 26 символов. Букву А можем заменить на любой из них, букву Б - на любой из оставшихся 25, С - на любой из оставшихся 24… Получаем 26*25*24*… - то есть факториал от 26. Факториал размерности алфавита.

Если взять log 2 26!, это будет очень много. Думаю, вы точно получите в районе 100 бит длины ключа, а то и поболее. Оказалось, что с точки зрения формального представления стойкости указанный алгоритм шифрования - довольно неплохой. 100 бит - приемлемо. При этом все, наверное, в детстве или юности, когда сталкивались с кодировками, видели, что такие алгоритмы дешифруются тривиально. Проблем с расшифровкой нет.

Долго существовали всякие алгоритмы подстановки в разных конструкциях. Одним из них, еще более примитивным, является шифр Цезаря, где таблица формируется не случайной перестановкой символов, а сдвигом на три символа: А меняется на D, B на Е и т. д. Понятно, что шифр Цезаря вместе со всеми его вариантами перебрать очень легко: в отличие от табличной подстановки, в ключе Цезаря всего 25 вариантов при 26 буквах в алфавите - не считая тривиального шифрования самого в себя. И его как раз можно перебрать полным перебором. Здесь есть некоторая сложность.

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

В чем проблема? Надо статистику распределения букв исказить, чтобы распространенные буквы не так светились в зашифрованном тексте. Очевидный способ: давайте будем шифровать самые часто встречающиеся буквы не в один символ, а в пять разных, например. Если буква встречается в среднем в пять раз чаще, то давайте по очереди - сначала в первый символ будем зашифровывать, потом во второй, в третий и т. д. Далее у нас получится маппинг букв не 1 к 1, а, условно, 26 к 50. Статистика, таким образом, нарушится. Перед нами первый пример полиалфавитного шифра, который как-то работал. Однако с ним есть довольно много проблем, а главное, очень неудобно работать с таблицей.

Берем в качестве ключа слово ВАСЯ. Берем сообщение МАША. Задействуем шифр Цезаря, но отсчитывая от этих букв. Например, В - третья буква в алфавите. Мы должны сдвинуть на три буквы соответствующую букву в открытом тексте. М сдвигается в П. А в А. Ш - на 16, перескочим букву А, получим, условно, Д. Я сдвинет А в Я. ПАДЯ.

Что удобно в получившемся шифре? Здесь было две одинаковых буквы, но в результате они зашифровались в разные. Это классно, потому что размывает статистику. Метод хорошо работал, пока где-то в XIX веке, буквально недавно на фоне истории криптографии, не придумали, как его ломать. Если посмотреть на сообщение из нескольких десятков слов, а ключ довольно короткий, то вся конструкция выглядит как несколько шифров Цезаря. Мы говорим: окей, давайте каждую четвертую букву - первую, пятую, девятую - рассматривать как шифр Цезаря. И поищем среди них статистические закономерности. Мы обязательно их найдем. Потом возьмем вторую, шестую, десятую и так далее. Опять найдем. Тем самым мы восстановим ключ. Единственная проблема - понять, какой он длины. Это не очень сложно, ну какой он может быть длины? Ну 4, ну 10 символов. Перебрать 6 вариантов от 4 до 10 не очень сложно. Простая атака - она была доступна и без компьютеров, просто за счет ручки и листа бумаги.

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

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

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

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

Помимо шифров подстановки, были еще шифры перестановки. С ними тоже все довольно просто. Берем сообщение ВАСЯИ, записываем его в блок какой-то длины, например в ДИДОМ, и считываем результат так же.

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

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

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


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

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

Из этой истории есть одно занятное исключение - шифроблокноты. Речь идет о настоящей шпионской истории про настоящий шпионаж. Некие люди, которым нужна абсолютно устойчивая коммуникация, генерируют случайные числа - например, буквальным бросанием кубика или буквальным выниманием шаров из барабана, как в лото. Создают два листа, где печатают эти случайные числа. Один лист отдают получателю, а второй оставляют у отправителя. При желании пообщаться они используют этот поток случайных чисел в качестве ключевого потока. Нет, история взята не из совсем далекого прошлого. У меня есть настоящий радиоперехват от 15 октября 2014 года: 7 2 6, 7 2 6, 7 2 6. Это позывной. 4 8 3, 4 8 3, 4 8 3. Это номер шифроблокнота. 5 0, 5 0, 5 0. Это количество слов. 8 4 4 7 9 8 4 4 7 9 2 0 5 1 4 2 0 5 1 4 и т. д. 50 таких числовых групп. Не знаю где, где-то не в России сидел какой-нибудь человек с ручкой и карандашом у обычного радиоприемника и записывал эти цифры. Записав их, он достал похожую штуку, сложил их по модулю 10 и получил свое сообщение. Другими словами, это реально работает, и подобное сообщение нельзя взломать. Если действительно были сгенерированы хорошие случайные числа и он впоследстии сжег бумажку с ключом, то осуществить взлом нельзя никак, совсем.

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

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


Самый исторически распространенный алгоритм подобного рода называется RC4. Он был разработан Роном Ривестом лет 25 назад и активно использовался очень долго, был самым распространенным алгоритмом для TLS, всех его различных вариантов, включая HTTPS. Но в последнее время RC4 начал показывать свой возраст. Для него существует некоторое количество атак. Он активно используется в WEP. Была одна хорошая лекция Антона , история, которая показывает: плохое применение пристойного даже по нынешним меркам алгоритма шифрования приводит к тому, что компрометируется вся система.

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

Большое достоинство RC4 - в том, что он целиком внутрибайтовый, а значит, его программная реализация работает довольно быстро - сильно быстрее, в разы, если не в десятки раз быстрее, чем сравнимый и существовавший примерно в одно время с ним шифр DES. Поэтому RC4 и получил такое распространение. Он долго был коммерческим секретом компании RSA, но потом, где-то в районе 90-х годов, некие люди анонимно опубликовали исходники его устройства в списке рассылки cypherpunks. В результате возникло много драмы, были крики, мол, как же так, какие-то неприличные люди украли интеллектуальную собственность компании RSA и опубликовали ее. RSA начала грозить всем патентами, всевозможными юридическими преследованиями. Чтобы их избежать, все реализации алгоритма, которые находятся в опенсорсе, называются не RC4, а ARC4 или ARCFOUR. А - alleged. Речь идет о шифре, который на всех тестовых кейсах совпадает с RC4, но технически вроде как им не является.

Если вы конфигурируете какой-нибудь SSH или OpenSSL, вы в нем не найдете упоминания RC4, а найдете ARC4 или что-то подобное. Несложная конструкция, он уже старенький, на него сейчас есть атаки, и он не очень рекомендуется к использованию.


Было несколько попыток его заменить. Наверное, на мой предвзятый взгляд самым успешным стал шифр Salsa20 и несколько его последователей от широко известного в узких кругах персонажа Дэна Берштайна. Линуксоидам он обычно известен как автор qmail.

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

Salsa20 устроен так, чтобы он всегда выполнялся за константное одинаковое время. Внутри он состоит всего из трех примитивов: это сдвиг на константное время, а также сложение по модулю 2 и по модулю 32, 32-битных слов. Скорость Salsa20 еще выше, чем у RC4. Он пока что не получил такого широкого распространения в общепринятой криптографии - у нас нет cipher suite для TLS, использующих Salsa20, - но все равно потихоньку становится мейнстримом. Указанный шифр стал одним из победителей конкурса eSTREAM по выбору лучшего поточного шифра. Их там было четыре, и Salsa - один из них. Он потихоньку начинает появляться во всяких опенсорс-продуктах. Возможно, скоро - может, через пару лет - появятся даже cipher suite в TLS с Salsa20. Мне он очень нравится.

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

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

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

В Salsa указанная проблема решена, поскольку в нем на вход поступает в том числе и номер блока, который надо сгенерировать. Дальше к номеру блока 20 раз применяется алгоритм. 20 раундов - и мы получаем 512 бит выходного потока.

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

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

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

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

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

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

Размер блока в современных шифрах - как правило, 128 бит. Бывают разные вариации, но как правило, речь идет про 128 или 256 бит, не больше и не меньше. Размер ключа - точно такой же, как для поточных алгоритмов: 128 или 256 бит в современных реализациях, от и до.

Из всех широко распространенных блочных шифров сейчас можно назвать два - DES и AES. DES очень старый шифр, ровесник RC4. У DES сейчас размер блока - 64 бита, а размер ключа - 56 бит. Создан он был в компании IBM под именем Люцифер. Когда в IBM его дизайном занимался Хорст Фейстель, они предложили выбрать 128 бит в качестве размера блока. А размер ключа был изменяемый, от 124 до 192 бит.

Когда DES начал проходит стандартизацию, его подали на проверку в том числе и в АНБ. Оттуда он вернулся с уменьшенным до 64 бит размером блока и уменьшенным до 56 бит размером ключа.


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

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

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


У нее есть несколько интересных достоинств. Первое важное достоинство: функция F может быть любой. Она не должна обладать свойствами обратимости, она может и не быть линейной или нелинейной. Все равно шифр остается симметричным.

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

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

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

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

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

И наконец, окончательная перестановка P. Она опять перемешивает 32 бита между собой. Все очень несложно, раундовая функция максимально простая.

Самое интересное ее свойство заключается в указанных S-боксах: задумано очень сложное превращение 6 бит в 4. Если посмотреть на всю конструкцию, видно, что она состоит из XOR и пары перестановок. Если бы S-боксы были простыми, весь DES фактически представлял бы собой некоторый набор линейных преобразований. Его можно было бы представить как матрицу, на которую мы умножаем наш открытый текст, получая шифротекст. И тогда атака на DES была бы тривиальной: требовалось бы просто подобрать матрицу.

Вся нелинейность сосредоточена в S-боксах, подобранных специальным образом. Существуют разные анекдоты о том, как именно они подбирались. В частности, примерно через 10 лет после того, как DES был опубликован и стандартизован, криптографы нашли новый тип атак - дифференциальный криптоанализ. Суть атаки очень простая: мы делаем мелкие изменения в открытом тексте - меняя, к примеру, значение одного бита с 0 на 1 - и смотрим, что происходит с шифротекстом. Выяснилось, что в идеальном шифре изменение одного бита с 0 на 1 должно приводить к изменению ровно половины бит шифротекста. Выяснилось, что DES, хоть он и был сделан перед тем, как открыли дифференциальный криптоанализ, оказался устойчивым к этому типу атак. В итоге в свое время возникла очередная волна паранойи: мол, АНБ еще за 10 лет до открытых криптографов знало про существование дифференциального криптоанализа, и вы представляете себе, что оно может знать сейчас.

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

56 бит сейчас уже можно просто перебрать на кластере машин общего назначения - может, даже на одном. И это плохо. Что можно предпринять?

Просто сдвинуть размер ключа нельзя: вся конструкция завязана на его длину. Triple DES. Очевидный ответ был таким: давайте мы будем шифровать наш блок несколько раз, устроим несколько последовательных шифрований. И здесь всё не слишком тривиально.

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

Окей, 56 бит. Давайте возьмем два - k1 и k2. 56 + 56 = 112 бит. 112 бит даже по нынешним меркам - вполне приемлемая длина ключа. Можно считать нормальным всё, что превышает 100 бит. Так почему нельзя использовать два шифрования, 112 бит?

Одно шифрование DES состоит из 16 раундов. Сеть применяется 16 раз. Изменения слева направо происходят 16 раз. И он - не группа. Есть доказательство того, что не существует такого ключа k3, которым мы могли бы расшифровать текст, последовательно зашифрованный выбранными нами ключами k1 и k2.

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

Эффективная стойкость алгоритма - не 112 бит, а 57, если у нас достаточно памяти. Нужно довольно много памяти, но тем не менее. Поэтому решили - так работать нельзя, давайте будем шифровать три раза: k1, k2, k3. Конструкция называется Triple DES. Технически она может быть устроена по-разному. Поскольку в DES шифрование и дешифрование - одно и то же, реальные алгоритмы иногда выглядят так: зашифровать, расшифровать и снова расшифровать - чтобы выполнять операции в аппаратных реализациях было проще.

Наша обратная реализация Triple DES превратится в аппаратную реализацию DES. Это может быть очень удобно в разных ситуациях для задачи обратной совместимости.

Где применялся DES? Вообще везде. Его до сих пор иногда можно пронаблюдать для TLS, существуют cipher suite для TLS, использующие Triple DES и DES. Но там он активно отмирает, поскольку речь идет про софт. Софт легко апдейтится.

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

Однажды DES стал показывать свой возраст, с ним стало тяжело, и люди решили придумать нечто поновее. Американская контора по стандартизации, которая называется NIST, сказала: давайте проведем конкурс и выберем новый классный шифр. Им стал AES.

DES расшифровывается как digital encrypted standard. AES - advanced encrypted standard. Размер блока в AES - 128 бит, а не 64. Это важно с точки зрения криптографии. Размер ключа у AES - 128, 192 или 256 бит. В AES не используется сеть Фейстеля, но он тоже многораундовый, в нем тоже несколько раз повторяются относительно примитивные операции. Для 128 бит используется 10 раундов, для 256 - 14.

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

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

Каждый раунд состоит из четырех довольно простых операций. Первый раунд - подстановка по специальной таблице.

В AES мы строим байтовую матрицу размером 4 на 4. Каждый элемент матрицы - байт. Всего получается 16 байт или 128 бит. Они и составляют блок AES целиком.

Вторая операция - побайтовый сдвиг.

Устроен он несложно, примитивно. Мы берем матрицу 4 на 4. Первый ряд остается без изменений, второй ряд сдвигается на 1 байт влево, третий - на 2 байта, четвертый - на 3, циклично.

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

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

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

Мы повторяем 4 описанных шага 10 раз, и на выходе из 128-битного блока снова получаем 128-битный блок.

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

Производители современных процессоров, Intel и AMD, уже разработали ассемблерные инструкции для реализации AES внутри чипа, потому что стандарт довольно несложный. Как итог - AES еще быстрее. Если через DES на современной машинке мы можем зашифровать, например, 1-2 гигабита, то 10-гигабитный AES-шифратор находится рядом и коммерчески доступен обычным компаниям.

Блочный алгоритм шифрует блок в блок. Он берет блок на 128 или 64 бита и превращает его в блок на 128 или 64 бита.

А что мы будем делать, если потребуется больше, чем 16 байт?

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

Да, очевидно, побьем всё на блоки по 16 байт и зашифруем. Такое шифрование называется ECB - electronic code boot, когда каждый из блоков по 16 байт в случае AES или по 8 байт в случае DES шифруется независимо.


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


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

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


Мы не только берем ключ и открытый текст, но и генерируем случайное число, которое не является секретным. Оно размером с блок. Называется оно инициализационным вектором.

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

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

Однако у CBC есть несколько проблем.

О размере блока. Представьте: мы начали шифровать и, допустим, у нас DES. Если бы DES был идеальным алгоритмом шифрования, выход DES выглядел бы как равномерно распределенные случайные числа длиной 64 бита. Какова вероятность, что в выборке из равномерно распределенных случайных чисел длиной 64 бита два числа совпадут для одной операции? 1/(2 64). А если мы сравниваем три числа? Давайте пока прервемся.

Все книги и пособия вы можете скачать абсолютно бесплатно и без регистрации.

NEW Алферов, Зубов, Кузьмин, Черемушкин. Основы криптографии. 2005 год. 480 стр. djvu. 19.2 Мб.
Написано ведущими специалистами в области криптографии, имеющими многолетний опыт разработки криптографических средств защиты и преподавания дисциплин криптографического цикла в ведущих вузах страны. Излагаются основные понятия и разделы, позволяющие получить представление о задачах и проблемах современной криптографии. В пособие вошли как традиционные вопросы классификации и оценки надежности шифров, так и системные вопросы использования криптографических методов защиты информации.
Для студентов, аспирантов, изучающих дисциплины по криптографии и компьютерной безопасности, преподавателей, а также широкого круга специалистов, задачами которых являются квалифицированный выбор и организация использования криптографических средств защиты информации.

Скачать .

NEW Н. Фергюсон, Б. Шнайер. Практическая криптография. 2005 год. 416 стр. pdf. 16.9 Мб.
В современном деловом мире вопрос безопасности компьютерных систем приобретает решающее значение. Проигнорировав его, вы лишаете себя возможности заработать деньги, расширить свой бизнес, а, следовательно, ставите под угрозу само существование вашей компании. Одной из наиболее многообещающих технологий, позволяющих обеспечить безопасность в киберпространстве, является криптография.
Данная книга, написанная всемирно известными специалистами в области криптографии, представляет собой уникальное в своем роде руководство по практической разработке криптографической системы, устраняя тем самым досадный пробел между теоретическими основами криптографии и реальными криптографическими приложениями.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

А.А. Болотов и др. Элементаоное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых.. 2006 год. 274 стр. djvu. 12.7 Мб.
Настоящая книга содержит описание и сравнительный анализ алгоритмов на эллиптических кривых. Изучаются протоколы эллиптической криптографии, имеющие аналоги - протоколы на основе алгебраических свойств мультипликативной группы конечного поля и протоколы, для которых таких аналогов нет - протоколы, основанные на спаривании Вейля и Тейта. В связи с этим описаны алгоритмы спаривания Вейля и Тейта и их модификации. Изложение теории сопровождается большим числом примеров и упражнений.

Данная книга является продолжением публикуемых ранее изданий книги этих же авторов "Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы"

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

А.А. Болотов и др. Элементаоное введение в эллиптическую криптографию. Алгебраические и алгоритмтческие основы. 2006 год. 324 стр. djvu. 15.0 Мб.
Настоящая книга посвящена перспективному направлению в области защиты информации, математическую основу которого составляет теория эллиптических кривых. Книга содержит необходимые для изучения эллиптической криптографии сведения по теории конечного поля и базовые понятия теории эллиптических кривых. В ней излагаются используемые алгебраические понятия и методы эффективной реализации базовых алгебраических операций, с помощью которых могут строиться как известные, так и перспективные криптографические системы, основанные на использовании группы точек эллиптической кривой. Изложение сопровождается большим числом примеров и упражнений.
Предназначено для студентов, преподавателей вузов и специалистов в области защиты информации, прикладной математики, вычислительной техники и информатики. Издание представляет интерес для лиц, связанных с кодированием и передачей информации и цифровой техникой, а также специалистов по прикладной математике, интересующихся компьютерной алгеброй.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

А.В. Бабаш. Криптография. 2007 год. 511 стр. djvu. 9.7 Мб.
Книга написана в форме пособия, направленного на изучение «классических» шифров, то есть шифров с симметричным ключом. После краткого исторического очерка в ней рассмотрены вопросы дешифрования простейших шифров, методы криптоанализа и синтеза криптосхем, вопросы криптографической стойкости, помехоустойчивости и имитостойкости шифрсистем. Архитектура пособия двухуровневая. Первый уровень предназначен для студентов, изучающих дисциплины криптографии и компьютерной безопасности, читателей, впервые знакомящихся с учебными материалами по криптографии. Второй уровень - для аспирантов, преподавателей вузов соответствующего профиля, для круга специалистов, чьей задачей является использование криптографических средств защиты информации, для читателей, желающих познакомиться с теоретической криптографией. На пособие получены положительные рецензии специалистов и организаций.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

Баричев С.Г., Серов Р.Е. Основы современной криптографии. 60 стр. djvu 740 Кб.
В этой книге будут рассматриваться только основы криптографии. Современная криптография включает в себя четыре крупных раздела:
Симметричные криптосистемы.
Криптосистемы с открытым ключом.
Системы электронной подписи.
Управление ключами.
Основные направления использования криптографических методов - передача конфиденциальной информации по каналам связи (например, электронная почта), установление подлинности передаваемых сообщений, хранение информации (докумен- (документов, баз данных) на носителях в зашифрованном виде.

Скачать .

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

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

Грушо А.А., Применко Э.А., Тимонина Е.Е. Анализ и синтез криптоалгоритмов. КУРС ЛЕКЦИЙ. 2000 год. 110 стр. PDF. 1.4 Мб.
Криптоалгоритмы – это алгоритмы преобразования данных, использующие “секрет”. Основной параметр качества криптоалгоритма – устойчивость к попыткам противника открыть “секрет”. Такая устойчивость в криптографии называется стойко- стью. Криптографическую стойкость надо обосновывать, так как в защите критической информации логика: “я не могу раскрыть “секрет”, следовательно, никто не может” неприменима. Методы обоснования криптографической стойкости основаны на накопленном опыте раскрытия “секретов” криптоалгоритмов.
В соответствии с традицией современной криптографии курс лекций содержит описание наиболее известных универсальных методов криптоанализа, методов анализа блочных и поточных шифров, методов анализа хэш-функций и алгоритмов с несимметричным ключом. По мере знакомства с методами анализа читателю предлагаются разделы, содержащие методы синтеза криптоалгоритмов.

Скачать

Н. Коблиц. КУРС ТЕОРИИ ЧИСЕЛ И КРИПТОГРАФИИ. 2001 год, 254 стр. djvu. 3.0 Мб.
Цель данной книги - ввести читателя в те области арифметики, как классические, так и самые современные, которые находятся в центре внимания приложений теории чисел, особенно криптографии. Предполагается, что знание высшей алгебры и теории чисел ограничено самым скромным знакомством с их основами; по этой причине излагаются также необходимые сведения из этих областей математики. Авторами избран алгоритмический подход, причем особое внимание уделяется оценкам эффективности методов, предлагаемых теорией.
Особенностью книги является изложение совсем недавно разработанных приложений теории эллиптических кривых. Перевод на русский язык осуществлен с оригинала второго издания, существенно пересмотренного по сравнению с первым изданием и снабженного обновленным списком литературы. Каждая глава включает в себя тщательно составленную подборку задач, как правило, снабженных подробными указаниями и решениями.
Все это позволяет рекомендовать книгу не только в качестве ценного пособия для общетеоретической подготовки специалистов по защите информации, но и как полезный источник примеров практической применимости целого ряда абстрактных разделов математики и кибернетики. Книга прекрасно подходит и для самообразования.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

С. Коутинхо. Введение в теорию чисел. Алгоритм RSA. 2001 год. 328 стр. djvu. 2.8 Мб.
Криптография! Многие еще с детства заинтригованы этим процессом. Кто не помиит «пляшущих человечков» Конан Дойля? Но реальная схема шифрования и проще, и сложнее, чем об этом написано в знаменитом рассказе классика.
Увилев в названии математическую теорию, некоторые из вас сочтут кннгу скучной и неинтересной. Ошибаетесь! Пособие написано живо, интересно и очень доступно. Для понимания сути достаточно знаний средней школы. Но несмотря на простой стиль изложения, все утверждения снабжены строгими доказательствами или ссылками на литературу.
Kpуг читателей очень широк: от школьников, интересующихся теорией чисел или шифрованием, до банковских и корпоративных программистов, желающих глубже вникнуть в основы своей деятельности.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Скачать

Осипян В.О. Осипян. К.В. Криптография в задачах и упражнениях. 2004 год. 146 стр. djvu. 1.7 Мб.
Приведено более 450 различных задач и упражнений, сгруппированных в соответствии с основными направлениями развития криптографических методов повышения информационной безопасности автоматизированных систем обработки данных. Каждому разделу предшествует краткое введение, состоящее из определений и основных понятий соответствующей области науки. Представленные задачи и упражнения охватывают как классические методы криптографической защиты информации, так и современные методы обеспечения конфиденциальности и целостности данных, ориентированные на применение вычислительной техники.
Для студентов, обучающихся по специальностям группы «Информационная безопасность», а также может быть полезен всем, желающим повысить собственный уровень знаний в области безопасной передачи и обработки информации.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

Н. Птицын. ПРИЛОЖЕНИЕ ТЕОРИИ ДЕТЕРМИНИРОВАННОГО ХАОСА В КРИПТОГРАФИИ. 2002 год, 80 стр. PDF. 1.6 Мб.
Настоящая работа посвящена приложению теории детерминироо ванного хаоса (нелинейной динамики) к компьютерной криптограафии. Рассмотрена взаимосвязь между хаотическими и криптографиическими системами на концептуальном и практическом уровнях. Теооретическое обоснование этой связи включает обсуждение таких поонятий как экспоненциальная чувствительность к начальным условиям, эргодичность, смешивание, сложность, случайность, непредсказуемость. Рассмотрены два подхода к практическому применению нелиинейных системы в криптографии: (1) аппроксимация непрерывных систем при помощи математики с плавающей запятой и (2) бинарный хаос с ограниченным числом состояний. Представлен обзор публикаций с описанием хаотических шифров и хаотических псевдослучайных генераторов. Рассмотрено приложение нелинейных систем с точным решением и неоднозначным преобразованием для построения псевдослучайных генераторов.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

А.Г. Ростовцев, Е.Б. Маховенко. Теоретическая криптография. 2005 год. 479 стр. djvu. 9.3 Мб.
Данное издание включает в себя материалы книг "Алгебраические основы криптографии", "Введение в криптографию с открытым ключом", "Введение в теорию итерированных шифров", выпущенных в из-дательстве "Мир и Семья" в 2000 2003 гг. Книга состоит из трех частей. Первая часть содержит сведения из алгебры, теории чисел, алгебраической геометрии. Вторая часть посвящена алгоритмам криптографии с открытым ключом, особое внимание уделено эллиптическим кривым. Третья часть содержит основные сведения из области итерированных шифров и хэш-функций. В приложении приведены эллиптические кривые для стандарта цифровой подписи ГОСТ Р 34.10-2001.
Книга может быть использована в качестве учебного пособия для углубленного изучения криптографии. В отличие от большинства изданий по криптографии, основное внимание уделено методам криптоанализа.
Предназначается для студентов, преподавателей, математиков и инженеров, специализирующихся в области разработки и исследования криптографических методов и средств защиты информации.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

Б.Я. Рябко, А.Н.Фионов. Криптографические методы защиты информации. 2005 год. 229 стр. djvu. 9.3 Мб.
Учебное пособие для вузов; Гриф УМО МО РФ; Учебное пособие; ВУЗ; Изложены основные подходы и методы современной криптографии для решения задач, возникающих при обработке, хранении и передаче информации. Основное внимание уделено новым направлениям криптографии, связанным с обеспечением конфиденциальности взаимодействий пользователей компьютеров и компьютерных сетей. Рассмотрены основные шифры с открытыми ключами, методы цифровой подписи, основные криптографические протоколы, блоковые и потоковые шифры, криптографические хеш-функции, а также редко встречающиеся в литературе вопросы о конструкции доказуемо невскрываемых криптосистем и криптографии на эллиптических кривых. Изложение теоретического материала ведется достаточно строго, но с использованием элементарного математического аппарата. Подробно описаны алгоритмы, лежащие в основе криптографических отечественных и международных стандартов. Приведены задачи и упражнения, необходимые при проведении практических занятий и лабораторных работ.
Для студентов, обучающихся по направлению «Телекоммуникации», может быть полезна специалистам.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

Н. Смарт. Криптография. 2005 год. 526 стр. pdf. 8.3 Мб.
Один из лучших в мировой практике курсов. Предназначен специалистам, работающим в области защиты информации, и специалистам-разработчикам программного обеспечения. Чрезвычайно подробно изложены симметричные шифры, криптосистемы с открытым ключом, стандарты цифровых подписей, отражение атак на криптосистемы. Даны примеры на языке Java, многочисленные оригинальные задачи, отражающие новейшее развитие теории и практики криптографии.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

Х.К.А.ван Тилборг. Профессиональное руководство и интерактивный учебник. 2006 год. 471 стр. djvu. 22.1 Мб.
Книга голландского криптолога посвящена современными аспектам криптографии и криптоанализа. Среди них можно выделить три главных направления традиционные (симметрические) криптосистемы, системы с публичными ключами и криптографические протоколы. Основные результаты снабжены доказательствами. Главной же особенностью служат многочисленные примеры, созданные на базе известного пакета "Mathematica" компьютерной алгебры. К книге приложен CD ROM, позволяющий (при наличии пакета "Mathematica") модифицировать примеры, в частности, увеличивая значения параметров. Это - первая столь многоплановая учебная книга по криптографии на русском языке. С примерами прилагается англоязычный вариант этой книги.
Книга, в первую очередь, адресована математикам, инженерам и студентам, специализирующимся в области защиты информации. Но она окажется интересной и для более широкого круга читателей, чему, в частности, могут способствовать детальные приложения, посвященные теории чисел и конечным полям, делающие книгу достаточно замкнутой в себе.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

Фомичев В.М. Дискретная математика и криптология. Курс лекций. 2003 год. 397 стр. djvu. 12.9 Мб.
Книга написана ведущим специалистом в области криптологии, имеющим многолетний опыт преподавания в МИФИ. Изложены базовые вопросы криптологии и необходимые для их изучения основы математического аппарата. С целью закрепления материала даны задачи и упражнения.
Рекомендуется для студентов, аспирантов, изучающих дисциплины по криптологии и компьютерной безопасности, преподавателей, а также практических работников, имеющих дело с криптографическими методами защиты информации.

Черемушкин А.В. Лекции по арифметическим алгоритмам криптографии. 2002 год, 100 стр. PDF. 585 Кб.
Лекции читались в Институте крипиографии связи и информатики.Курс отличается компактностью и простотой изложения, хотя написан строгим математическим языком. Рекомендуется всем, занимающимся криптографией.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ященко, редактор. 270 стр. PDF.
Оглавление:
1. Основные понятия криптографии. 2. Криптография и теория сложности. 3. Криптографические протоколы. 4. Алгоритмические проблемы теории чисел. 5. Математика разделения секрета. 6. Комльютер и криптография. Приложение: отрывок из статьи Шеннона "Теория связи в секретных системах" (около 40 стр.).

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Скачать

Victor Shoup. A Computational Introduction to Number Theory and Algebra. 2005 год. 512 стр. PDF. 4.6 Mб.
Оглавление (по главам):
1. Basic properties of the integers. 2. Congruences. 3. Computing with large integers. 4. Euclid’s algorithm. 5. The distribution of primes. 6. Finite and discrete probability distributions. 7. Probabilistic algorithms. 8. Abelian groups. 9. Rings. 10. Probabilistic primality testing. 11 Finding generators and discrete logarithms in Z. 12, Quadratic residues and quadratic reciprocity. 13 Computational problems related to quadratic residues. 14. Modules and vector spaces. 15. Matrices. 16. Subexponential-time discrete logarithms and factoring. 17 More rings. 18. Polynomial arithmetic and applications. 19. Linearly generated sequences and applications. 20 Finite felds. 21. Algorithms for ?nite felds. 22. Deterministic primality testing.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

R. F. Churchhouse. Codes and ciphers. Julius Caesar, the Enigma and the internet. 2004 год, 240 стр. PDF. 1.1 Мб.
Оглавление (по главам):
1. Introduction. 2. From Julius Caesarto simples ubstitution. 3. Polyalphabetic systems. 4.Jigsaw ciphers. 5.Two-letter ciphers. 6.Codes. 7. Ciphers forspies. 8. Producin grandom numbersandletters. 9.The Enigma cipher machine. 10. The Hagelin cipher machine. 11. Beyond the Enigma. 12. Public key cryptography. 13. Encipherment and the internet.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

J. TALBOT, D. WELSH. Complexity and Cryptography. 2006 год, 290 стр. PDF. 1.1 Мб.
Оглавление (по главам):
1. Basics of cryptography. 2. Complexity theory. 3. Non-deterministic computation. 5. Symmetric cryptosystems. 6. One way functions. 7. Public key cryptography. 8. Digital signatures. 9. Key establishment protocols. 10. Secure encryption. 11. Identification schemes. Мног приложений.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

I. F. Blake, G. Seroussi, N. P. Smart редакторы. Advances in Elliptic Curve Cryptography. 2005 год, 280 стр. PDF. 1.9 Мб.
Оглавление (по главам):
I. Elliptic Curve Based Protocols. II. On the Provable Security of ECDSA. III. Proofs of Security for ECIES. IV. Side-Channel Analysis. V. Defences Against Side-Channel Analysis. VI. Advances in Point Counting. VII. Hyperelliptic Curves and the HCDLP. VIII. Weil Descent Attacks. IX. Pairings. X. Cryptography from Pairings.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

Jeroen Mathias Doumen. Some Applications of Coding Theory in Cryptography. 2003 год, 80 стр. PDF. 415 Кб.
Оглавление (по главам):
1. Preliminaries and notation. 2. Adaptive chosen ciphertext attacks on the McEliece cryptosystem. 3. Digital signature schemes based on error–correcting codes. 4. Two families of Mersenne–like primes. 5 Pseudorandom sequences from elliptic curves.

. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Скачать .

Nicolas Gisin, Grґ egoire Ribordy, Wolfgang Tittel and Hugo Zbinden. Quantum cryptography. 2004 год, 110 стр. PDF. 1.3 Mб.
Оглавление (по главам):
1. Introduction. 2. A beautiful idea. 3. Technological challenges. 4. Experimental quantum cryptography with Faint laser pulses. 5 Experimental quantum cryptography with photon pairs. 6. Eavesdropping

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

Шифрование подразделяют на симметричное, асимметричное и комбинированное.

1. Симметричная криптография

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

Рис. 1

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

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

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

В настоящее время симметричные шифры – это:

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

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

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

Roadmap

Это первый урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:

• Урок 1. Исторические шифры. Основы и исторические шифраторы. Как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины (ты здесь)
• Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ
• Что такое сеть Фейстеля и какими бывают отечественные блочные шифры, используемые в современных протоколах, - ГОСТ 28147-89, «Кузнечик»
• В чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайера и как они работают
• Виды электронных подписей, как они работают и как их использовать
• Урок 6. Квантовая криптография. Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи

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

Термины

Для начала давай определимся с терминологией:

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

В мире криптографии путаться в этих словах - ужасный моветон.

Зачем мне знания о криптографии?

Предположим, криптография очень нужна, но пусть ей займутся дядьки с усами математики. Зачем же мне знания по криптографии?

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

Если ты программист или специалист по ИБ, то здесь вообще от криптографии никуда не скрыться. Любой крупный проект требует обеспечения безопасности информации. Неважно, что ты разрабатываешь: контентный сервис, почтовик, мессенджер, соцсеть или просто интернет-магазин, - везде есть критичные данные, которые надо защищать от перехвата или угона БД. Каждая операция должна быть защищена криптографическими протоколами. В этом случае криптография - подходящий инструмент. Если ты еще с ней не столкнулся, будь уверен - это на 100% лишь вопрос времени.

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

Зачем изучать старые шифры?

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

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

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

Исторические шифры и первые шифраторы

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

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

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

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

Шифр сдвига

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

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

Пример шифра

Исходный текст: Hi, Brut! How are you?
Шифрованный текст: Kl, Euxw! Krz duh brx?

Расшифрование

На этапе расшифрования мы имеем шифрованный текст и ключ, равный трем. Чтобы получить исходный текст, ищем для каждого символа сдвиг на три позиции к началу алфавита. Так, для первого символа K сдвиг три будет означать символ H. Далее посимвольно расшифровываем текст, пока не получаем исходную фразу Hi, Brut! How are you? .

Криптоанализ

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

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

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

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

Шифр замены

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

Пример шифра

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

Исходный текст: Hi, Brut! How are you?
Шифрованный текст: Vl, Enfh!Vrz bnw drf?

Расшифрование

При расшифровании заменяем каждый символ шифротекста соответствующим символом из известной нам таблицы подстановки: v => h, l => i и так далее. После чего получаем исходную строку Hi, Brut! How are you? .

Криптоанализ

Криптоанализ этого шифра также выполняется методом частотного анализа текста. Рассмотрим пример:

MRJGRJ LK HVW XBSLHBM RI QNWBH ENLHBLJ, LHK SRMLHLXBM, WXRJRPLX, BJG XRPPWNXLBM XWJHNW. LH LK RJW RI HVW MBNQWKH XLHLWK LJ HVW ZRNMG BJG HVW MBNQWKH XLHD LJ WFNRSW. LHK SRSFMBHLRJ LK BERFH 8 PLMMLRJ. MRJGRJ LK GLYLGWG LJHR KWYWNBM SBNHK: HVW XLHD, ZWKHPLJKHWN, HVW ZWKH WJG, BJG HVW WBKH WJG. HVW VWBNH RI MRJGRJ LK HVW XLHD, LHK ILJBJXLBM BJG EFKLJWKK XWJHNW. JFPWNRFK EBJUK, RIILXWK, BJG ILNPK BNW KLHFBHWG HVWNW, LJXMFGLJQ HVW EBJU RI WJQMBJG, HVW KHRXU WAXVBJQW, BJG HVW RMG EBLMWD. IWZ SWRSMW MLYW VWNW, EFH RYWN B PLMMLRJ SWRSMW XRPW HR HVW XLHD HR ZRNU. HVWNW BNW KRPW IBPRFK BJXLWJH EFLMGLJQK ZLHVLJ HVW XLHD. SWNVBSK HVW PRKH KHNLULJQ RI HVWP LK HVW KH. SBFM\"K XBHVWGNBM, HVW QNWBHWKH RI WJQMLKV XVFNXVWK. LH ZBK EFLMH LJ HVW 17HV XWJHFND ED KLN XVNLKHRSVWN ZNWJ. HVW HRZWN RI MRJGRJ ZBK IRFJGWG ED OFMLFK XBWKBN BJG LJ 1066 NWEFLMH ED ZLMMLBP HVW XRJTFWNRN. LH ZBK FKWG BK B IRNHNWKK, B NRDBM SBMBXW, BJG B SNLKRJ. JRZ LH LK B PFKWFP.

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

W - 88, H - 74, L - 67, J - 55, B - 54, K - 52, R - 51, N - 41, M - 36, V - 35, X - 29, G - 27, F - 23, P - 16, S - 16, I - 15, Z - 13, E - 13, D - 11, Q - 10, U - 5, Y - 4, T - 1, O - 1, A - 1

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

Дальше пробуем найти наиболее короткое слово, куда входит уже известная нам буква W => e. Видим, что сочетание HVW чаще всего встречается в шифре. Нетрудно догадаться, что, скорее всего, это триграмма the, то есть в тексте мы уже определили три символа. Если посмотреть на промежуточный результат, сомнений не остается:

MRJGRJ LK the XBSLt BM RI QNe Bt ENLt BLJ, Lt K SRMLt LXBM, e XRJRPLX, BJG XRPPe NXLBM Xe Jt Ne . Lt LK RJe RI the MBNQe Kt XLt Le K LJ the ZRNMG BJG the MBNQe Kt XLt D LJ e FNRSe . Lt K SRSFMBt LRJ LK BERFt 8 PLMMLRJ. MRJGRJ LK GLYLGe G LJt R Ke Ye NBM SBNt K: the XLt D, Ze Kt PLJKt e N, the Ze Kt e JG, BJG the e BKt e JG. the h e BNt RI MRJGRJ LK the XLt D, Lt K ILJBJXLBM BJG EFKLJe KK Xe Jt Ne . JFPe NRFK EBJUK, RIILXe K, BJG ILNPK BNe KLt FBt e G the Ne , LJXMFGLJQ the EBJU RI e JQMBJG, the Kt RXU e AXh BJQe , BJG the RMG EBLMe D. Ie Z Se RSMe MLYe h e Ne , EFt RYe N B PLMMLRJ Se RSMe XRPe t R the XLt D t R ZRNU. the Ne BNe KRPe IBPRFK BJXLe Jt EFLMGLJQK ZLt h LJ the XLt D. Se Nh BSK the PRKt Kt NLULJQ RI the P LK the Kt . SBFM\"K XBthe GNBM, the QNe Bt e Kt RI e JQMLKh Xh FNXh e K. Lt ZBK EFLMt LJ the 17t h Xe Jt FND ED KLN Xh NLKt RSh e N ZNe J. the t RZe N RI MRJGRJ ZBK IRFJGe G ED OFMLFK XBe KBN BJG LJ 1066 Ne EFLMt ED ZLMMLBP the XRJTFe NRN. Lt ZBK FKe G BK B IRNt Ne KK, B NRDBM SBMBXe , BJG B SNLKRJ. JRZ Lt LK B PFKe FP.

Отлично, уже известны три буквы. Снова ищем наиболее короткие слова с новыми известными нам подстановками. Сочетание it является частоупотребляемым, и, поскольку буква t уже дешифрована (HVW => the), очевидно, что в нашем тексте L => i (LH => it). После этого обращаемся к поиску биграмм is и to, устанавливаем, что K => s, R => o. Затем обращаем внимание на триграммы ~ing и and. Анализ текста показывает, что BJG, скорее всего, шифротекст от and. После замены всех наиболее часто встречающихся символов получаем текст:

Mondon is the Xa Sita M o I QNeat ENitain , its So Miti Xa M, e Xono Pi X, and Xo PPe NXia M Xent Ne . it is one o I the Ma NQest Xities in the Zo NMd and the Ma NQest Xit D in e FNo Se . its So SFMation is a Eo Ft 8 Pi MMion . Mondon is di Yided into se Ye Na M Sa Nts : the Xit D, Zest Pinste N, the Zest end , and the east end . the hea Nt o I Mondon is the Xit D, its Iinan Xia M and EFsiness Xent Ne . n FPe No Fs Ean Us , o IIi Xes , and Ii NPs a Ne sit Fated the Ne , in XMFdin Q the Ean U o I en QMand , the sto XU e AXhan Qe , and the o Md Eai Me D. Ie Z Seo SMe Mi Ye he Ne , EFt o Ye N a Pi MMion Seo SMe Xo Pe to the Xit D to Zo NU. the Ne a Ne so Pe Ia Po Fs an Xient EFi Mdin Qs Zithin the Xit D. Se Nha Ss the Post st Ni Uin Q o I the P is the st . Sa FM\"s Xathed Na M, the QNeatest o I en QMish Xh FNXhes . it Zas EFi Mt in the 17th Xent FND ED si N Xh Nisto She N ZNen . the to Ze N o I Mondon Zas Io Fnded ED OFMi Fs Xaesa N and in 1066 Ne EFi Mt ED Zi MMia P the Xon TFe No N. it Zas Fsed as a Io Nt Ness , a No Da M Sa Ma Xe , and a SNison . no Z it is a PFse FP.

London is the capital of Great Britain, its political, economic, and commercial centre. It is one of the largest cities in the world and the largest city in Europe. Its population is about 8 million. London is divided into several parts: the City, Westminster, the West End, and the East End. The heart of London is the City, its financial and business centre. Numerous banks, offices, and firms are situated there, including the Bank of England, the Stock Exchange, and the Old Bailey. Few people live here, but over a million people come to the City to work. There are some famous ancient buildings within the City. Perhaps the most striking of them is the St. Paul"s Cathedral, the greatest of English churches. It was built in the 17th century by Sir Christopher Wren. The Tower of London was founded by Julius Caesar and in 1066 rebuilt by William the Conqueror. It was used as a fortress, a royal palace, and a prison. Now it is a museum.

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

Шифр Рихарда Зорге

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

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

Продолжение доступно только подписчикам

Вариант 1. Оформи подписку на «Хакер», чтобы читать все материалы на сайте

Подписка позволит тебе в течение указанного срока читать ВСЕ платные материалы сайта. Мы принимаем оплату банковскими картами, электронными деньгами и переводами со счетов мобильных операторов.

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

Понятие протокола

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

Особенности протоколов:

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

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

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

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

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

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

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

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

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

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

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

Для ее решения требуется обеспечить:

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

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

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

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

Целостность — гарантированная невозможность несанкционированного изменения информации. При нарушении целостности возможно использование вставки, удаления и замены.

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

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

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

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

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

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

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

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

Пусть Х — открытый текст (ОТ ), Y — шифртекст (ШТ ). Тогда формально процессы зашифрования Е и расшифрования D можно записать в виде:

Е К1 (X ) = Y,

D K 2 (Y ) = X,

где символ Е К1 означает правило зашифрования открытого текста X на ключе к1,

D К2 — правило расшифрования шифртекста Y на ключе к2.

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

D K 2 (E K 1 (X )) = X.

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

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

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

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

Выбор криптографического алгоритма и режима его использования зависит от:

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

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

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

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

Приведем терминологию, соответствующую ГОСТ «Криптография . Термины и определения».

Зашифрование — применение к ОТ шифрпреобразования с выбранным ключом для получения ШТ.

Расшифрование — применение к ШТ обратного шифрпреобразования с известным ключом для получения открытого текста.

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

Целостность

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

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

Для проверки целостности к ОТ X добавляется проверочная комбинация S, называемая кодом аутентификации сообщения (КАС ) или имитовставкой. В этом случае по каналу связи передается пара Y = (X , S). Пользователь при получении сообщения X вычисляет значение проверочной комбинации S и сравнивает его с принятым значением. Несовпадение говорит о том, что данные изменены.

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

H K (X ) = S.

К кодам аутентификации предъявляются требования:

• невозможность вычисления H K (X ) = S для заданного сообщения X без знания ключа К (атака типа имитация);
• невозможность подбора для заданного сообщения X с известным значением H K (X ) = S другого сообщения X 1 с известным значением H K (X 1) = S 1 без знания ключа К (подмена сообщения).

Аутентификация

Аутентификация — установление подлинности, особенно остро эта проблема стоит, когда стороны не доверяют друг другу. Установление подлинности (проверка и подтверждение) — это важная часть проблемы обеспечения достоверности получаемой информации.

Применительно к сеансу связи аутентификация означает:

• проверку целостности соединения;
• невозможность повторной передачи данных.

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

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

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

• односторонней идентификации;
• взаимной идентификации.

Цифровая подпись

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

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

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

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

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

Возможны два подхода при использовании криптосистем с открытым ключом применительно к цифровой подписи.

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

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

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