Анализ криптостойкости методов защиты информации в операционных системах Microsoft Window 9x — страница 10

слова, кроме подвергаемых перестановке, остаются теми же самыми. Выходная последовательность n-битных слов обозначается как Zt =(Zt )t=1¥ .Начальная таблица S0 задается в терминах ключевой последовательности K = (KL)t=02n -1 с использованием той же самой функции следующего состояния, начиная от таблицы единичной подстановки (L)2n L=02n -1. Более строго, пусть j0 = 0 и для каждого 1 ≤ t ≤ 2n вычисляется jt = (jt - 1 + St-1(t-1) + Kt-1) mod 2 n, а затем

переставляются местами St-1(t-1) и St-1(jt). На последнем шаге порождается таблица, представляющая S0. Ключевая последовательность K составляется из секретного ключа, возможно повторяющегося, и случайного ключа, передаваемого в открытом виде в целях ресинхронизации. До последнего времени в открытой литературе практически не было публикаций по криптоанализу алгоритма RC4. Компания RSA Data Security объявила, что шифр обладает иммунитетом к

методам линейного и дифференциального криптоанализа, высоко не линеен и не похоже, чтобы у него были короткие циклы. Обычно цитируется заключение закрытой работы криптографа RSA Labs Мэтта Робшоу: "Не имеется известных слабых ключей и, хотя нет доказательства для нижней границы периодов последовательностей RC4, проведенный теоретический анализ показывает, что период в подавляющем большинстве случаев превышает 10100. Тщательный и

всеобъемлющий анализ стойкости RC4 не выявил никаких оснований подвергать сомнению стойкость, обеспечиваемую генератором RC4". Первой открытой публикацией можно считать работу Йована Голича, представленную на конференции Eurocrypt '96. В ней отмечается, что для последовательностей, генерируемых RC4, не подходят методы статистического анализа. Но, с другой стороны, как показано в работах, для блоков, размер которых превышает M (размер

внутренней памяти генератора), всегда существует линейная статистическая слабость или так называемая "линейная модель". Такую модель можно эффективно определять с помощью метода аппроксимации линейной последовательной схемой. Линейная статистическая слабость - это линейное соотношение между битами гаммы, которое выполняется с вероятностью, отличающейся от 1/2. Главная цель работы Голича - с помощью метода АЛПС вывести

линейные модели для RC4. Метод АЛПС заключается в нахождении и решении последовательной линейной схемы, которая аппроксимирует генератор гаммы и приводит к линейным моделям с относительно большим корреляционным коэффициентом c, где вероятность соответствующего линейного соотношения между битами гаммы составляет (1+ c)/2. При анализе использовалась техника двоичных производных. Пусть Z = (Zt)t=1¥ обозначает последовательность