Внимание! Все представленные в данной статье материалы являются демонстрационными и не должны применяться в серьезных приложениях, поскольку предлагаемое не прошло независимый аудит и не было надлежащим образом проверено, и предлагается лишь как доказательство концепции или как сравнительно простой способ генерации случайных чисел для некриптографических приложений. Если вам нужен надежный криптографический генератор случайных чисел, то воспользуйтесь уже существующими решениями и ни в коем случае не реализуйте данные решения самостоятельно!
Внимательно прочитайте данное предупреждение, и если вы готовы ознакомится с нашим примером, который мы выкладываем в образовательных целях, то добро пожаловать в эту статью.
Криптографический генератор псевдослучайных чисел (далее в статье, будем ссылаться на этот термин по сокращенному наименованию — КГПСЧ или просто по термину «генератор«) — это такой генератор псевдослучайных чисел, выдаваемая последовательность чисел которого, позволяет использовать такой генератор в криптографии. Это означает, что по сравнению с классическими генераторами псевдослучайных чисел, к КГПСЧ предъявляются более строгие требования из соображений безопасности, поскольку чисто одних статистических требований для приложений криптографии недостаточно.
В большинстве языков программирования, в стандартной библиотеке реализован стандартный (т.е некриптографический), но высококачественный генератор псевдослучайных чисел. И D, в этом смысле, то же не стал исключением — в std.random реализован генератор на базе Вихря Мерсенна, и он не криптографический. Поэтому, мы решили ради эксперимента попробовать реализовать КГПСЧ в D самостоятельно и узнать насколько сложно будет проверить данную концепцию.
Для реализации криптографических генераторов псевдослучайных чисел могут быть применены разные подходы, но мы выбрали самый (как нам показалось) простой — мы решили сделать такой генератор воспользовавшись блочным шифром в режиме счетчика.
Стоит напомнить, что несмотря на обилие блочных алгоритмов шифрования, применять данные алгоритмы можно в довольно ограниченном множестве режимов шифрования. Одним из таких режимов, как раз и является режим счетчика, в котором идет шифрования некоторой последовательности с последующим возвратом результата шифрования на вход самого выбранного шифровального алгоритма. При использовании такого подхода, все что необходимо сделать — это обеспечить реализацию надежного блочного алгоритма шифрования, функции приращения (это то что будет генерировать входную последовательность) и сгенерировать секретный ключ, который будет использоваться все время работы КГПСЧ.
Весь данный функционал по сути зависит всего от двух параметров — начального значения счетчика и заданного секретного ключа, однако, мы подумали, и решили добавить возможность явного задания функции приращения. Данное решение было мотивировано тем, что заданием собственного варианта функции приращения можно добиться разных уровней «случайности» выходных значений, а правильным ее выбором можно повысить и стойкость генератора. Обычно в качестве функции приращения выбирают обычное увеличение значения счетчика на 1 (т.е обычный инкремент), но мы решили в качестве функции по умолчанию использовать иной вариант — одна часть счетчика увеличивается на 1, а вторая используется для индикации того, нужно ли приращение.
На таких принципах мы решили сделать свою реализацию, однако, прежде чем мы ее вам покажем, стоит упомянуть ряд ее деталей. Мы решили, что наш генератор будет давать в качестве выхода: 64-битные числа (метод next), случайные числа в интервале [0; 1) (метод random) и некоторое количество случайных байтов (метод randomBytes). В качестве входных значений выступают: ключ (который состоит из 4 32-битных значений с типом uint), значение счетчика (2 32-битных значения с типом uint) и функция приращения (необязательный параметр, значение по умолчанию описано выше). Входные значения задаются при инициализации структуры путем вызова ее конструктора и для первых двух параметров значения по умолчанию не представлены (угадайте, почему).
Также, в качестве блочного шифра мы решили использовать Raiden. Решение, мягко говоря, спорное, но Raiden реализуется буквально в несколько строк, легко инкапсулируется в структуру и прост для понимания. Еще мы выбрали его, поскольку решили просто проверить сам концепт использования алгоритма шифрования в режиме счетчика и под рукой был исходный код только для Raiden.
В итоге сама реализация у нас получилась вот такой:
module raidenprng64;
struct RaidenCSRNG64
{
private {
/// The key for the Raiden algorithm
uint[4] key;
/// The counter for CTR mode
uint[2] counter;
/// The increment function
uint[2] function(ref uint[2]) incrementFunction;
/// Encryption with Raiden
void encryptWithRaiden(ref uint[2] outBuffer)
{
uint b0 = counter[0], b1 = counter[1], sk;
foreach (i; 0..16)
{
sk = key[i % 4] = ((key[0] + key[1]) + ((key[2] + key[3]) ^ (key[0] << (key[2] & 0x1F))));
b0 += ((sk + b1) << 9) ^ ((sk - b1) ^ ((sk + b1) >> 14));
b1 += ((sk + b0) << 9) ^ ((sk - b0) ^ ((sk + b0) >> 14));
}
outBuffer[0] = b0;
outBuffer[1] = b1;
}
}
this(uint[4] key, uint[2] counter, uint[2] function(ref uint[2]) incrementFunction = null)
{
this.key = key.dup;
this.counter = counter.dup;
if (incrementFunction is null)
{
/// Default increment function implementation
this.incrementFunction = (ref uint[2] counter) {
if (++counter[1] == 0)
{
++counter[0];
}
return counter;
};
}
else
{
/// User defined increment
this.incrementFunction = incrementFunction;
}
}
/// Next random number
ulong next()
{
uint[2] result;
// Encrypt the counter with the Raiden algorithm
encryptWithRaiden(result);
// Increment the counter using the provided increment function
counter = incrementFunction(counter);
return cast(ulong) result[0] << 32 | result[1];
}
/// Generate a random value in the range [0, 1)
double random()
{
return this.next / cast(double) ulong.max;
}
/// Generate random bytes
ubyte[] randomBytes(size_t numberOfBytes)
{
ubyte[] bytes;
foreach (_; 0..numberOfBytes)
{
bytes ~= cast(ubyte) (this.next & 0xFF); // Generate random bytes by extracting the least significant byte
}
return bytes;
}
}
/// Base increment function
auto standardIncrement(ref uint[2] counter)
{
enum LEAST_SIGNIFICANT_BITS = 16; // Number of least significant bits
enum TOTAL_BITS = 32; // Total number of bits in the counter
counter[1] += 1;
counter[1] %= (1 << LEAST_SIGNIFICANT_BITS);
if (counter[1] == 0)
{
counter[0] += 1;
counter[0] %= (1 << (TOTAL_BITS - LEAST_SIGNIFICANT_BITS));
}
return counter;
}
unittest {
uint[4] key = [0x01234567, 0x89ABCDEF, 0xFEDCBA98, 0x76543210];
uint[2] counter = [0x00000000, 0x00000000];
uint[2] counter2 = [0x00000001, 0x00000000];
auto rng = new RaidenCSRNG64(key, counter);
assert(rng.next != rng.next);
assert(rng.random != rng.random);
assert(rng.randomBytes(16) != rng.randomBytes(16));
auto rng2 = RaidenCSRNG64(key, counter2);
assert(rng2.next != rng.next);
assert(rng2.random != rng.random);
assert(rng2.randomBytes(16) != rng.randomBytes(16));
}
auto DieHarder(size_t NUMBER_OF_ITERATIONS, RaidenCSRNG64 rng)
{
import std.format;
import std.stdio;
enum HEADER =
`#==================================================================
# generator raidencsrng64 seed = 0
#==================================================================
type: d
count: %d
numbit: 64`;
File f;
f.open(`raiden64.input`, `w`);
f.writeln(HEADER.format(NUMBER_OF_ITERATIONS));
foreach (_; 0..NUMBER_OF_ITERATIONS) {
f.writeln(rng.next);
}
f.close;
}
void main()
{
import std.stdio;
uint[4] key = [0x01234567, 0x89ABCDEF, 0xFEDCBA98, 0x76543210];
uint[2] counter = [0x00000000, 0x00000000];
auto rng = RaidenCSRNG64(key, counter, &standardIncrement);
// Генерация следующего случайного числа
ulong randomNumber = rng.next();
// Генерация случайного числа в диапазоне [0, 1)
double randomValue = rng.random();
// Генерация случайного массива байтов
ubyte[] randomBytes = rng.randomBytes(16);
// Использование сгенерированных случайных значений
import std.stdio;
writeln(randomNumber, " ", randomValue, " ", randomBytes);
// Подготовка файла к тестам DieHarder
DieHarder(1_000_000_000, rng);
}Сама реализация буквально следует тому, что описали мы выше и понять ее можно за считанные минуты. К данной реализации мы еще добавили реализацию варианта функции приращения (которая, впрочем, почти не отличима от стандартной). Вариант функции приращения (тот что вне структуры) показывает как можно самостоятельно расширить возможности КГПСЧ на базе Raiden с помощью замены схемы работы счетчика. Данная функция принимает по ссылке массив со значениями счетчика и возвращает новое его значение, при этом, иных ограничений на функцию приращения не накладывается.
Также мы реализовали функцию под названием DieHarder, которая служит для проведения статистического тестирования генератора с помощью известного пакета dieharder. Эта функция не является необходимой и служит для генерации файла, который будет содержат количество псевдослучайных чисел, которое будет указано как первый аргумент. Файл, который создается при помощи функции DieHarder («крепкий орешек») подается на вход пакету dieharder при помощи команды:
dieharder -g 202 -f <имя_файла_со_случайными_числами> -a
и его генерация, как собственно говоря, и прохождение теста может занять продолжительное время.
Предполагая, что наш генератор сразу провалит тестирование, мы этой командой решили запустить тестирование, сгенерировав почти 20-гигабайтный файл, содержащий 1 000 000 000 значений типа ulong (это 64-битные значения без знака). Представьте себе наше удивление, после того, как генератор не провалил первые тесты!
Более того, мы были сильно удивлены тем, что по прошествии 3 (!) дней интенсивной работы на компьютере одного из авторов блога, генератор не провалил ни одного теста ! Несмотря на столь неожиданную для нас стойкость, в 3 тестах (если не ошибаюсь из 120) наш генератор показал некоторую слабость (эти тесты пакетом dieharder помечены фразой «WEAK») и это показатель для того, что стоит обратить внимание на некоторые детали внутреннего устройства КГПСЧ. Мы считаем, что использование другой функции приращения (допустим на базе какой-нибудь хорошей хэш-функции) способно улучшить результат, однако, мы не настолько компетентны, чтобы это доказать или подтвердить это каким-либо иным способом.
Кроме того, ложку дегтя добавляет то, что dieharder завис на нескольких последних тестах и в итоге пришлось несколько тестов запускать вручную, что отражается в таком протоколе тестирования (включены результаты запуска dieharder со всеми тестами и ручные результаты):
dlang dieharder -g 202 -f raiden64.input -a
#=============================================================================#
# dieharder version 3.31.2 Copyright 2003 Robert G. Brown #
#=============================================================================#
rng_name | filename |rands/second|
file_input| raiden64.input| 1.03e+06 |
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
diehard_birthdays| 0| 100| 100|0.57609750| PASSED
diehard_operm5| 0| 1000000| 100|0.36583434| PASSED
diehard_rank_32x32| 0| 40000| 100|0.16269073| PASSED
diehard_rank_6x8| 0| 100000| 100|0.21261744| PASSED
diehard_bitstream| 0| 2097152| 100|0.66908655| PASSED
diehard_opso| 0| 2097152| 100|0.51597447| PASSED
diehard_oqso| 0| 2097152| 100|0.02433674| PASSED
diehard_dna| 0| 2097152| 100|0.59449638| PASSED
diehard_count_1s_str| 0| 256000| 100|0.97432396| PASSED
diehard_count_1s_byt| 0| 256000| 100|0.72643929| PASSED
diehard_parking_lot| 0| 12000| 100|0.05056232| PASSED
diehard_2dsphere| 2| 8000| 100|0.97730413| PASSED
diehard_3dsphere| 3| 4000| 100|0.51498484| PASSED
# The file file_input was rewound 1 times
diehard_squeeze| 0| 100000| 100|0.87396571| PASSED
# The file file_input was rewound 1 times
diehard_sums| 0| 100| 100|0.00063155| WEAK
# The file file_input was rewound 1 times
diehard_runs| 0| 100000| 100|0.99825784| WEAK
diehard_runs| 0| 100000| 100|0.50353022| PASSED
# The file file_input was rewound 1 times
diehard_craps| 0| 200000| 100|0.17689339| PASSED
diehard_craps| 0| 200000| 100|0.83569502| PASSED
# The file file_input was rewound 3 times
marsaglia_tsang_gcd| 0| 10000000| 100|0.60071747| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.43081302| PASSED
# The file file_input was rewound 3 times
sts_monobit| 1| 100000| 100|0.94277878| PASSED
# The file file_input was rewound 3 times
sts_runs| 2| 100000| 100|0.98882658| PASSED
# The file file_input was rewound 3 times
sts_serial| 1| 100000| 100|0.14721788| PASSED
sts_serial| 2| 100000| 100|0.97699391| PASSED
sts_serial| 3| 100000| 100|0.64895499| PASSED
sts_serial| 3| 100000| 100|0.79410478| PASSED
sts_serial| 4| 100000| 100|0.56273919| PASSED
sts_serial| 4| 100000| 100|0.31220089| PASSED
sts_serial| 5| 100000| 100|0.61404743| PASSED
sts_serial| 5| 100000| 100|0.69564681| PASSED
sts_serial| 6| 100000| 100|0.53661523| PASSED
sts_serial| 6| 100000| 100|0.72352558| PASSED
sts_serial| 7| 100000| 100|0.89873260| PASSED
sts_serial| 7| 100000| 100|0.73234004| PASSED
sts_serial| 8| 100000| 100|0.21594913| PASSED
sts_serial| 8| 100000| 100|0.22596533| PASSED
sts_serial| 9| 100000| 100|0.12208020| PASSED
sts_serial| 9| 100000| 100|0.90863569| PASSED
sts_serial| 10| 100000| 100|0.23472224| PASSED
sts_serial| 10| 100000| 100|0.62564695| PASSED
sts_serial| 11| 100000| 100|0.95415231| PASSED
sts_serial| 11| 100000| 100|0.19408376| PASSED
sts_serial| 12| 100000| 100|0.41662058| PASSED
sts_serial| 12| 100000| 100|0.71889872| PASSED
sts_serial| 13| 100000| 100|0.74766242| PASSED
sts_serial| 13| 100000| 100|0.98174339| PASSED
sts_serial| 14| 100000| 100|0.59550451| PASSED
sts_serial| 14| 100000| 100|0.26937321| PASSED
sts_serial| 15| 100000| 100|0.71844744| PASSED
sts_serial| 15| 100000| 100|0.72340616| PASSED
sts_serial| 16| 100000| 100|0.56816894| PASSED
sts_serial| 16| 100000| 100|0.68920227| PASSED
# The file file_input was rewound 3 times
rgb_bitdist| 1| 100000| 100|0.10929340| PASSED
# The file file_input was rewound 3 times
rgb_bitdist| 2| 100000| 100|0.20348937| PASSED
# The file file_input was rewound 3 times
rgb_bitdist| 3| 100000| 100|0.99825660| WEAK
# The file file_input was rewound 3 times
rgb_bitdist| 4| 100000| 100|0.31367222| PASSED
# The file file_input was rewound 3 times
rgb_bitdist| 5| 100000| 100|0.85481199| PASSED
# The file file_input was rewound 3 times
rgb_bitdist| 6| 100000| 100|0.28060249| PASSED
# The file file_input was rewound 3 times
rgb_bitdist| 7| 100000| 100|0.84191368| PASSED
# The file file_input was rewound 4 times
rgb_bitdist| 8| 100000| 100|0.74682640| PASSED
# The file file_input was rewound 4 times
rgb_bitdist| 9| 100000| 100|0.15885952| PASSED
# The file file_input was rewound 4 times
rgb_bitdist| 10| 100000| 100|0.43063856| PASSED
# The file file_input was rewound 4 times
rgb_bitdist| 11| 100000| 100|0.77916819| PASSED
# The file file_input was rewound 4 times
rgb_bitdist| 12| 100000| 100|0.68027081| PASSED
# The file file_input was rewound 4 times
rgb_minimum_distance| 2| 10000| 1000|0.71710887| PASSED
# The file file_input was rewound 4 times
rgb_minimum_distance| 3| 10000| 1000|0.46846588| PASSED
# The file file_input was rewound 4 times
rgb_minimum_distance| 4| 10000| 1000|0.91222677| PASSED
# The file file_input was rewound 4 times
rgb_minimum_distance| 5| 10000| 1000|0.10981802| PASSED
# The file file_input was rewound 5 times
rgb_permutations| 2| 100000| 100|0.37268625| PASSED
# The file file_input was rewound 5 times
rgb_permutations| 3| 100000| 100|0.23012241| PASSED
# The file file_input was rewound 5 times
rgb_permutations| 4| 100000| 100|0.54119790| PASSED
# The file file_input was rewound 5 times
rgb_permutations| 5| 100000| 100|0.25436411| PASSED
# The file file_input was rewound 5 times
rgb_lagged_sum| 0| 1000000| 100|0.79393716| PASSED
# The file file_input was rewound 5 times
rgb_lagged_sum| 1| 1000000| 100|0.91711082| PASSED
# The file file_input was rewound 5 times
rgb_lagged_sum| 2| 1000000| 100|0.91502859| PASSED
# The file file_input was rewound 6 times
rgb_lagged_sum| 3| 1000000| 100|0.98394830| PASSED
# The file file_input was rewound 6 times
rgb_lagged_sum| 4| 1000000| 100|0.81240919| PASSED
# The file file_input was rewound 7 times
rgb_lagged_sum| 5| 1000000| 100|0.17401906| PASSED
# The file file_input was rewound 7 times
rgb_lagged_sum| 6| 1000000| 100|0.56799702| PASSED
# The file file_input was rewound 8 times
rgb_lagged_sum| 7| 1000000| 100|0.95032814| PASSED
# The file file_input was rewound 9 times
rgb_lagged_sum| 8| 1000000| 100|0.21105608| PASSED
# The file file_input was rewound 10 times
rgb_lagged_sum| 9| 1000000| 100|0.21079116| PASSED
# The file file_input was rewound 11 times
rgb_lagged_sum| 10| 1000000| 100|0.39040620| PASSED
# The file file_input was rewound 12 times
rgb_lagged_sum| 11| 1000000| 100|0.35221465| PASSED
# The file file_input was rewound 14 times
rgb_lagged_sum| 12| 1000000| 100|0.42097149| PASSED
# The file file_input was rewound 15 times
rgb_lagged_sum| 13| 1000000| 100|0.55336728| PASSED
# The file file_input was rewound 17 times
rgb_lagged_sum| 14| 1000000| 100|0.10381691| PASSED
# The file file_input was rewound 18 times
rgb_lagged_sum| 15| 1000000| 100|0.80516194| PASSED
# The file file_input was rewound 20 times
rgb_lagged_sum| 16| 1000000| 100|0.11737794| PASSED
# The file file_input was rewound 22 times
rgb_lagged_sum| 17| 1000000| 100|0.18591240| PASSED
# The file file_input was rewound 24 times
rgb_lagged_sum| 18| 1000000| 100|0.89115097| PASSED
# The file file_input was rewound 26 times
rgb_lagged_sum| 19| 1000000| 100|0.03636804| PASSED
# The file file_input was rewound 28 times
rgb_lagged_sum| 20| 1000000| 100|0.43378797| PASSED
# The file file_input was rewound 30 times
rgb_lagged_sum| 21| 1000000| 100|0.17986732| PASSED
# The file file_input was rewound 32 times
rgb_lagged_sum| 22| 1000000| 100|0.22070491| PASSED
# The file file_input was rewound 35 times
rgb_lagged_sum| 23| 1000000| 100|0.78980965| PASSED
# Тесты которые пришлось запустить вручную
rgb_kstest_test| 0| 10000| 1000|0.34093518| PASSED
dab_bytedistrib| 0| 51200000| 1|0.12027760| PASSED
dab_dct| 256| 50000| 1|0.56791062| PASSED
dab_filltree| 32| 15000000| 1|0.43381453| PASSED
dab_filltree| 32| 15000000| 1|0.57207921| PASSED
dab_filltree2| 0| 5000000| 1|0.97170600| PASSED
dab_filltree2| 1| 5000000| 1|0.71964485| PASSED
dab_monobit2| 12| 65000000| 1|0.13561693| PASSED
Это, конечно, не так страшно, просто сам пакет прогоняет один и тот же тест с разными параметрами и такие результаты, в целом, более убедительны. Также, обращаем ваше внимание, на то, что мы — не математики, и нам сложно как-то детально прокомментировать результаты тестирования и также по этой причине мы ограничились только одним пакетом (хотя у одного из авторов блога была мысль испытать еще и пакет STS от NIST, но мы решили остановится).
В целом получился интересный эксперимент, в котором нам помогал ChatGPT (версия 3.5-turbo) и которому мы дали готовую реализацию Raiden на D. Так подсказки ChatGPT помогли начать тестирование генератора, но с ключами для пакета он ошибся и нам пришлось их искать самим на странице пакета.
Возможно, когда мы убедимся в надежности данного генератора и его стойкости, мы сделаем его аннонс как полноценного криптографически стойкого генератора случайных чисел, однако сейчас мы не можем его рекомендовать в таком качестве и предлагаем использовать как пример или небольшой генератор последовательностей для некриптографических целей.
P.S: Еще раз прочтите предупреждение в начале статьи. Мы — не математики, и тем более не криптографы, а простые экспериментаторы-самоучки. Если вам нужен КГПСЧ, то используйте проверенные решения, а не куски нашего кода из этой статьи !
