Что такое генератор псевдослучайных чисел. Как работает генератор на основе регистра сдвига с обратной связью. Какие существуют виды генераторов ПСЧ на регистрах сдвига. Как выбрать параметры генератора для получения последовательности максимальной длины.
Принцип работы генератора псевдослучайных чисел на регистре сдвига
Генератор псевдослучайных чисел (ГПСЧ) на основе регистра сдвига с обратной связью является одним из наиболее распространенных и эффективных способов генерации псевдослучайных последовательностей. Рассмотрим основной принцип его работы.
Ключевые компоненты такого генератора:
- Регистр сдвига — последовательность триггеров, в которых хранятся биты
- Цепь обратной связи — комбинация выходов некоторых триггеров
- Сумматор по модулю 2 (XOR) — формирует новый бит на основе обратной связи
Принцип работы заключается в следующем:
- Регистр инициализируется начальным значением (seed)
- На каждом такте содержимое регистра сдвигается вправо на 1 бит
- Новый бит формируется схемой обратной связи и записывается слева
- Выходной бит снимается с крайнего правого разряда
Таким образом генерируется псевдослучайная последовательность битов. Ее период зависит от параметров регистра и обратной связи.
Виды генераторов ПСЧ на регистрах сдвига
Существует несколько основных разновидностей генераторов псевдослучайных чисел на регистрах сдвига:
1. Линейный конгруэнтный генератор (LFSR)
Это простейший вид ГПСЧ на регистре сдвига. Обратная связь формируется как XOR нескольких разрядов регистра. Период последовательности не превышает 2^n-1, где n — длина регистра.
2. Генератор Галуа
Вместо XOR использует более сложные нелинейные функции обратной связи. Позволяет получить более длинные и качественные последовательности.
3. Фильтрованный генератор
Применяет дополнительную функцию фильтрации к выходу LFSR для улучшения статистических свойств.
Выбор параметров для получения последовательности максимальной длины
Чтобы генератор формировал последовательность максимальной длины 2^n-1, необходимо правильно выбрать полином обратной связи. Такой полином должен быть примитивным.
Основные правила выбора:
- Степень полинома равна длине регистра n
- Полином должен быть неприводимым
- Период полинома должен равняться 2^n-1
Существуют таблицы примитивных полиномов для различных значений n. Например, для n=4 подходящий полином — x^4 + x + 1.
Применение генераторов ПСЧ на регистрах сдвига
Генераторы псевдослучайных чисел на основе регистров сдвига нашли широкое применение в различных областях:
- Криптография — для генерации ключей и шифрования
- Цифровая связь — формирование расширяющих последовательностей
- Тестирование цифровых схем
- Моделирование и статистика
- Компьютерные игры и графика
Их основные преимущества — простота реализации, высокое быстродействие и хорошие статистические свойства генерируемых последовательностей.
Анализ качества генераторов ПСЧ на регистрах сдвига
Для оценки качества генераторов псевдослучайных чисел на регистрах сдвига применяются различные статистические тесты. Основные критерии качества:
- Равномерность распределения битов
- Отсутствие корреляций между битами
- Большой период повторения
- Непредсказуемость следующего бита
Наиболее распространенные тесты включают:
- Частотный монобитный тест
- Тест на последовательность одинаковых битов
- Тест на самую длинную последовательность единиц
- Тест рангов бинарных матриц
- Спектральный тест
Хороший генератор должен успешно проходить большинство статистических тестов.
Реализация генератора ПСЧ на регистре сдвига
Рассмотрим пример реализации простого 4-битного генератора псевдослучайных чисел на регистре сдвига с обратной связью:
«`python class LFSR: def __init__(self, seed, taps): self.state = seed self.taps = taps def step(self): feedback = sum([self.state & (1 << tap) for tap in self.taps]) % 2 self.state = ((self.state << 1) & 0xf) | feedback return self.state & 1 # Инициализация генератора seed = 0b1000 # Начальное значение taps = [1, 3] # Отводы для x^4 + x + 1 lfsr = LFSR(seed, taps) # Генерация последовательности sequence = [lfsr.step() for _ in range(15)] print(sequence) ```Этот код реализует 4-битный LFSR генератор с полиномом x^4 + x + 1. Он генерирует последовательность максимальной длины 15 битов, после чего цикл повторяется.
Криптографическая стойкость генераторов на регистрах сдвига
Хотя генераторы псевдослучайных чисел на регистрах сдвига широко используются в криптографии, их криптографическая стойкость имеет ряд ограничений:
- Линейность — делает их уязвимыми к атакам на основе решения системы линейных уравнений
- Малая длина регистра — ограничивает размер ключевого пространства
- Предсказуемость — зная часть выхода, можно восстановить все состояние
Для повышения криптостойкости применяются следующие методы:
- Использование нелинейных функций обратной связи
- Комбинирование нескольких регистров сдвига
- Применение дополнительных операций перемешивания выхода
- Увеличение длины регистра
Однако даже с этими улучшениями, простые генераторы на регистрах сдвига не рекомендуется использовать в серьезных криптографических приложениях без дополнительных мер защиты.
Сравнение генераторов ПСЧ на регистрах сдвига с другими типами ГПСЧ
Генераторы псевдослучайных чисел на регистрах сдвига имеют свои преимущества и недостатки по сравнению с другими типами ГПСЧ. Рассмотрим основные отличия:
Преимущества ГПСЧ на регистрах сдвига:
- Простота реализации как в аппаратном, так и в программном виде
- Высокая скорость генерации последовательности
- Возможность получения очень длинных периодов
- Хорошие статистические свойства при правильном выборе параметров
Недостатки по сравнению с другими ГПСЧ:
- Меньшая криптостойкость, чем у современных криптографических ГПСЧ
- Более предсказуемое поведение, чем у генераторов на основе хаотических систем
- Меньшая гибкость настройки параметров, чем у программных генераторов
В целом, генераторы на регистрах сдвига остаются популярным выбором для многих приложений благодаря своей простоте и эффективности. Однако для критически важных задач, требующих высокой степени непредсказуемости, часто предпочитают более сложные типы ГПСЧ.
НОУ ИНТУИТ | Лекция | Поточные шифры и генераторы псевдослучайных чисел. Часть 2
< Лекция 8 || Лекция 9: 1234 || Лекция 10 >
Аннотация: Продолжаем знакомиться с генераторами псевдослучайных чисел, используемых для поточного шифрования информации. В частности, мы рассмотрим алгоритмы генерации псевдослучайных чисел на основе сдвиговых регистров с обратной связью и RC4. Кроме того, в этой лекции мы изучим, каким образом можно использовать режимы OFB и CTR блочных шифров для получения псевдослучайных чисел.
Ключевые слова: генератор псевдослучайных чисел, шифратор, бит, сдвиговый регистр, регистр сдвига, длина, поточный шифр, linear, feedback, shift register, LFSR, обратная связь, регистр, значение, место, операции, алгоритм, GSM, битовые операции, AES, output, блок данных, байт, OFB, шифр, параметр, поток, счетчик, CTR, выход, генератор, RC4, SSL, Windows, класс, алгоритм Прима, слово, массив, таблица, перестановка, инициализация, ключ, секретный ключ, последовательный алгоритм, потоковое шифрование, random number generator, RNG, системный таймер, получатель сообщения, надежность шифра, вероятность, безопасность, канал связи, надежность, сети передачи данных, злоумышленник, криптоанализ, distribution, center, KDC, протокол обмена ключами, центр распределения ключей, доступ, сеть, симметричное шифрование
intuit.ru/2010/edi»>Цель лекции: продолжить знакомство с генераторами псевдослучайных чисел, используемых для поточного шифрования информации, а также с некоторыми режимами блочных шифров для получения псевдослучайных чисел.Генераторы псевдослучайных чисел на основе сдвиговых регистров с обратной связью
В теории кодирования и криптографии широко применяются так называемые сдвиговые регистры с обратной связью. Они использовались в аппаратуре шифрования еще до начала массового использования ЭВМ и современных высокоскоростных программных шифраторов.
Сдвиговые регистры с обратной связью могут применяться для получения потока псевдослучайных бит. Сдвиговый регистр с обратной связью состоит из двух частей: собственно n-битного сдвигового регистра и устройства обратной связи ( рис. 8.1).
Рис. 8.
Извлекать биты из сдвигового регистра можно только по одному. Если необходимо извлечь следующий бит, все биты регистра сдвигаются вправо на 1 разряд. При этом на вход регистра слева поступает новый бит, который формируется устройством обратной связи и зависит от всех остальных битов сдвигового регистра. За счет этого биты регистра изменяются по определенному закону, который и определяет схему получения ПСЧ. Понятно, что через некоторое количество тактов работы регистра последовательность битов начнет повторяться. Длина получаемой последовательности до начала ее повторения называется периодом сдвигового регистра.
Поточные шифры с использованием сдвиговых регистров достаточно долго использовались на практике. Это связано с тем, что они очень хорошо реализуются с помощью цифровой аппаратуры.
ru/2010/edi»>Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linear feedback shift register – LFSR). Обратная связь в этом устройстве реализуется просто как сумма по модулю 2 всех (или некоторых) битов регистра. Биты, которые участвуют в обратной связи, образуют отводную последовательность. Линейные сдвиговые регистры с обратной связью или их модификации часто применяется в криптографии.Для того, чтобы стало понятнее, как работает сдвиговый регистр с обратной связью, рассмотрим 4-битовый LFSR с отводом от первого и четвертого разрядов, представленный на рис. 8.2.
Рис. 8.2.
Запишем в изображенный на рисунке регистр начальное значение 1011. Вычислять последовательность внутренних состояний регистра удобно с помощью таблицы, представленной на таблица 8.1. В таблице отражены первые девять состояний регистра.
На каждом шаге все содержимое регистра сдвигается вправо на один разряд. При этом можно получить в качестве результата один бит. На освободившееся слева место поступает бит, равный результату вычисления функции обратной связи . Выходную последовательность генератора псевдослучайных бит образует последний столбец таблицы (извлекаемый бит).
Номер состояния | Внутреннее состояние регистра b4, b3, b2, b1 | Результат вычисления функции обратной связи | Извлекаемый бит ( b1 ) |
---|---|---|---|
0 | 1 0 1 1 | 0 | 1 |
1 | 0 1 0 1 | 1 | 1 |
2 | 1 0 1 0 | 1 | 0 |
1 1 0 1 | 0 | 1 | |
4 | 0 1 1 0 | 0 | 0 |
5 | 0 0 1 1 | 1 | 1 |
6 | 1 0 0 1 | 0 | 1 |
7 | 0 1 0 0 | 0 | 0 |
8 | 0 0 1 0 | 0 | 0 |
Основным недостатком генераторов псевдослучайных чисел на базе линейных сдвиговых регистров является сложность программной реализации. Сдвиги и битовые операции легко и быстро выполняются в электронной аппаратуре, поэтому в разных странах выпускаются микросхемы и устройства для поточного шифрования на базе алгоритмов с использованием сдвиговых регистров с обратной связью.
Использование режимов OFB и CTR блочных шифров для получения псевдослучайных чисел
Можно использовать любой блочный алгоритм, например AES или ГОСТ 28147-89, для поточного шифрования информации, используя режимы OFB и CTR блочных шифров.
Название режима OFB (Output FeedBack) переводится как «обратная связь по выходу».
Пусть минимальный блок данных, используемый для передачи, состоит из j бит; обычным значением является j=8 (то есть минимальной порцией передаваемых данных является 1 байт). В режиме OFB блочный шифр f на основе секретного ключа К и некоторого инициализирующего значения Y
Таким образом, для получения псевдослучайной последовательности используется схема:
Yi=f(Yi-1,K), zi=j младших бит Yi, 1<=i<=k
Если размер блока шифра равен N бит, то параметр j может принимать значения от 1 до N. Значение Y0 называют также инициализирующим вектором.
Последовательность чисел zi можно использовать в качестве гаммы для шифрования потока исходных данных, состоящего из символов хi:
в результате чего получится поток зашифрованных символов yi.
Так как значения yi не зависят от открытого текста xi, то каждый раз, используя одни и те же параметры К и Y0, мы получим одну и ту же последовательность гаммы zi. Поэтому рекомендуется менять значение ключа К для передачи каждого нового сообщения.
Расшифрование сообщений для описанного режима может производиться только с начала последовательности, так как невозможно получить произвольный элемент последовательности zi, не вычислив все предыдущие.
Основное достоинство режима OFB заключается в том, что последовательность z может быть сформирована заранее для того, чтобы быстро шифровать или расшифровывать поточные сообщения в момент их поступления. Это может быть актуально для систем, обрабатывающих данные в реальном масштабе времени.
Еще одно важное достоинство режима OFB состоит в том, что если при передаче данных произошла ошибка, то она не распространяется на следующие зашифрованные блоки, и тем самым сохраняется возможность расшифрования последующих блоков. Например, если в результате передачи по зашумленному каналу связи появился ошибочный бит в блоке yi, то это приведет к невозможности расшифрования только этого блока и получения одного блока исходных данных xi. Дальнейшая последовательность блоков будет расшифрована корректно.
Название режима CTR происходит от слова «CounTeR» — «счетчик». Этот режим является модификацией режима OFB. Единственное отличие от OFB заключается в том, что в режиме CTR шифруется не предыдущий выход шифра, а счетчик, увеличиваемый на каждом шаге на 1. Первоначальное значение счетчика определяется некоторым инициализирующим значением Y0. Общая формула выглядит следующим образом:
Yi=f(Yi-1+1,K), zi=j старших бит Yi
Преимущество режима CTR состоит в том, что любой элемент последовательности z может быть вычислен непосредственно. Этот факт связан с тем, что на каждом шаге Yi увеличивается на единицу, и, следовательно, если нам известен номер шага i, то значение Yi можно вычислить непосредственно, зная Y0 и i по формуле:
Yi=f(Y0+i,K),intuit.ru/2010/edi»>Это дает возможность шифровать и дешифровать любые фрагменты сообщения независимо друг от друга.
Дальше >>
< Лекция 8 || Лекция 9: 1234 || Лекция 10 >