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

Для генерации истинно случайных последовательностей (РРСП) используются физические генераторы.

Это электронные устройства, в которых используются естественные случайности реального мира – шумы в результате переходных процессов в полупроводниковых диодах, тепловые шумы высокомных резисторов, радиоактивный распад и т.д.

Один из принципов работы физического генератора – наблюдение событий, когда шум превышает некоторый порог.

Измерим время между первым событием и вторым, затем – время между вторым событием и третьим.

Если , то полагаем выход генератора равным 1; если , то выход равен 0, и так далее…

Существенной проблемой таких генераторов случайных данных является наличие отклонений от равновероятности и корреляций в сгенерированной последовательности.

Как с этим бороться?

А)Пусть вероятность появления нуля смещена на , т.е. может быть записана как .

Сложение по двух одинаково распределенных независимых битов даст: . При сложении четырех битов получим: . Процесс сходится к равновероятному распределению битов.

Б)Другой подход. Пусть распределение единиц и нулей в последовательности есть величины и соответственно.

Преобразуем последовательные пары битов:

– если это одинаковые биты, то отбросим их и рассмотрим следующую пару;

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

Данный метод позволяет решить проблему смещения, сохранив свойства случайности источника (с некоторой потерей в объеме данных).

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

Физические генераторы получили широкое распространение после создания микропроцессоров, имеющих встроенные шумовые элементы.

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

В силу названных причин при построении программных и программно-аппаратных средств криптографической защиты информации широкое распространение получили генераторы ПСП.

1. Наиболее простым программным датчиком псевдослучайных чисел является линейный конгруэнтный генератор (ЛКГ), который описывается рекуррентным уравнением вида , где – случайное начальное значение, – множитель, – приращение, – модуль.

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

– числа и взаимно просты: НОД ;

– кратно любому простому , делящему ;

– кратно 4, если кратно 4.

Для реализации ЛКГ на персональных компьютерах с учетом их разрядной сетки нередко используется модуль . При этом наиболее качественные статистические свойства ПСП достигаются для константы .

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

Недостатком ЛКГ в плане их использования для создания поточных шифров является предсказуемость выходных последовательностей.

2. Регистры сдвига с линейной обратной связью (Linear Feedback Shift Registers – LFSR) включают собственно регистр сдвига и схему вычисления функции обратной связи (tap sequence) – см. рис. 4.2.

Рис. 4.2 Регистр сдвига с линейной обратной связью (LFSR)

На схеме содержимое регистра – последовательность битов – сдвигается с приходом тактового импульса (clock pulse) на один разряд вправо. Бит самого младшего разряда считается выходом LFSR в данном такте работы. Значение самого старшего разряда при этом является результатом сложения по модулю 2 (функция XOR) разрядов (точек съема) обратной связи. Генерируемая последовательность называетсялинейной рекуррентой.

Теоретически, -битный LFSR может сгенерировать псевдослучайную последовательность с периодом бит. Такие LFSR называютсярегистрами максимального периода.

Для этого регистр сдвига должен побывать во всех ненулевых внутренних состояниях.

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

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

Полином называется минимальным полиномом соответствующей рекуррентной последовательности.

Для каждой конечной (или периодической) последовательности можно указать LFSR, который, при некотором начальном заполнении, порождает эту последовательность.

Среди всех таких регистров, существует регистр минимальной длины .

Величина называется линейной сложностью последовательности .

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

Примитивный полином степени над полем вычетов по модулю два – это неприводимый полином, который делит , но не делит для любых : .

Теорема. Для того, чтобы последовательность, порожденная LFSR имела максимальный период, необходимо и достаточно, чтобы ее минимальный полином, был примитивным полиномом по модулю 2.

Например, примитивным полиномом является .

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

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

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

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

Наиболее эффективные решения были получены на основе составных генераторов.

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

Существуют 2 основных подхода к конструированию соответствующих генераторов:

1) системно-теоретический подход;

2) сложностно-теоретический подход;

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

На основе такого подхода Рюппелем сформулирован следующий набор критериев для таких генераторов:

1.Большой период выходной последовательности, отсутствие повторений.

2. Высокая линейная сложность выходной последовательности.

3. Неотличимость от РРСП по статистическим критериям.

4. Перемешивание: любой бит выходной последовательности должен быть сложным преобразованием всех или большинства бит начального состояния.

5. Рассеивание: изменение одного бита начального состояния должно кардинально изменять выходную последовательность.

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

Примером удачного построения составного генератора с точки зрения повышения линейной сложности является каскад Голмана (рис. 4.3). Каскад Голмана включает несколько регистров сдвига LFSR. Первый регистр движется равномерно с шагом 1. Сдвиг каждого последующего регистра управляется предыдущим так, что изменение состояния последующего регистра в такте происходит, если в такте с предыдущего регистра снимается 1. Иначе, состояние последующего регистра не изменяется.

Если все LFSR – длины , то линейная сложность системы с регистрами равна .

Рис. 4.3. Каскад Голлмана

Типичным примером комбинирования регистров сдвига является схема чередующегося «старт-стоп» генератора (Alternating Stop-and-Go Generator).

У этого генератора большой период и большая линейная сложность.

В «старт-стоп» генераторе (рис. 4.4) используется три линейных регистра сдвига различной длины. LFSR-2 меняет состояние, если выход LFSR-1 равен 1; LFSR-3 меняет состояние в противном случае. Результат генератора есть сложение по модулю 2 выходов регистров LFSR-2, LFSR-3.

Рис. 4.4. Чередующийся старт-стопный генератор

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

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

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

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

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

Примером генераторана основе однонаправленной функции может служить генератор на основе алгоритма RSA с параметрами вида .

Здесь , где – секретные большие, неравные простые числа,

– показатель степенной функции, НОД , .

Результат работы одного такта генератора – младший бит . Стойкость этого генератора не ниже стойкости RSA. Если достаточно большое, то генератор обеспечивает практическую стойкость.

BBS-генератор. Математическая теория этого генератора – квадратичные вычеты по составному модулю .

Параметры генератора: секретные большие, неравные простые числа, , такие, что, ; число ; – случайный секретный вычет по модулю .

Первым шагом вычисляется начальное состояние .

В основном цикле елемент ПСП з номером равен , т.е -ым псевдослучайным числом является младший бит числа .

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

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

Mod 987.

Фокус заключается в том, что берется число и осуществляется возведение в квадрат.

432² = 186624; 186624 mod 987 = 81; 432⁴ mod 987 = 81² mod 987 = 639
432⁸ -> 639² mod 987 -> 690 …. 432⁵¹² -> 858
так как 678= 512+128+32+4+2, то:
432⁶⁷⁸->(81)(639)….(858) -> 204

Вычисления с использованием показателя включают в себя ограниченное число умножений. Если числа содержат несколько сотен цифр, необходимы специальные подпрограммы для выполнения таких вычислений. Рассмотрим последовательность степеней 2ⁿ mod 11:

2 4 8 5 10 9 7 3 6 1

Здесь числа от 1 до 10 появляются в виде псевдослучайной последовательности.

Теорема 2

Пусть p является простым числом. Существует такое a, что для каждого 1£ b £ p-1
существует такое1£ x £ p-1, что a^xº _pb.

Степени 2 mod 7 равны 2, 4, 1. Далее числа повторяются, а числа 3, 5, или 6 не могут быть получены никогда. Рассмотрим некоторые следствия этой теоремы.

Следствие 4.Пусть a соответствует требованиям теоремы 2, тогда a^p-1 º _p1.
Следствие 5.Для любого b ¹ 0, b^p-1 º _p1.
Следствие 6. Если x º _(p-1)y, тогда b^x º _pb^y

Лемма
Пусть b ¹ 0, d наименьшее положительное число, такое что b^d º_p1. Тогда для любогос>0cb^c º_p1 dделит c без остатка. В частности для следствия5, dделитp-1без остатка.

Согласно теореме 2, если p простое число, существует такое a, при котором равенство a^x º _pb имеет решение для любогоb¹ 0.Такое значениеaназываетсяпримитивным корнем p, а x называется дискретным логарифмом b. Получение b при заданных a и x относительно просто, определение же x по a и b заметно сложнее. Многие современные системы шифрования основываются на факте, что никаких эффективных путей вычисления дискретных логарифмов не найдено. Никакого эффективного метода определения примитивных корней также неизвестно. Однако часто возможно найти примитивные корни в некоторых специальных случаях. Возьмем p=1223. p-1=2*13*47. Согласно лемме, если a не примитивный корень, тогда мы либо имеем a²⁶, a⁹⁴ или
a⁶¹¹ º ₁₂₂₃1. a=2иa=3не годятся, ноa=5соответствует всем трем условиям, таким образом, это значение является примитивным корнем. Мы могли бы сказать, что a=4 не может быть признано примитивным корнем без проверки.

Легко показать, что если a примитивный корень, a^x примитивный корень в том и только том случае, если (x,p-1)=1. В этом примере это означает, что число примитивных корней равно

1222*(1/2)*(12/13)*(46/47)=552

Таким образом, если мы выберем а произвольно, вероятность того, что это будет примитивный корень равна ~.45. Выбирая а наугад и тестируя, можно сравнительно быстро найти примитивный корень.

Современные системы шифрования используют асимметричные алгоритмы с открытым и секретным ключами, где нет проблемы безопасной транспортировки ключа. К числу таких систем относится алгоритм rsa (rivest-shamir-adleman - разработчики этой системы – Рональд Ривест, Ади Шамир и Леонард Адлеман, 1977 год), базирующийся на разложение больших чисел на множители.

Другие сходные алгоритмы используют целочисленные логарифмы и вычисление корней уравнений. В отличие от других систем эти позволяют кроме шифрования эффективно идентифицировать отправителя (электронная подпись). К системам с открытым ключом предъявляются следующие требования:

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

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