Статистическое тестирование последовательностей

Случайные и псевдослучайные последовательности

Случайные последовательности (СП) играют в криптографии важную роль в исследовательских задачах и в реализации криптографических методов и средств защиты. Случайные последовательности используются для формирования начальных параметров криптографических алгоритмов (ключей, инициальных векторов и др.), последовательностей шифрующих подстановок в поточных криптосистемах. Случайность и криптография тесно взаимосвязаны: основная цель криптографических систем состоит в преобразовании неслучайных осмысленных открытых текстов в кажущуюся случайной последовательность символов шифрованного текста. Это свойство криптосистем используют для генерации псевдослучайных п ос лед о вате л ь н осте й.

Наилучшие криптографические свойства криптосистемы достигаются при использовании так называемых идеальных случайных последовательностей (ИСП), математическая модель которых представляется реализацией последовательности независимых случайных величин (с.в.), имеющих равномерное распределение вероятностей на заданном конечном алфавите. Такие последовательности называют также равномерно распределенными (на некотором множестве) случайными последовательностями (РРСП). Равномерно распределенные случайные последовательности (на множестве X мощности к) — это последовательность {?_t,…} с.в., принимающих значения в X, определенных на некотором вероятностном пространстве и удовлетворяющих двум базовым условиям при любом п е N:

• 1) для любых номеров 1 < ^ < … < t_n с.в. ^ ,…, ^ независимы в совокупности;
• 2) с.в. равномерно распределена на X, т. е. Р (С,₍ = х) = 1 /к для любого хе X.

При базовых условиях выполнен для любых номеров 1 < t_x < … < t_n:

1) распределение /7-мерной с.в. (?*_t>•••") является равномерным на множестве Х^п;

2) последовательность, … есть РРСП (воспроизводится при «прореживании»);

3) (воспроизводится при суммировании), т. е. для неслучайной/случайной последовательности {гр} над аддитивной группой X, не зависящей от {Q, СП {?, + лJ есть РРСП;

4) предсказание значения С,_п при известных знаках i^, L_>n__{ невоз можно, т. е. для любого набора (х_1?х_п) е X^й выполнено: Р (С,_п = х_п / ^ = x_t, …,^_₁=x_n__i)=p (t;"=x) = i/k.

Существуют различные подходы к формальному определению термина «случайность», основанные на понятиях вычислимости и алгоритмической сложности. Исторически первый подход, частотный, предложен фон Мизесом (Mises) в начале XX в. и развивался Черчем, Колмогоровым и Ловеландом (Loveland). Идея частотного подхода в том, что в СП должна наблюдаться устойчивость частот встречаемости элементов. Например, знаки 0 и 1 должны встречаться независимо и с равными вероятностями не только в самой двоичной СП, но и в любой ее подпоследовательности, выбранной независимо от исходных условий генерации.

Другой подход, сложностной, предложенный независимо Колмогоровым и Чейтином (Chaitin), основан на том, что любое описание реализации СП не может быть существенно короче самой этой реализации. Иными словами, СП должна иметь сложное строение, и энтропия ее начальных элементов должна быть велика. При данном подходе показано, что последовательность случайна, если ее алгоритмическая сложность близка к длине последовательности.

Третий подход, количественный, развит Мартин-Лефом (Martin-Lof). Он заключается в разбиении вероятностного пространства последовательностей на СП (таких много) и неслучайные (таких мало). Неслучайными считаются последовательности, в которых наблюдаются какие-либо закономерности. Последовательность случайна, если она проходит определенные тесты, выявляющие закономерности. Однако если требовать, чтобы последовательность прошла любой статистический тест, то окажется, что СП вообще не существует. На практике используют некоторый набор тестов, где доля СП, им не удовлетворяющих, стремится к 0 при неограниченном увеличении длины последовательностей.

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

Указанные подходы к определению случайности имеют недостатки. Частотный подход затруднен на практике неопределенностью правил выбора подпоследовательностей, сложностной подход влечет необходимость уменьшения избыточности языка программирования. Использование количественного подхода затруднено определением множества тестов, применяемых к исследуемым последовательностям. Нижние оценки сложности криптографического подхода ориентированы на набор известных тестов, а он со временем может пополняться, что приводит к переоценке сложности. Вместе с тем для криптографических приложений наиболее подходящим является криптографический подход, учитывающий статистические свойства последовательностей и область их применения.

Генерируемые, но определенному правилу последовательности, имитирующие РРСП, называются псевдослучайными последовательностями (ПСП). Имитация понимается как близость ряда характеристик генерируемых ПСП к аналогичным характеристикам ИСП.

В математической литературе ПСП над конечным множеством X определяется как последовательность длины ш, порождаемая из случайной последовательности длины п с помощью детерминированной функции полиномиальной вычислительной сложности. Полиномиальная сложность вычисления означает число условных вычислительных операций (например, число сложений и умножений в некотором числовом поле), достаточных для вычисления ПСП длины т, ограничено сверху величиной /(/?), где f (x) — полином с целыми неотрицательными коэффициентами. Генератор ПСП часто моделируется автоматом Мили, где случайными элементами являются начальные состояния, функции переходов и выходов.

Порождение ПСП, используемых в криптографических приложениях, основано на реализации многократных итераций определенного преобразования конечного множества X (часто X = V_n). Такая выходная последовательность является периодической. Однако длина периода может быть весьма большой, что обеспечивается использованием линейных регистров сдвига с примитивными многочленами. Для многих генераторов доказаны хорошие статистические свойства и высокая линейная сложность, большая длина периода, однако доказать аналитические и статистические свойства часто не удается. Для обоснования многих свойств используются статистические тесты.