Виды генераторов случайных чисел (ГСЧ)
Исторически потребность в случайных числах возникла в связи с проведением выборочных наблюдений в место сплошных. Интерес к проблеме получения случайных чисел возрос во время появления первых ЭВМ, так как ЭВМ расширила возможности использования случайных чисел.
Для получения случайных чисел можно использовать различные способы. В общем случае все методы генерирования случайных чисел можно разделить на:
· Аппаратные;
· Биометрические;
· Программные.
За эталон генератора случайных чисел принят такой генератор, который порождает последовательность случайных чисел с равномерным законом распределения в интервале (0;1). За одно обращение данный генератор возвращает одно случайное число. Если наблюдать такой ГСЧ достаточно длительное время, то окажется, что, например, в каждый из десяти интервалов (0;0.1),(0.1;0.2),(0.2;0.3),…,(0.9;1) попадет практически одинаковое количество случайных чисел – то есть они будут распределены равномерно по всему интервалу (0;1). Если генератор выдает числа, смещенные в какую-либо часть интервала(одни числа выпадают чаще других), то результат решения задачи, решаемой статистическим методом, может оказаться неверным. Поэтому проблема построения хорошего генератора действительно случайных и действительно равномерно распределенных чисел стоит очень строго.
Аппаратные ГСЧ
Аппаратные ГСЧ (или по-другому их называют физические) представляют собой устройства, преобразующие в цифровую форму какой-либо параметр окружающей среды или физического процесса. Параметр и процесс выбираются таким образом, чтобы обеспечить хорошую «случайность» значений при считывании. Примером аппаратного генератора может служить цифровая схема с неопределенным состоянием. Схема ГСЧ состоит из пары инверторов, выход каждого из которых подключен к входу другого. Если на выходе у первого инвертора будет логический низкий уровень сигнала, то второй инвертор получит этот уровень на входе и, соответственно, выдаст высокий уровень сигнала на выходе и наоборот. Дополнительно в цепь добавлены два транзистора, включение которых дает на входе и выходе обоих инверторов логический высокий сигнал. Каждый период тактирующего сигнала, при отключении транзисторов, оба инвертора стремятся принять противоположное положение, т.е. одно из двух устойчивых состояний, генерируя при этом один случайный бит. Такой генератор обладает одной из самых высоких скоростей выходного потока (до 3Гбит/с) и низким энергопотреблением.
|
|
|
Очень часто используется паразитные процессы в электронике (токи утечки, туннельный пробой диодов, цифровой шум видеокамеры, шумы на микрофонном входе звуковой карты и т.п.). Формируемая таким образом последовательность чисел, как правило, носит абсолютно случайный характер и не может быть воспроизведена заново по желанию пользователя.
|
|
|
| Источ-ник шума |
| Усилитель |
| Двух-сторонний ограничитель |
| Кла-пан |
| Счетчик |
| Буфер |
| Тактовые импульсы |
| Случайные числа |
Рассмотрим примераппаратного генератора на основе физического генератора шума. Структурная схема генератора показана на рис. 1
Рисунок 1. Структурная схема аппаратного ГСЧ
В аппаратных ГСЧ источником случайности является какой-либо физический процесс. Наиболее часто для этих целей используют флуктуационные шумы, возникающие в полупроводниковых приборах. Источником флуктуационных шумов может быть шумовой диод, представляющий собой стабилитрон, рабочий режим которого выбран в неустойчивости области p-nперехода. Под действием многих факторов (изминение температуры, давления, влажности, питающего напряжения) на выходе диода появляются слабые флуктуационные колебания напряжения (флуктуационный шум). Эти колебания усиливаются и подаются на двухсторонний ограничитель амплитуды. На выходе ограничителя имеем двухполярную последовательность импульсов постоянной амплитуды и переменной (случайной) длительности. Последовательность этих импульсов управляет электронным клапаном. На второй вход электронного клапана поступает регулярная последовательность тактовых импульсов. В течении положительной полуволны сигнала на выходе на выходе ограничителя клапан открывается, и последовательность тактовых импульсов поступает в счетчик, который подсчитывает их количество. Во время отрицательной полуволны клапан закрыт, содержимое счетчика (случайное число) переписывается в буфер.
|
|
|
Биометрические ГСЧ
При этом ГСЧ в качестве источника случайности могут использоваться различные биометрические характеристики человека.
Например, в программе PGP (PrettyGoodPrivacy) в качестве случайного параметра используются интервалы времени между случайными нажатиями пользователем клавиш на клавиатуре и значения нажатых клавиш. Эти параметры оцифровываются и записываются в 256-битный буфер. При необходимости формирования ключа случайные числа извлекаются из буфера.
Другим вариантом получения случайных чисел является отслеживание координат «мыши» при ее случайном перемещении пользователем. Основной недостаток биометрического способа заключается в невысокой производительности генерирования случайных чисел и их недостаточной «случайности».
|
|
|
Программные ГСЧ
При этом способе, в отличие от предыдущего, могут формироваться достаточно длинные последовательности двоичных или q-ичных псевдослучайных чисел путем преобразования по определенному алгоритму некоторых начальных данных, которые могут быть либо детерминированными, либо случайными числами. Известно достаточно много таких алгоритмов. Рассмотрим некоторые из них.
Линейный конгруэнтный генератор. Псевдослучайная последователь-
ность (ПСП) формируется согласно уравнению.
xn+1=(a×xn+b)modm
Где целые числа xn, xn+1 - n-й иn+1-й элементы ПСП; m>0 – модуль; 0<a, b<m, 
- начальное заполнение. Максимальный период ПСП равен m при выборе параметров генератора согласно следующей теореме.
Теорема 1.1 Линейная конгруэнтная последовательность, определяемая числами a, b, mимеет период равный mтогда и только тогда, когда
- m и b взаимно простые числа;
- a– 1 кратноpдля каждого простого p, являющегося делителем m;
- a– 1 кратно 4, если mкратно 4.
Аддитивный генераторФибоначчи.Псевдослучайная последовательность (ПСП) формируется согласно уравнению
xn+1=(xn-p+xn-q)modm.
Теорема 1.2 Если многочлен xq+xp+1является примитивным над полем GF,То последовательность, формируется фддитивным генератором Фибоначчи, имеет максимальный период равный 
.
Генераторы ПСП на основе криптографических преобразований Структурная схема такого генератора включает счетчик и блочный шифратор (рис. 2). Начальное состояние счетчика и ключ для блочного шифра задаются
| ПСП |
| Ключ |
| Случайное число |
| Счетчик |
| Блочный шифратор |
чисто случайными числами.
Рис. 2. Схема генератора ПСП на основе блочного шифра
В дальнейшем с каждым тактом счетчик увеличивает свое состояние на 1. Числа с выхода счетчика шифруются блочным шифром. Выходные блоки шифратора образуют псевдослучайную последовательность чисел.
Применение ГСЧ
Генерация действительно случайных чисел играет очень важную роль в самых разных приложениях – в криптографии, в области численного моделирования, в игровой индустрии и других областях. В последние пятьдесят лет, в связи с расширением области применения компьютеров и быстрым развитием электронных сетей связи, число таких приложений постоянно растет. Высокое качество генерации случайных чисел играет жизненно важную роль.
К сожалению, этот факт зачастую упускается из виду. Здесь можно привести пример алгоритма RANDU, десятилетиями использовавшегося на мейнфреймах (больших универсальных высокопроизводительных отказоустойчивых серверах), но оказавшегося впоследствии очень плохим, что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.
Для того чтобы гарантировать конфиденциальность передаваемого сообщения, отправитель создает зашифрованный текст путем сочетания текста, который необходимо передать, с ключом с помощью алгоритма шифрования. Затем этот зашифрованный текст передается по незащищенному каналу связи получателю, который использует алгоритм расшифровки и ключ для расшифровки, чтобы восстановить исходный текст. В идеале злоумышленник не может расшифровать зашифрованный текст без ключа. Таким образом, сила системы шифрования в конечном итоге зависит от силы ключа или, что эквивалентно, от сложности для перехватчика угадать его. Эта трудность заметно увеличивается с длиной ключа – типичные размеры ключа, используемые в настоящее время, составляют 56 бит (DES), 168 бит (3-DES) и 256 бит (IDEA и AES). Как известно, ключ – одна из важнейших частей криптографии, ни один процесс шифрования или дешифрования не обходится без ключа. Некоторые ключи присылаются от доверенного источника, например, сервера криптографических ключей, большинство – создаются с помощью генератора случайных чисел. При этом генерация качественной случайной последовательности является неотъемлемой и самой важной частью многих криптографических операций. Для создания криптостойкого ключа с помощью генератора необходимо учитывать множество факторов, таких как длина ключа, его энтропия, использование истинно случайных и псевдослучайных чисел, а также предусматривать возможные атаки на генератор.
Другим примером служит процедура аутентификации (authentication) – проверка подлинности. Эта процедура необходима, например, для того, чтобы при подключении клиента к серверу система удостоверилась в том, что он на самом деле имеет право на доступ к данным. Не обсуждая деталей данной процедуры, отметим, что на практике она часто использует случайные числа.
Случайные числа необходимы и в лотереях и азартных играх. Здесь должна отсутствовать возможность для игроков увеличить вероятность выигрыша, обнаружив склонность к определенным результатам в процессе игры. Поэтому современные лотереи и игровые автоматы основаны на использовании случайных чисел, чтобы гарантировать одинаковую вероятность выигрыша.
Вывод по главе
Генераторы случайных последовательностей – очень важный элемент в криптографических приложениях. Случайность собираемых данных делаетпланирование малопредсказуемым, а моделирование состояний подобного генератора, затрудняет предсказание и обнаружение атак на него. Поэтому криптостойкий генератор требует тщательного выбора источника случайности.
Глава посвящена анализу способов построения генератора случайных чисел для криптографических задач. Были рассмотрены виды генераторов и их применение в криптографии. Исследованы их характеристики и сделан вывод о том, что последовательность случайных чисел может формироваться только аппаратным генератором чисел.
Дата добавления: 2018-06-01; просмотров: 5107; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!