Построение функций Ф1, Фk+1 и расчет вероятностей P(Ф1, Фk+1)

Ищется последовательность пар функций

удовлетворяющая приводимым ниже условиям.

При равномерном распределении на S для слова а( 1), а(2),..., а{к) е А* рассмотрим вероятности

Для расчета значения Р(ФЬ Фш) заметим, что в силу перестановочности автомата А индуцированные равномерным распределением на S вероятностные распределения на множествах ha(i)(S), ..., ha^..ha(i)(S),•••>

ha{k)...hav)(S) равномерные. В связи с чем, при случайном и равновероятном выбореs ns' из S

Утверждение 1. Если при случайном и равновероятном выборе s из S при любом j е {1,..., &-1} события

независимы, то

где 5а(у), j g {1,..к) определяется из равенства

при случайном и равновероятном выборе «s^eS.

Доказательство. Аналоги данного утверждения доказаны в статье49 и работе[1]. Тем не менее, авторы считают полезным для читателя провести полностью доказательство. Индукция по к. При к = 1 требуемое равенство очевидно. Пусть это равенство верно для к =j. Докажем его для j +1. Имеем

Замечание 1. При отказе от условия независимости указанных в утверждении 1 событий данное утверждение становится неверным. Так, например, взяв к> 1 и слово (а{ 1), а(2),..., а(к)) так, чтобы = Е, где

Е— тождественное отображение S в S, и Ф] = Ф^+ь получим P(Oi(V) = = Фж(Лв(*)...Ла(1)У))=1, а ДЛЯ функций Ф1 И Ф*+1 = Ф1+1 получим P(0(s) = ®k+(ha{k)''ha{)рУ) 0.

Предположим, что значение вероятности

достигается на наборах {а'(1),а'(2),..., компоненты a'(j) которых

удовлетворяют условию

Matsui М. The First Experimental Cryptanflysis of the data Encryption Standard. FSIA CRYPT94.P. 1-11.

Это множество компонент обозначим через Х(Ф7, Фу+i), je {1,..., А:}. Положим

Тогда

Замечание 2. Трудоемкость (в опробованиях аеХ) получения значения вероятности (3.4.4) равна

Здесь в операцию «опробование» входит и расчет вероятности P(Oj(s) = Oj+(has)), которая может быть рассчитана путем нахождения числа решений систем уравнений

Обозначим через ДФЬ Ф2,..., Фш) множество всех наборов а( 1),..., а(к), для которых выполняется (3.4.4). Очевидно,

Первый этап метода. После выбора двоичных функций Фь Ф2,.. .,Ф*+1 и расчета вероятности по формуле (3.4.4) строится, как было указано ранее, статистическая процедура разделения гипотез Я0, Яь трактуя известные состояния s), s?..... s,w как выборку из равномерного распределения на S, а наблюдения Ф^') = Фш(^> К{i)sf), либо Ф^) * Фж(Лв(*),...,Лв(1)в() как

выборку из одного из распределений:

Таким образом, с помощью статистики - расстояния Хэмминга

принимается одна из гипотез Н0, Н. При принятии Н0 делается вывод о том, что искомое решение (6(1), 6(2),..., Ь{к)) системы (3.4.1) принадлежит ДФЬ Фш), после чего переходят ко второму этапу метода. Если же принимается гипотеза Нх — (6(1), 6(2),...,6(A)) ? ДФЬ Ф2,..., Ф*ц)> то считается, что решение не найдено, метод завершает свою работу. Обозначим через а = Р(Я]/Я0), р = P{HJH) ошибки критерия первого и второго рода.

Второй этап метода. Итак, принято решение, что (6(1), 6(2),... ,6(А:)) е Х(Ф, Ф2,..., Фж)> При этом само множество ДФЬ Ф2,..., Фж) нам неизвестно. Рассмотрим два случая:

Первый случай. На втором этапе последовательно ищутся варианты значений компонент 6(1), 6(2),..., Ь{к) решения. Опробуются х(1)е X. Для опробуемого варианта х(1) вычисляются состояния hx^s(, j е {1,..., Я} автомата А. Полностью аналогично указанной выше статистической процедуре строится статистический критерий, который с помощью последователь- ности пар (hmst, 4), (hx{ 1)4, 4),..., (hmsC$) и статистики

разделяет гипотезы Hq, н]. Гипотеза hJ состоит в том, что

где

Гипотеза н] состоит в том, что

При принятии гипотезы Hq(H}) делается вывод о правильном (о неправильном) определении истинной части 6(1) решения.

Обозначим через oti = P{h}i hJ), Pi = P(hJ/ н)) ошибки критерия первого и второго рода.

В результате за Х опробований будет найдено в среднем (|Z| - l)pi ложных значений х(1) и истинное значение 6(1) будет найдено с вероятностью (1-ai). Для каждого найденного значения х(1) = a( 1) опробуются все значения х(2). Для опробуемого варианта х(2) по статистике

принимаются гипотезы:

При принятии гипотезы н$ делается вывод о правильном определении части х(2)а{Х)=Ь(2)Ь{) входного слова автомата. При принятии гипотезы н? делается вывод о неправильном определении части х(2)а{) входного слова автомата. Ошибки первого и второго рода критерия обозначим через а2, р2. За Х опробований будет найдено в среднем (Х - l)pi|A|p2 + + (1 - oti)(|X| - 1)р2 ложных вариантов начальных частей х(2)х(1) решения и с вероятностью (1 - oci)(l - а2) найдена истинная часть b(2)b(l) решения. Аналогично получаются ложные варианты начальных частей х(3)х(2)х(1) решения. Их будет

а истинное значение b(3)b(2)b{) будет не отсеяно с вероятностью

Положив a,j = аь РУ = Рьу g {1,..., А:}, получим, что в результате за Г2 = кХ опробований будет найдено в среднем

ложных вариантов решения системы (3.4.1). Истинный вариант будет не отсеян с вероятностью (1 — а О*.

Второй случай: (b{ 1), Ь(2),..., Ь{к)) ? Х(Ф{, Ф2,..., Фш)- Проводится указанная выше (случай 1) процедура определения вариантов решения системы (3.4.1). Трудоемкость процедуры равна Г2 + Г32 опробований х е X, Г3 опробований частей неизвестной последовательности х(1), х(2),..., x(kj).

Третий этап метода. Проводится опробование полученных вариантов решения в системе (3.4.1), т.е. для каждого варианта {а{к)а(к-),..., я(1)) проверяется выполнение равенств:

Таких опробований будет проведено в среднем Г3 + (1 - а{)к в первом случае и Г3 - во втором. Таким образом, общая трудоемкость метода (без учета опробования истинного варианта на третьем этапе) выражается величиной

Характеристиками надежности л метода являются:

Р(Н0) - вероятность применения второго этапа метода;

вероятность Р((6(1), 6(2),...,6(&)) е ДФЬ Ф2,...,Ф*+0) - при случайном и равновероятном выборе входного слова (6(1), 6(2),..., Ь(к)) из

(1 —

Рассмотрим события:

1) (6(1), 6(2),..., b{k)) g Х(Фх, Ф2,..., Фш), вероятность этого события

равна ВД

xk

2) на первом этапе принята гипотеза Я0, вероятность этого события (при выполнении условия 1)) равна 1 - а;

3) на втором этапе истинное решение не отсеялось, вероятность этого события при выполнении условий 1), 2), есть (1 - аО*.

При выполнении этих условий на третьем этапе истинное решение будет найдено.

Следовательно,

Замечание 3. С ростом к вероятность Р(ФЬ Фж)> подсчитанная по формуле (3.4.4) при естественных предположениях о границах значений 5*.

1

j е {1 стремится к что негативно отражается на эффективности

рассматриваемого метода. В связи с этим в ряде случаев можно ограничиться нахождением двоичных функций Фь Ф2,.Фа>+1 для к'< к и расчетом Р(ФЬ Фг+i). В этом случае на первом этапе метода опробуются ’’хвосты" х(к'+)х(к'+2),..., х{к) неизвестного решения системы (3.4.1). Для опробуемого варианта а{к'+)а(к'+2),..., а{к) с помощью статистики

различают гипотезы Я0, Н

Гипотеза Я0 соответствует опробованию истинной части b(k’+),...,b(k) решения b(l),...,b(kr) х b(k'+l),...,b(k), Н — ложной. При принятии гипотезы Н0 переходят к определению оставшейся части решения системы (3.4.1). Последняя задача решается полностью аналогично представленной выше. Расчет трудоемкости и надежности такого обобщенного метода с учетом приведенных формул не вызывает затруднений.

  • [1] Ritter T. Linear Cryptanalysis: A Literature Survey. URL: http://www.cyphersbyritter.com
 
Посмотреть оригинал