Лекция
Привет, Вы узнаете о том , что такое линейный метод криптоанализа, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое линейный метод криптоанализа , настоятельно рекомендую прочитать все из категории Криптоанализ, Виды уязвимости и защита Информации .
В открытой печати линейной метод криптоанализа впервые был предложен японским математиком Мацуи. Метод предполагает, что криптоаналитик знает открытые и соответствующие зашифрованные тексты.
Обычно при шифровании используется сложение по модулю 2 текста с ключом и операции рассеивания и перемешивания. Задача криптоаналитика - найти наилучшую линейную аппроксимацию (после всех циклов шифрования ) выражения
xi1+ .... + xir + yj1 + yjs=zk1 + .... + zk t (3.1)
Пусть pL - вероятность того, что (3.1) выполняется, при этом необходимо, чтобы pL - 1/2 и величина | pL-1/2 | должна быть максимальна.
Если | pL-1/2 | достаточно велика и криптоаналитику известно достаточное число пар открытых и соответствующих зашифрованных текстов, то
сумма по модулю 2 бит ключа на соответствующей позиции в правой части (3.1) равна наиболее вероятному значению суммы по модулю 2
соответствующих бит открытых и зашифрованных текстов в левой части. Если pL > 1/2, то сумма бит ключа в правой части (3.1) равна нулю, если сумма бит в левой части равна нулю больше, чем для половины пар зашифрованных текстов, и сумма бит ключа в правой части (3.1) равна единице, если сумма бит в левой части равна единице больше, чем для половины текстов . Если pL< 1/2 , то наоборот : сумма бит ключа в правой части (3.1) равна нулю , если сумма бит в левой части равна единице больше , чем для половины пар открытых и зашифрованных текстов, и сумма бит ключа в правой части (3.1) равна единице, если сумма бит в левой части равна нулю больше, чем для половины текстов. Для нахождени каждого бита собственно ключа теперь нужно решить систему линейных уравнений для известных линейных комбинаций этих бит, но эта процедура не представляет сложности, так как сложность решения системы линейных уравнений описываетс полиномом не более третьей степени от длины ключа.
Требуемое для раскрытия ключа количество N пар открытых и зашифрованных текстов (блоков) оценивается выражением
N е | pL-1/2 | -2 .
Для раскрытия ключа шифра DES этим методом необходимо 247 пар известных открытых и зашифрованных текстов.
Метод линейного криптоанализа впервые был предложен в начале 90-х гг. XX в. японским ученым М. Матсуи (Matsui). В своей работе [18] он показал, как можно осуществить атаку на алгоритм шифрования DES, сократив сложность анализа до 247.
Существенным недостатком метода стала необходимость иметь в наличии большой объем данных, зашифрованных на одном и том же секретном ключе, что делало метод малопригодным для практического применения к вскрытию шифра. Однако, если предположить, что к аналитику в руки попал шифрованный текст, содержащий важные сведения, а также некий черный ящик (устройство или программа), который позволяет выполнить любое число текстов, зашифрованных с помощью известного алгоритма шифрования на секретном ключе, не раскрывая при этом самого ключа, то применение метода линейного криптоанализа становится вполне реальным. Многие алгоритмы шифрования, известные на момент опубликования работы [18], впоследствии были проверены на устойчивость к этому методу и не все из них оказались достаточно стойкими и, как следствие, потребовали доработки.
Знание механизмов работы метода линейного криптоанализа позволяет криптографам еще на этапе проектирования крптоалгоритмов обеспечить стойкость шифров. Об этом говорит сайт https://intellect.icu . Вот почему так важно уметь применять известные методы криптоанализа на практике.
Итак, рассмотрим основные понятия, связанные с методом линейного криптоанализа. Любой алгоритм шифрования в самом общем виде можно представить как некоторую функцию Е, зависящую от входного сообщения X, секретного ключа К и возвращающую шифрованное сообщение Y:
Зная само преобразование Е и входное сообщение X, нельзя однозначно сказать, каким будет выходное сообщение Y. В данном случае нелинейность функции (13) зависит от внутренних механизмов преобразования Е и секретного ключа К. М. Матсуи показал, что существует возможность представить функцию шифрования (13) в виде системы уравнений, которые выполняются с некоторой вероятностью р. При этом для успешного проведения анализа вероятность уравнений р должна быть как можно дальше удалена от значения 0,5 (т. е. приближаться либо к нулю либо к единице). Так как уравнения, получаемые в ходе анализа криптоалгоритма, являются вероятностными, их стали называть линейными статистическими аналогами.
Определение. Линейным статистическим аналогом нелинейной функции шифрования (13) называется величина Q, равная сумме по модулю 2 скалярных произведений входного вектора X, выходного вектора Y и вектора секретного ключа К соответственно с двоичными векторами а, р и у, имеющими хотя бы одну координату, равную единице:
в том случае, если вероятность того, что Q=0 отлична от 0,5 (P(Q=0)#),5).
В отличие от дифференциального криптоанализа, в котором большое значение вероятности гарантирует успех атаки, в линейном криптоанализе успех анализа может быть обеспечен как уравнениями с очень большой вероятностью, так и уравнениями с очень маленькой вероятностью. Для того чтобы понять, какое из возможных уравнений лучше всего использовать для анализа, используют понятие отклонения.
Определение. Отклонением линейного статистического аналога называют величину ту = 11 — 2р|, где р - вероятность, с которой выполняется линейный аналог.
Отклонение определяет эффективность линейного статистического аналога. Чем отклонение больше, тем выше вероятность успешного проведения анализа. Фактически отклонение показывает, насколько вероятность статистического аналога отдалена от значения р = 0,5.
Для успешного применения метода линейного криптоанализа необходимо решить следующие задачи:
Первый шаг анализа заключается в нахождении эффективных статистических аналогов. Для алгоритмов шифрования, в которых все блоки заранее известны, этот шаг можно выполнить единожды, основываясь на анализе линейных свойств всех криптографических элементов шифра. В результате анализа должна быть получена система уравнений, выполняющихся с некоторыми вероятностями. Левая часть уравнений должна содержать в себе сумму битов входного и выходного сообщения, правая часть уравнения - биты секретного ключа. Система уравнений должна быть определенной, т. е. содержать все биты исходного секретного ключа. Данный этап не является вычислительно сложным, однако требует больших знаний, логики работы и внимательности. Он может быть автоматизирован. Однако при этом необходимо помнить, что для каждого определенного алгоритма шифрования система линейных аналогов строится всего один раз и в дальнейшем может быть использована для нахождения разных секретных ключей шифрования, которые используются для шифрования данных с помощью анализируемого шифра.
Если первый шаг анализа является чисто теоретическим и полностью зависит от структуры алгоритма, то второй шаг является исключительно практической частью, которая заключается в анализе известных пар открытый - закрытый текст с помощью полученной ранее системы статистических аналогов. Для этого используется следующий алгоритм.
Алгоритм. Пусть N - число всех открытых текстов и Т - число открытых текстов, для которых левая часть линейного статистического аналога равна 0. Рассмотрим два случая.
Пользуясь приведенным выше алгоритмом, можем обобщить вышесказанное для уравнения X©Y = К.
Если T>N/2, то
Если T
Успех алгоритма возрастает с ростом N и Д = |1 - 2р|.
Данный алгоритм будет иметь успех при анализе большого числа текстов N. Следовательно, второй шаг анализа является вычислительно сложным. Поэтому для ускорения времени анализа можно и нужно использовать параллельные вычисления.
В результате работы вышеприведенного алгоритма будет получена определенная (а возможно, и переопределенная) система уравнений, отражающая взаимосвязь битов ключа. Третий шаг анализа заключается в решении данной системы, например, методом Гаусса, что позволит получить значения битов секретного ключа шифрования.
Выводы из данной статьи про линейный метод криптоанализа указывают на необходимость использования современных методов для оптимизации любых систем. Надеюсь, что теперь ты понял что такое линейный метод криптоанализа и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Криптоанализ, Виды уязвимости и защита Информации
Комментарии
Оставить комментарий
Криптоанализ, Виды уязвимости и защита Информации
Термины: Криптоанализ, Виды уязвимости и защита Информации