Датчик случайных чисел windows

Быстрый переход
 

Вы не можете создавать новые темы в этом форуме.

Вы не можете отвечать в этом форуме.

Вы не можете удалять Ваши сообщения в этом форуме.

Вы не можете редактировать Ваши сообщения в этом форуме.

Вы не можете создавать опросы в этом форуме.

Вы не можете голосовать в этом форуме.

Генераторы случайных чисел в разных ОС

Картинка с сайта: habr.com

«Генерация случайных чисел слишком важна, чтобы оставлять ее на волю случая» — Роберт Р. Кавью

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

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

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

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

Немного про энтропию

Чтобы не перегружать текст, я решил не давать таких определений как информационная энтропия и количество информации. Многим они и так знакомы. Поэтому спокойно позволяю себе использовать такие фразы, как «больше энтропии», «пул энтропии», «источник энтропии». А для тех, кто столкнулся с этими терминами впервые, — wiki или воспринимать энтропию интуитивно, как меру случайности(или саму случайность, например «источник энтропии»), и чем она больше, тем «более случайны» полученные биты.

Генератор псевдослучайных чисел — это функция, которая перемешивает входные биты, применяя к ним простые операции несколько раз, выдает наружу результат, который и является последовательностью случайных бит. Для примера рассмотрим алгоритм ChaCha20, применяемый в Linux, и SP800-90 AES-CTR-DRBG в Windows

• ChaCha20 — это развитие алгоритма Salsa20. Он основан на комбинации операций: 32-битное сложение, XOR и побитовое вращение. Если кратко: матрица 4 * 4 заполняется особой константой, ключом, счетчиком и одноразовым числом для текущей итерации, а затем происходит перемешивание бит в течение 20 раундов алгоритма. При этом нечетные раунды отвечают за изменения бит по столбцам матрицы, а четные за изменения по диагоналям. Полученные на выходе биты и есть псевдослучайное число, которое к тому же является входным состоянием для следующего запуска генератора. Но, так как при таком подходе было бы очень легко предсказать все следующие числа, существует обязательная операция изменения ключа после каждого запроса;

Код перемешивания в ChaCha

// linux/lib/crypto/chacha.c
for (i = 0; i < nrounds; i += 2) {
// Odd round
    x[0]  += x[4];    x[12] = rol32(x[12] ^ x[0],  16);
    x[1]  += x[5];    x[13] = rol32(x[13] ^ x[1],  16);
    x[2]  += x[6];    x[14] = rol32(x[14] ^ x[2],  16);
    x[3]  += x[7];    x[15] = rol32(x[15] ^ x[3],  16);

    x[8]  += x[12];   x[4]  = rol32(x[4]  ^ x[8],  12);
    x[9]  += x[13];   x[5]  = rol32(x[5]  ^ x[9],  12);
    x[10] += x[14];   x[6]  = rol32(x[6]  ^ x[10], 12);
    x[11] += x[15];   x[7]  = rol32(x[7]  ^ x[11], 12);

    x[0]  += x[4];    x[12] = rol32(x[12] ^ x[0],   8);
    x[1]  += x[5];    x[13] = rol32(x[13] ^ x[1],   8);
    x[2]  += x[6];    x[14] = rol32(x[14] ^ x[2],   8);
    x[3]  += x[7];    x[15] = rol32(x[15] ^ x[3],   8);

    x[8]  += x[12];   x[4]  = rol32(x[4]  ^ x[8],   7);
    x[9]  += x[13];   x[5]  = rol32(x[5]  ^ x[9],   7);
    x[10] += x[14];   x[6]  = rol32(x[6]  ^ x[10],  7);
    x[11] += x[15];   x[7]  = rol32(x[7]  ^ x[11],  7);
// Even round
    x[0]  += x[5];    x[15] = rol32(x[15] ^ x[0],  16);
    x[1]  += x[6];    x[12] = rol32(x[12] ^ x[1],  16);
    x[2]  += x[7];    x[13] = rol32(x[13] ^ x[2],  16);
    x[3]  += x[4];    x[14] = rol32(x[14] ^ x[3],  16);

    x[10] += x[15];   x[5]  = rol32(x[5]  ^ x[10], 12);
    x[11] += x[12];   x[6]  = rol32(x[6]  ^ x[11], 12);
    x[8]  += x[13];   x[7]  = rol32(x[7]  ^ x[8],  12);
    x[9]  += x[14];   x[4]  = rol32(x[4]  ^ x[9],  12);

    x[0]  += x[5];    x[15] = rol32(x[15] ^ x[0],   8);
    x[1]  += x[6];    x[12] = rol32(x[12] ^ x[1],   8);
    x[2]  += x[7];    x[13] = rol32(x[13] ^ x[2],   8);
    x[3]  += x[4];    x[14] = rol32(x[14] ^ x[3],   8);

    x[10] += x[15];   x[5]  = rol32(x[5]  ^ x[10],  7);
    x[11] += x[12];   x[6]  = rol32(x[6]  ^ x[11],  7);
    x[8]  += x[13];   x[7]  = rol32(x[7]  ^ x[8],   7);
    x[9]  += x[14];   x[4]  = rol32(x[4]  ^ x[9],   7);
}

Картинка с сайта: habr.com

• SP800-90 AES CTR DRBG (англ.: CounTeR mode Deterministic Random Byte Generator) — это криптографически стойкий генератор псевдослучайных чисел, основанный на блочном шифровании AES (англ.: Advanced Encryption Standard) в режиме счетчика. Текущее состояние генератора описывается тремя объектами: ключ K, вектор V, который является счетчиком, и счетчик повторного заполнения counter. В упрощенном виде процесс создания выходной последовательности можно разбить на 2 части:

  • Создание ключа K и начального вектора V при помощи алгоритма обновления и дополнительных входных данных;

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

Картинка с сайта: habr.com

Картинка с сайта: habr.com

Случайные события

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

Linux

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

В данный момент используется 4 типа источников случайных событий:

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

• Информация от таймера, прерывания, типа прерывания, значения;

• Время прерывания;

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

Чтобы инициализировать или переинициализировать ГПСЧ, необходимо из пула энтропии достать несколько случайных байт. Для этого, весь пул хэшируется алгоритмом SHA-1, а хэш-сумма выдается как случайный набор бит. При этом предпринимаются меры для обеспечения безопасности генератора в будущем. Во-первых, результат хэширования перемешивается с пулом, чтобы по выходному значению нельзя было восстановить текущее состояние. Во-вторых, происходит постоянная оценка оставшегося количества энтропии в пуле.

Из-за последнего существует 2 способа взаимодействия со случайными числами в Linux — /dev/random и /dev/urandom. Первый блокируется, когда оценка по количеству энтропии становится ниже нуля, а второй выдает числа всегда, даже если пул не пополняется случайными битами. При этом числа все еще могут оставаться достаточно случайными для требуемой задачи.

Стоит добавить, что на многих шагах, где это имеет смысл, в коде добавлены обращения к «железным» генераторам случайных чисел, которые работают быстрее и дают более качественную энтропию. Это, возможно, было бы не так важно, но Intel еще в Ivy Bridge добавили инструкции RDRAND и RDSEED, позже и AMD сделали это. Таким образом у многих современных компьютеров в CPU есть быстрый генератор случайных чисел. Почему это необходимо — будет объяснено в заключении.

Windows

В Windows процесс создания случайных чисел подчинен достаточно сложной древовидной структуре. Есть три типа источников энтропии, которые отличаются предназначением и качеством. Энтропия, получаемая из них, используется для инициализации и переинициализации корневого ГПСЧ — все случайные числа тем или иным образом получаются из него. Так как в современных многоядерных компьютерах было бы непозволительно медленно иметь только один генератор, то для каждого логического CPU, создается свой ГПСЧ, который инициализируется корневым. Далее, на каждый пользовательский процесс, заводятся и инициализируются свой ГПСЧ и его дочерние генераторы для каждого логического CPU. Таким образом мы получаем что-то вроде дерева генераторов.

Все генераторы, кроме корневого, переинициализируются, когда понимают, что их состояние устарело. Это происходит с помощью ведения и сравнения эпох. Счетчик инкрементируется каждый раз, когда корневой генератор переинициализируется. При этом каждый из его «потомков» в дереве локально запоминает состояние счетчика при его собственной переиницализации. Корневой генератор заполняется по расписанию — при загрузке системы, а далее с экспоненциально растущим периодом: 1, 3, 9, 27 секунд и т.д. Максимальное значение периода составляет 1 час.

В качестве источников энтропии в Windows используются:

• Время прерываний (основной источник) — при каждом прерывании берется отметка о времени с помощью чтения с TSC (англ.: TimeStamp Counter) и записывается в специальный массив на 256 байт компактным образом;

• TPM (англ.: Trusted Platform Module) — выдает 40 байт на старте и 64 байта при каждой переинициализации, но из-за ограничений, не может этого делать чаще, чем раз в 40 минут;

• RDRAND/RDSEED — «железные» генераторы, предоставляемые процессором;

• Seed файл — запись в реестре, которая создается ОС во время работы и используется во время следующей загрузки;

• Внешняя энтропия — запись в реестре, которая делается установщиком для первого запуска системы, но также может быть использована пользователем в будущем, чтобы влиять на процесс инициализации;

• ACPI-OEM0 — создается гипервизором Hyper-V и заполняет при каждом запуске гостевой ОС;

• Данные из драйверов — хэшируются и представляются как очень плохой источник энтропии, который, однако, позволяет по-разному инициализировать систему на разных физически машинах;

• UEFI — случайные числа из UEFI-драйвера;

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

• Уникальное (не случайное) число от Hyper-V — помогает бороться с повторением состояния при запуске снапшота системы.

Hyper-V

Как правило, не только Hyper-V при работе с Windows предоставляет такие улучшения. Многие гипервизоры «прикидываются» Hyper-V, чтобы обеспечивать такой же функционал и использовать встроенные возможности по повышению производительности при работе с Windows.

Во время старта системы данные с 7 источников (Seed файл, внешняя энтропия, TPM, RDRAND, ACPI-OEM0, UEFI и время старта) хэшируются SHA-512 и используются для инициализации SP800-90 AES-CTR-DRBG. Уже во время работы системы, данные предоставленные источником, помещаются в пул (за исключением первого раза, когда они идут сразу на переинициализацию корневого ГПСЧ).

Заключение

Как можно было заметить, многие источники случайных событий связаны с текущим состоянием машины, следовательно при виртуализации могут начаться проблемы. В Linux в комментариях к коду иногда открыто признается эта проблема. В Windows с Hyper-V (или другим гипервизором, «прикидывающимся» им) пытаются с этим бороться, но сама проблема все же иногда проявляется. Ситуация несколько облегчается, тем фактом, что в современных процессорах есть «железные» генераторы случайных чисел, а так же существуют виртуализированные генераторы, которые подсовывают случайные числа хостовой ОС гостевой. Ведь нельзя оставлять это на волю случая…

Литература

Linux
Windows
ChaCha20
SP800-90 AES-CTR-DRBG

Реализация DI в PHP

Jason-Webb 13.05.2025

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

Обработка изображений в реальном времени на C# с OpenCV

stackOverflow 13.05.2025

Объединение библиотеки компьютерного зрения OpenCV с современным языком программирования C# создаёт симбиоз, который открывает доступ к впечатляющему набору возможностей. Ключевое преимущество этого. . .

POCO, ACE, Loki и другие продвинутые C++ библиотеки

NullReferenced 13.05.2025

В C++ разработки существует такое обилие библиотек, что порой кажется, будто ты заблудился в дремучем лесу. И среди этого многообразия POCO (Portable Components) – как маяк для тех, кто ищет. . .

Паттерны проектирования GoF на C#

UnmanagedCoder 13.05.2025

Вы наверняка сталкивались с ситуациями, когда код разрастается до неприличных размеров, а его поддержка становится настоящим испытанием. Именно в такие моменты на помощь приходят паттерны Gang of. . .

Создаем CLI приложение на Python с Prompt Toolkit

py-thonny 13.05.2025

Современные командные интерфейсы давно перестали быть черно-белыми текстовыми программами, которые многие помнят по старым операционным системам. CLI сегодня – это мощные, интуитивные и даже. . .

Конвейеры ETL с Apache Airflow и Python

AI_Generated 13.05.2025

ETL-конвейеры – это набор процессов, отвечающих за извлечение данных из различных источников (Extract), их преобразование в нужный формат (Transform) и загрузку в целевое хранилище (Load). . . .

Выполнение асинхронных задач в Python с asyncio

py-thonny 12.05.2025

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

Работа с gRPC сервисами на C#

UnmanagedCoder 12.05.2025

gRPC (Google Remote Procedure Call) — открытый высокопроизводительный RPC-фреймворк, изначально разработанный компанией Google. Он отличается от традиционых REST-сервисов как минимум тем, что. . .

CQRS (Command Query Responsibility Segregation) на Java

Javaican 12.05.2025

CQRS — Command Query Responsibility Segregation, или разделение ответственности команд и запросов. Суть этого архитектурного паттерна проста: операции чтения данных (запросы) отделяются от операций. . .

Шаблоны и приёмы реализации DDD на C#

stackOverflow 12.05.2025

Когда я впервые погрузился в мир Domain-Driven Design, мне показалось, что это очередная модная методология, которая скоро канет в лету. Однако годы практики убедили меня в обратном. DDD — не просто. . .

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

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

Пример:
Инициализировать массив с помощью
датчика случайных чисел и вывести его
на печать в n колонок,
число колонок ввести с клавиатуры.

#include
«stdafx.h»

#include
<iostream>

#include
<clocale>

using
namespace
std;

int
_tmain(int
argc, _TCHAR* argv[])

{

setlocale
(LC_ALL,»Russian»);

const
int
N=100; //
размер
массива

int
dig[N],col;

int
i;

//
заполнение массива с помощью датчика
случайных чисел

for
(i=0; i<N; i++)

dig[i]=rand();

cout<<
«Введите
число колонок (от 2 до 9): «;

cin>>col;

for
(i=0; i<N; i++)

{cout<<dig[i];

if
((i+1)%col) cout<<«\t»;

else
cout<<«\n»;

}

cout<<«\n»;

system
(«pause»);

return
0;

}

В
примере размер массива задан с помощью
именованной константы N,
при этом использован метод её определения,
с помощью ключевого слова const.

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

Например,
можно уменьшить количество цифр в числе,
выполнив операцию «деление по модулю».
Замените инструкцию

dig[i]=rand()
на dig[i]=rand()%100
и Вы увидите, что генерируемые числа
находятся в диапазоне от 0 до 99,
так как именно в этом диапазоне находятся
возможные «остатки от деления»
произвольного числа на 100.

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

Эту
проблему можно разрешить с помощью
функции srand() из
библиотеки stdlib.

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

И в заключении,
разберем генерацию случайной
последовательности дробных чисел.
Инструкция dig[i]=rand()%100/3.5 будет
генерировать дробные числа.

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

1. В
   объявлении массива укажем double dig[N];

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

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

• Подключить
  библиотеку iomanip

#include
<iomanip>

• Определить
  формат вывода числа, например: общее
  число знаков 8, из них 3-после запятой

cout<<setw
(8)<<setprecision(3)<<dig[i];

Выполнив эти
действия, получаем ровные столбцы.

Измененная
программа будет выглядеть следующим
образом:

#include
«stdafx.h»

#include
<iostream>

#include
<iomanip>

#include
<clocale>

#include
<time.h>

using
namespace
std;

int
_tmain(int
argc, _TCHAR* argv[])

{

setlocale
(LC_ALL,»Russian»);

time_t
k;

srand
(time(&k)); //
инициализировать генератор случайных
чисел

const
int
N=100; //
размер
массива

int
i,col;

double
dig[N];

//
заполнение массива с помощью датчика
случайных чисел

for
(i=0; i<N; i++)

dig[i]=rand()%100/3.5; //
генерация
дробных
чисел

cout<<
«Введите
число колонок (от 2 до 9): «;

cin>>col;

for
(i=0; i<N; i++)

{cout<<setw
(8)<<setprecision(3)<<dig[i];

if
((i+1)%col) cout<<»
«;

else cout<<«\n»;

}

cout<<«\n»;

system
(«pause»);

return
0;

}

Соседние файлы в папке Теория

• #

  30.09.2023415.76 Кб211.docx

• #

  30.09.2023254.03 Кб192.docx

• #

  30.09.2023251.93 Кб173.docx

• #

  30.09.2023419.07 Кб184.docx

• #

  30.09.2023636.88 Кб205.docx

• #
• #