Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Общие сведения о дифференциальном криптоанализе




Понятие дифференциального криптоанализа впервые было введено в 1990 году Эли Бихамом и Ади Шамиром. Используя этот метод, Бихам и Шамир нашли способ атаки алгоритма DES с использованием подобранного открытого текста, который оказался эффективнее атаки «в лоб».

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

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

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

Схема блочного шифратора

 
 

Рисунок 6.1

 

где K = (K(1), K(2), …, K(r)) получается по некоторой схеме из К0, или независимо и равновероятно выбирается для каждого цикла. Пусть Х(1) и Х’(1) – пара открытых текстов. Рассмотрим следующие разности:

DХ(1) = Х(1) – Х’(1);

DY(i) = Y(i) – Y’(i).

Задача дифференциального криптоанализа заключается в том, чтобы найти такие DХ(1), что при случайном равновероятном выборе Х(1), К(1), К(2), …, К(r-1) с вероятностью более 1/(2N) появится DY(r-1).

Назовем пару (a, b) возможных значений вектора (DХ(1), DY(i)) называется дифференциалом I-го цикла.

Тогда дифференциальный анализ описывается следующей моделью (рис. 6.2).

 

Модель дифференциального криптоанализа

Рисунок 6.2

 

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

1. Выбираем дифференциал (r-1) – го цикла (a, b), для которого вероятность Р(DХ(1) = a, DY(r-1) = b) большая.

2. Случайно выбираем Х(1) и подбираем Х’(1) так, чтобы DХ(1) = a. Пусть известны Y(r) и Y’(r).

3. Делаем предположение, что DY(r-1) = b и, зная Y(r) и Y’(r), находим К(r).

4. Повторяем 2 и 3 пока один подключ не начнет появляться чаще других.

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

Метод «встреча посередине»

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

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

Метод «разделяй и побеждай»

Метод анализа «разделяй и побеждай» основан на том, что множество ключей К допускает представление K = K1xK2. То есть каждый ключ kÎK может быть записан в виде вектора k = (k1, k2), где k1ÎK1 и k2ÎK2.

Также обязательным условием является существование некоторого критерия h, позволяющего при известных открытом и закрытом текстах проверять правильность первого подключа k1 в ключе k = (k1, k2).

Метод «разделяй и побеждай» предлагает опробовать сначала элементы множества K1, отбраковывая варианты k1 по критерию h. Отсюда мы определим k1 – первую компоненту вектора k = (k1, k2). Затем, используя найденное значение k1 и известный шифртекст, опробуем варианты k2. Трудоемкость определения компоненты k1 равна в среднем операций опробования, соответственно трудоемкость определения k2 равна в среднем операций опробования. Тогда в среднем трудоемкость метода равна против при методе полного перебора.

Основная проблема при применении метода «разделяй и побеждай» состоит в нахождении критерия h, который зависит от конкретного преобразования T или вообще может не существовать. Иногда критерий h может описываться вероятностно-статистической моделью.

 


Поделиться:

Дата добавления: 2015-04-18; просмотров: 64; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты