Требования к ключам

Алгоритмы данного типа представляют собой способ шифрования, в котором для шифрования и дешифрования применяется один и тот же криптографический ключ. Ключ алгоритма должен сохраняться в секрете обеими сторонами.

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

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

ЛРР и его свойства

Рассмотрим сдвиговый регистр с обратной связью (Linear Feedback Shift Register, сокращённо LFSR) — логическое устройство, схема которого изображена на рис. 1.2.

Сдвиговый регистр представляет собой последовательность битов. (Количество битов определяется длиной сдвигового регистра. Если длина равна n битам, то регистр называется n-битовым сдвиговым регистром.) Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит.

Рисунок 1.2 — Схема ЛРР В качестве начального содержимого регистра битов (S m _ 1, S m _ 2, …, S 1, S 0) 2 задается случайный (псевдослучайный) двоичный m _ разрядный вектор (запрещенной является только нулевая комбинация).

Бит обратной связи ЛРР формируется согласно следующему соотношению:

гдеSjсодержимое ячеек регистра;

ciкоэффициенты образующего полинома (причем c 0 = 1).

ЛРР состоит из n ячеек памяти, двоичные состояния которых в момент времени t = 0, 1, … характеризуются значениями S0(t), S1(t), …, Sn-1(t) A = {0, 1}. Выходы ячеек памяти связаны не только последовательно друг с другом, но и с сумматорами в соответствии с коэффициентами передачи a0, a1, …, an-1 A: если ai = 1, то значение Si (t) i-ой ячейки передается на один из входов i-го сумматора; если же ai = 0, то такая передача отсутствует. Обычно коэффициенты передачи задаются с помощью полинома:

Состояние ЛРР в текущий момент времени t задается двоичным n-вектор-столбцом S (t) = (Sn-1(t), …, S0(t))'.

Содержание ячеек ЛРР с течением времени изменяется следующим образом, определяя тем самым динамику состояний ЛРР:

Текущие значения нулевой ячейки регистра используются в качестве элементов порождаемой ЛРР двоичной псевдослучайной последовательности Sy = S0(t) (см. рис. 3).

Дополнительно кратко рассмотрим основные свойства ЛРР и ЛРПМ (на периоде). 3].

Функционирование ЛРР однозначно определяется используемым образующим полиномом f (t) :

f (t) = c m t m + c m — 1 t m _ 1 +. .. + c 2 t 2 + c 1 t 1 + 1, f (t) Z 2 [t ] .

Здесь mстепень полинома (deg (f (t)));

ci коэффициенты ci {0, 1}, c0 = 1.

Период ЛРПМ (линейной рекуррентной последовательности максимального периода) T = 2 m — 1.

ЛРПМ может быть получена только при использовании примитивного образующего полинома f (t). В противном случае период формируемой последовательности будет заведомо меньшим.

Расстояние единственности l 0 = 2 m .

То есть закон функционирования ЛРР (вид образующего полинома) может быть однозначно восстановлен по 2m безошибочно полученным подряд расположенным битам ЛРПМ. Это и следующее (связанное с ним) свойство являются основными недостатками ЛРР, из — за которых они не могут использоваться в изолированном виде в качестве ГКП.

Структурная скрытность Sc = l 0 / T = 2m / (2 m — 1) .

То есть структурная скрытность для ЛРР достаточно низкая закон функционирования ЛРР легко раскрываем.

Количество нулей (на периоде ЛРПМ) на один меньше количества единиц: N0 = 2 m — 1 — 1 и N1 = 2 m — 1 соответственно.

Длина максимальной серии из единиц m, из нулей (m _ 1).

Цикличность: циклом называют непрерывную последовательность одинаковых двоичных чисел. Появление иной двоичной цифры автоматически начинает новый цикл. Длина цикла равна количеству одинаковых цифр в нем. Необходимо, чтобы половина всех «полосок» (подряд идущих идентичных компонентов последовательности) имела длину 1, одна четвертая — длину 2, одна восьмая — длину 3 и т. д. Свойства псевдослучайности: из общего количества серий на периоде ЛРПМ.

• 1 / 2 всех длин имеют длину 1;
• 1 / 4 длину 2;

.. .

1 / 2 k длину k.

На периоде ЛРПМ по одному разу встречаются все m — разрядные комбинации от 1 до 2 m — 1 (свойство «окна»).

Количество изоморфизмов ЛРПМ N И = (T) / m (здесь (T) значение функции Эйлера) .

То есть для данной степени m существует N И примитивных полиномов и, соответственно, N И ЛРПМ, отличающихся тонкой структурой и не являющихся циклическими сдвигами друг относительно друга.

Сумма двух ЛРПМ, отличающихся только циклическим сдвигом, также является ЛРПМ, отличающейся от двух исходных только циклическим сдвигом.

То есть комбинирование (линейное) нескольких отрезков одной и той же ЛРПМ не дает увеличения структурной скрытности.

Примитивный (базовый) многочлен степени n по модулю 2 — это неприводимый многочлен, который является делителем, но не является делителем для всех d, являющихся делителями .

Неприводимый многочлен степени n нельзя представить в виде умножения никаких других многочленов, кроме него самого и единичного.

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

Таким образом, не существует проблемы выбора примитивного полинома обратной связи h (x) для ЛРР достаточно большой длины n, т. е. такого полинома, который обеспечит достаточно большой период выходной последовательности T = 2n — 1 при любом начальном заполнении. Отметим также, что с целью сокращения числа отводов в конструкции ЛРР среди примитивных полиномов данной степени используют полиномы с наименьшим числом ненулевых коэффициентов.

Выходная последовательность линейного рекуррентного регистра сдвига, реализованного на примитивном полиноме, обладает свойствами «баланса» и «окна». Свойство «баланса» состоит в том, что число нулей на периоде T = 2n — 1 точно равно 2n — 1 — 1, а число единиц равно 2n — 1. Свойство «окна» гарантирует, что во всех 2n — 1 «окнах» из n символов, расположенных друг за другом на периоде, все возможные 2n — 1 ненулевые двоичные последовательности появятся только по одному разу.

Перечисленные свойства ЛРР, а также некоторые другие, приводят к тому, что последовательность символов на выходе ЛРР может быть принята за чисто случайную. Она практически не отличается от последовательностей, получаемых при бросании симметричной монеты. Однако в действительности выходная последовательность ЛРР является строго детерминированной. Она однозначно задана начальным заполнением aj {0,1}, j = 0, 1,…, n — 1, и полиномом обратной связи h (x), в силу чего ее называют псевдослучайной последовательностью (ПСП).