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

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

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

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

• Слишком короткий период/периоды.
• Последовательные значения не являются независимыми.
• Некоторые биты «менее случайны», чем другие.
• Неравномерное одномерное распределение.
• Обратимость.

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

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

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

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

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

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

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

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

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

Хотя многие криптостойкие ГПСЧ или поточные шифры предлагают гораздо более «случайные» числа, такие генераторы гораздо медленнее обычных арифметических и могут быть непригодны во всякого рода исследованиях, требующих, чтобы процессор был свободен для более полезных вычислений.

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

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

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

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

19.09.2017, Вт, 13:18, Мск , Текст: Валерия Шмырова

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

Получение патента

Компания «Код безопасности» получила патент на технологию биологического датчика случайных чисел. По словам разработчиков, при создании технологии был использован «новый подход к решению задачи генерации случайных чисел с использованием компьютера и человека». Разработка уже используется в ряде продуктов, в том числе в «Континент-АП», Secret Net Studio, «Континент TLS» и Jinn, а также в криптографической библиотеке SCrypt.

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

Возможности технологии

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

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

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

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

Научная новизна

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

Новизна технологии «Кода безопасности» заключается в том, что источником случайности является реакция человека на меняющееся изображение, который выводится на дисплей устройства. Именно поэтому в названии изобретения присутствует слово «биологический». Компания сообщает, что ни она, ни Роспатент не нашли в России и в мире запатентованных аналогов технологии. Однако в целом такие методики известны: например, последовательность можно генерировать, опираясь на такие действия пользователя, как клики или движения мышью или нажатие клавиш на клавиатуре.

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

Продукты, где используется технология

«Континент» - это аппаратно программный комплекс, предназначенный для шифрования данных. Используется в российском госсекторе, например, в Казначействе. Состоит из межсетевого экрана и инструментария для создания VPN. Был создан компанией НИП «Информзащита», сейчас его разработкой занимается ООО «Код Безопасности».

Конкретно сервер доступа «Континент» и система криптозащиты информации «Континент-АП» представляют собой модуль защищенного удаленного доступа с использованием алгоритмов ГОСТ, а «Континент TLS VPN» - это система обеспечения защищенного удаленного доступа к веб-приложениям также с использованием алгоритмов шифрования ГОСТ.

Secret Net Studio - это комплексное решение для защиты рабочих станций и серверов на уровне данных, приложений, сети, операционной системы и периферийного оборудования, которое также разрабатывает «Код безопасности». Jinn-Client предназначен для криптографической защиты информации для создания электронной подписи и доверенной визуализации документов, а Jinn-Server - это программно-аппаратный комплекс для построения систем юридически значимого электронного документооборота.

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

Чем занимается «Код безопасности»

«Код безопасности» – российский компания, которая занимается разработкой ПО и аппаратуры. Была основана в 2008 г. Сфера применения продукции - защита информационных систем и приведение их в согласие с международными и отраслевыми стандартами, в том числе защита конфиденциальной информации, вплоть до гостайны. «Код безопасности» имеет девять лицензий Федеральной службы по техническому и экспортному контролю (ФСТЭК) России, Федеральной службы безопасности (ФСБ) России и Министерства обороны.

Штат компании насчитывает порядка 300 специалистов, реализацией продукции занимаются 900 авторизованных партнеров во всех регионах России и в странах СНГ. Клиентская база «Кода безопасности» насчитывает около 32 тыс. государственных и коммерческих организаций.

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

Введение

Таблица 1. Подходы к определению случайности

Псевдослучайный процесс и задача пользователя

1. Генерируемые последовательности должны быть близки по статистическим характеристикам к идеальным случайным последовательностям, в частности, полюсность (относительная частота «1») двоичной последовательности должна быть близка к 1/2.
2. В ходе реализации процесса среднестатистическим пользователем скорость генерации должна быть не менее 10 бит/сек.
3. Продолжительность генерации среднестатистическим пользователем 320 бит (которые соответствуют в алгоритме ГОСТ 28147-89 сумме длины ключа (256 бит) и длины синхропосылки (64 бита)) не должна превышать 30 секунд.
4. Удобство работы пользователя с программой БиоДСЧ.

Рисунок 1. Траектории движения центров кругов внутри рабочей области

Задача пользователя – сгенерировать М случайных бит. После появления в рабочей области последнего круга пользователь должен быстро удалить все N движущихся кругов, кликая в произвольной последовательности в площадь каждого круга мышью (в случае планшета – пальцем). Сеанс генерации некоторого количества бит СП завершается после удаления всех кругов. Если сгенерированного за один сеанс количества бит недостаточно, то сеанс повторяется столько раз, сколько необходимо для генерации М бит.

Измеряемые величины процесса

• координаты X и Y точки a i ;
• расстояние R от центра круга до точки a i ;
• номер сектора внутри i-го круга, содержащего точку a i ;
• номер круга и др.

Результаты экспериментов

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

Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Его называют методом середины квадратов.

Пусть задано 4-значное число R 0 =0.9876. Возведём его в квадрат. Получим 8-значное числоR 0 2 =0.97535376. Выберем 4 средние цифры из этого числа и положимR 1 =0.5353. Затем снова возведём в квадрат и извлечём из него 4 средние цифры. ПолучимR 2 и т.д. Этот алгоритм не оправдал себя. Получалось больше чем нужно малых значенийR i .

Однако, представляет интерес исследовать качество этого генератора со смещённой вправо группой выбора цифр у R i 2 :

где a-максимальная значность дроби для данной ЭВМ (например, а=8).

b-количество знаков после запятой в числеR i (например, 5).

INT(А)- целая часть числа.

Для a=8,b=5,R 0 =0.51111111 на ПКZX-Spectrumполучается около 1200 неповторяющихся чисел.

Задание: Исследование следует проводить при варьировании а,b,R 0 . Найти при каких величинахa,b,R 0 получается наибольшая длинаLпоследовательности неповторяющихся чисел при “хороших” стохастических параметрах. Установить влияет ли величинаR 0 на качество датчика. Если влияет, то определить область “приемлемых” значений параметраR 0 . Представить результаты тестирования оптимального варианта значенийa,b,R 0 .

Мультипликативные алгоритмы. Датчик №2: Линейный конгруэнтный генератор Лемера 1951.

где U i ,M,Cиp–целые числа.

AmodB- остаток от деления нацелоAнаB,

A mod B =A-B*INT (A/B)

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

Максимальный период получается при C0, но такой генератор даёт плохие стохастические результаты .

При C=0 генераторы называют мультипликативными. Они имеют лучшие стохастические параметры. Формулы их использования называют ещё методом вычетов.

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

где U i ,M,p-целые числа, 0i <1, 1U i p-1.

Если выбрать U 0 иMтакими, чтобы дляR 0 =U 0 /pполучалась несократимая дробь и взятьpиMвзаимно простыми, тогда всеR i будут несократимыми дробями вида:R i =U i /p.

Получим наибольшую (но не более p) длину неповторяющейся последовательности чисел. ЗначенияU 0 ,pиMудобно выбрать из простых чисел.

Задание: Исследовать при какихU 0 ,pиMдлина последовательности неповторяющихся чисел будет не менее 10000 при «хороших» стохастических параметрах. Определить влияет ли величинаR 0 приMиp=constна статистические характеристики датчика. Если влияет, то определить область допустимых величинU 0 . Представить результаты тестирования генератора для оптимальных величинp,MиU 0 .

Датчик №3: Модификация Коробова .

где p- большое простое число, например 2027, 5087, …

М - целое число, отвечающее условиям:

n– целое число. Т.е. выбираемMблизким кp/2 из множества чиселM=p– 3 n .

Например, для p=5087 берёмn=7. Потому что 3 7 =2187, а 3 8 =6561 будет уже большеp. Итак: М=5087-2187=2900.

Получаем числа U i в интервале = и числаR i в интервале (0,1).

Задание: ПодобратьMиpпри которых получаются лучшие статистические параметры датчика и наибольшая длинаL. Выяснить влияет ли величинаR 0 на стохастические характеристики датчика и, если влияет, то определить область допустимых значенийR 0 . Представить результаты тестирования датчика для оптимальных значенийM,pиR 0 .

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

Считается, что первая попытка создать физический датчик случайных чисел относится к 3500 году до н.э. и связана с настольной игрой сенет, древнеегипетским светским развлечением. Согласно современным реконструкциям правил игры для определения набранного каждым игроком количества очков и очередности ходов в этой игре использовались четыре плоские палочки, одна сторона которых была белой, другая - черной. Палочки бросали одновременно и в зависимости от выпавшей комбинации цветов определяли дополнительные возможности игроков. В начале XX в. последовательности случайных чисел имитировались вручную - с помощью бросаний монеты или игральной кости, раскладывания игральных карт, рулетки, извлечения шаров из урны и т.д. Современные физические (аппаратные) датчики представляют собой специальные устройства, генерирующие случайные числа на основе преобразования случайных шумов естественного или искусственного происхождения (тепловой шум, дробовой эффект в электронных лампах, радиоактивный распад и т.д.). Например, машина ERNIE 4 (electronic random number indicator equipment ),

• 1 Иногда, хотя и редко, к стандартным относят распределение, задаваемое таблицей 0 1 ... 8 9
• 0,1 0,1 ... 0,1 0,1/ с помощью которой определяют выигравшие номера в ежемесячной Британской лотерее, в качестве источника случайных величин использует тепловой шум транзисторов. У физического способа получения последовательности случайных чисел есть особенности, которые для имитационной модели являются недостатками. К ним относятся, в первую очередь, необходимость специальных мер по обеспечению стабильности источника сигнала, преобразуемого в случайные числа, и невозможность воспроизведения полученной последовательности случайных чисел.

Таблицы случайных чисел лишены указанных недостатков. Поясним, что понимается под таблицей случайных чисел. Предположим, что мы осуществили N независимых опытов, в результате которых получили случайные цифры а, а 2 ,осдг. Запись этих цифр (в порядке появления и в форме прямоугольной таблицы) даст так называемую таблицу случайных цифр. Используется она следующим образом. В ходе расчетов нам может потребоваться либо случайная цифра, либо случайное число. Если потребуется случайная цифра, то мы можем взять любую цифру из этой таблицы. То же относится к случаю целого случайного числа - для каждого разряда можно выбрать любую цифру. Если нам понадобится случайное число 0 k очередных цифр сц, а 2 , ос/, и считать, что 8 = (Хоцо^.-.о^. При этом в случае «идеальной» таблицы случайных цифр выбирать цифры из нее можно случайным образом, можно подряд, можно использовать любой алгоритм выбора, не зависящий от значений цифр таблицы, начинать с любого места таблицы, читать в любом направлении.

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

Историческая справка

Леонард Типпет (Leonard Henry Caleb Tippett , 1902-1985) - английский статистик, ученик К. Пирсона и Р. Фишера. В 1965-1966 гг. - президент Королевского статистического общества. С его именем связаны некоторые важные результаты в теории экстремальных значений, например распределение Фишера - Типпета и теорема Фишера - Типпета - Гнеденко.

Позже были сконструированы специальные устройства (машины), механически вырабатывающие случайные числа. Первую такую машину в 1939 г. использовали М. Дж. Кендалл и Б. Бэбингтон-Смит при создании таблиц, включающих 100 тыс. случайных цифр. В 1955 г. компания RAND Corporation опубликовала хорошо известные таблицы с миллионом случайных цифр, полученных другой машиной такого типа. Практическое применение таблиц случайных чисел ограничивается в настоящее время, как правило, задачами, в которых используются методы случайного отбора

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

Это интересно

В России действует ГОСТ 18321-73 (СТ СЭВ 1934-79), устанавливающий правила отбора единиц продукции в выборку при проведении статистического приемочного контроля качества, статистических методов анализа и регулирования технологических процессов для всех видов штучной продукции производственно-технического назначения и товаров народного потребления. В нем, в частности, указывается, что при отборе единиц продукции в выборку «используют таблицы случайных чисел по СТ СЭВ 546-77».

многократно применять; все числа легко воспроизводятся; и запас чисел в такой последовательности ограничен. Однако у последовательности псевдослучайных чисел есть очевидное преимущество перед таблицей: существуют простые формулы для расчета псевдослучайного числа, при этом на получение каждого числа затрачивается всего 3-5 команд, а программа расчета занимает в накопителе лишь несколько ячеек.

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

• Tippett L. Random sampling numbers. London: Cambridge University Press, 1927.
• См.: Кнут Д. Э. Искусство программирования. 3-е изд. М. : Вильямс, 2000. Т. 2. Гл. 3.Случайные числа.

Главная » Монтаж кровли » Аппаратный датчик случайных чисел. Датчики случайных и псевдослучайных чисел