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

СОДЕРЖАНИЕ 
 

Введение 

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

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

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

2.2  Нахождение  статических аналогов для первого цикла алгоритма DES

2.3 Нахождение  статических аналогов для трех  циклов алгоритма DES

2.4 Пример применения  линейного криптоанализа к раскрытию ключа 

Заключение 

Список использованной литературы 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ 
 

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

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

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

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

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

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

     Смысл алгоритма состоит в получении соотношений (линейных уравнений) в виде:

      (1.1)

     где P_n, C_n, K_n - n-ые биты текста, шифротекста и ключа. 

     Данные  соотношения называются линейными  аппроксимациями. Для произвольно выбранных бит открытого текста, шифротекста и ключа вероятность справедливости такого соотношения P примерно равна 1/2. Такими соотношениями, вероятность которых заметно отличается от 1/2 можно пользоваться для вскрытия алгоритма.

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

     В блочных шифрах анализ преимущественно  концентрируется на S-блоках, так как они являются нелинейной частью шифра. Наиболее эффективное однораундовое соотношение для алгоритма DES использует свойство таблицы S5. Второй входной бит таблицы равен результату операции XOR над всеми выходными битами с вероятностью 3/16 (смещение в 5/16 относительно 1/2). А для полнораундового DES известно соотношение, выполняющееся с вероятностью 1/2 + 2⁻²⁴.

     Линейный  криптоанализ имеет одно очень полезное свойство — при определённых условиях можно свести основное соотношение к уравнению вида:

                     (1.2)

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

     Хотя аппроксимацию с наибольшим отклонением от 1/2 найти не сложно, возникает ряд проблем при экстраполировании метода на полнораундовый шифр. Первая затрагивает вычисление вероятности линейной аппроксимации. В принципе, это потребовало бы от криптоаналитика просмотреть все возможные комбинации открытых текстов и ключей, что невыполнимо. Решение этой проблемы — сделать ряд предположений и приблизить вероятность, используя лемму о набегании знаков (piling-up lemma). При использовании этой леммы линейная аппроксимация представляется в виде цепочки аппроксимаций, причём каждая из них охватывает лишь небольшую часть шифра. Такая цепочка называется линейной характеристикой. Вероятность нахождения комбинации:

                                         (1.3)

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

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

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

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

 

     Таблица 2.1 – Требуемое количество открытых текстов для нахождения ключа в зависимости от количества циклов алгоритма DES. 
 
 
 
 
 
 
 
 
 
 
 

     2.1 ОСНОВНЫЕ ИДЕИ ЛИНЕЙНОГО КРИПТОАНАЛИЗА  DES 
 

     Линейный  криптоанализ основывается на том, что  существует возможность заменить нелинейную функцию ее линейным аналогом. Так как все зашифровываемые тексты представлены в двоичном виде, то будем рассматривать случайную величину Q - {0,1}, для которой P(Q=I) = р, соответственно P(Q=0) = 1-р, а  ∆(Q) = |1-2р|.

     

     Рисунок 2.1.1 – Схема произвольного блочного шифра. 

     Рассмотрим  схему произвольного блочного шифра  в i-м цикле, изображенную на рисунке (2.1.1): здесь E - функция шифрования. X(i) - блок открытого текста в i-м цикле, Y(i) - блок шифртекста, K(i) - подключ, используемый в i-м цикле. Y(i), X(i) принадлежит V_n, K(i) принадлежит V_m, где n - размер блока, m - размер подключа.

Y(i) = E(X(i),K(i)).                                        (2.1.1)

     Обозначим через (Х, а) = X₁a₁ ... X_na_n = X_1L ... X_iK = X[i₁...,i_k] - скалярное произведение двух двоичных векторов X и а, где (а_1L,..., а_1K)- единнчные координаты вектора а, а по сути дела сложение по модулю 2 битов вектора X, соответствующих ненулевым битам вектора а.

     Определение 1: линейным статистическим аналогом нелинейной функции (2.1.1) будем называть случайную величину:

                   (2.1.2)

если  вероятность P(Q(i) = 1) = р ≠ 1/2 для случайно выбранного открытого текста X(i).

     Отклонение  A(Q(i)) = |1-2р| определяет эффективность линейного статистического аналога (2.1.2).

     Для применения линейного криптоанализа  необходимо решить следующие задачи:

1. нахождение эффективного статистического линейного аналога и вычисление его вероятности;

2. определение ключа (или некоторых бит ключа) с использованием эффективного линейного статистического аналога. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.2 Нахождение статических аналогов для первого цикла алгоритма DES. 

     Наиболее  эффективным является рассмотрение блока F алгоритма DES, а именно находящиеся в нем S-блоки, так как именно в этом случае можно явно проследить зависимость выходных битов от входных в их всевозможных комбинациях. Один цикл DES преобразования изображен на рисунке (2.2.1).

     

     Рисунок 2.2.1 - Цикл DES преобразования.

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

Y = Fa(X ⊕ K), a = 1,…,8,                                 (2.2.1)

      где Y  ∈  V4, X,K  ∈  V6.

     Линейным  статистическим  аналогом  каждого  из  всевозможных  уравнений (2.2.1) будет являться уравнение вида:

(Y,j) = (X’,i),                                                 (2.2.2)

где X’ = X ⊕ K, 1 ≤ i  ≤ 63, 1 ≤  j  ≤ 15.

     Обозначим через Qa(i, j), a = 1,…,8; i = 1,…63; j = 1,…15; число ненулевых X  ∈  V6 для а -го S блока DES таких, что для i и j выполняется равенство (4). В этом случае значение Q_a(i, j) будет определять количество совпадений суммы по модулю 2 некоторых битов входных данных с суммой по модулю 2 некоторых битов выходных данных. Так как сумма по модулю 2 двух одинаковых бит (1 и 1 или 0 и 0) в результате дает 0, то Q_a(i, j) и будет по сути дела  указывать,  сколько раз из  возможных 64  комбинаций  выполняется формула (2)  с результатом 0. Так как всего 64  возможных комбинации,  то при Q_a(i, j)=32 будем иметь Р = (Q = 0) = 32/64 = 1/2, а Р(Q = 1) = 1 – ½ = ½. Поэтому когда Q_a ≠ 32,  можно сказать, что есть статистическая связь между входными  и выходными битами  а -го S блока.  При этом  чем больше  будет отклонение значения вероятности для каждой пары (i, j), тем более эффективным будет линейный аналог.

      Пусть:

Q*_a(i*, j*): | Q*_a(i*, j*) – 32| = max| Q_a(i, j) – 32|                    (2.2.3)

где 1  ≤ i  ≤ 63; 1  ≤ j  ≤ 15.

      Тогда уравнение:

(X,i*)  ⊕  (Y,j*) = (К, i*)                                     (2.2.4)

является  эффективным линейным статистическим аналогом для  а -го S блока в классе всех линейных статистических аналогов вида (2.2.2) с вероятностью:

Ра = Q*a(i*, j*)/64, а = 1,…,8.                                 (2.2.5)

     Анализ  всех восьми S-блоков показал, что наибольшее отклонение от ½ находится в S5 блоке. Чтобы все вышесказанное стало более понятным, проанализируем S5 блок алгоритма DES.

     Шестибитовым  входам в S5 - блок однозначно соответствуют  четырехбитовые выходы. Их значения можно  определить с помощью известной таблицы замены, которая представляет собой таблицу из четырех строк и шестнадцати столбцов. По шести входным битам S блока, изображенного на таблице (2.2.1) определяется, под каким  номером  столбцов  и  строк  следует  искать  выходное  значение.