(17)

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

(18)

знаков гаммы, где – наибольший элемент множества .

Доказательство. Первое утверждение теоремы следует непосредственно из соотношений (10), (16), а последнее – из описания алгоритма. Наконец, поскольку для нахождения векторов () требуется элементарных операций, а для решения СЛУ (7) методом Гаусса – операций, то трудоемкость алгоритма составляет элементарных операций.

Следствие. Пусть в условиях теоремы , при ,

(19)

где . Тогда асимптотическая трудоемкость алгоритма при и составляет элементарных операций.

Остановимся подробнее на процедуре построения множества , выполняемой на первом этапе алгоритма. Напомним, что это множество состоит из неотрицательных целых чисел , для которых выполняются соотношения (4) и (5), причем, согласно последнему из них, должно быть не меньше чем.

Назовем число допустимым, если , и недопустимым – в противном случае.

Из равенства , , следует, что если и , то каждое значение является допустимым и можно положить , выбирая
в качестве наименьшее натуральное число, для которого выполняется равенство (5). Если же , то не все значения допустимы, и процедура построения множества может оказаться слишком трудоемкой. Вместе с тем, как показывает следующее утверждение, во многих практически важных случаях “удельный вес” недопустимых значений невелик.

Утверждение. Пусть – полноцикловое линейное преобразование над полем , и . Тогда вероятность того, что выбранное случайно и равновероятно из множества число является недопустимым, меньше чем

НЕ нашли? Не то? Что вы ищете?

Доказательство. Обозначим – совокупность всех
недопустимых чисел из множества ; – подпространство векторного пространства , порожденное строками матрицы ; – подпространство, дуальное к векторному
пространству, порожденному столбцами матрицы . Из данных определений следует, что

.

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

Утверждение доказано.

Численные расчеты и вычислительные эксперименты

Для того чтобы получить численные значения параметров, характеризующих эффективность предложенной атаки, и оценить возможность ее применения на практике, был проведен ряд вычислительных экспериментов. Ниже (рис. 1, табл. 1) приведены типичные результаты, полученные в ходе таких экспериментов при следующих значениях исходных параметров: длина начального состояния генератора ; длина ключа ; число неизвестных функции усложнения . Для задания линейной функции переходов (матрицы ) использовался примитивный над полем полином ,
а для задания существенных переменных функции усложнения (матрицы ) – фиксированный набор чисел .

Данные на рисунке получены в результате 200 независимых испытаний, в -м из которых генерировалась случайная равновероятная -матрица и подсчитывалось значение случайной величины . Для каждого интервала на
рисунке показано количество тех значений , для которых .

Эмпирическое распределение числа допустимых значений в интервале

Полученные результаты свидетельствуют о том, что для случайно сгенерированных матриц допустимые числа появляются достаточно часто. Например, в 35 из 200 проведенных испытаний количество допустимых чисел составляет от 191 до 195. Эффект “полного ранга” (когда все значения допустимы или, что то же самое, все матрицы имеют ранг ) наблюдается примерно в 25 % случаев (45 из 200).

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4