Полная версия

Главная arrow Информатика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Дополнительные пояснения

Отметим, что значения величин Х(к), а, аь рь непосредственно не следуют из входных данных задачи. В связи с чем, представляет интерес следующий комментарий, устанавливающий связь этих параметров с входными данными алгоритма.

Обращаем внимание на то, что выбор функций Фь Ф2,..., Фж осуществлен так, что в качестве Х(к) может быть использована мощность множества ДФЬ Ф2,..., Фж)|- Далее по тексту следует, что

в частности, Х(к) = ДФЬ Ф2)|-|ДФ2, Фз)| ... ДФь Фьн)|* Напомним, что множество ДФ/, Oj+{)9je {1,..., к} состоит из тех a'(j) из X, для которых выполнено условие

Для нахождения множества ДФ/, Ф/+0 необходимо предварительно

рассчитывать вероятность Р(ФД) = Ф/+1 (/*«(/>?)) для всех a(j) еХ. Значение

данной вероятности равно 1770 + 1171, где то - число решений относительно

I S |

seS системы из двух булевых уравнений

а т - число решений системы уравнений

Таким образом, вероятность Р(Ф/я) = Ф/Д/ц»?)) полностью определена функциями Фь Ф2,..., Ф^+ь а множество ДФ/, ФД получается с помощью равенства (3.4.2).

Относительно ошибок а = P(Hi/H0), р = Р{Но!Н) используемого критерия можно сказать следующее. Их значения зависят от выбора вида критерия, различающего указанные гипотезы. Укажем связь ошибок с исходными данными для критерия Неймана-Пирсона, проверяющего гипотезы Я0:

против альтернативы Н.

Пусть V= (vi, v2, Vn) выборка из распределения Бернулли с вероятностью «успеха» р (P(v = 1) = р). Критерий Неймана-Пирсона, проверяющего гипотезы Н0: р = р0 против альтернативы р = р, строится следующим образом. Рассмотрим случай 0< ро< р<. Статистика отношения правдоподобия имеет вид

{ А,

N j j

где T - число успехов в выборке т = Е vj .Так как ро<Ри то ^/ ~Ро) > ^

У у=1 ) Po(1-Pl)

Для любого С можно выбрать t так, что неравенство L(V) > С будет эквивалентно неравенству Т> t. Параметры критерия (vb v2,..., v^), р, п, t таковы, что, фиксируя два из них, остальные два определяются однозначно. Параметр N у нас уже фиксирован. Фиксируем дополнительно вероятность ошибки первого рода а. Параметры ta и (1 - р) - мощность критерия находят так.

Целое число ta определяют из условия

Возможны два случая: а = а' и а < а'.

Если выбранное а совпало с а', то критерий является нерандомизированным и задается критической областью {(vb v2,..., vN): Т> ?а} (областью принятия гипотезы Hi). Вероятность ошибки первого рода а равна вероятности события Т > ta при распределении Бернулли с вероятностью «успеха» ро. Мощность критерия равна вероятности события Т > ta при распределении Бернулли с вероятностью ’’успеха"р.

Данная вероятность подсчитывается по формуле

Если а < а', то критерий является рандомизированным и задается критической функцией

Мощность критерия рассчитывается по формуле

При N —> оо, воспользовавшись теоремой Мавра-Лапласа, критерий можно асимптотически задать критической областью

где Ф(ца) = а, Ф - функция нормального распределения с параметрами

(0,1).

У

Для Pi = Ро + , у > 0 мощность критерия при N—>оо асимптотически

равна

Приведем несколько пояснений относительно эффективности рассмотренного метода. Очевидно, она зависит от эффективности статистических критериев. В нашем случае их эффективность растет с ростом величины р0 - pi. В связи с чем можно рекомендовать выбирать функции Фь Ф2,..., Фк+i так, чтобы они не были константами и максимизировали или минимизировали вероятность р0 (3.4.4), так как альтернативная гипотеза состоит в том, что Р = . Для этого надо при каждомjк} провести расчет вероятностей Р(Ф^8)j+i(haS)), а е X и найти максимальные значения из них по (3). Такие расчеты значительно облегчаются для линейных функций Фь Ф2,..., Фк+ь В этом случае поиск наилучшей (см. замечание 1) последовательности линейных функций Uj,..., Uk+i можно вести последовательно: перебором 2П - 2 не константных функций U в качестве функции ®j+i и расчета для функции Uha наилучших линейных статистических аналогов (с помощью быстрого преобразования Фурье), каждый из которых пробуется в качестве функции Ф}

Напомним читателю основные понятия, связанные с линейными аналогами двоичных функций.

Рассмотрим двоичную функцию

Считаем, что ее переменные являются независимыми случайными величинами с распределениями:

Тогда для любого набора а = (a1fan) е F2n выполняется равенство

Обозначим через p(f(xb...,xn) = 1) вероятность того, что при случайном и равновероятном выборе переменных значение функции будет равно единице.

Имеем

где х = {хь...,хп).

Здесь через f обозначен вес функции/- число двоичных наборов, на которых она принимает значение, равное единице.

Двоичная функция g(x) называется статистическим аналогом функции

л

Дх), если p(f(x) = д{х)) >-. Здесь p(f(x) = д(х)) - вероятность совпадения значений функций fug при случайном и равновероятном выборе набора х е Ff. Очевидно свойство: если p{f{x) = h{x)) <~, то

здесь

На использовании статистических аналогов двоичных функций основан целый ряд статистических методов анализа криптосхем. Основная идея этих методов заключается в замене «сложной» функции Дх), используемой в исследуемой схеме, на один из ее статистических аналогов более простого вида, причем этот аналог g(x) выбирают так, чтобы вероятность p(J{x) = g(x)) была максимальной. В этом случае функция g(x) будет нести информацию о многих свойствах исследуемой функции, однако за счет отличия значений функций fix) и g(x) на некоторых наборах задача из детерминированной становится вероятностной, для решения которой используются статистические методы.

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

Напомним эти известные понятия.

Пусть (а, х) = ах^ ф... Ф апхп - некоторая линейная функция. Определяют параметр Afa равенством:

В приведенных выше обозначениях Аа называют коэффициентом статистической структуры функции/

Получим формулу для вычисления коэффициентов статистической структуры:

1 До llf’(x) 0(а, х)|| , ,

Тогда 2 + ~2" = ^--2^- Следовательно Дд=2п 1 -||f(x) 0(а,х)||.

Множество | Дд : а е F2n} называют статистической структурой функции /

Рассмотрим связь между коэффициентами статистической структуры и коэффициентами Фурье двоичной функции/

Через Сfa обозначим коэффициент Фурье двоичной функции/ Сначала рассмотрим случай а = 0:

поэтому Д' = 2n_1 - 2Л Cq .

Теперь пусть а Ф 0:

поэтому Ag = -2ПСа.

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

Кроме того, становится очевидным следующее представление двоичной функции через коэффициенты ее статистической структуры:

Замечание об эффективности алгоритма Мицуру Мацуи

Линейный анализ изобрел японский ученый Мицуру Мацуи. Предложенный им в 1993 г. метод изначально был направлен на вскрытие алгоритма DES. Впоследствии линейный криптоанализ был распространен и на другие алгоритмы (см. работу[1] и статью[2]).

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

Так, например, линейный криптоанализ Мацуи r-раундового DES требует значительного числа открытых текстов. Это следует из следующей таблицы.

Количество

раундов

Количество известных открытых текстов для нахождения ключа

8

221

12

233 Eurokrypt' 93

16

247 Crupto' 94

Сложность атаки связана с количеством необходимых известных открытых текстов, так как для любой пары (открытый текст-шифртекст) требуется небольшое количество вычислений для реализации алгоритма. Например, атака на г = 8 DES занимает 40 с на рабочей станции, а атака на г = 12 DES занимает 50 ч, что примерно в 4500 раз больше.

  • [1] Ritter Т. Linear Cryptanalysis: A Literature Survey. URL: // http://www.cyphersbyritter.com
  • [2] Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems. URL: // http://citeseer.ist.psu.edu — The Weizmann Institute of Science, Israel — July19, 1990.
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>