Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей icon

Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей




Скачати 81.32 Kb.
НазваЛекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей
Дата конвертації24.11.2012
Розмір81.32 Kb.
ТипЛекция
1. /Лекции 1_5/Вопросы к лекции 4.doc
2. /Лекции 1_5/Вопросы к лекции 5.doc
3. /Лекции 1_5/Лекция 1.doc
4. /Лекции 1_5/Лекция 2.doc
5. /Лекции 1_5/Лекция 3.doc
6. /Лекции 1_5/Лекция 4.doc
7. /Лекции 1_5/Лекция 5.doc
Лекции 4 в чем заключается свойство непредсказуемости равномерно распределенной случайной последовательности?
Лекции 5 Как устроен линейный конгруэнтный генератор ррсп?
Лекция основные понятия и задачи криптологии > Предмет криптологии, криптография и криптоанализ История криптографии ровесница истории письменности
Лекция элементарные шифры и их свойства
Лекция модели угроз безопасности криптосистем одним из важнейших направлений исследований в теоретической криптографии является создание стойких криптосистем
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации
Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей

Лекция 5. ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ И МЕТОДЫ ИХ ГЕНЕРАЦИИ




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


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

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

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

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

Если , то полагаем выход генератора равным 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-генератор. Математическая теория этого генератора – квадратичные вычеты по составному модулю .

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

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

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

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

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



Схожі:

Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconРектор Академии Астрологии М. Б. Левин формальные методы прогнозирования событий и ректификации натальной карты лекция
В этом отношении книга С. Айзина представляет собой отрадное исключение. Методы, которые проанализированы известны, известны в астрологии...
Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconДокументи
1. /Параконная Н.К._Рег_ональна економ_ка/Лекции/Лекция 1 Вводная.doc
2. /Параконная...

Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconДокументи
1. /Аннотация 2.doc
2. /Аннотация.doc
Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconГенераторы

Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconДокументи
1. /1/Билеты по курсу.doc
2. /1/Вступительная...

Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconДокументи
1. /Генераторы.pdf
Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconСамостоятельная работа по теме: «Предел последовательности»

Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconДокументи
1. /Лекция ь1 .doc
2. /Лекция ь1 Общие вопросы...

Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconТехнологии вермикультивирования в Китае
В китае используются различные методы культивирования дождевых червей в зависимости от климатических условий (ямы в земле, бурты,...
Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconДокументи
1. /Л.Микроек/1. Вводная лекция/Лекция 1.doc
2. /Л.Микроек/1....

Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей iconЛекция №2а 1 Основные виды деформаций 1 Закон Гука при растяжении (сжатии) 2 Испытания материалов на растяжение 3 Задачи к практическому занятию 11 Лекция №2а
Реальные тела могут деформироваться, т е изменять свою форму и размеры. Деформация тел происходит вследствии нагружения их внешними...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи