Анализ алгоритмов шифрования в сетях передачи данных

 

МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ -

УЧЕБНО-НАУЧНО-ПРОИЗВОДСТВЕННЫЙ КОМПЛЕКС»

Кафедра «Электроника, вычислительная техника

и информационная безопасность»

КУРСОВАЯ РАБОТА

по дисциплине «Информационная безопасность и защита информации»

на тему: «Анализ алгоритмов шифрования в сетях передачи данных»

Студент Богатырев П. Ю. Шифр 091122

Учебно-научно-исследовательский

институт информационных технологий

Специальность 230201 «Информационные системы и технологии»

Группа 31-ИТ

Руководитель Фисун А.П.

Орел 2012

Содержание

Введение

Криптоанализ в контексте криптологии

.1 Терминология криптологии

.2 Криптографическая защита, как элемент систем обеспечения безопасности информации

.3 Исторические шифры и их взлом

.4 Особенности современной криптологии

.5 Современная криптография

.6 Современный криптоанализ

Основные методы современного криптоанализа

.1 Метод грубой силы

.2 Атаки класса «встреча посередине»

.3 Дифференциальный криптоанализ

.4 Линейный криптоанализ

.5 Временной криптоанализ

.6 Решеточный криптоанализ

Заключение

Литература

Введение

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

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

-Определиться с используемой в криптологии терминологией;

-Рассмотреть место криптографических методов защиты в общей системе обеспечения безопасности информации;

-Изучить простые (докомпьютерные) шифры и методы их взлома;

-Выделить особенности современной криптолографии

-Охарактеризовать современный криптоанализ

-Рассмотреть современные методы криптоанализа;

Основным методом выполнения поставленных задач является анализ литературы и электронных ресурсов по данной тематике. Наиболее полное собрание электронных ресурсов по теме собрано по адресу #"justify">1 Криптоанализ в контексте криптологии

.1 Терминология криптологии

В данной курсовой будет использоваться система терминов, приведенная в [1].

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

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

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

Шифрование - процесс зашифрования или расшифрвания.

Криптосистема состоит из пространства ключей, пространства открытых текстов, пространства шифротекстов и алгоритмов зашифрования и расшифрования.

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

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

Стойкость криптоалгоритма - способность шифра противостоять всевозможным попыткам его раскрытия, т.е. атакам на него.

1.2 Криптографическая защита, как элемент систем обеспечения безопасности информации

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

-"классическая задача криптографии" - защита данных от разглашения и искажения при передаче по открытому каналу связи;

-"подпись электронного документа" - защита от отказа от авторства сообщения;

-"вручение заказного письма" - защита от отказа от факта получения сообщения.

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

.3 Исторические шифры и их взлом

Идея шифрования текста зародилась достаточно давно. Есть сведения о наличии шифрованных документов в Древней Индии, Древнем Египте, Древней Греции. Как правило, в древние времена использовались так называемые шифры замены и шифры перестановки. [4]

Наиболее известный шифр древности - шифр Цезаря, описанный историком Древнего Рима Светонием. Гай Юлий Цезарь использовал в своей переписке шифр собственного изобретения. Применительно к современному русскому языку он состоял в следующем. Выписывался алфавит: А, Б, В, Г, Д, Е,...,; затем под ним выписывался тот же алфавит, но со сдвигом на 3 буквы влево (см. рисунок 1) [4].

АБВГДЕЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЬЪЭЮЯГДЕЕЖ3ИИКЛМНОПРСТУФХЦЧШЩЫЬЪЭЮЯАБВРисунок 1 - таблица замены в шифре Цезаря применительно к русскому языку

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

Одним из первых приборов, реализующих шифр перестановки, является так называемый прибор СЦИТАЛЛА. Он был изобретен в древней "варварской" Спарте во времена Ликурга; Рим быстро воспользовался этим прибором. Для зашифрования текста использовался цилиндр заранее обусловленного диаметра. На цилиндр наматывался тонкий ремень из пергамента, и текст выписывался построчно по образующей цилиндра (вдоль его оси). Затем ремень сматывался и отправлялся - получателю сообщения. Последний наматывал его на цилиндр того же диаметра и читал текст по оси цилиндра. В этом примере ключом такого шифра являлся диаметр цилиндра и его длина, которые, по существу, порождают двухстрочную запись, указанную выше. [4]

Интересно, что изобретение дешифровального устройства "АНТИСЦИТАЛЛА" приписывается великому Аристотелю. Он предложил для этого использовать конусообразное "копье", на которое наматывался перехваченный ремень, который передвигался по оси до того положения, пока не появлялся осмысленный текст. [4]

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

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

.4 Особенности современной криптологии

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

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

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

.5 Современная криптография

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

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

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

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

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

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

Стоит отметить, что существует симметричный алгоритм шифрования, который доказано является абсолютно стойким. В прикладной криптографии шифр носит название «Одноразовый блокнот» [7]. Этот алгоритм был предложен Шенноном в его статье «Теория связи в секретных системах» [6]. Суть алгоритма в простом наложении ключа сложением по модулю 2. Однако должно выполняться 3 ограничения:

Длина ключа должна быт не меньше длины сообщения;

Ключ должен представлять случайную последовательность (ни один статистический тест не должен выявлять в нем закономерности [1]);

Ключ должен использоваться один единственный раз.

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

.6 Современный криптоанализ

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

В зависимости от данных, которые криптоаналитик может «добыть» у шифратора, существуют следующие виды атак [8]:

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

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

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

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

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

Стоит отметить, что современные шифры достаточно стойки, и их криптоанализ зачастую носит чисто теоретический характер. Так, наилучшее вскрытие полного 16-раундового DES методом дифференциального криптоанализа требует 247 выбранных открытых текстов [9]. Очевидно, что такая атака трудноосуществима на практике. Тем не менее, производительность вычислительных средств постоянно растет, и не исключено, что в ближайшем будущем будут разработаны квантовые компьютеры или ЭВМ основанные на электромагнитных световых волнах. Поэтому, криптоанализ ставит задачу сделать как можно больший «запас» прочности для алгоритмов. В криптологии существует даже такой термин, как «запас криптостойкости» (security margin) [8]. Суть его в следующем. В процессе взлома шифра, криптоаналитик может использовать неполный алгоритм (например, с уменьшенным числом раундов, или с небольшими изменениями в структуре раунда). Если вскрытие произошло удачно, то разница между раскрытым алгоритмом и полным и обозначается вышеуказанным термином.

2 Основные методы современного криптоанализа

.1 Метод грубой силы

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

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

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

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

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

Неправильная реализация алгоритмов на практике часто упрощает вскрытие грубой силой. Например, в ОС Windows XP для хранения паролей использует LM-хеширование, которое преобразует все символы пароля в верхний регистр, и обрезает значимую длину до 8 символов. Это существенно сокращает ключевое пространство, и на данный момент вскрытие пароля в данной ОС не представляет никакой сложности.

.2 Атаки класса «встреча посередине»

шифрование криптография криптоанализ

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

Рисунок 2 - Иллюстрация метода «встреча по середине» для Double DES

Крупные государства могут иметь вычислительные средства, для взлома DES методом грубой силы (размер ключа в DES 56 значащих бит). В таком случае взлом Double DES методом встречи посередине всего в 2 раза сложнее, чем полный перебор ключей обычного DES, что несравнимо меньше 2112 возможных вариантов «двойного» ключа [10].

.3 Дифференциальный криптоанализ

Как видно из названия, данный метод связан с вычислением разности. Действительно, в данном случае берутся две пары открытый]шифрованный текст, вводиться некоторая функция разности между двумя текстами, и производиться наблюдение, как значение этой функции меняется после шифрования. Операции перестановки и XOR (в том числе с ключом), практически не влияют на разность (ее легко вычислить), поэтому изменение разности в основном характеризует работу S-блоков. Проанализировав статистическими методами возможные значения S-блоков, можно сделать некоторые предположения о ключе. [11]

Данный метод подробно описан в [16]. Основная процедура ДКА r- циклического шифра с использованием выбранных открытых текстов может быть следующей:

. На этапе предвычислений ищем множество (r-1)-цикловых дифференциалов (a 1,b 1)r-1 , (a 2,b 2)r-1 ,.... (a s,b s)r-1 . Упорядочиваем это множество дифференциалов по величине их вероятности.

. Выбираем открытый текст x произвольным образом и вычисляем x* так, чтобы разность между x и x* была равна a 1. Тексты x и x* шифруется на подлинном ключе и после r циклов получаем пару шифртекстов y(r) , y*(r). Предполагаем, что на выходе предпоследнего (r-1)-ого цикла разность шифртекстов равна наиболее вероятной: D y(r-1)=b 1. Для тройки (D y(r-1), y(r) , y*(r)) находим каждое возможное (если их несколько) значение подключа последнего цикла к(r). Добавляем его к количеству появлений каждого такого значения подключа к(r).

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

. Повторяем пп.1-3 для предпоследнего цикла, при этом значения y(r-1) вычисляются расшифрованием шифртекстов на найденном подключе последнего цикла к(r). Далее действуем аналогично, пока не будут раскрыты ключи всех циклов шифрования.

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

Можно показать, что марковский r-цикловый шифр с независимыми подключами является уязвимым для ДКА тогда и только тогда, когда для одного цикла шифрования ключ по известной тройке (y,y*,D x) может быть легко вычислен, и существует (r-1)-цикловый дифференциал (a ,b )к-1 такой, что его вероятность удовлетворяет условию(D y(r-1)=b | D x=a )>>2-n ,

где n-количество бит в блоке шифруемого текста.

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

Q(r)і 2/ (Pmax - 1/(2n-1)),

где Pmax=max(a )max(b )(P(D y(r-1)=b | D x=a )).

В частности, если Pmax » 1/(2n-1), то атака не будет успешной. Поскольку вычисление подключа - более трудоемкая операция, чем шифрование, то единицей измерения сложности является сложность нахождения возможных подключей одного цикла по известным (D y(r-1),y(r),y*(r)).

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

.4 Линейный криптоанализ

Линейный криптоанализ изобрел японский криптолог Мицуру Мацуи (Mitsuru Matsui). Предложенный им в 1993 г. метод изначально был направлен на вскрытие алгоритма DES. Впоследствии линейный криптоанализ был распространен и на другие алгоритмы. [12]

Смысл линейного криптоанализа состоит в нахождении соотношений следующего вида: [12]

Pi1 Å Pi2 Å … Å Pia Å Cj1 Å Cj2 Å … Å Cjb = Kk1 Å Kk2 Å … Å Kkc

где Pn, Cn и Kn - n-е биты открытого текста, шифртекста и ключа соответственно.

Для произвольно выбранных бит открытого текста, шифртекста и ключа вероятность P справедливости такого соотношения составляет около ½. В том случае, если криптоаналитику удается найти такие биты, при которых вероятность P заметно отличается от ½, данным соотношением можно воспользоваться для вскрытия алгоритма. [12]

Для раскрытия ключа шифра DES этим методом необходимо 247 пар известных открытых и зашифрованных текстов. [16]

.5 Временной криптоанализ

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

Общая схема атаки описана в [17]. Атаку можно трактовать как проблему распознавания сигналов. "Сигнал" состоит из вариаций измерения времени для известных бит, "шум" - из погрешностей измерения времени и вариаций измерения времени для неизвестных бит. Свойства "сигнала" и "шума" определяют количество замеров времени, требуемых для атаки. Пусть получено j сообщений y0, y1, ., yj-1 и им соответствующие измерения времени T0, T1, ., Tj-1. Вероятность, что предположение xb для первых b бит правильно, пропорциональна,

где t(yi,xb) - время, требуемое для первых b итераций цикла вычсиления yix mod n с использованием бит xb,- ожидаемая фунция распределения вероятности T-t(y,xb) по всем значениям y и правильному xb. Т.к. F определена как распределение вероятностиTi-t(yi,xb), если xb правильно, то это - лучшая функция для предсказания Ti-t(yi,xb). Обратите внимание, что измерения времени и промежуточные значения s могут использоваться для улучшения оценки F.

При правильном предположении для xb-1 имеются два возможных значения для xb. Вероятность того, что xb - является правильным, а xb' - неправильным, может быть найдена как

2.6 Решеточный криптоанализ

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

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

xi = Fi(y1, ..., yn, z1, ..., zN). (1)

где yi

разряды шифрограммы, zj

разряды ключа. Булевы функции

Fi не имеют аналитической записи (она очень сложна), но значения их могут быть вычислены для произвольного набора аргументов. Если открытые и зашифрованные тексты известны в достаточном количестве, равном O(N), то система уравнений (1) имеет единственное решение, которое и является ключом. При этом достаточно знать только отдельные разряды некоторых блоков открытого текста. Запишем для этого случая систему уравнений (1) в виде

fi(z1, ..., zN) = ai (2)

Поскольку система (2) имеет единственное решение, оно может быть записано в виде булевой формулы, содержащей единственную конъюнкцию:

(3)

Символ z c тильдой означает вхождение переменной с инверсией или без инверсии.

С другой стороны, (2) может быть записана в виде следующей конъюнкции булевых формул:

(4)

Если xi = 1, то Fi входит без инверсии, в противном случае Fi входит с инверсией. Поскольку левые части выражений (3) и (4) равны 1 на одном и том же наборе аргументов, они представляют одну и ту же булеву функцию, которую назовем целевой, при этом (4) дает способ вычисления целевой функции для произвольного ключа.

Подход подтвержден экспериментально. Для ГОСТ 28147-89 найден обширный класс потенциально слабых ключей, которые, возможно, допускают вскрытие c низкой сложностью. При этом требуется всего четыре блока подобранных открытых текстов. [15]

Заключение

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

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

Литература

1 М. А. Асосков и др. Поточные шифры / Асосков А.В., Иванов М.А., Мирский А.А., Рузин А.В., Сланин А.В., Тютвин А.Н. - М.: Кудиц-образ, 1983.

Ю.Е. Пудовченко, Пределы роста [Электронный ресурс]/Ю. Е. Пудовченко, режим доступа: http://ssl.stu.neva.ru/psw/crypto.html

П. Семьянов Почему криптосистемы ненадежны? [Электронный ресурс]/П. Семьянов, - режим доступа: http://ssl.stu.neva.ru/psw/publications/crypto.html

А. Винокуров, Задачи решаемые криптографическими методами [Электронный ресурс] / А. Винокуров, - режим доступа: http://www.enlight.ru/ib/tech/crypto/part2.htm

5 А.В. Лунин, А.А. Сальников, Перспективы развития и использования асимметричных алгоритмов в криптографии [Электронный ресурс]/А.В. Лунин, А.А. Сальников, - режим доступа: http://ssl.stu.neva.ru/psw/crypto/Lunin24.html

Клод Шеннон, Работы по теории информации и кибернетике / К. Шенон, - М., ИЛ, 1963, с. 333-369 (Перевод В.Ф.Писаренко).

Брюс Шнайер, Ханаанский бальзам [Электронный ресурс] / Б. Шнайер, - режим доступа: http://www.password-crackers.ru/articles/30/#_ftn1.

С.П. Панасенко, Современные методы вскрытия алгоритмов шифрования, часть 1 [Электронный ресурс] / С.П. Панасенко - режим доступа: http://old.cio-world.ru/it-market/community/291719/page2.html

Брюс Шнайер, Прикладная криптография: Протоколы, алгоритмы, исходные тексты на языке Си [ Б. Шнайер, - Триумф, 2002 - 816 с.

10 С.П. Панасенко, Современные методы вскрытия алгоритмов шифрования, часть 2 [Электронный ресурс] / С.П. Панасенко - режим доступа: <http://old.cio-world.ru/weekly/293694>/

С.П. Панасенко, Современные методы вскрытия алгоритмов шифрования, часть 3 [Электронный ресурс] / С.П. Панасенко - режим доступа: http://old.cio-world.ru/weekly/295841/page2.html

С.П. Панасенко, Современные методы вскрытия алгоритмов шифрования, часть 4 [Электронный ресурс] / С.П. Панасенко - режим доступа: http://old.cio-world.ru/weekly/298888/page2.html

Пауль Кочер, Временной анализ реализаций Диффи-Хеллмана, RSA, DSS и других систем [Электронный ресурс] / П. Кочер, - режим доступа: http://ssl.stu.neva.ru/psw/crypto/timing.html

А. Г. Ростовцев, Решеточный криптоанализ [Электронный ресурс] / А. Г. Ростовцев, - режим доступа: http://ssl.stu.neva.ru/psw/crypto/rostovtsev/resh_analysis.pdf

Ростовцев А. Г., Маховенко Е. Б., Два подхода к анализу блочных шифров [Электронный ресурс] / Ростовцев А. Г., Маховенко Е. Б., - режим доступа: http://ssl.stu.neva.ru/psw/crypto/rostovtsev/dva_podhoda.pdf

А.Г. Ростовцев, Н.В. Михайлова Методы криптоанализа классических шифров [Электронный ресурс] / А.Г. Ростовцев, Н.В. Михайлова, - режим доступа: http://ssl.stu.neva.ru/psw/crypto/rostovtsev/cryptoanalysis.html

П. Кочер, Временной анализ реализаций Диффи-Хеллмана, RSA, DSS и других систем [Электронный ресурс] / П. Кочер, - режим доступа: http://ssl.stu.neva.ru/psw/crypto/timing.html

МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ГОСУДАРСТВЕННЫЙ УНИВЕРС

Больше работ по теме: