Критерии оценки ПСП

Многообразие критериев оценки ПСП чрезвычайно велико. Каждый из подходов к анализу последовательностей можно отнести к одной из двух групп. Первая группа связана с поиском закономерностей, позволяющих воспроизвести последовательность по ее отрезку небольшой длины. При этом основные требования к последовательности сводятся к отсутствию в ней относительно простых межзнаковых зависимостей. Вторая группа критериев связана с оценкой статистических свойств последовательности: имеется ли в исследуемой последовательности какой-либо частотный дисбаланс, позволяющий аналитику прогнозировать по известному отрезку последовательности следующий знак, т. е. предположить значение следующего бита с вероятностью большей, чем при случайном выборе? Основные требования к ПСП по второй группе критериев сводятся к тому, чтобы ряд ее статистических свойств соответствовал свойствам случайной идеальной последовательности, т. е. в ПСП должны быть равномерно распределены частоты встречаемости и отдельных знаков, и 5-грамм при достаточно больших значениях s.

При системном подходе для анализа последовательностей используются известные тесты и разрабатываются новые тесты с учетом особенностей анализируемого объекта. Если в ходе анализа в некотором классе последовательностей обнаруживается новая слабость, то разрабатывается новый тест, который пополняет используемый набор известных тестов.

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

Одна из первых формулировок трех основополагающих требований к статистическим свойствам периодических двоичных ПСП была дана С. Голомбом^[1]. Эти требования к последовательностям получили известность в криптографии как постулаты Голомба.

Для периода {.х₀, х_{,…, x_t__{} двоичной чисто периодической ПСП Xобозначим:

• п_{ и п₀ — частоты соответственно единиц и нулей, = х₀ + + … +.

+ x_t_ 1, n₀ = t-n_{;

• • nf и wg — частоты 5-грамм вида (1,…, 1) и (0,…, 0), s > 1;
• • n_{(d) и n₀(d) — соответственно частоты единиц и нулей на (0, t-^{-отрезке} последовательности X^ = (г, — © X (_i+dy_mtKt}, de {0, 1,…, t- 1};
• • c_x^(d) — функция автокорреляции, c_x_^(d) = (n_{(d) — n₀(d))t-K

При данных обозначениях постулаты Голомба таковы:

• 1) щ — п₀1 < 1;
• 2) п_х2-⁵⁺¹ = nf = n^s_Q = п₀2~^0s+ 5=1,…, [log₂?];
• 3) функция c_x^(d) принимает лишь два значения (двузначная).

Третье правило — условие независимости знаков последовательности.

Xа также некая мера различения последовательности Х_^ и ее копии, начинающейся в другой точке цикла.

Последовательности, удовлетворяющие постулатам 1—3, называют псевдотумовыми (ПШ-последовательностями). Постулаты исходят из условия сохранения положительных статистических свойств, присущих ЛРП максимальной длины периода. Для любой НРП выполнены первые два постулата Голомба.

Правила Голомба не гарантируют высокого качества ПСП и являются скорее необходимыми. На практике использование постулатов Голомба для оценки качества ПСП затруднительно, в силу сложности теоретического расчета длин периодов ПСП, частот 5-грамм на периоде, а также значений функции автокорреляции. Расчет на ЭВМ возможен лишь для ПСГ1 с небольшой длиной периода, что ограничивает использование постулатов Голомба в криптографических приложениях.

• [1] Golomb S. W. Shift register sequences. San Francisco: Holden Day, 1967.