Comment générer de grands nombres aléatoires C

Je suis à la recherche d'un moyen de produire de grands nombres aléatoires de l'ordre de 2^64 en C... (100000000 - 999999999), à utiliser dans un algorithme de chiffrement à clé publique (p et q).

Je ne veux pas générer un nombre inférieur à 2^64 (qui est, plus petit que 100000000).

Est-il quelque chose qui pourrait m'aider à faire cela?

2^64 est beaucoup plus grande que 999999999.
[100000000 - 999999999] est 900,000,000 des valeurs différentes. Ce sont des chiffres sont de l'ordre de 30 bits, pas 64.

OriginalL'auteur gfppaste | 2011-10-27

  1. 12

    random() renvoie un long sur un système 64 bits doivent être 64 bits. Si vous êtes sur un système 32 bits, vous pouvez effectuer les opérations suivantes:

    #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;

    Bien sur une NIX système, vous pourriez lire /dev/random dans votre mémoire tampon:

    #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;

    Un

    rand() est limitée par RAND_MAX qui pas nécessaire 2^32. Et, vous avez encore besoin de quelque chose pour passer à srand(). /dev/random fonctionnalité est également disponible sur autres plates-formes.
    Ce n'est pas s'assurer que l'exigence "je ne veux pas générer nombre plus petit que ... 100000000" est remplie.
    Ajoutez la ligne num = (num % (999999999 - 100000000)) + 100000000; pour générer un nombre aléatoire de la limite inférieure de 100000000 et la limite supérieure de la 999999999.
    Mieux, mais maintenant les chiffres ci-dessus 805933941 (2^64 -1 mod 899999999) sont légèrement moins probable que les chiffres ci-dessous 😉
    Sur mon pc RAND_MAX est 2^31, pas 2^32.

    OriginalL'auteur David M. Syzdek

  2. 9

    Vous pouvez combiner deux de 4 octets aléatoires entiers pour produire une 8 octets:

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

    Depuis rand retourne int, et sizeof(int) >= 4 sur presque n'importe quelle plate-forme moderne, ce code devrait fonctionner. J'ai ajouté le << 0 à l'intention plus explicite.

    Le masquage avec 0x00000000FFFFFFFF et 0xFFFFFFFF00000000 est pour éviter le chevauchement des bits dans les deux numéros en cas sizeof(int) > 4.

    MODIFIER

    Depuis @Banthar a commenté que RAND_MAX n'est pas nécessairement 2 ^ 32, et je pense qu'il est assuré d'être au moins 2 ^ 16, vous pouvez le combiner quatre 2 octets juste pour être sûr:

    uint64_t random = 
  (((uint64_t) rand() <<  0) & 0x000000000000FFFFull) | 
  (((uint64_t) rand() << 16) & 0x00000000FFFF0000ull) | 
  (((uint64_t) rand() << 32) & 0x0000FFFF00000000ull) |
  (((uint64_t) rand() << 48) & 0xFFFF000000000000ull);
    Si vous utilisez ^ de combiner les nombres au lieu de |, vous n'avez pas besoin de s'inquiéter à propos de l'effet de masque.
    Tout-en-un: RAND_MAX est très rare d'être 2 ^ 32. Il peut être (2 ^ 32) - 1. Pourtant, même ce qui est rare. Plus il est probable même que INT_MAX qui a une valeur commune de (2 ^ 31) - 1 ou (2 ^ 15) - 1. C spécifie RAND_MAX être au moins (2^15) - 1, pas 2 ^ 16.

    OriginalL'auteur Blagovest Buyukliev

  3. 7

    Vous êtes à la recherche pour un de chiffrement-force PRNG, comme openssl/rand: http://www.openssl.org/docs/crypto/rand.html

    Ou BCryptGenRandom sur Windows Vista et supérieur.
    +1: à l'aide de rand() car c'est un trou de sécurité (la prévision de la sortie de rand() n'est pas très difficile)
    openssl.org/docs/crypto/rand.html lien mort en Août 2018. L'un des problèmes avec un lien unique réponse.

    OriginalL'auteur wkl

  4. 3

    Je sais que je vais probablement obtenir b____giflé par OliCharlesworth, mais utiliser rand() avec une échelle et de décalage. C'est dans stdlib.h afin de couvrir l'ensemble de la gamme vous devez l'ajouter à un autre plus petit rand() pour combler les lacunes dans la cartographie.

    OriginalL'auteur MartyTPS

  5. 3

    Vous pouvez faire un grand nombre L de plus petits nombres (par exemple, A & B). Par exemple, avec quelque chose comme L = (2^ n)*A + B où ^ désigne l'exponentiation et n est une constante de type entier (p. 32). Ensuite, vous code 1<<n (bit à bit décalage vers la gauche) pour la puissance de 2 de l'opération.

    De sorte que vous peut faire un grand nombre aléatoire de petits nombres aléatoires.

    que signifient les lettres L, n, A, and b veux dire? pourriez vous m'expliquer s'il vous plaît?
    En supposant de plus petits nombres u32 sont uniformément réparties, est un nombre combiné u64 = (u32 << 32) | u32 aussi?
    Je suppose que oui, mais vous devriez demander à un mathématicien.
    L = (2^ n)*A + B est un problème si la plage de B n'est pas [0...(2^ n)-1]. Mieux utiliser L = (2^ n)*A ^ B si B gamme est plus large (et toujours une puissance de 2). Le mieux est de L = (max_possible_value_of_B + (type_of_L)1) *A + B

    OriginalL'auteur Basile Starynkevitch

  6. -1

    Ou, vous pouvez utiliser deux générateurs de nombres aléatoires INDÉPENDANTES les graines et les mettre à leur sortie des numéros ensemble, comme l'a suggéré. Cela dépend si vous voulez une version 64 bits d'un générateur de nombres aléatoires avec une période de l'ordre de 2^64. Il suffit de ne pas utiliser la valeur par défaut d'appel, qui dépend du temps, parce que vous allez obtenir les mêmes graines pour chaque générateur. Le droit chemin, je ne sais pas ...

    OriginalL'auteur jwoods486