Случайные числа
Дополнительные главы
Любая «компьютерная» система натыкается на своё фундаментальное свойство — она детерминирована. Зная текущее состояние, можно вычислить следующее, а следовательно, ничего случайного произойти не может. Это то, как мы (как человечество) проектировали технику и это именно то, что мы от неё хотим. Однако для решения некоторых задач необходимы случайные числа.
Забавный факт. Проще сказать, что не является случайным, чем наоборот.
Существует два основных способа получения случайных последовательностей чисел: алгоритмический (Pseudo-Random Number Generators, PRNG) и аппаратный (True Random Number Generators, TRNG). PRNG подразумевает использование некоторой математической формулы, а TRNG основан на некотором физическом явлении. У каждого свои плюсы и минусы.
| PRNG | TRNG | |
|---|---|---|
| Скорость | Высокая | Низкая |
| Детерминизм | Детерминирован | Недетерминирован |
| Периодичность | Периодический | Апериодический |
Не всегда требуется «настоящая» случайность. Иногда последовательности достаточно казаться случайной. Например, в игре Simon устройство формирует последовательность цветов, а задача игрока — безошибочно её повторить. Если будут выпадать одни и те же цвета или игрок подметит какой-то шаблон в их появлении, играть будет неинтересно. Человек не заметит разницы, если числа начнут повторяться, условно, через миллион раз. Следовательно, псевдослучайная последовательность здесь вполне подойдёт.
Внушительным периодом обладает вихрь Мерсенна, но легче реализовать более простой алгоритм — линейный конгруэнтный метод (англ. linear congruential generator), задаваемый формулой:
Любой алгоритм оценивается не только по периоду, учитываются и другие статистические свойства, и вихрь Мерсенна по ним не является самым лучшим. Например, его лучше не использовать для задач, связанных с криптографией. Обратитесь к статье на Хабрахабре «В поисках криптостойкого ГПСЧ».
Xn+1=\left(aX{n}+c\right)~~{\bmod {~}}~m~,
где a, c и m — некоторые константы. Неудачно выбранные параметры[2] могут превратить генерируемую последовательность в предсказуемую.
Остаётся указать начальное значение x0, называемое сидом (англ. seed), которое не должно быть константой.
Рекомендации по выбору констант можно найти в Википедии.
#define M 145800
#define A 3661
#define C 30809
static int seed = 0;
void rand_set_seed(int value) {
seed = value;
}
int rand(void) {
seed = (A * seed + C) % M;
return seed;
}Уроборос: для формирования случайной последовательности требуется случайное число. Откуда его взять? Брать число, полученное от каких-нибудь синхронных событий, нельзя: это константа. Код есть код, ядро молотит инструкции, количество которых строго определено. Говоря более научным языком, необходим источник энтропии. Им может выступить какое-нибудь физическое явление. Тепловой шум, наводки и т.д. Часто используют показания подвешенной в воздух ножки АЦП или, что лучше, внутреннего канала АЦП (температуры МК). Впрочем, и другие асинхронные к выполнению программы процессы подойдут: длительность нажатия кнопки в тактах, время подключения к Wi-Fi сети и т.д.
Это плохое решение, ведь ножка легко подтягивается резистором к нужному напряжению.
Главное, чтобы злоумышленник не узнал, какой алгоритм используется и какие параметры были выбраны.
Не все алгоритмы генерации псевдослучайных чисел могут использоваться для задач криптографии. Желательно использовать TRNG. В микроконтроллерах stm32f4 TRNG — один из блоков периферии, основанный на джиттере цепочки инверторов. Он сертифицирован по NIST SP800-22b (набор тестов), т.е. может быть использован в криптографических целях.
В сети доступна реализация TRNG для микроконтроллера stm32f103 — NeuG. В качестве источника энтропии используются два модуля АЦП (температурный датчик, шум на опорном напряжении и напряжении питания), показания которых пропускаются через блок CRC32. Данная последовательность операций производится 35 раз (1120 бит) и передаётся в хэш-функцию (SHA-256) с 128 битами предыдущего преобразования. В описании не указано, что последовательность удовлетворяет требованиям NIST.
