Случайные числа

Любая «компьютерная» система натыкается на своё фундаментальное свойство — она детерминирована. Зная текущее состояние – следующее вычислимо, а, следовательно, ничего случайного произойти не может. Это то, как мы (как человечество) проектировали технику и это именно то, что мы от неё хотим. Однако для решения некоторых задач необходимы случайные числа.

Забавный факт. Проще сказать, что не является случайным, чем наоборот.

Существует два основных способа получения случайных последовательностей чисел — алгоритмический (Pseudo-Random Number Generators, PRNG) и аппаратный (True Random Number Generators, TRNG). PRNG подразумевает использование некоторой математической формулы, а TRNG основан на некотором физическом явлении. У каждого свои плюсы и минусы.

 PRNGTRNG
СкоростьВысокаяНизкая
ДетерминизмДетерминированаНедетерминирована
ПериодичностьПериодическаяАпериодическая

Не всегда требуется «настоящая» случайность. Иногда от последовательности достаточно казаться случайной. Например, в игре Simon устройство формирует последовательность цветов, а задача игрока безошибочно её повторить. Если будут выпадать одни и те же цвета или игрок подметит какой-то шаблон в их появлении, то играть будет не интересно. Человек не заметит разницы, если числа начнут повторяться, условно, через миллион раз. Следовательно, псевдослучайная последовательность здесь вполне подойдёт.

Внушительным периодом обладает вихрь Мерсенна1, но легче реализовать более простой алгоритм, — линейный конгруэнтный метод (англ. linear congruential generator), — задаваемый формулой:

где a, c и m некоторые константы. Неудачно выбранные параметры2 могут превратить генерируемую последовательность в предсказуемую.

Остаётся указать начальное значение x0 называемое сидом (англ. seed), которое не должно быть константой.

Уроборос. Для формирования случайной последовательности требуется случайное число. Откуда его взять? Брать число, полученное от каких-нибудь синхронных событий нельзя — это константа. Код есть код, ядро молотит инструкции, количество которых строго определено. Говоря более научным языком, необходим источник энтропии. Им может выступить какое-нибудь физическое явление. Тепловой шум, наводки и т.д. Часто используют показания подвешенной в воздух ножки АЦП3 или, что лучше, внутреннего канала АЦП (температуры МК). Впрочем, и другие асинхронные к выполнению программы процессы подойдут: длительность нажатия кнопки в тактах, время подключения к Wi-Fi сети и т.д.

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

Не все алгоритмы генерации псевдослучайных чисел могут использоваться для задач криптографии. Желательно использовать TRNG4. В микроконтроллерах stm32f4 TRNG один из блоков периферии, основанный на джиттере цепочки инверторов. Он сертифицирован по NIST SP800-22b (набор тестов), т.е. может быть использован в целях криптографии.


1 Любой алгоритм оценивается не только по периоду, учитываются и другие статистические свойства, и вихрь Мерсенна по ним не является самым лучшим. Например, его лучше не использовать для задач, связанных с криптографией. Обратитесь к статье на Хабрахабре «В поисках криптостойкого ГПСЧ».
2 Рекомендации по выбору констант можно найти в Википедии.
3 Это плохое решение, ведь ножка легко подтягивается резистором к нужному напряжению.
4 В сети доступна реализация TRNG для микроконтроллера stm32f103NeuG. В качестве источника энтропии используется два модуля АЦП (температурный датчик, шум на опорном напряжении и напряжении питания), показания которых пропускается через CRC32 блок. Данная последовательность операций производится 35 раз (1120 бит) и скармливается хэш-функции (SHA-256) с 128 битами предыдущего преобразования. В описании не написано, что последовательность удовлетворяет требования NIST.