Датчики псевдослучайных чисел доклад

Обновлено: 08.07.2024

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

Вложение	Размер
sluchaynye_chisla_i_psevdosluchaynye_posledovatelnosti.ppt	2.31 МБ

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

Подписи к слайдам:

Ревченко Л.П. учитель информатики ГОУ школы № 497 Невского района Случайные числа 2019 год

Со случайностью мы сталкиваемся на каждом шагу Случайность

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

Телефонная линия должна иметь достаточную пропускную способность

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

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

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

Таблицы случайных цифр В 1927 году Л. Триппет опубликовал таблицы, содержащие свыше 40 000 случайных цифр, произвольно взятых из отчетов о переписи. Позже были сконструированы специальные машины, механически вырабатывающие случайные числа. Первую такую машину использовали М. Дж. Кендалл и Б. Бэбингтон-Смит при создании таблиц из 100 000 случайных цифр. 2057 0762 1429 8535 9029 9745 3458 5023 3502 2436 6435 2646 0295 6177 2755 3080 3275 0521 6623 1133 3278 0500 7573 7426 3188 0187 7707 3047 4901 3519 7888 6411 1631 6981 1972 4269 0022 3860 1580 6751 4022 6540 7804 5528 4690 3586 9839 6641 0404 0735 0888 3504 2651 9051 5764 7155 6489 2660 3341 8784

Осуществив N независимых опытов и получив N случайных цифр, запишем эти цифры (в порядке появления) в таблицу, получим таблицу случайных цифр. Таблицы случайных цифр использовали при расчетах вручную. При расчетах на ЭВМ таблицами не пользовались. Такая таблица не помещалась во внутреннюю память ЭВМ , а обращение к внешним ЗУ замедляло счет. Как получить таблицу случайных цифр?

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

Джон фон Нейман (3.12 1903 — 8.02 1957, Будапешт, Вашингтон), американский математик и физик. Первым такой подход предложил в 1946 году Джон фон Нейман, известный как разработчик архитектуры первых ЭВМ. Идея состояла в том, что нужно только самое первое случайное число. Дальше применяется следующее рекуррентное правило: число возводится в квадрат и из результата берется середина. Таким образом строится последовательность чисел.

Пример получения последовательности десятизначных случайных чисел А = - первое число А 2 = 5772156649 33317792380594909201 33317 7923805949 09201 7923805949 - второе число 62786700717407790601 62786 7007174077 90601 7007174077 - третье случайное число А = А = А 2 = . . . А 2 =

Реализация алгоритма фон Неймана для двузначных чисел Program numbers; Var a, b, c, I : integer; Begin Writeln (' Генерация двузначных чисел'); Writeln (‘Введите любое двузначное число'); Readln(n); For i:=10 to 99 do begin b:=a*a; if b div 1000>0 then c:=b mod 1000 else c:=b; a:=c div 10; if (a=1) or (a=2) or (a=3) then a:=a*10; if a=10 then a:=a+2; if a=60 then a:=a+1; write (a:5); end ; end .

А где же здесь случайность? Никакой случайности здесь нет. Но получаемые таким способом числа ведут себя как случайные. Частота появления любого числа в этой последовательности примерно одинакова. А в моделировании именно это и надо! В результате, вместо последовательности случайных чисел мы имеем ее модель, сохраняющую самое главное свойство: равномерное распределение вероятностей появления членов этой последовательности. Такие последовательности называются псевдослучайными . Алгоритм получения псевдослучайного числа называется датчиком случайных чисел .

Продолжение истории После изобретения Джона фон Неймана математики придумывали различные датчики случайных чисел. Проблема в том, что все псевдослучайные последовательности являются периодическими. Тогда можно ли говорить о моделировании случайности? В алгоритме фон Неймана для десятизначных чисел повторяющаяся последовательность чисел появляется через 10 10 операций. Для человека провести столько опытов дело нескольких лет, а для компьютера — нескольких часов. В сложных случаях получения достоверных результатов моделирования, например, работы ядерного реактора, требуются датчики с большим периодом (10 100 ). Разработка быстрых и надежных датчиков случайных чисел продолжается.

Программа определения S и результаты ее работы Число точек , N 1000 5000 15000 50000 100000 Площадь , S 3.164 3.165 3.141 3.154 3.138 Ответ: S  3.14 2 2

Программа определения S фигуры, ограниченной кривой Y = X 2 , методом Монте-Карло Число точек ,N 1000 5000 15000 50000 100000 Площадь ,S 0.334 0.325 0.332 0.330 0.332 Ответ: S  1/3

Программа определения S фигуры, ограниченной кривой Y = X 3 , методом Монте-Карло Ответ: S  1/4 Число точек ,N 1000 5000 15000 50000 100000 Площадь ,S 0.261 0.241 0.247 0.251 0.251

Программа определения S фигуры треугольник методом Монте-Карло Ответ: S  1/2 Число точек , N 1000 5000 15000 50000 100000 Площадь ,S 0.489 0.495 0.501 0.498 0.502

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

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

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

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

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

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

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

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

‒ блока памяти, хранящего информацию о состоянии генератора,

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

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

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

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

‒ Одноразовые случайные числа,

‒ Соль в схемах цифровой подписи, например, ECDSA.

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

Известно 4 подхода к их конструированию:

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

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

‒ Большой период, отсутствие повторений;

‒ Критерий линейной сложности: повышенная линейная сложность, локальная линейная сложность (Линейная сложность генератора — это длина кратчайшего LFSR, которая может сгенерировать выход генератора; линейная сложность есть мера случайности псевдослучайного генератора);

‒ Статистические критерии, такие как идеальное распределение:

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

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

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

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

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

‒ время прибытия сетевых пакетов и т. п.

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

Долгов В. И. Криптографическая защита информации в АСУ СН. —:, 1998. — с.
Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования. — 3-е изд. — М.: Вильямс, 2000. — 832 с.
Жельников В. Псевдослучайные последовательности чисел // Кpиптография от папируса до компьютера. — М.: ABF, 1996. — 335 с.

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

Содержание

Детерминированные ГПСЧ

Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и в среднем составляет около 2 n/2 , где n — размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2 n . Если ГПСЧ может сходиться к слишком коротким циклам, такой ГПСЧ становится предсказуемым и является непригодным.

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

В частности, алгоритм мейнфреймах, оказался очень плохим [1] [2] , что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.

ГПСЧ с источником энтропии или ГСЧ

Наравне с существующей необходимостью генерировать легко воспроизводимые последовательности случайных чисел, также существует необходимость генерировать совершенно непредсказуемые или попросту абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (ГСЧ — англ. random number generator, RNG ). Так как такие генераторы чаще всего применяются для генерации уникальных симметричных и асимметричных ключей для шифрования, они чаще всего строятся из комбинации криптостойкого ГПСЧ и внешнего источника энтропии (и именно такую комбинацию теперь и принято понимать под ГСЧ).

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

В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора. До появления возможности считывать значения счётчика тактов, сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ до сих пор используют традиционные (устаревшие) методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в [3] , или взаимодействия между потоками, как, например, в Java secure random.

Примеры ГСЧ и источников энтропии

Несколько примеров ГСЧ с их источниками энтропии и генераторами:

ГПСЧ в криптографии

Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а так же различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или семенем (англ. seed ), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюма, Блюма и Шуба, а так же счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.

Аппаратные ГПСЧ

Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы и также держатся в секрете. Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA- или

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

Примечания

См. также

NIST STS — пакет статистического тестирования
CryptX — пакет статистического тестирования

Ссылки

Литература

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое "Датчик случайных чисел" в других словарях:

датчик случайных чисел — Аппаратно реализованное устройство (элемент, блок), предназначенное для генерации случайных битовых последовательностей, обладающих необходимыми свойствами равновероятности порождаемой ключевой гаммы. [Домарев В.В. Безопасность информационных… … Справочник технического переводчика

датчик случайных чисел — Узел вычислительной машины, который служит для выработки случайных чисел … Политехнический терминологический толковый словарь

Датчик случайных величин — [random number generator] то же: датчик случайных чисел, генератор случайных чисел устройство или программа, предназначенные для выработки последовательности случайных чисел по заданному закону распределения вероятностей их значений … Экономико-математический словарь

Случайных чисел датчик — устройство для выработки случайных чисел, равномерно распределённых в заданном диапазоне чисел. Применяется для имитации реальных условий функционирования систем автоматического управления, для решения задач методом статистических… … Большая советская энциклопедия

СЛУЧАЙНЫХ ЧИСЕЛ ДАТЧИК — устройство для выработки случайных чисел, равномерно распределённых в заданном диапазоне. Применяется для имитации реальных условий функционирования систем автоматич. управления, при решении на ЭВМ задач методом статистич. испытаний (т. н.… … Большой энциклопедический политехнический словарь

Датчик — первичный преобразователь, элемент измерительного, сигнального, регулирующего или управляющего устройства системы, преобразующий контролируемую величину (давление, температуру, частоту, скорость, перемещение, напряжение, электрический ток … Большая советская энциклопедия

Аппаратное шифрование — Аппаратное шифрование процесс шифрования, производимый при помощи специализированных вычислительных устройств. Содержание 1 Введение 2 Достоинства и недостатки аппаратного шифрования … Википедия

Метод Фибоначчи с запаздываниями — (Lagged Fibonacci generator) один из методов генерации псевдослучайных чисел. Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делают невозможным их использование в статистических алгоритмах, требующих… … Википедия

"Случайность - это такая закономерность, которую не удалось обнаружить"

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

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

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

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

Линейный конгуэнтный генератор псевдослучайных чисел (ЛКГ ПСЧ)

x₀ - начальное значение (инициализирующий вектор)
a - множитель
b - приращение
m - модуль

У такого генератора максимальный период равен m. Он достигается, например, при выборе констант Парка-Милера:

Нелинейные конгуэнтные генераторы псевдослучайных чисел (НКГ ПСЧ)

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

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

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

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

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

Физические датчики шума
Резисторы, полупроводниковые и вакуумные электронные приборы - генерируют случайные последовательности импульсов различной амплитуды. Наиболее удобно применять в вычислительных устройствах физические датчики шума на основе полупроводниковых приборов с Зенеровским пробоем (стабилитроны).

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

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

В нашем телеграм канале мы рассказываем о главных новостях из мира IT, актуальных угрозах и событиях, которые оказывают влияние на обороноспособность стран, бизнес глобальных корпораций и безопасность пользователей по всему миру. Узнай первым как выжить в цифровом кошмаре!

Читайте также:

Датчики псевдослучайных чисел доклад

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

Подписи к слайдам:

Похожие статьи

Методы генерации случайных чисел | Статья в журнале.

Методология сравнения потоковых шифров | Статья в журнале.

Нахождение k-error линейной сложности бинарной.

Реализация алгоритма RC4 на CBuilder | Статья в журнале.

Роль больших простых чисел в современной криптографии

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

Исследование алгоритмов генерации простых чисел

Обзор аппаратных генераторов случайных чисел

Анализ псевдослучайных последовательностей на.