Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

СОДЕРЖАНИЕ

Введение

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 требует значительного числа открытых текстов. Это отражено в следующей таблице:

Количество циклов алгоритма DES	Количество необходимых известных открытых текстов для нахождения ключа
8	2²¹
12	2³¹
16	2⁴⁷

Таблица 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) определяется, под каким номером столбцов и строк следует искать выходное значение.

Таблица 2.2.1 – Пятый S-блок DES.

В ходе анализа мы прослеживаем все возможные комбинации двоичных векторов i и j. Каждую пару векторов мы используем в качестве маски, которую накладываем на все возможные пары вход – выход блока замены. Эти маски указывают нам на биты входа и выхода соответственно, которые необходимо сложить по модулю 2, а затем сравнить полученные результаты. Результат анализа приведен в приложении в таблице (2). В этой таблице значение Q5(i,j), имеющее наибольшее отклонение от ½, помечено *. Следовательно, Q*5(I*,j*) = 12, где j = (1,1,1,1), а i = (0,1,0,0,0,0). Это говорит о том, что из всех возможных входных значений (от 0 до 63) и соответствующих им выходных значений, 12 раз встречается совпадение второго входного бита и суммы по модулю 2 всех четырех выходных битов. Из таблицы (2), приведенной в приложении, следует, что данными 12 парами являются следующие:

Получается, что (Y,j) = (X,i) ⊕ (K,i), где i=16, а j = 15, для 12 пар входвыход S5 блока из имеющихся 64. Говоря другими словами, в большинстве случаев они будут неравны между собой, а следовательно их сумма по модулю два в большинстве случаев будет равна 1. То есть по уравнению (2.1.2) получается, что в большинстве случаев Q(i,j) = 1.

Прибавив по модулю два (X,i) к правой и левой части уравнения (Y,j)=(X,i) ⊕ (K,i), получим эффективный линейный статистический аналог S5 блока:

X2 ⊕ Y1 ⊕ Y2 ⊕ Y3 ⊕ Y4 = K2, (2.2.6)

и это уравнение выполняется с вероятностью р = 3/16.

Уравнения для эффективных линейных статистических аналогов всех S блоков приведены в таблице 2.2.2. Здесь X = (x1, …, x6), Y = (y1, …, y4), K=(k1,…, k6) – входные, выходные и ключевые векторы соответственно.

Таблица 2.2.2 - Уравнения для эффективных линейных статистических аналогов всех S блоков DES.

Так как в рассматриваемом нами S5 - блоке в уравнении участвует второй бит, то легко можно посчитать, что этот бит на самом деле будет 26 битом всего входного сообщения Х. Однако, зная, что при входе в F блок, входной вектор претерпевает изменения с помощью перестановки с расширением, то, воспользовавшись приведенной ниже таблицей, легко можно определить, что на 26 позиции будет находиться на самом деле 17 входной бит таблицы 2.2.3.

Таблица 2.2.3 – Промежуточные вычисления.

Точно так же выходной вектор, прежде чем выйти из F-блока претерпевает перестановку с помощью F - блока. Поэтому выходящие из S5 блока 17, 18, 19 и 20 биты соответственно окажутся на 8, 14, 25 и 3 позиции выходного вектора таблицы (2.2.4).

Таблица 2.2.4 – Промежуточные вычисления.

Тогда полученное нами эффективное линейное статистическое уравнение примет вид:

X17 ⊕ Y3 ⊕ Y8 ⊕ Y14 ⊕ Y25 = K26, (2.2.7)

при ∆ = 5/8.

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

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

Прежде чем пояснить вышесказанное на примере, рассмотрим несколько базовых определений:

Лемма 1: если Q(1),…, Q(n) – независимые бинарные случайные величины, то

∆ (Q(1)⊕ … ⊕ Q(n)) = П ∆ (Q(i)), (2.3.1)

где i=1,…, n.

Доказательство: докажем эту лемму для двух независимых величин. Так как Q(1) и Q(2) независимы и при этом Р(Q(1)=1)=р1, Р(Q(2)=1)=р2, Р(Q(1)=0)=1– р1 и Р(Q(2)=0)=1 – р2. то Р(Q(1)⊕ Q(2) = 1) = Р(Q(1)=1)Р(Q(2)=0) + Р(Q(1)=0)Р(Q(2)=1) = р2(1 – р1) + р1(1 – р2) = р2 – р1р2 + р1 – р1р2 = р2 + р1 2р1р2. ∆ (Q(1)⊕ Q(2)) = 1 – 2р(Q(1)⊕ Q(2) =1) = 1 – 2(р2 + р1 – 2р1р2) = 1 – 2р2 – 2р1 + 4р1р2 = (1 – 2р1)( 1 – 2р2) = ∆ (Q(1)) ∆ (Q(2)).

А теперь расcмотрим n независимых величин. Пусть Q(1)⊕ Q(2) ⊕ … ⊕ Q(n-1) = Q’ и p’ = p(Q’=1), pn = p(Q(n)=1).

Тогда P(Q’ ⊕ Q(n) = 1) = p(Q’=1)p(Q(n) = 0) + p(Q’=0)p(Q(n) = 1) = p’(1-pn) + (1-p’)pn = p’ + pn – 2p’pn. ∆ (Q(1)⊕ … ⊕ Q(n)) = ∆ (Q’ ⊕ Q(n)) = 1 – 2p(Q’ ⊕ Q(n) = 1) = 1 – 2(p’ + pn – 2p’pn) = 1 – 2pn – 2p’ +4p’pn = (1 – 2p’)(1 – 2pn) = ∆ (Q’) ∆(Q(n)) = П ∆ (Q(i)).

Рисунок 2.3.1 – Схема трех раундов DES.

Замечание 1: массе называл тройной суммой S(i) для i-го раунда случайную величину вида

Q(i) = fi (X(i)) ⊕ gi (Y(i)) ⊕ hi (K(i)), (2.3.2)

где fi, gi, hi – равновероятностные булевы функции.

В определении Матсуи fi, gi, hi – линейные функции.

Определение 2: последовательные тройные суммы S(1+i) и S(i) называются вязанными, если fi+1 = gi.

Из определения следует, что Q(i) ⊕ S(1+i) = fi (X(i)) ⊕ gi (Y(i)) ⊕ hi(K(i)) ⊕ fi+1 (X(i+1)) ⊕ gi+1 (Y(i+1)) ⊕ bi+1 (K(i+1)),где Y(i) = X(i+1).

Определение 3: если Q(1),…, Q(n) – связанные тройные суммы, то тогда:

(2.3.3)

и Q1….n называется n-раундовой тройной суммой.

В случае линейных функций формула (2.3.3) дает иное соотношение:

(2.3.4)

которое выполняется с вероятностью, определяемой ∆ (Q(1)⊕ … ⊕ Q(n)) и леммой 1.

Определение 4: эффективным линейным статистическим аналогом называется линейный статистический аналог (2.3.4) из заданного множества с наибольшим ∆ .

Поясним все вышесказанное на примере. Для этого рассмотрим схему

3-раундового DES, изображенную на рисунке (2.3.1) .

Эффективными линейными статистическими аналогами 1-й и 3-й итераций являются уравнения:

(2.3.5)

каждое из которых выполняется с вероятностью 3/16.

Учитывая Х(1) = PR(3) = CL, Y( = PL ⊕ X(2), Y(3) = CR ⊕ X(2),

после сложения этих уравнений получим:

(2.3.6)

По лемме 1 ∆ = (5/8)*(5/8) = 25/64 и это уравнение выполняется с вероятностью р = (1 – ∆ )/2 = 39/128.

Найти биты ключа К(1) ⊕ К(3) можно, решая уравнение (2.3.6) с использованием алгоритма, приведенного ниже.

Алгоритм: пусть N - число всех открытых текстов и T - число открытых текстов, для которых левая часть (2.3.6) равна 0.

Если Т> N/2, то:

Успех алгоритма возрастает с ростом N и ∆ = |1 – 2p|. Вероятность успеха определяется следующей леммой.

Лемма 2: пусть N - число открытых текстов и р - вероятность выполнения линейного уравнения (2.1.2). Предположим, что ∆ = |1 — 2р| —> 0. Тогда вероятность успеха алгоритма имеет вид:

(2.3.6)

где

(2.3.7)

Числовые вычисления (2.3.7) сведены в таблице (2.3.1)

N	1/16∆ A²	I/8∆	I/4∆	I/2∆
Pусп	0,841	0,921	0,977	0.998

Таблица 2.3.1 – Числовые вычисления

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

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

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

Схема данного алгоритма представлена на рисунке (2.4.1). Входной блок представляет собой последовательность из 16 бит, которые разделяются на две части, правая из которых проходит через блок шифрования f, после чего складывается по модулю 2 с левой частью. Выходное шифрованное сообщение состоит из двух 8-битовых частей, правая часть которого представляет собой правую часть входного сообщения, а левая - результат сложения по модулю два.

Рассмотрим подробнее f блок, изображенный а рисунке (2.4.2). Входное 8-битовое сообщение проходит через блок перестановки с расширением так, что на выходе мы имеем 12 бит. Данные таблицы перестановки с расширением приведены в таблице (2.4.1). Читать таблицу следует справа налево. То есть третий бит становится в первую позицию и т. д. таким образом что самый старший бит имеет номер I, а самый младший - номер 12. После этого 12-битовый ключ и преобразованное входное сообщение складываются по модулю 2. Результат сложения разбивается на три группы по четыре бита, каждая из которых проходит соответственно блок I, блок 2 и блок З. При этом из первых двух блоков выходит по три бита, а из третьего блока - два.

Замена в первых двух блоках производится по приведенным табл. 2.4.2 и 2.4.3 по следующему принципу.

Рисунок 2.4.1 – Общая схема алгоритма шифрования.

Пусть в блок входит четыре бита: al, а2, аЗ, а4. При этом первый бит определяет номер строки (если а I = 0. то это соответствует первому- столбцу, а если а I = I - второму), а остальные три - номер столбца (ООО = первому столбцу, 111= восьмому столбцу).

Несколько иначе дело обстоит с третьим блоком. Из него в отличие от первых двух выходит не три бита, а два. Замена осуществляется согласно таблице 2.4.4. При этом, если al, а2, аЗ, а4 - входные биты блока 3, то биты al и а4 определяют номер сроки, а биты а2 и аЗ - номер столбца (аналогично S- блокам алгоритма DES).

Рисунок 2.4.2 - Алгоритм шифрования.

Линейный криптоанализ 📙 Курсовая → 🆔 116921