WikiSort.ru - Не сортированное

Атака на основе только шифртекста

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

Атака на основе подобранного открытого текста

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

Атака на основе адаптивно подобранного открытого текста

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

Линейный метод криптоанализа

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

${\displaystyle x_{i_{1}}+\ldots +x_{i_{r}}+y_{j_{1}}+y_{j_{s}}=z_{k_{1}}+\ldots +z_{k_{t}}}$ , (1)

которая будет наилучшей. Пусть ${\displaystyle p}$  — это вероятность того, что (1) выполняется. Понятно, что нам надо, чтобы ${\displaystyle p\approx 0.5}$ , а также чтобы величина ${\displaystyle |p-0.5|}$ была максимальна. В случае если эта величина достаточно велика и криптоаналитику известно достаточно много пар открытого и соответствующего ему шифрованного текста, то сумма по модулю 2 бит ключа на соответствующей позиции в правой части равенства (1) равна наиболее вероятному значению суммы по модулю 2 соответствующих бит в открытом и шифрованном текстах в левой части. В случае, когда ${\displaystyle p>0.5}$ , сумма в правой части (1) равна нулю, когда сумма бит в левой части равна нулю более чем в половине пар зашифрованных текстов. Сумма бит в правой части равна единице, если сумма бит в левой части равна единице более чем в половине случаев текстов. Если ${\displaystyle p<0.5}$ , то наоборот: сумма бит в правой части равна единице, если в левой части сумма бит равна нулю более чем для половины текстов. И сумма бит в правой части равна нулю, если сумма бит в левой части равна единице более чем в половине случаев. Для нахождения каждого бита ключа теперь надо решить систему линейных уравнений для соответствующих известных комбинаций этих бит. Это не представляет сложности, так как сложность данной системы выражается полиномом не более чем третьей степени от длины ключа. Количество необходимых пар открытый/шифрованный текст для вскрытия шифра оценивается формулой ${\displaystyle N=|p-1/2|2^{-2}}$ . Для вскрытия шифра DES таким методом получается, что необходимо примерно 2⁴⁷ пар открытый / зашифрованный блок.

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

Дифференциальный метод криптоанализа (ДКА) был в 1990 году предложен Э.Бихамом и А.Шамиром. Дифференциальный криптоанализ — это попытка вскрыть секретный ключ блочных шифров, которые основаны на повторном применении криптографически слабых операций шифрования r раз. При криптоанализе предполагается, что на каждом цикле шифрования используется свой подключ шифрования. ДКА может использовать как выбранные, так и известные открытые тексты. Главным условием успеха попыток вскрытия r-циклического шифра является существование дифференциалов (r-1)-го цикла, которые имеют большую вероятность. Дифференциал i-го цикла определяется как пара чисел ${\displaystyle (\alpha ,\beta )_{i},}$ таких что пара различных открытых текстов x и x* c разностью ${\displaystyle \alpha }$ может после i-го цикла дать на выходе пару y и y* с разностью ${\displaystyle \beta }$ . Вероятность i-циклового дифференциала — это условная вероятность ${\displaystyle P(\Delta y(i)=\beta |\Delta x=\alpha )}$ того, что разность y и y* после i-го цикла равна ${\displaystyle \beta }$ при условии, что изначально были x и x* с разностью ${\displaystyle \alpha }$ . Открытый текст x и подключи к¹, к², …, кⁱ считаем независимыми и случайными. Процедура ДКА r-циклического шифра с выбранными открытыми текстами может быть следующей:

1. Данный этап является этапом предвычислений. На нём мы ищем множество (r-1)-цикловых дифференциалов ${\displaystyle (\alpha _{1},\beta _{1})_{r-1},(\alpha _{2},\beta _{2})_{r-1},....(\alpha _{s},\beta _{s})_{r-1}}$ . Упорядочиваем данное множество по величине их вероятностей.
2. Данный этап требует от нас выбрать x и x*, так чтобы их разность была равна ${\displaystyle \alpha _{1}}$ , для них имеем пару шифртекстов y(r), y*(r). Считаем, что на выходе предпоследнего цикла разность равна наиболее вероятной ${\displaystyle \Delta y(r-1)=\beta _{1}}$ . Для тройки ${\displaystyle (\Delta y(r-1),y(r),y^{*}(r))}$ находим каждое возможное значение подключа k^(r). Увеличиваем счетчик появления каждого такого значения подключа к^(r).
3. На данном этапе повторяем предыдущий пункт до тех пор пока один или несколько подключей не начнут появляться чаще других. Берем данный ключ (или множество ключей) в качестве решения к^(r).
4. На данном этапе мы повторяем пункты 1-3 для (r-1)-го цикла при этом значения y(r-1) вычисляются расшифровыванием y(r) с использованием ключа к^(r), найденного в предыдущем пункте. И повторяем данные действия пока не найдем ключи всех циклов.

Данный метод был изначально предложен для решения одного шифра, но затем он показал успехи в криптоанализе многих марковских шифров. Шифр называется марковским, если у него уравнение на одном цикле удовлетворяет условию, что вероятность дифференциала не зависит от выбора открытых текстов. Тогда если ключи циклов независимы, то последовательность разностей каждого цикла образует марковскую цепь, в которой каждый последующий элемент зависит только от предыдущего. Примерами марковских шифров являются DES и FEAL. Покажем, что марковский r-цикличный шифр с независимыми подключами является уязвимым для ДКА тогда и только тогда, когда для одного цикла ключ легко вычисляется по известной тройке ${\displaystyle (y,y^{*},\Delta x)}$ . Также существует (r-1) дифференциал ${\displaystyle (\alpha ,\beta )_{r-1}}$ , причем его вероятность удовлетворяет выражению ${\displaystyle P(\Delta y(r-1)=\beta |\Delta x=\alpha )\gg 2^{-n},}$ где n — количество бит в блоке шифруемого текста. Сложность нахождения ключа r-цикличного шифра Q(r) определяется как число используемых шифрований с последующим нахождением ключа: ${\displaystyle Q(r)\geqslant 2/(P_{\mathrm {max} }-1/(2^{n}-1)),}$ где ${\displaystyle P_{\mathrm {max} }=\operatorname {max} (\alpha )\operatorname {max} (\beta )(P(\Delta y(r-1)=\beta |\Delta x=\alpha )).}$ В частности, в случае если ${\displaystyle P_{\mathrm {max} }\approx 1/(2^{n}-1)}$ , то такая атака не будет успешной. Так как операция нахождения подключа более трудоемкая чем операция шифрования, то единицей измерения сложности является сложность нахождения возможных подключей для одного цикла по известным тройкам ${\displaystyle (\Delta y(r-1),y(r),y^{*}(r)).}$ Отличительной чертой дифференциального криптоанализа является то, что он почти не использует алгебраических свойств шифра (таких как линейность, замкнутость, аффинность и прочие.) Он основан только на неравномерности распределения вероятностей дифференциалов.