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

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

9 голосов
/ 27 октября 2011

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

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

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

Ответы [ 6 ]

13 голосов
/ 27 октября 2011

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

9 голосов
/ 27 октября 2011

Вы можете объединить два 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.

EDIT

Поскольку @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);
7 голосов
/ 27 октября 2011

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

3 голосов
/ 27 октября 2011

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

3 голосов
/ 27 октября 2011

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

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

0 голосов
/ 11 августа 2015

Или, вы можете использовать два генератора случайных чисел с НЕЗАВИСИМЫМИ семенами и сложить их выходные числа, как предложено. Это зависит от того, хотите ли вы 64-разрядное число ГСЧ с периодом в диапазоне 2 ^ 64. Только не используйте вызов по умолчанию, который зависит от времени, потому что вы получите идентичные семена для каждого генератора. Правильный путь, я просто не знаю ...

...