Я ищу способ генерировать большие случайные числа порядка 2 ^ 64 в C... (100000000 - 999999999) для использования в алгоритме шифрования с открытым ключом (как p и q).
Я не хочу генерировать число меньше 2^64 (то есть меньше 100000000).
Есть ли что-нибудь, что могло бы помочь мне сделать это?
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, &num, 8);
close(fd);
// enforce limits of value between 100000000 and 999999999
num = (num % (999999999 - 100000000)) + 100000000;
A
rand() ограничено RAND_MAX, что не обязательно 2^32. И вам все еще нужно что-то передать srand(). Функции /dev/random также доступны на других платформах.
- person Piotr Praszmo; 27.10.2011
num = (num % (999999999 - 100000000)) + 100000000;, чтобы сгенерировать случайное число нижнего предела 100000000 и верхнего предела 999999999.
- person David M. Syzdek; 28.10.2011
RAND_MAX это 2^31, а не 2^32.
- person Chiel ten Brinke; 26.12.2014
u32 распределены равномерно, является ли такое объединенное число u64 = (u32 << 32) | u32 также?
- person this; 02.07.2015
num = (num << 32) | rand();, вероятно, слабое значение. Если вы используете 32-битную систему, то RAND_MAX, вероятно, будет 2 ^ 31-1 или намного меньше. Тогда num = (num << 32) | rand(); будет всегда генерировать необработанное num с некоторыми очищенными битами в одной и той же позиции. num % (999999999 - 100000000) действительно помогает распространять эту проблему, но ценой еще большего отсутствия равномерного распределения.
- person chux - Reinstate Monica; 16.08.2018
Вы можете объединить два 4-байтовых случайных целых числа, чтобы получить 8-байтовое:
#include <stdint.h>
...
uint64_t random =
(((uint64_t) rand() << 0) & 0x00000000FFFFFFFFull) |
(((uint64_t) rand() << 32) & 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) & 0x000000000000FFFFull) |
(((uint64_t) rand() << 16) & 0x00000000FFFF0000ull) |
(((uint64_t) rand() << 32) & 0x0000FFFF00000000ull) |
(((uint64_t) rand() << 48) & 0xFFFF000000000000ull);
^ для объединения чисел вместо |, вам не нужно беспокоиться о маскировании.
- person caf; 28.10.2011
RAND_MAX вряд ли будет 2 ^ 32. Это может быть (2 ^ 32) - 1. Но даже это редкость. Скорее всего, это то же самое, что и INT_MAX, который имеет общее значение (2 ^ 31) - 1 или (2 ^ 15) - 1. C определяет RAND_MAX как минимум (2^15) - 1, а не 2 ^ 16.
- person chux - Reinstate Monica; 16.08.2018
Вы ищете криптостойкий PRNG, например openssl/rand: http://www.openssl.org/docs/crypto/rand.html
rand() для этого является дырой в безопасности (предсказать вывод rand() не очень сложно)
- person Frank Farmer; 28.10.2011
Я знаю, что ОлиЧарльсворт, вероятно, даст мне пощечину, но используйте rand() со шкалой и смещением. Он находится в stdlib.h. Чтобы охватить весь диапазон, вы должны добавить его к другому меньшему rand(), чтобы заполнить пробелы в отображении.
Вы можете составить большое число L из меньших чисел (например, A и B). Например, с чем-то вроде L = (2^ n)*A + B, где ^ обозначает возведение в степень, а n — некоторое постоянное целое число (например, 32). Затем вы кодируете 1<<n (побитовый сдвиг влево) для операции степени 2.
Таким образом, вы можете сделать большое случайное число из меньших случайных чисел.
L, n, A, and b? не могли бы вы объяснить, пожалуйста?
- person Ameen; 06.12.2014
u32 распределены равномерно, является ли такое объединенное число u64 = (u32 << 32) | u32 также?
- person this; 02.07.2015
L = (2^ n)*A + B является проблемой, если диапазон B не равен [0...(2^ n)-1]. Лучше использовать L = (2^ n)*A ^ B, если диапазон B шире (и все еще степень двойки). Лучше всего L = (max_possible_value_of_B + (type_of_L)1) *A + B
- person chux - Reinstate Monica; 16.08.2018
Или вы можете использовать два генератора случайных чисел с НЕЗАВИСИМЫМИ начальными числами и объединить их выходные числа, как было предложено. Это зависит от того, хотите ли вы 64-битное число RNG с периодом в диапазоне 2 ^ 64. Только не используйте вызов по умолчанию, который зависит от времени, потому что вы получите одинаковые семена для каждого генератора. Как правильно, я просто не знаю...
