Как генерировать большие случайные числа C

ProgramBox

Как генерировать большие случайные числа C

Post author:admin
Запись опубликована:31 января, 2023
Post category:Вопросы по программированию

#c #random #rsa

#c #Случайный #rsa

Вопрос:

Я ищу способ генерировать большие случайные числа порядка 2 ^ 64 в C … (100000000 — 999999999) для использования в алгоритме шифрования с открытым ключом (как p и q).

Я не хочу генерировать число меньше 2 ^ 64 (то есть меньше 100000000).

Есть ли что-нибудь, что могло бы мне помочь в этом?

Ответ №1:

random() возвращает значение long, которое в 64-битной системе должно быть 64 бита. Если вы используете 32-битную систему, вы можете сделать следующее:

 #include <inttypes.h>

uint64_t num;

/* add code to seed random number generator */

num = rand();
num = (num << 32) | rand();

// enforce limits of value between 100000000 and 999999999
num = (num % (999999999 - 100000000))   100000000;

В качестве альтернативы в системе NIX вы можете прочитать /dev/random в свой буфер:

 #include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <inttypes.h>   

int fd;
uint64_t num; 
if ((fd = open("/dev/random", O_RDONLY) == -1)
{
    /* handle error */
};
read(fd, amp;num, 8);
close(fd);

// enforce limits of value between 100000000 and 999999999
num = (num % (999999999 - 100000000))   100000000;

1. rand() ограничено RAND_MAX тем, что не является необходимым 2^32 . И вам все равно нужно что-то передать srand() . /dev/random функциональность также доступна на других платформах .

2. Это не гарантирует выполнение требования «Я не хочу генерировать число меньше … 100000000».

3. Добавьте строку num = (num % (999999999 - 100000000)) 100000000; для генерации случайного числа с нижним пределом 100000000 и верхним пределом 999999999.

4. Лучше, но теперь числа выше 805933941 (2 ^ 64 -1 mod 899999999) немного менее вероятны, чем числа ниже 😉

5. На моем компьютере RAND_MAX 2^31 нет 2^32 .

Ответ №2:

Вы могли бы объединить два 4-байтовых случайных целых числа для получения 8-байтового:

 #include <stdint.h>
...
uint64_t random = 
  (((uint64_t) rand() <<  0) amp; 0x00000000FFFFFFFFull) | 
  (((uint64_t) rand() << 32) amp; 0xFFFFFFFF00000000ull);

Поскольку rand возвращает int и sizeof(int) >= 4 практически на любой современной платформе, этот код должен работать. Я добавил << 0 , чтобы сделать намерение более явным.

Маскировка с 0x00000000FFFFFFFF помощью и 0xFFFFFFFF00000000 предназначена для предотвращения перекрытия битов в двух числах в случае sizeof(int) > 4 .

Редактировать

Поскольку @Banthar прокомментировал, что RAND_MAX это не обязательно 2 ^ 32 , и я думаю, что это гарантировано, по крайней мере 2 ^ 16 , вы можете объединить четыре 2-байтовых числа, чтобы быть уверенным:

 uint64_t random = 
  (((uint64_t) rand() <<  0) amp; 0x000000000000FFFFull) | 
  (((uint64_t) rand() << 16) amp; 0x00000000FFFF0000ull) | 
  (((uint64_t) rand() << 32) amp; 0x0000FFFF00000000ull) |
  (((uint64_t) rand() << 48) amp; 0xFFFF000000000000ull);

1. Если вы используете ^ для объединения чисел вместо | , вам не нужно беспокоиться о маскировке.

2. По одному: RAND_MAX очень маловероятно 2 ^ 32 . Это может быть (2 ^ 32) - 1 . Но даже это необычно. Скорее всего, это то же INT_MAX самое, что и то, которое имеет общее значение (2 ^ 31) - 1 или (2 ^ 15) - 1 . C указывает RAND_MAX как минимум (2^15) - 1 , нет 2 ^ 16 .

Ответ №3:

Вы ищете PRNG с криптографической надежностью, например openssl/rand : http://www.openssl.org/docs/crypto/rand.html

1. Или BCryptGenRandom в Windows Vista и выше.

2. 1: использование rand() для этого является дырой в безопасности (прогнозирование результата rand() не очень сложно)

3. openssl.org/docs/crypto/rand.html мертвая ссылка в августе 2018 года. Одна из проблем с ответом только на ссылку.

Ответ №4:

Я знаю, что, вероятно, получу b____ от OliCharlesworth, но используйте rand() со шкалой и смещением. Это в stdlib.h Чтобы охватить весь диапазон, вы должны добавить его к другому меньшему rand(), чтобы заполнить пробелы в отображении.

Ответ №5:

Вы можете сделать большое число L из меньших чисел (например A , amp; B ). Например, с чем-то вроде L = (2^ n)*A B , где ^ обозначает возведение в степень и n является некоторым постоянным целым числом (например, 32). Затем вы кодируете 1<<n (побитовый сдвиг влево) для операции степени 2.

Таким образом, вы можете создать большое случайное число из меньших случайных чисел.

1. что означают буквы L, n, A, and b ? не могли бы вы объяснить, пожалуйста?

2. Предполагая, что меньшие числа u32 распределены равномерно, является ли такое объединенное число u64 = (u32 << 32) | u32 также?

3. @это. Я думаю, что да, но вы должны спросить математика.

4. L = (2^ n)*A B является проблемой, если диапазон B не равен [0 …(2 ^ n) -1]. Лучше использовать L = (2^ n)*A ^ B , если B диапазон шире (и по-прежнему равен степени 2). Лучше всего L = (max_possible_value_of_B (type_of_L)1) *A B

Ответ №6:

Или вы можете использовать два генератора случайных чисел с независимыми начальными значениями и объединить их выходные числа, как предложено. Это зависит от того, хотите ли вы 64-битное число RNG с периодом в диапазоне 2 ^ 64. Просто не используйте вызов по умолчанию, который зависит от времени, потому что вы получите одинаковые начальные значения для каждого генератора. Правильный путь, я просто не знаю…