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

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

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

Открытие линейного криптоанализа послужило толчком к построению новых криптографических схем.

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

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

где 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) к уравнению вида:

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

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

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

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

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

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

Хэш-функция.

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

• для данного значения h(M) должно быть невозможно найти аргумент М. Такая хэш-функция называется стойкой в смысле обращения или стойкой в сильном смысле;

• для данного аргумента М должно быть невозможно найти другой аргумент М такой, что h(M) = h(M’). Такая хэш-функция называется стойкой в смысле вычисления коллизий или стойкой в слабом смысле.

Хэш-функция может использоваться:

• для создания сжатого образа сообщения, применяемого в механизме цифровой подписи;

• для защиты пароля;

• для построения кода аутентификации сообщений;

• для контроля соответствия порядка вычислений, проводимых в некотором процессе.

Отметим, что в первом и третьем случае необходимы хэш-функции, стойкие в смысле вычисления коллизий, а в остальных — стойкие в смысле обращения. Схема вычисления значения h(M) хэш-функции h для сообщения М обычно включает в себя:

• алгоритм вычисления шаговой функции хэширования g;

• итеративную процедуру вычисления хэш-функции h.

Для практических применений хэш-функция должна быть быстро вычислимой. Это достигается применением таких преобразований как шифрование n-битного блока текста, операции модульной арифметики, быстрое преобразование Фурье и др

78. Семейство алгоритма, вычисляющих хэш – функцииMD (MD2, MD4, MD5).

MD2 MD4 MD5

Семейство алгоритмов вычисления хэш-функции MD (Message Digest Algorithm) разработано Р.Л. Ривестом. Хэш-функции в этих алго­ритмах преобразуют входное сообщение произвольной длины в сжатый 128-битный образ. Эти алгоритмы могут использоваться, например, в со­вокупности с несимметричным криптоалгоритмом типа RSA. Основные операции, используемые в этих алгоритмах – сложение по модулю 232, циклический сдвиг, логические операции Å, Ù, Ú.Алгоритм MD2, предложенный в 1989 г., ориентирован на 8-разрядный процессор и отличается от MD4 и MD5 (ориентированных на 32-разрядный процессор) способом дополнения сообщения (с применени­ем 16-байтной контрольной суммы), значением стартового вектора хэши­рования и использованием 256-байтной перестановки, а обработка одного блока сообщения в нем выполняется за 18 циклов.

В алгоритме MD4, разработанном в 1990 г., обработка одного блока выполняется за 3 цикла, каждый из которых включает в себя 16 операций. На каждом цикле используется своя цикловая функция fj, 1 <= j <=3, где f1 =, f2 =, f3 =.

Наиболее употребительным является алгоритм вычисления хэш-функции MD5, созданный в 1991 г., который и будет рассмотрен под­робно.

Пусть исходное сообщение т задано t-битной строкой m1m2…mt. Строка сообщения m дополняется до длины, сравнимой с 448 по модулю 512 (то есть длине сообщения «не хватает» ровно 64 битов, чтобы быть кратной 512), а именно: к сообщению присоединяется одна «1», a затем необходимое количество нулей. Причем дополнение строки выполняется даже в том случае, если ее длина уже сравнима с 448 по модулю 512 (в этом случае к сообщению просто добавляется 512 бит).

К полученной строке присоединяется 64-битное представление числа t. В случае t³264, используются только младшие 64 бита числа t. Пусть дополненное сообщение М= М1М2…Мn, где Мi — 16-словный блок с размером слова 32 бита, а n кратно 16. Стартовый вектор хэширования MD0 имеет длину 128 бит и пред­ставляет собой конкатенацию четырех 32-битных слов md0||md1||md2||md3, где

md0 = 01234567, md1 = 89abcdef, md2 = fedcba98, md3 = 76543210.

В алгоритме MD5 используются четыре цикловые функции fj, 1£j£4, каждая из которых сопоставляет трем 32-битным словам X, Y и Z одно 32-битное слово.

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

Вычисление хэш-функции h:

Вход: М = М1М2,…Мn (n блоков по 512 бит).

Алгоритм: Для всех i=1,…, n MDi ß g(MDi-1, Мi).

Выход: h(M) = MDn

При вычислении используется накопитель E, содержащий четыре 32-битных слова А, В, С, D. Исходным заполнением накопителя Е явля­ются слова стартового вектора хэширования MD0. Обработка 16-словного блока Мi, 1 £ I £ n, сообщения M осущест­вляется за 4 цикла, каждый из которых включает в себя 16 шагов.

На каждом шаге i-того цикла А В+((А+fj(В, С, D) + Mi[s]+r)<<<k),

1 < j <. 4, где Mi[s] — слово, выбранное из Мi, s, r и k — параметры шага;

X<<<k — циклический сдвиг слова Х влево на k бит; «+» — операция сложения по модулю 232. Таким образом, на каждом шаге выполняется четыре операции сложения, одна операция сдвига и вычисляется значение одной цикловой функции. Для каждой итерации MDi представляет собой конкатенацию те­кущих значений четырех слов накопителя Е. После обработки блока Mn, итоговым сжатым образом сообщения будет 128-битная строка из четы­рех слов MDn = A||B||C||D.

Дата добавления: 2015-12-01