วิธีสร้างตัวเลขสุ่มขนาดใหญ่ C

ฉันกำลังมองหาวิธีสร้างตัวเลขสุ่มขนาดใหญ่ตามลำดับ 2^64 ใน C... (100000000 - 999999999) เพื่อใช้ในอัลกอริธึมการเข้ารหัสคีย์สาธารณะ (as p และ q)

ฉันไม่ต้องการสร้างตัวเลขที่เล็กกว่า 2^64 (นั่นคือ น้อยกว่า 100000000)

มีอะไรที่สามารถช่วยฉันทำเช่นนี้?


c rsa random
person gfppaste    schedule 27.10.2011    source แหล่งที่มา
comment
2^64 มากกว่า 999999999 มาก   -  person undur_gongor    schedule 28.10.2011
comment
[100000000 - 999999999] คือค่าที่แตกต่างกัน 900,000,000 ค่า ตัวเลขเหล่านี้เป็นลำดับ 30 บิต ไม่ใช่ 64   -  person chux - Reinstate Monica    schedule 16.08.2018

คำตอบ (6)


arrow_upward
14
arrow_downward

Random() ส่งคืนค่ายาวซึ่งในระบบ 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

person David M. Syzdek    schedule 27.10.2011
comment
rand() ถูกจำกัดด้วย RAND_MAX ซึ่งไม่จำเป็น 2^32 และคุณยังต้องการบางสิ่งเพื่อส่งต่อไปยัง srand() /dev/random ฟังก์ชันการทำงานยังมีให้บริการบน แพลตฟอร์มอื่นๆ - person Piotr Praszmo; 27.10.2011
comment
สิ่งนี้ไม่รับประกันข้อกำหนดที่ฉันไม่ต้องการสร้างจำนวนที่น้อยกว่า ... ตรงตาม 100000000 - person undur_gongor; 28.10.2011
comment
เพิ่มบรรทัด num = (num % (999999999 - 100000000)) + 100000000; เพื่อสร้างตัวเลขสุ่มของขีดจำกัดล่าง 100000000 และขีดจำกัดบน 999999999 - person David M. Syzdek; 28.10.2011
comment
ดีกว่า แต่ตอนนี้ตัวเลขที่สูงกว่า 805933941 (2^64 -1 mod 899999999) มีความน่าจะเป็นน้อยกว่าตัวเลขด้านล่างเล็กน้อย ;-) - person undur_gongor; 28.10.2011
comment
บนพีซีของฉัน RAND_MAX คือ 2^31 ไม่ใช่ 2^32 - person Chiel ten Brinke; 26.12.2014
comment
สมมติว่าจำนวนที่น้อยกว่า u32 มีการกระจายอย่างสม่ำเสมอ แล้วจำนวนรวมดังกล่าวจะเป็น u64 = (u32 << 32) | u32 ด้วยหรือไม่ - person this; 02.07.2015
comment
num = (num << 32) | rand(); น่าจะอ่อนแอหากคุณใช้ 32 บิต ดังนั้น RAND_MAX น่าจะเป็น 2^31-1 หรือน้อยกว่ามาก จากนั้น num = (num << 32) | rand(); จะเสมอสร้าง raw num โดยมีบิตบางส่วนถูกล้างในตำแหน่งเดียวกัน num % (999999999 - 100000000) ช่วยกระจายปัญหานั้นไปรอบๆ โดยที่ยังขาดการกระจายแบบเดียวกันอีกด้วย - person chux - Reinstate Monica; 16.08.2018

arrow_upward
10
arrow_downward

คุณสามารถรวมจำนวนเต็มสุ่ม 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 Blagovest Buyukliev    schedule 27.10.2011
comment
หากคุณใช้ ^ เพื่อรวมตัวเลขแทน | คุณไม่จำเป็นต้องกังวลเกี่ยวกับการมาสก์ - person caf; 28.10.2011
comment
ทีละรายการ: 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

arrow_upward
7
arrow_downward

คุณกำลังมองหา PRNG ที่มีการเข้ารหัสที่แข็งแกร่ง เช่น openssl/rand: http://www.openssl.org/docs/crypto/rand.html

person wkl    schedule 27.10.2011
comment
หรือ BCryptGenRandom บน Windows Vista และ สูงกว่า - person Alexey Frunze; 28.10.2011
comment
+1: การใช้ rand() สำหรับสิ่งนี้เป็นช่องโหว่ด้านความปลอดภัย (การทำนายผลลัพธ์ของ rand() นั้นไม่ได้ท้าทายมากนัก) - person Frank Farmer; 28.10.2011
comment
openssl.org/docs/crypto/rand.html ลิงก์เสียในเดือนสิงหาคม 2018 . หนึ่งในปัญหาที่มีลิงก์เท่านั้นที่ตอบได้ - person chux - Reinstate Monica; 16.08.2018

arrow_upward
3
arrow_downward

ฉันรู้ว่าฉันอาจจะโดน b____ ตบโดย OliCharlesworth แต่ใช้ rand() ด้วยสเกลและออฟเซ็ต มันอยู่ใน stdlib.h เพื่อให้ครอบคลุมทั้งช่วง คุณควรเพิ่มมันลงใน rand() ที่เล็กกว่าอีกอันเพื่อเติมเต็มช่องว่างในการแมป

person MartyTPS    schedule 27.10.2011

arrow_upward
3
arrow_downward

คุณสามารถสร้างตัวเลขขนาดใหญ่ L จากจำนวนที่น้อยกว่าได้ (เช่น A & B) เช่น L = (2^ n)*A + B โดยที่ ^ หมายถึงการยกกำลัง และ n คือจำนวนเต็มคงที่ (เช่น 32) จากนั้นคุณโค้ด 1<<n (เลื่อนไปทางซ้ายระดับบิต) สำหรับการดำเนินการยกกำลัง 2

ดังนั้นคุณสามารถสร้างตัวเลขสุ่มขนาดเล็กจำนวนมากโดยการสุ่มได้

person Basile Starynkevitch    schedule 27.10.2011
comment
ตัวอักษร L, n, A, and b หมายถึงอะไร? คุณช่วยอธิบายหน่อยได้ไหม? - person Ameen; 06.12.2014
comment
สมมติว่าจำนวนที่น้อยกว่า u32 มีการกระจายอย่างสม่ำเสมอ แล้วจำนวนรวมดังกล่าวจะเป็น u64 = (u32 << 32) | u32 ด้วยหรือไม่ - person this; 02.07.2015
comment
@นี้. ฉันเดาว่าใช่ แต่คุณควรถามนักคณิตศาสตร์ - person Basile Starynkevitch; 02.07.2015
comment
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 - person chux - Reinstate Monica; 16.08.2018

arrow_upward
-1
arrow_downward

หรือคุณสามารถใช้ตัวสร้างตัวเลขสุ่มสองตัวที่มีเมล็ดแบบอิสระและรวมหมายเลขเอาต์พุตไว้ด้วยกันตามที่แนะนำ ขึ้นอยู่กับว่าคุณต้องการ RNG จำนวน 64 บิตที่มีจุดในช่วง 2^64 หรือไม่ เพียงอย่าใช้การเรียกเริ่มต้นที่ขึ้นอยู่กับเวลา เพราะคุณจะได้รับเมล็ดพันธุ์ที่เหมือนกันสำหรับเครื่องกำเนิดแต่ละตัว มาถูกทางก็ไม่รู้...

person jwoods486    schedule 10.08.2015