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

Размещено на http://www.allbest.ru/

КУРСОВАЯ РАБОТА

ГЕНЕРАТОРЫ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Содержание

Введение

1. Классификация генераторов ключевых последовательностей

1.1 Основные требования к средствам формирования случайных и псевдослучайных последовательностей

1.2 Классификация генераторов псевдослучайных последовательностей

1.2.1 RSA-алгоритм генерации псевдослучайных последовательностей

1.2.2 Алгоритм Блюма -- Блюма -- Шуба

1.3Физические генераторы случайных последовательностей

1.3.1 Генератор Гряда

1.4 Квантовые генераторы случайных чисел

Введение

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

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

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

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

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

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

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

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

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

для зашифрования ключей

для зашифрования данных

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

1. Классификация генераторов ключевых последовательностей

1.1 Основные требования к средствам формирования случайных и псевдослучайных последовательностей

В качестве средств формирования случайных и псевдослучайных последовательностей используют устройства или алгоритмы, называют генераторами случайных и псевдослучайных последовательностей. Генератором случайных последовательностей (ГВС) называют устройство или алгоритм, который формирует на своем выходе последовательность статистически независимых символов с основанием алфавита m [1].

Генератором псевдослучайных последовательностей (ГПВП) называют детерминированные алгоритмом, совокупность алгоритмов или совокупность алгоритмов и средств, для заданной последовательности длиной k формируют при своей работе последовательность символов длиной l >> k, которая обладает большинством свойств случайной последовательности. На приведены упрощенную схему генератора псевдослучайных последовательностей, где:

1 - генератор случайной последовательности длиной k;

2 - схема формирования начальных значений k и П параметров ГПВП;

3 - генератор псевдослучайных символов;

4 - логика обратной связи.[2,3]

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

В общем виде псевдослучайную последовательность (ПСП) Y можно задать как зависимость:

(1.1)

от начальных значений ключа К и параметров П, а также случайных последовательностей. При этом обратная связь Y приводит к воздействию его на параметры, начальные значения и работу генератора 3.[3]

Основным назначением ГПВП и ГВС в криптографии является формирование ключей, начальных значений ключей, параметров и синхромаркеров [4,5].

Свойства ПВП оценивают с использованием ряда количественных показателей. Основными показателями являются: Период l (длина) ПВП

Основа алфавита m;

Вероятность перекрытия в пространстве или во времени двух сегментов и, то есть в разных абонентов или у одного абонента в течение времени;

Структурная скрытность (эквивалентная сложность) последовательности;

Количество (энтропия источника) ключей для случая, когда ГПВП используется как источник ключей;

Расстояние равнозначности конкретной последовательности;

Безопасное время ГПВП;

Сложность формирования последовательности;

Длина параметров обратной связи B2 и B3;

Свойства случайности, ривноймовирности, независимости и однородности.[6,7]

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

1.2 Классификация генераторов псевдослучайных последовательностей

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

Можно выделить следующие задачи, требующие решения при построении компьютерных систем (КС) в защищенном исполнении:

обеспечение работоспособности компонентов КС и системы в целом при наличии случайных и умышленных деструктивных воздействий;

обеспечение секретности и конфиденциальности информации или наиболее важной ее части; защита от НСД;

обеспечение аутентичности информации (целостности, подлинности и пр.

обеспечение юридической значимости пересылаемых электронных документов;

обеспечение аутентичности участников информационного обмена;

обеспечение неотслеживаемости информационных потоков в системе;

защита прав собственников информации.

Перечисленные задачи - это объекты исследований таких научных дисциплин, как техническая диагностика, криптология, стеганография, теория кодирования, информационная безопасность. Все они без исключения решаются стохастическими методами. Иначе говоря, средства генерации качественных ПСП - это то, что объединяет все вышеперечисленные задачи, позволяя подойти к вопросам их решения с единых исходных позиций[9]

1.2.1 RSA-алгоритм генерации псевдослучайных последовательностей

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

1) Сгенерировать достаточно большие простые различные числа p,q и вычислить числа , . Выбирать случайное целое число k, , взаимно простое с ц, так, что НОД(k, ц) = 1.

2) Выбрать случайное целое - стартовое значение - .

3) Для выполнить шаги 4,5.

4) Вычислить

5) Вычислить - самый младший бит числа в двоичном представлении.

6) Сформировать выходную последовательность

Недостатком RSA - алгоритма является его невысокое быстродействие при реализации на универсальных компьютерах, вызванное большими затратами машинного времени при выполнении модулярного умножения на шаге 4.[10]

1.2.2 Алгоритм Блюма -- Блюма -- Шуба

Алгоритм Блюма - Блюма - Шуба- это генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом (Blum et al, 1986).

BBS выглядит так:

(1.2)

где M = pq является произведением двух больших простых p и q. На каждом шаге алгоритма выходные данные получаются из xn путём взятия либо бита четности, либо одного или больше наименее значимых бит xn.
Два простых числа, p и q, Должны быть оба Сравнимые с 3 по модулю 4 (это гарантирует, что каждый квадратичные вычет имеет один квадратный корень, который также является квадратичным вычет) и наибольший общий делитель НОД должен быть мал (это увеличивает длину цикла).

Интересной особенностью этого алгоритма является то, что для получения xn необязательно вычислить все n - 1 предыдущих чисел, если известно начальное состояние генератора x0 и числа p и q. n-ное значение может быть. псевдослучайный последовательность алгоритм

Этот генератор подходит для криптографии, но не для моделирования, потому что он недостаточно быстр. Однако, он имеет необычно Высокую стойкость, которая обеспечивается качеством генератора Исходя из вычислительной сложности задачи факторизации чисел. Когда простые числа выбраны осторожно, и O (loglogM) бит каждого xn являются выходными данными, тогда предел Взятый как M быстро растёт, и вычисление выходных бит будет настолько же трудно, как и факторизация M.

Если факторизация целых чисел так трудна (как предполагается), тогда BBS с большим M будет иметь выход, свободный от любых неслучайных узоров, Которые могут быть выявлены при достаточном объёме вычислений. Однако, возможно появление быстрого алгоритма для факторизации, и вследствие этого BBS НЕ является гарантированно надёжным.

1.3 Физические генераторы случайных последовательностей

Составляющим или основным элементом генераторов ключей является физический генератор случайных чисел. Фи-зычный генератор случайных чисел (ФГВЧ) -устройство , который генерирует случайные числа на основе физического процесса (тепловой шум, фотоэлектрический эффект или квантовые явления), который является абсолютно непредсказуемым. В некоторых источниках ФГВЧ называют недетерминированные генератором случайных чисел (НГВЧ) или генератором случайных чисел (ГСЧ).

Анализ показал, что в современных криптографических системах скорость генерации случайных последовательностей должна превышать 1Мбит / с. Такие параметры могут быть реализованы на основе эл-охранительных датчиков шума с широким спектром частот [1,5]. Случайные изменения параметров (тепловой шум) наблюдаются во всех электронных компонентах при температурах выше абсолютного нуля по Кельвином. Потому как физические датчики шума могут быть использованы любые электронные компоненты.

Полупроводниковый шумовой диод - это полу-проводной прибор, являющийся источником шума из заданной спектральной плотностью в определенном диапазоне частот. Например, датчики шума на основе кремний диодов Зенеровського пробой (стабилитроны) генерируют случайный сигнал с равномерным спектром от единиц Гц до десятков МГц и амплитудами в десятки мВ. Такие приборы разработаны и выпускаются как специализированные шумовые диоды с Зенеровським пробоем (например, КГ401). Они при напряжении 8-9 В и токе от 50 до 100 мкА генерируют широкий спектр (до десятков МГц) случайных импульсов с амплитудами от 0,1 до 1В. Потребляемая мощность таких датчиков шума менее 1 мВт при напряжении от 10 до 20 В, что позволяет легко встраивать их в вычислительные системы. Малогабаритные и экономических показания датчиков шума на основе шумовых диодов с Зенеровским пробоем являются одними из самых-лучших при реализации в интегральном исполнении на одном кристалле с вычислительной системой.[11]

Экспериментальные исследования свойств случайных последовательностей аппаратного генератора электронного ключа «Кристалл-1»

Одними из функций устройства электронный ключ (ЭК) «Кристалл-1» являются:

Генерация личных и открытых ключей для алгоритма ЭЦП;

Генерация личных и открытых ключей для протокола распределения ключей;

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

Для тестирования статистических свойств вы- случайно последовательностей ЭК «Кристалл-1» использовалась методика NIST STS [4], рекомендованная Национальным институтом по стандартизации и тех-нологии США, разработана для статистического тестирование алгоритмов-кандидатов на AES (NIST SP 800 -22). Пакет NIST STS включает в себя 16 статистических тестов. Эти тесты используются для проверки гипотезы о случайности двоичных Прогрессивных носителей произвольной длины, порождаемых ГВС или ГПВП. По совокупности результатов всех тестов при-имеется решение о том, будет ли заданная Прогрессивный носитель нулей и единиц «случайной» или нет.[12]

С использованием методики NIST STS была осуществлена тестирования случайной последовательности ГСЧ ЭК «Кристалл-1 (Д)» и ГСЧ ЭК «Кристалл-1 (Т)», а также проведено сравнение свойств этих последовательностей со свойствами ПВП генератора псевдослучайных цифр BBS [4] (тестовая выборка NIST). [13]

1.3.1 Генератор Гряда

Генератор случайных чисел "Гряда-1" является аппаратным средством формирования, который встраивается, случайных чисел на основе использования физически случайных процессов.

Аппаратный датчик случайных последовательностей "Гряда-1" предназначен для работы в составе персонального компьютера, имеющего слот расширения ISA 16. Датчик не использует линии запроса на прерывание (IRQ), каналы прямого доступа к памяти (DMA) и имеет фиксированные адреса портов ввода / вывода (034Аh и 0348h), поэтому перед установкой не нужно дополнительное настройки датчика. Перед установкой отключите питания персонального компьютера. Раскройте корпус системного блока и в свободный слот шины расширения ISA 16 вставьте и надежно закрепите плату "Гряда-1", после чего установите на место крышку корпуса компьютера.

Вместе с аппаратным датчиком случайных чисел "Гряда-1" поставляется программное обеспечение для работы в операционных системах Windows 95 и Windows 98. Создайте рабочий каталог и скопируйте в него файлы rnd1.exe и rnd1с.exe с дискеты, которая поставляется вместе с аппаратным датчиком. Следует отметить, что обе утилиты ориентированы на программный интерфейс Win32 и не будут функционировать под управлением операционных систем MS DOS и Windows 3.1.

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

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

Если утилита запущена без параметров, то будет выведена краткая справка об использовании. При возникновении ошибок (неверное имя файла, блокировки файла вторым процессом) будет выведена соответствующее сообщение.

Запустите програму. В появившись окно "Random number generator Gryada-1" в меню Options / Language выберите предпочтительный язык интерфейса. Ниже описание приводится для интерфейса на русском языке. Задайте следующие параметры:

В поле "Путь к файлу с выборкой" укажите файл, где должна быть сохранена выборка (возможно включение полный или относительный пути во имя файла). Если файл уже существует, его содержимое будет заменено новой выборке случайных чисел. Если указанного файла нет, он будет создан. Нажав на кнопку "Выбрать ..." или выбрав пункт меню Файл / Выбрать файл ..., Вы можете задать имя с помощью стандартного диалога Windows для выбора файла.

В поле "Размер выборки" укажите размер выборки в байтах (десятичное число, находящееся в диапазоне от 1 до 2147483648).

Нажмите кнопку "Запуск"

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

Интерфейс утилиты позволяет сохранять размер выборки, путь и имя файла с выборкой, и язык интерфейса, используемые в текущем сеансе работы. Если вы хотите, чтобы эти параметры были доступны в следующем сеансе работы, убедитесь, что в меню Настройка / Сохранить отмечен параметр.

Для окончания работы с утилитой нажмите кнопку "Выход" или выберите пункт меню Файл / Выход. При этом отмечены в меню Настройка / Сохранить параметры будут сохранены и загружены в следующем сеансе работ

1.4 Квантовые генераторы случайных чисел

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

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

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

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

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

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

Свет состоит из элементарных «частиц», называемых фотонами. В определенной ситуации фотоны демонстрируют случайное поведение. Одна из таких ситуаций, которая очень хорошо подходит для генерации бинарных случайных чисел, заключается в следующем. На полупрозрачное зеркало направляются фотоны, генерируемые источником одиночных фотонов. Фотон может отразиться, а может пройти через полупрозрачное зеркало с вероятностью 50%. Выбор, который «делает» фотон, абсолютно случаен. На выходе системы стоят два счетчика фотонов, регистрирующих прошедшие и отраженные фотоны и формирующих выходные электрические сигналы.

Кроме оптической части - «сердца» генератора случайных чисел - система включает в себя подсистему, которая управляет синхронизацией, а также сбором и обработкой данных, поступающих с детекторов, выполняет статистические и аппаратные проверки последовательности. Как отмечалось выше, физические процессы трудно точно сбалансировать. Таким образом, трудно гарантировать, что вероятность записи 0 и 1 в точности равна 50%. Например, в генераторе Quantis разница между этими двумя вероятностями меньше 10%, что эквивалентно вероятностям от 45% до 55%. Поскольку это смещение не может быть приемлемым для некоторых приложений, то обязательно выполняется алгоритм пост-обработки для удаления смещения в последовательности случайных чисел. Как уже говорилось выше, одним из главных преимуществ квантовых генераторов случайных чисел на оптических фотонах является то, что они основаны на простом и принципиально случайном процессе, который легко моделировать и контролировать. Подобные квантовые генераторы имеют высокую скорость выходного потока - до 10-16 Мбит/с, - при которой не наблюдается никаких корреляций и выполняются все статистические тесты. Еще одним примером является генератор случайных чисел с использованием полупроводникового лазера с короткими и резкими пиками интенсивности. Лазер пропускается через среду с обратной связью с задержкой, то есть интенсивность излучения на выходе определяется интенсивностью сигнала на входе и состоянием среды, которое зависит от интенсивности на входе. Известно, что изменение интенсивности - процесс квазипериодический, то есть с течением времени почти повторяется, поэтому напрямую использовать его в качестве генератора случайных чисел нельзя.

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

Результат каждого измерения записывается в строку длиной в 8 бит. Он вычитается из значения предыдущего измерения, а результат усекается. Таким образом, удается избавиться от квазипериодичности и добиться генерации случайного потока нулей и единиц со скоростью примерно 12.5 Гигабит в секунду.

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