Министерство образования и науки РФ новосибирский государственный университет физический факультет Кафедра физико-технической информатики проблемы безопасности в информационных технологиях (курс лекций)

Скачать 4.51 Mb.

Название	Министерство образования и науки РФ новосибирский государственный университет физический факультет Кафедра физико-технической информатики проблемы безопасности в информационных технологиях (курс лекций)
страница	16/58
Дата публикации	09.07.2013
Размер	4.51 Mb.
Тип	Учебно-методическое пособие

100-bal.ru > Информатика > Учебно-методическое пособие

1 ... 12 13 14 15 16 17 18 19 ... 58

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

Если процесс шифрования описать в виде Y = E_K[X], где X – исходное сообщение, K – криптографический ключ, то процесс выявления X и/или K называется криптоанализом. Самая простая атака на алгоритм шифрования – это полный перебор всех возможных ключей (brute force, метод «грубой силы»). Если ключ имеет достаточную длину, время перебора становится нереально большим. При длине ключа n количество возможных ключей представляет число 2ⁿ, т.е. время перебора в общем случае растёт экспоненциально от длины ключа.

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

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

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

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

Понятие дифференциального криптоанализа было введено Эли Бихамом (Biham) и Ади Шамиром (Shamir) в 1990 году. Конечная задача дифференциального криптоанализа – используя свойства алгоритма, в основном свойства S-box, определить подключ раунда. Конкретный способ дифференциального криптоанализа зависит от рассматриваемого алгоритма шифрования.

Если в основе алгоритма лежит сеть Фейстеля, то можно считать, что блок m состоит из двух половин - m₀ и m₁. Дифференциальный криптоанализ рассматривает отличия, которые происходят в каждой половине при шифровании. (Для алгоритма DES «отличия» определяются с помощью операции XOR, для других алгоритмов возможен иной способ). Выбирается пара незашифрованных текстов с фиксированным отличием. Затем анализируются отличия, получившиеся после шифрования одним раундом алгоритма, и определяются вероятности различных ключей. Если для многих пар входных значений, имеющих одно и то же отличие Х, при использовании одного и того же подключа одинаковыми (Y) оказываются и отличия соответствующих выходных значений, то можно говорить, что Х влечет Y с определенной вероятностью. Если эта вероятность близка к единице, то можно считать, что подключ раунда найден с данной вероятностью. Так как раунды алгоритма независимы, вероятности определения подключа каждого раунда следует перемножать. Считается, что результат шифрования данной пары известен. Результаты дифференциального криптоанализа используются как при разработке конкретных S-box, так и при определении оптимального числа раундов.

Другим способом криптоанализа является линейный криптоанализ, который использует линейные приближения преобразований, выполняемых алгоритмом шифрования. Данный метод позволяет найти ключ, имея достаточно большое число пар (незашифрованный текст, зашифрованный текст). Рассмотрим основные принципы, на которых базируется линейный криптоанализ. Обозначим:
P[1], … , P[n] - незашифрованный блок сообщения.

C[1], … , C[n] - зашифрованный блок сообщения.

K[1], … , K[m] - ключ.

A[i, j, …, k] = A[i]

A[j]

… A[k]
Целью линейного криптоанализа является поиск линейного уравнения вида

P[α₁, α₂, …, α_a]

C[β₁, β₂, …, β_b] = K[γ₁, …, γ_c]

выполняющееся с вероятностью р

0.5. α_i, β_i и γ_i – фиксированные позиции в блоках сообщения и ключе. Чем больше р отклоняется от 0.5, тем более подходящим считается уравнение.

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

Уравнения составляются следующим образом. Вычисляются значения левой части для большого числа пар соответствующих фрагментов незашифрованного и зашифрованного блоков. Если результат оказывается равен нулю более чем в половине случаев, то полагают, что K[γ1, …, γс] = 0. Если в большинстве случаев получается 1, полагают, что K[γ1, …, γс] = 1. Таким образом получают систему уравнений, решением которой является ключ.

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

1 ... 12 13 14 15 16 17 18 19 ... 58

Похожие:

	Министерство образования республики беларусь белорусский государственный... Книга предназначена для студентов, аспирантов, научных работников. В ней рассматриваются основные положения и понятия современной...		Министерство образования и науки российской федерации томский государственный... Целью дисциплины является ознакомление студентов с базовыми понятиями следующих разделов информатики: теория информации, технические...
	Министерство образования Российской Федерации Санкт Петербургский... Задачи курса: Изучить основные математические результаты и методы, лежащие в основе метода конечных элементов и других вариационных...		Министерство образования и науки российской федерации правительство... Правила определяют основные требования технической эксплуатации железной дороги
	Министерство образования и науки российской федерации белгородский... Главного управления мчс россии по Республике Тыва и структурных подразделений по согласованию с Министерством образования и науки...		Программа по формированию навыков безопасного поведения на дорогах... Министерство образования и науки Российской Федерации новосибирский государственный университет экономики и управления – «нинх»
	Министерство образования Российской Федерации Санкт Петербургский... Определение высоковольтной проводимости и конвективного механизма тока. Знакомство с эгд-технологиями и устройствами. Особенности...		Основная образовательная программа высшего профессионального образования... «Новосибирский национальный исследовательский государственный университет» (Новосибирский государственный университет, нгу)
	Образования Российской Федерации томский государственный университет... Алгоритм построения совокупной модели пересечения трехмерных объектов, 3ds формат, dll, плагин для 3ds max		Курс лекций по истории и философии науки утверждено Редакционно-издательским... Глотова В. В. Краткий курс лекций по истории и философии науки: учеб пособие / В. В. Глотова. Воронеж: фгбоу впо «Воронежский государственный...
	Министерство образования и науки российской федерации государственное... Рабочая программа учебной дисциплины «Управление стоимостью предприятия в сфере эксплуатации недвижимости» составлена в соответствии...		Реферат по курсу медицинской энтомологии Тема: лихорадка паппатачи «Новосибирский национальный исследовательский государственный университет» (Новосибирский государственный университет, нгу)
	Реферат по курсу энтомологии студентка медф гр. 13451. 1 «Новосибирский национальный исследовательский государственный университет» (Новосибирский государственный университет, нгу)		Министерство образования и науки российской федерации фбгоу впо «Марийский... Наименование результата: монография «Лингводидактика поликультурного образования»
	Первый Московский государственный медицинский университет имени И.... Элективный курс предназначен для учащихся 9 классов общеобразовательных учреждений. Курс основан на знаниях и умениях, полученных...		Министерство образования и науки российской федерации томский государственный... Государственное общеобразовательное учреждение-средняя общеобразовательная школа

Школьные материалы