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

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

Корреляционные коэффициенты можно определять с помощью техники преобразования Уолша. На следующем шаге, получив линейные аппроксимации, в матричной форме записывают базовые уравнения комбинирующего узла с памятью St+1 = ASt + BXt + D(Xt, St), t≥0, yt = CSt + DXt + e(Xt, St), t ≥0, где векторы рассматриваются как матрицы-столбцы; A, B, C, D - двоичные матрицы; а e и каждый компонент в D = (d1, . . . , dM) – несбалансированные булевы функции, именуемые функциями

шума. Основная идея состоит в том, чтобы рассматривать {e(Xt ,St)}t=0¥ и {d(Xt ,St)}t=0¥ , 1≤i≤M, в качестве входных последовательностей, так что последние уравнения оказываются задающими неавтономную линейную машину с конечным числом состояний или ЛПС, именуемую АЛПС комбинирующего узла с памятью. Тогда можно решать эту ЛПС с использованием техники производящих функций (D-преобразований). В частности, пусть S, X, D, e, y обозначают

производящие функции от переменной z для последовательностей {St}, {Xt}, D(Xt, St)}, e (Xt, St)}, yt}, соответст венно. Тогда уравнения сводятся к виду Решение имеет вид где I - единичная матрица, det(zA - I) = f(z), f(0) = 1, - многочлен, обратный к характеристическому многочлену матрицы переходов A степени, не превышающей ранг A (≤M); а элементы (присоединенной) матрицы adj(zA - I) - это полиномы от z степени не более M-1. Вычислительная сложность для отыскания

такого решения составляет O(M3(N+1)). В другом виде решение можно переписать как где xi и dj обозначают производящие функции для {xit} и {dj(Xt, St)}, а степени полиномов gi(z) и hj(z) самое большее равны M и M-1, 1≤i≤N, 1≤j≤M, соответственно. Полагая решение можно преобразовать к виду: где подразумевается, что вектор состояния St-k - это функция от (Xt-k-1M-k, S t-M) для каждого 0≤k≤M-1. Линейные функции входа и выхода в (2) скоррелированы тогда и только

тогда, когда функция шума e несбалансирована. Коэффициент корреляции не зависит от времени, если функция следующего состояния сбалансирована. Если это условие не удовлетворяется, то корреляционный коэффициент может зависеть от времени, поскольку от St более не требуется сбалансированность для каждого t≥0. Функция шума e в (3) определена как сумма индивидуальных шумовых функций, которые несбалансированы при условии, что