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

самых младших бит слов выхода RC4, и пусть Z/=( Z/t = Zt+ Zt+1) t=1¥ и Z//=( Z//t = Zt+ Zt+2) t=1¥ обозначают ее первую и вторую двоичные производные, соответственно. Показано, что Z/ не коррелирует ни с 1, ни с 0, но Z// коррелирует с 1 с корреляционным коэффициентом, близким к 15*2-3n при больших 2n, где n – длина ключа. Поскольку длина выходной последовательности, требуемая для выявления статистической слабости с корреляционным коэффициентом c, составляет

O(c-2), то эта длина равна примерно 64n /225. Например, если n = 8, как рекомендуется в большинстве приложений, то требуемая длина близка к 240. Результаты компьютерных экспериментов согласуются с теоретическими предсказаниями. Поскольку результирующий коэффициент корреляции существенно превышает величину 2M/2, то установленную линейную модель следует рассматривать как статистическую слабость генератора, по крайней мере в

теоретическом аспекте. В 1997 году опубликована большая работа Йована Голича, посвященная криптоанализу обобщенной схемы комбинирующего узла с произвольным размером памяти. Исследованы корреляционные свойства таких узлов, обоснованы новые конструктивные критерии, предъявляемые к схемам подобного типа. Разработан эффективный метод аппроксимации линейной последовательной схемой для построения линейных функций от входа и

выхода со сравнительно большим коэффициентом взаимной корреляции. Это практичная процедура, позволяющая с высокой вероятностью находить пары взаимно коррелированных линейных функций (от самое большее M + 1 последовательных выходных бит и самое большее M + 1 последовательных векторов входа) со сравнительно большими коэффициентами корреляции. Метод АЛПС состоит в задании и решении линейной последовательной схемы (ЛПС), которая

аппроксимирует комбинирующий узел с памятью. Эта ЛПС имеет добавочные несбалансированные входы и основана на линейных аппроксимациях функции выхода и всех компонент функции следующего состояния. Линейная аппроксимация булевой функции - это любая линейная функция, с которой заданная булева функция скоррелирована. Описанный метод применим к произвольным комбинирующим узлам с памятью без ограничений на функции выхода и

следующего состояния. Сначала отыскиваются линейные аппроксимации функции выхода f и каждой из функций-компонент функции следующего состояния F. Это эквивалентно выражению каждой из этих M+1 функций в виде суммы линейной функции и несбалансированной функции. Если подлежащая декомпозиции функция уже несбалансированна, то можно выбрать константно-нулевую линейную функцию. Если подлежащая декомпозиции функция статистически