Лемма 3.1

Пример 3.1

Определение 3.1

Последовательность называется периодической с периодом, если — наименьшее натуральное число, для которого

при всех.

Отрезок длины есть подпоследовательность из, состоящая из идентичных символов, ограниченная иными символами. Если отрезок начинается в момент, то справедливы условия

Мы различаем следующие отрезки:

блок длины,

лакуна длины.

Автокорреляцияпериодической последовательности с периодом определяется формулой:

(3.1)

где (соответственно,) обозначает число совпадений (соответственно, несовпадений) на полном периоде между и; вторая последовательность есть последовательность, сдвинутая влево на позиций. Таким образом,

Заметим, что можно также написать.

Рассмотрим периодическую последовательность с периодом, заданную ее первыми элементами.

С помощью функций Count, Length, Mod, RotateLeft и Table пакета "Mathematica" легко вычисляются все значения автокорреляционной функции,.

segment = {1, 1, 0, 1, 0, 0, 0, 0};

p = Length[segment];

Table[2*Count[Mod[

segment - RotateLeft[segment,k],2],0] - p) / p, {k, 0, p – 1}]

|| {1, 0, 0, 0, -1/2, 0, 0, 0}

Если кратно, получаем,, так что. В этом случае говорят о внутрифазовой автокорреляции. Если не делит, то говорят о внефазовой автокорреляции. В этом случае значение лежит между и.

Определение 3.2 (Golombs Randomness Postulates)

G1: Количество нулей и единиц в одном периоде приблизительно совпадает, т.е. вероятности их появления, если четно, и, если нечетно.

G2: Половина отрезков в цикле имеют длину 1, четверть отрезков имеют длину 2, восьмая часть отрезков имеют длину 3 и т.д.; кроме того, половина отрезков данной длины — лакуны, другая половина — блоки.

G3: Внефазовая автокорреляция имеет одно и то же значение для всех.

G1 утверждает, что нули и единицы встречаются приблизительно с одной и той же вероятностью. Их появления легко подсчитать с помощью функции Count пакета "Mathematica".

segment = {1, 1, 0, 1, 0, 0, 0, 0};

Count[segment,0]

Count[segment,1]

|| 5

|| 3

G2 утверждает, что после комбинации 011 символ 0 (приводящий к блоку длины 2) имеет ту же вероятность, что и символ 1 (приводящий к блоку длины), и т.п. Таким образом, G2 говорит, что конкретные -граммы встречаются с правильными частотами. Эти частоты можно вычислить с помощью функций Count,Length,RotateLeft, Table и Take пакета "Mathematica":

segment={0,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1};

p = Length[segment];

ngram = {1, 0, 1}; k = Length[ngram];

Count[Table[Take [

RotateLeft[segment, i], k] == ngram, {i, p}], True]

|| 3

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

Пусть — двоичная последовательность с периодом, удовлетворяющая постулатам случайности Голомба. Тогда нечетно и принимает значение, когда не делится на.

Доказательство. Рассмотрим циклическую -матрицу с верхней строкой. Подсчитаем двумя способами число всех совпадений за вычетом числа несовпадений между верхней строкой и всеми прочими строками. В силу постулата G3 построчный подсчет дает вклад для каждой строки с номером. В целом получается значение. Теперь мы подсчитаем ту же сумму по столбцам, рассматривая число совпадений за вычетом числа несовпадений между всеми нижними клетками и верхней.

Случай четного

В силу G1 вклад каждого столбца равен, так как каждый столбец содержит в точности совпадений нижних клеток с верхней и в точности несовпадений. Сумма этих значений по всем столбцам равна. Приравнивая два значения суммы, получаем. Однако из равенства (3.1) следует, что число целое. Это невозможно, когда, так как.

Случай нечетного

Для столбцов получаем вклад, равный 0, а для столбцов — вклад, равный. Следовательно, значение суммы есть. Приравнивание этой суммы к дает.

Хорошо известный критерий и спектральный критерий дают способы проверки свойств псевдослучайности данной последовательности.

Имеются также свойства криптографической природы, которым должна удовлетворять последовательность на рис. 3.1.

С1: период последовательности должен быть очень большим (величиной порядка 10⁵⁰);

С2: последовательность должна легко генерироваться;

С3: знание части открытого текста и соответствующего шифртекста (атака с известным открытым текстом) не должно позволить криптоаналитику сгенерировать всю последовательность.

Дата добавления: 2013-12-12