Cum se generează numere aleatorii mari C

Caut o modalitate de a genera numere aleatorii mari la ordinul 2 ^ 64 în C ... (100000000 - 999999999), pentru a fi folosit într-un algoritm de criptare publică (ca p și q).

Nu vreau să generez un număr mai mic de 2 ^ 64 (adică mai mic de 100000000).

Există ceva care să mă ajute să fac asta?

9
[100000000 - 999999999] este 900.000.000 de valori diferite. Acestea sunt numerele de ordine de 30 de biți, nu 64.
adăugat autor chux, sursa
2 ^ 64 este mult mai mare decât 999999999.
adăugat autor undur_gongor, sursa

6 răspunsuri

AleAtoriu() returneAză o lungă cAre pe un sistem 64bit Ar trebui să fie 64 de biți. DAcă vă AflAți pe un sistem 32bit, puteți fAce următoArele:

#include 

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;

AlternAtiv, pe un sistem NIX Ai puteA să citești/dev/AleAtoriu în tAmponul tău:

#include 
#include 
#include 
#include    

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

12
adăugat
Pe calculatorul meu RAND_MAX este 2 ^ 31 , nu 2 ^ 32 .
adăugat autor Chiel ten Brinke, sursa
num = (num << 32) | rand (); este probabil slab dat "Dacă sunteți pe un 32bit", atunci RAND_MAX este probabil 2 ^ 31-1 sau mult mai puțin. Apoi num = (num << 32) | rand (); va genera întotdeauna un număr brut num cu niște biți eliminați în aceeași poziție. num% (999999999 - 100000000) contribuie la distribuirea acestei probleme inca pe seama costului lipsei chiar mai mare de distributie uniforma.
adăugat autor chux, sursa
Presupunând că numerele mai mici u32 sunt distribuite uniform, este un număr combinat u64 = (u32 << 32) | u32 de asemenea?
adăugat autor this, sursa
Acest lucru nu asigură cerința "Nu vreau să generez un număr mai mic decât ... 100000000".
adăugat autor undur_gongor, sursa
Mai bine, dar acum numerele de mai sus 805933941 (2 ^ 64 -1 mod 899999999) sunt puțin mai puțin probabile decât numerele de mai jos ;-)
adăugat autor undur_gongor, sursa
Adăugați linia num = (num% (999999999 - 100000000)) + 100000000; pentru a genera un număr aleatoriu din limita inferioară de 100000000 și limita superioară de 999999999.
adăugat autor David M. Syzdek, sursa
rand() este limitat de RAND_MAX care nu este necesar 2 ^ 32 . Și mai aveți nevoie de ceva pentru a trece la srand() . Funcția /dev/random este de asemenea disponibilă pe alte platforme >.
adăugat autor Piotr Praszmo, sursa

Puteți combina două numere aleatoare de 4 octeți pentru a produce o valoare de 8 octeți:

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

Since rand returns int, and sizeof(int) >= 4 on almost any modern platform, this code should work. I've added the << 0 to make the intent more explicit.

The masking with 0x00000000FFFFFFFF and 0xFFFFFFFF00000000 is to prevent overlapping of the bits in the two numbers in case sizeof(int) > 4.

EDIT

Deoarece @Banthar a comentat că RAND_MAX nu este neapărat 2 ^ 32 și cred că este garantat cel puțin 2 ^ 16 combinați patru numere de 2 octeți pentru a fi sigur:

uint64_t random = 
  (((uint64_t) rand() <<  0) & 0x000000000000FFFFull) | 
  (((uint64_t) rand() << 16) & 0x00000000FFFF0000ull) | 
  (((uint64_t) rand() << 32) & 0x0000FFFF00000000ull) |
  (((uint64_t) rand() << 48) & 0xFFFF000000000000ull);
9
adăugat
Opriți-vă: RAND_MAX este puțin probabil să fie 2 ^ 32 . Ar putea fi (2 ^ 32) - 1 . Cu toate acestea, chiar și acest lucru este neobișnuit. Este mai probabil ca INT_MAX care are o valoare comună (2 ^ 31) - 1 sau (2 ^ 15) - 1 . C indică RAND_MAX cel puțin (2 ^ 15) - 1 , nu 2 ^ 16 .
adăugat autor chux, sursa
Dacă folosiți ^ pentru a combina numerele în loc de | , nu trebuie să vă faceți griji în legătură cu mascarea.
adăugat autor caf, sursa

You're looking for a cryptographic-strength PRNG, like openssl/rand: http://www.openssl.org/docs/crypto/rand.html

7
adăugat
openssl.org/docs/crypto/rand.html link mort în august 2018 Una dintre problemele cu un răspuns doar la un link.
adăugat autor chux, sursa
Sau BCryptGenRandom pe Windows Vista și superior.
adăugat autor Alexey Frunze, sursa
+1: folosind rand() pentru aceasta este o gaură de securitate (prezicerea ieșirii rand()
adăugat autor Frank Farmer, sursa

You can make a large number L out of smaller numbers (e.g. A & B). For instance, with something like L = (2^ n)*A + B where ^ denotes exponentiation and n is some constant integer (e.g. 32). Then you code 1< (bitwise left-shift) for the power-of 2 operation.

Deci, puteți face un număr mare aleatoriu de numere aleatorii mai mici.

3
adăugat
L = (2 ^ n) * A + B este o problemă dacă domeniul B nu este [0 ... (2 ^ n) -1]. Este mai bine să utilizați L = (2 ^ n) * A ^ B dacă intervalul B este mai mare (și încă o putere de 2). Cel mai bun este să L = (max_possible_value_of_B + (type_of_L) 1) * A + B
adăugat autor chux, sursa
Presupunând că numerele mai mici u32 sunt distribuite uniform, este un număr combinat u64 = (u32 << 32) | u32 de asemenea?
adăugat autor this, sursa
@acest. Cred că da, dar ar trebui să întrebați un matematician.
adăugat autor Basile Starynkevitch, sursa
ce înseamnă literele L, n, A și b ? ai putea să-ți explici?
adăugat autor Ameen, sursa

Știu că probabil voi fi b____slapped de OliCharlesworth, dar folosiți rand() cu o scară și o compensare. Este în stdlib.h Pentru a acoperi întreaga gamă, trebuie să adăugați că la o altă randură mai mică() pentru a completa golurile din mapare.

3
adăugat

Sau puteți utiliza două generatoare de numere aleatoare cu semințe INDEPENDENT și puneți împreună numerele de ieșire sugerate. Asta depinde dacă doriți un număr de 64 de biți dintr-un RNG cu o perioadă cuprinsă între 2 ^ 64. Doar nu folosiți apelul implicit care depinde de timp, deoarece veți obține semințe identice pentru fiecare generator. Calea cea dreaptă, nu știu ...

1
adăugat