מחולל מספרים אקראיים - מיידי, חינמי ואקראי באמת

מהו מחולל מספרים אקראיים?

מחולל מספרים אקראיים (RNG) הוא מערכת - חישובית, פיזיקלית או היברידית - המייצרת רצף של מספרים שלא ניתן לחזות טוב יותר מאשר במקרה. כל ערך פלט אינו תלוי סטטיסטית בערכים שלפניו, והרצף המלא אינו מציג דפוס ניכר שצופה יכול לנצל כדי לנחש פלטים עתידיים. הגדרה זו נשמעת פשוטה, אך השגתה בפועל היא אחת הבעיות הקשות יותר במתמטיקה שימושית ובמדעי המחשב.

הביטוי "מחולל מספרים אקראיים" מכסה שני דברים שונים באופן מהותי שלעתים קרובות מתבלבלים ביניהם: מחוללי מספרים פסאודו-אקראיים (PRNGs) , המשתמשים באלגוריתמים דטרמיניסטיים כדי לייצר רצפים שנראים אקראיים בלבד, ומחוללי מספרים אקראיים אמיתיים (TRNGs) , הקוצרים אנטרופיה פיזיקלית אמיתית מהיקום. קטגוריה שלישית, מחוללי מספרים פסאודו-אקראיים מאובטחים קריפטוגרפית (CSPRNGs) , נמצאת בין השניים - דטרמיניסטיים ביישום אך מתוכננים כך שאף התקפה אפשרית מבחינה חישובית לא תוכל להבחין בין הפלט שלהם לאקראיות אמיתית.

למה מחוללי מספרים אקראיים חשובים

מספרי גישה אקראית (RNG) הם תשתית נושאת עומס במדע, אבטחה ותוכנה יומיומית. ללא אקראיות אמינה, קריפטוגרפיה מודרנית קורסת: כל סשן TLS, כל הודעה מוצפנת, כל חתימה דיגיטלית תלויים במפתחות סודיים שחייבים להיות בלתי צפויים. בתי קזינו, הגרלות ומשחקים מקוונים תלויים במספרי גישה אקראית לצורך הוגנות. סימולציות מדעיות - החל ממידול אקלים ועד גילוי תרופות - משתמשות בדגימה אקראית כדי לקרב פתרונות שקשה לפתור אותם מבחינה אנליטית. דגימה סטטיסטית, בדיקות A/B, יצירת עולמות משחק פרוצדורליים ואפילו אתחול משקל רשת עצבית - כולם דורשים מספרים אקראיים באיכות גבוהה.

ההשלכות של אקראיות גרועה הן חמורות ומתועדות היטב. בשנת 2012, חוקרים גילו שמיליוני מפתחות ציבוריים של RSA באינטרנט חולקים גורמים ראשוניים משותפים מכיוון שהמכשירים שיצרו אותם לא היו בעלי אנטרופיה מספקת בזמן האתחול. תוקף שמפרק גורם ראשוני משותף יכול לשחזר את המפתח הפרטי ולפענח את כל התקשורת. בשנת 2010, קונסולת ה-Sony PlayStation 3 נשברה מכיוון שמימוש ה-ECDSA שלו השתמש שוב באותו ערך "אקראי" nonce עבור כל חתימה - ערך חוזר יחיד מספיק כדי לחלץ את המפתח הפרטי באופן אלגברי. אלה אינם מקרי קצה; הם התוצאה הצפויה של התייחסות לאקראיות כבעיה פתורה.

תחומי יישומים מרכזיים

• קריפטוגרפיה ואבטחה: יצירת מפתחות, וקטורי אתחול, nonces, salts, אסימוני session tokens ומספרי סידוריים של תעודות.
• סימולציות ומידול: שיטות מונטה קרלו, משוואות דיפרנציאליות סטוכסטיות, סימולציות פיזיקת חלקיקים, מודלים אפידמיולוגיים.
• משחקים והימורים: ערבוב קלפים, הטלת קוביות, תוצאות מכונות מזל, יצירת רמות פרוצדורליות, טבלאות שלל.
• סטטיסטיקה ומחקר: דגימה אקראית, ניסויים מבוקרים אקראיים, bootstrapping, פיצולי אימות צולבים.
• מערכות מבוזרות: בחירת מנהיג, איזון עומסים עם ריצוד, נסיגה אקספוננציאלית עם עיכובים אקראיים.
• למידת מכונה: אתחול משקל, מסכות נשירה, הגדלת נתונים, ירידת גרדיאנט סטוכסטית.

כיצד פועל מחולל מספרים פסאודו-אקראי

PRNG מתחיל ב- seed - מספר בודד או בלוק נתונים קטן - ומחיל פונקציה מתמטית דטרמיניסטית שוב ושוב כדי לייצר רצף ארוך של פלטים. בהינתן אותו seed, הרצף ניתן לשחזור מושלם. בהינתן seed שונה, הרצף נראה שונה לחלוטין. איכותו של PRNG נשפטת לפי מידת ההצלחה שלו במעבר מבחנים סטטיסטיים לאקראיות, ובמקרים של יישומי אבטחה, האם ניתן להסיק את מצבו הפנימי מהפלטים שלו.

גנרטורים חופפים ליניאריים

משפחת PRNG העתיקה והפשוטה ביותר משתמשת בפונקציה החזרתית X _n+1 = (aX _n + c) mod m , כאשר a, c ו-m הם קבועים שנבחרו בקפידה. פונקציית rand() של ספריית הסטנדרט C במימושים רבים היא מחולל קונגרונציאלי ליניארי (LCG). LCGs מהירים וקלים למימוש, אך יש להם חולשות חמורות: מחזור הביטים מסדר נמוך עם תקופות קצרות, תקופת הרצף המלא היא לכל היותר m, והמצב הפנימי ניתן לשחזור טריוויאלי ממספר פלטים מועט. הם מקובלים עבור סימולציות ומשחקים פשוטים ללא דרישת אבטחה, ולא מקובלים לחלוטין עבור כל דבר קריפטוגרפי.

מרסן טוויסטר

ה-Mersenne Twister (MT19937), שפורסם על ידי מאטסומוטו ונישימורה בשנת 1998, הפך ל-PRNG ברירת המחדל בפייתון, רובי, R, PHP ושפות רבות אחרות. יש לו מחזור של 2 ¹⁹⁹³⁷ −1 (גדול מבחינה אסטרונומית), הוא עובר כמעט את כל הבדיקות הסטטיסטיות ופועל במהירות. המצב הפנימי שלו הוא 624 מספרים שלמים של 32 סיביות. החולשה הקריטית: אם תוקף צופה ב-624 פלטים רצופים, הוא יכול לשחזר את המצב הפנימי המלא ולחזות כל פלט עתידי. לכן, Mersenne Twister אינו מתאים לחלוטין לכל יישום רגיש לאבטחה, למרות שהוא נעשה בו שימוש לרעה באופן נרחב בתפקיד זה.

PRNG מודרניים: Xoshiro, PCG ו-SFC

מערכות PRNG שאינן קריפטוגרפיות, המהוות כיום את שיטות העבודה המומלצות, כוללות את משפחת PCG (Permuted Congruential Generators), ‏ xoshiro256** ו- SFC64 . גנרטורים אלה קטנים יותר, מהירים יותר ועולים סטטיסטית על Mersenne Twister. ל-PCG בפרט יש ביצועים מצוינים על סוללת TestU01 BigCrush - חבילת הבדיקות הסטטיסטיות הסטנדרטית התובענית ביותר עבור PRNG. NumPy החליף את מחולל ברירת המחדל שלו מ-Mersenne Twister ל-PCG64 בגרסה 1.17 בדיוק מסיבה זו.

כיצד פועל PRNG מאובטח קריפטוגרפית

CSPRNG חייב לעמוד בשתי תכונות מעבר לאקראיות סטטיסטית רגילה. ראשית, חוסר יכולת חיזוי של הביט הבא : בהינתן כל הפלט הקודם, אף אלגוריתם בזמן פולינומי אינו יכול לחזות את הביט הבא בהסתברות גדולה באופן משמעותי מ-50%. שנית, עמידות לפשרת מצב : אם תוקף לומד את המצב הפנימי הנוכחי, הוא אינו יכול לשחזר פלטים קודמים (זה נקרא סודיות לאחור או התנגדות למעקב לאחור).

מערכות הפעלה מודרניות מספקות CSPRNGs כשירות ליבה. לינוקס חושפת /dev/urandom ואת syscall getrandom() , שניהם שואבים ממאגר אנטרופיה של הליבה שנזרע על ידי אירועי חומרה. Windows מספק BCryptGenRandom() . macOS ו-iOS משתמשים ב- arc4random_buf() , אשר מאז macOS 10.12 מגובה על ידי ChaCha20. המבנים הבסיסיים המשמשים ב-CSPRNGs הייצור כוללים Hash_DRBG , HMAC_DRBG ו- CTR_DRBG (כולם סטנדרטיים ב-NIST SP 800-90A), כמו גם גנרטורים מבוססי ChaCha20 המשמשים את BSDs ולינוקס מודרנית.

כיצד פועל מחולל מספרים אקראיים אמיתי

TRNG מחלץ אקראיות מתהליכים פיזיקליים שבאמת בלתי צפויים - בין משום שהם ביסודם מכניים קוונטיים ובין משום שהם כוללים מערכות קלאסיות כאוטיות הרגישות לתנאי התחלה בלתי ניתנים למדידה.

מקורות אנטרופיה פיזיקליים נפוצים

• רעש תרמי (רעש ג'ונסון-ניקוויסט): תנועה אקראית של אלקטרונים בנגד מייצרת תנודות מתח שניתן לדגום ולהפוך אותן לדיגיטליות.
• רעש ירי: הגעה דיסקרטית ואקראית של פוטונים או אלקטרונים לגלאי מייצרת אות אקראי מדיד.
• דעיכה רדיואקטיבית: תזמון אירועי דעיכה ממקור רדיואקטיבי הוא אקראי קוונטי לחלוטין. RANDOM.ORG משתמש ברעש רדיו אטמוספרי, שהוא בלתי צפוי באופן דומה.
• מקורות אופטיים קוונטיים: זמני הגעה של פוטונים, תנודות ואקום הנמדדות על ידי גילוי הומודיין, ובחירת נתיב של מפצל אלומה, כולם מקורות לאקראיות קוונטית מאושרת.
• אנטרופיה חומרתית במכשירים צרכניים: מעבדים מודרניים כוללים הוראות RNG חומרתיות ייעודיות. RDRAND של אינטל משתמש במקור רעש תרמי על השבב המותנה באמצעות AES-CBC-MAC. המקבילה של AMD פועלת באופן דומה. TrustZone של ARM כולל מקור אנטרופיה חומרתית הנגיש למערכת ההפעלה.
• מאגרי אנטרופיה של מערכת ההפעלה: לינוקס אוספת אנטרופיה מתזמון פסיקות, השהיית קלט/פלט של הדיסק, זמני הגעת חבילות רשת והוראות RNG של חומרה, ומערבבת אותם באמצעות מבנה קריפטוגרפי כדי לייצר את מאגר האנטרופיה של הליבה.

בעיית ההתניה

רעש פיזי גולמי לעיתים רחוקות מפוזר באופן אחיד. מקור רעש תרמי עשוי לייצר מעט יותר אפס שניות מאחד שניות עקב אסימטריות במעגל. לכן, TRNG כולל שלב התניה - בדרך כלל גיבוב קריפטוגרפי או פונקציית חילוץ - שדוחס את הדגימות הגולמיות לפלט קצר יותר ואחיד שניתן להוכיח. היחס בין ביטים גולמיים שנצרכו לביטים המופקים נקרא קצב האנטרופיה המינימלי , ו-TRNG מתוכנן היטב מאפיין קצב זה בקפידה. NIST SP 800-90B מגדיר את דרישות הבדיקה והאימות עבור מקורות אנטרופיה המשמשים במערכות פדרליות.

השוואה בין PRNG, CSPRNG ו-TRNG

נֶכֶס	PRNG	CSPRNG	טרנג
דטרמיניסטית	כֵּן	כן (אחרי הזריעה)	לֹא
ניתן לשחזור מזרעים	כֵּן	כֵּן	לֹא
עובר מבחנים סטטיסטיים	בְּדֶרֶך כְּלַל	כֵּן	כן (לאחר התניה)
מאובטח מפני חיזוי	לֹא	כֵּן	כֵּן
מְהִירוּת	מהיר מאוד	מָהִיר	איטי (מוגבל בחומרה)
דורש אנטרופיה של חומרה	רק לזריעה	רק לזריעה	תָמִיד
מקרי שימוש אופייניים	סימולציות, משחקים, דגימה	יצירת מפתחות, טוקנים, קריפטוגרפיה	מפתחות בעלי אבטחה גבוהה, רגולציה על הימורים, מחקר

ההגדרה הסטטיסטית של אקראיות

אקראיות אינה תכונה בינארית - היא קיימת על ספקטרום, והסטנדרט המתאים תלוי לחלוטין ביישום. רצף נחשב אקראי למטרה נתונה אם אף בדיקה רלוונטית למטרה זו לא יכולה להבדיל אותו מרצף אקראי אידיאלי מבחינה תיאורטית. NIST מפרסם חבילת בדיקות סטטיסטית (SP 800-22) המכסה חמישה עשר בדיקות, כולל ניתוח תדרים, מבחני הרצות, ניתוח ספקטרלי ומורכבות ליניארית. סוללת BigCrush של ספריית TestU01, שפותחה באוניברסיטת מונטריאול, תובענית אף יותר, ומיישמת 106 בדיקות שונות. גנרטור שנכשל ב-BigCrush אינו מתאים לעבודת סימולציה רצינית, ללא קשר למהירות הפעולה שלו.

כדאי לדייק לגבי מה שאיננה משמעותה של אקראיות. רצף כמו 1, 2, 3, 4, 5 אינו אקראי למרות שכל מספר בודד סביר כמו כל מספר אחר - הדפוס ניתן לחיזוי. לעומת זאת, רצף יכול להיראות מעוצב באופן מקומי על ידי מקריות (שלושה ראשים ברציפות ממטבע הוגן) מבלי להיות לא אקראי. אקראיות היא תכונה של תהליך היצירה, לא של רצף פלט מסוים כלשהו כשהוא מסתכל בנפרד.

כיצד פועלים מחוללי מספרים אקראיים: מנגנוני ליבה וטקטיקות מעשיות

מחוללי מספרים אקראיים מתחלקים לשתי קטגוריות בסיסיות - מחוללי מספרים פסאודו-אקראיים (PRNGs) המשתמשים באלגוריתמים דטרמיניסטיים עם ערך התחלתי, ומחוללי מספרים אקראיים אמיתיים (TRNGs) שמפיקים אנטרופיה מתופעות פיזיקליות. בחירת הסוג הנכון, זריעתו בצורה נכונה ויישומו במקרה השימוש הספציפי שלכם קובעים האם התוצאות שלכם מבוססות סטטיסטית, מאובטחות קריפטוגרפית או ניתנות לחיזוי בצורה מסוכנת.

אסטרטגיה שלב אחר שלב לבחירה ושימוש ב-RNG

לפני יצירת מספר בודד, עליכם להתאים את המחולל למשימה. שימוש ב-PRNG מהיר ליצירת מפתחות קריפטוגרפיים הוא אחת הטעויות המשמעותיות ביותר באבטחת תוכנה. באופן דומה, שימוש ב-RNG חומרתי איטי עבור סימולציית מונטה קרלו עם מיליארדי איטרציות מבזבז משאבים שלא לצורך. השלבים הבאים ידריכו אתכם בתהליך קבלת ההחלטות מעקרונות ראשוניים.

שלב 1: הגדירו את דרישות האקראיות שלכם

שאלו שלוש שאלות לפני שנוגעים בכלי או ספרייה:

• האם יכולת החיזוי חשובה? אם יריב שמנחש את המספרים שלך גורם נזק - בקריפטוגרפיה, הימורים, הגרלות או אסימוני אבטחה - אתה זקוק לאקראיות ברמה קריפטוגרפית. אם אתה מפעיל סימולציית פיזיקה או מנגן ערבוב של רשימת השמעה, PRNG באיכות גבוהה מספיק.
• כמה מספרים אתה צריך? לחלק מהגנרטורים יש מחזורים סופיים. למרסן טוויסטר, הנמצא בשימוש נרחב במודול random של פייתון ובשפות רבות, יש מחזור של 2 ¹⁹⁹³⁷ −1, שהוא גדול באופן אסטרונומי לרוב המטרות אך עדיין סופי ודטרמיניסטי.
• האם אתם זקוקים לשחזור? ניסויים מדעיים ויצירת משחקים פרוצדורליים דורשים לעתים קרובות את אותו רצף בדיוק כדי להתחדש. PRNG עם זרעים מספק לכם את זה. TRNG לא.

שלב 2: בחירת סוג הגנרטור המתאים

מקרה שימוש	גנרטור מומלץ	דוגמאות
מפתחות קריפטוגרפיים, סיסמאות, טוקנים	CSPRNG (PRNG מאובטח קריפטוגרפית)	מודול secrets (Python), crypto.randomBytes (Node.js), /dev/urandom (לינוקס)
סימולציות, סטטיסטיקה, למידת מכונה	PRNG איכותי	Mersenne Twister, PCG64, xoshiro256**
הגרלות, הגרלות ניתנות לביקורת	TRNG או RNG חומרה מוסמך	RANDOM.ORG, מודולי אבטחת חומרה (HSM)
משחקים, יצירת פרוצדורלים	PRNG זרעים	מרסן טוויסטר, LCG עם קבועים טובים
מערכות משובצות בזמן אמת	RNG חומרתי על שבב	אינטל RDRAND, ARM TrueRNG

שלב 3: זריעה נכונה של הגנרטור

ה-seed הוא נקודת הכשל היחידה עבור רוב פריסות PRNG. seed חלש או צפוי קורס את כל מודל האבטחה של PRNG, לא משנה כמה מתוחכם האלגוריתם שלו.

• השתמשו ב-seeds (מאגרי אנטרופיה) בעלי אנטרופיה גבוהה. מאגרי אנטרופיה של מערכת ההפעלה ( /dev/urandom ביוניקס, CryptGenRandom בחלונות) משלבים אירועי חומרה - תזמוני מקלדת, הפרעות דיסק, הגעת חבילות רשת - כדי לייצר seeds שכמעט בלתי אפשרי לחזות.
• לעולם אל תפעילו זריעה באמצעות שעון המערכת בלבד. תוקף שיודע את השעה המשוערת שבה התוכנית התחילה יכול לבצע פעולות Brute-force של זריעה מבוססת חותמת זמן תוך שניות. פגיעות זו נוצלה במתקפות אמיתיות על אתרי פוקר מקוונים ומערכות לוטו.
• לעולם אל תעשה קידוד קשיח של זרעים (seeds) בקוד ייצור. זרע קבוע מייצר את אותו הרצף בכל ריצה. זה שימושי לבדיקות אך קטסטרופלי לאבטחה.
• יש לבצע זריעה מחדש מעת לעת ביישומים ארוכי טווח. אם האפליקציה שלך פועלת במשך ימים או שבועות, הזרקה תקופתית של אנטרופיה חדשה מונעת מהמחולל לחזור למצב צפוי.

שלב 4: החלת הגנרטור על המשימה הספציפית שלך

יצירת מספר אקראי גולמי היא לעיתים רחוקות המטרה הסופית. היישום המעשי - דגימה, ערבוב, מיפוי טווחים - מציג מצבי כשל משלו.

יצירת מספרים בטווח

הגישה הנאיבית של שימוש באופרטור המודולו ( rand() % N ) גורמת להטיה מודולו. אם טווח הפלט של המחולל אינו מתחלק באופן שווה ב-N, ערכים מסוימים מופיעים בתדירות גבוהה יותר מאחרים. לדוגמה, אם המחולל שלך מייצר ערכים מ-0 עד 32767 ואתה רוצה מספרים מ-0 עד 99, ערכים 0-67 יופיעו מעט בתדירות גבוהה יותר מאשר 68-99 מכיוון ש-32768 אינו מתחלק ב-100.

• השתמשו בדגימת דחייה. בטלו ערכים שנופלים בזנב המוטה וציירו מחדש. רוב ספריות הסטנדרטים המיושמות היטב עושות זאת באופן אוטומטי.
• השתמשו בפונקציות טווח מובנות. פונקציות random.randint(a, b) של Python, ThreadLocalRandom.nextInt(origin, bound) של Java ופונקציות דומות מטפלות בהטיה באופן פנימי.
• לשימוש קריפטוגרפי, השתמשו במודול secrets בפייתון או במקביל, אשר מיישם בחירת טווחים בלתי מוטה כברירת מחדל.

ערבוב רשימה בצורה הוגנת

ערבוב פישר-ייטס (הנקרא גם ערבוב קנות') הוא האלגוריתם הנכון היחיד ליצירת תמורה אקראית אחידה. הוא פועל על ידי איטרציה מהאלמנט האחרון לראשון, תוך החלפת כל אלמנט באלמנט שנבחר באופן אקראי במיקומו הנוכחי או לפניו.

1. התחל באינדקס האחרון i = n−1.
2. בחר אינדקס אקראי j כאשר 0 ≤ j ≤ i.
3. החליפו אלמנטים במיקומים i ו- j .
4. הפחת את i וחזור על הפעולה עד ש- i = 0.

החלופה התמימה - בחירת מיקום אקראי לכל אלמנט בנפרד - אינה מייצרת התפלגות אחידה. חלק מהתמורות מופיעות בתדירות גבוהה יותר מאחרות, וזהו פגם מדיד וניתן לניצול במשחקי קלפים והגרלות.

דגימה ללא החלפה

כאשר נדרשים k ערכים ייחודיים מאוכלוסייה של n, שליפה והסרת כפילויות אינה יעילה. השתמשו בדגימת מאגרים עבור מערכי נתונים גדולים או סטרימינג, או בפישר-ייטס על עותק של האוכלוסייה עבור קבוצות קטנות יותר. random.sample(population, k) של פייתון מיישמת זאת בצורה נכונה ויעילה.

שלב 5: בדיקת איכות הפלט של הגנרטור שלך

אפילו RNG מיושם כהלכה יכול להיכשל ביישומים ספציפיים אם המאפיינים הסטטיסטיים שלו אינם תואמים את דרישות האפליקציה. חבילות בדיקות סטנדרטיות מזהות את רוב הפגמים.

• TestU01 (BigCrush): סוללת הבדיקות הסטטיסטיות הקפדנית ביותר עבור PRNGs. היא מיישמת מאות בדיקות ומסוגלת לזהות קורלציות עדינות שבדיקות פשוטות יותר מפספסות. גנרטורים ישנים רבים, כולל כמה גרסאות LCG, נכשלים ב-BigCrush.
• דיהארד / דיהארד: חבילה נפוצה של מבחנים סטטיסטיים שפותחה במקור על ידי ג'ורג' מרסליה. דיהארד היא הגרסה המעודכנת והמורחבת.
• NIST SP 800-22: חבילת הבדיקות הסטנדרטית עבור RNGs קריפטוגרפיים, הנדרשת להסמכת FIPS. היא בודקת תדירות, ריצות, תכונות ספקטרליות ועוד.
• PractRand: טוב במיוחד בזיהוי כשלים בגנרטורים עם פרקי זמן קצרים או דיפוזיה חלשה.

טעויות נפוצות שיש להימנע מהן

רוב כשלי ה-RNG במערכות ייצור נובעים מקבוצה קטנה של שגיאות חוזרות. זיהוין מראש מונע את רוב הפגיעויות והבעיות הסטטיסטיות בעולם האמיתי.

טעות 1: שימוש ב-Math.random() או שווה ערך לאבטחה

פונקציות Math.random() של JavaScript, מודול random של Python (לא secrets ), rand() של PHP ופונקציות דומות למטרות כלליות מתועדות במפורש כלא מתאימות לשימוש קריפטוגרפי. הן נותנות עדיפות למהירות על פני חוסר יכולת לחיזוי. תוקף שצופה בכמות מספקת של ערכי פלט יכול לשחזר את המצב הפנימי של Mersenne Twister עם עד 624 פלטים רצופים של 32 סיביות, ולאחר מכן לחזות את כל הערכים העתידיים. התקפה זו הודגמה בפלטפורמות הימורים חיות.

טעות 2: שימוש חוזר באותו זרע בין סשנים

אם יישום אינטרנט מזריק את מזהה התהליך או חותמת הזמן של ההפעלה למחולל אסימון ההפעלה שלו, כל אסימון הפעלה שנוצר באותה שנייה חולק את אותו ה-seed. זה לא תיאורטי - זה היה שורש הפגיעויות של חטיפת הפעלה במסגרות ייצור.

טעות 3: יצירת מעט מדי ביטים עבור האנטרופיה הנדרשת

לקוד סודי בן 6 ספרות יש בערך 20 סיביות של אנטרופיה. ל-UUID v4 יש 122 סיביות. מפתח קריפטוגרפי זקוק לפחות ל-128 סיביות להצפנה סימטרית ול-256 סיביות לאבטחה ארוכת טווח מפני חומרה עתידית. יצירת אסימונים קצרים והנחה שהם בלתי ניתנים לניחוש היא פגם מבני, לא פרט יישום.

טעות 4: התעלמות מהתנהגות ספציפית לפלטפורמה

• בכמה ליבות לינוקס ישנות יותר, קריאה מבלוקים של /dev/random כאשר מאגר האנטרופיה מתרוקן. /dev/urandom אינו חוסם והוא בטוח לרוב מטרות ההצפנה לאחר האתחול הראשוני.
• למכונות וירטואליות יכולה להיות אנטרופיה מופחתת בעת ההפעלה מכיוון שחסר להן גיוון אירועי חומרה כמו במכונות פיזיות. זריעה מיד לאחר יצירת מופעים של מכונה וירטואלית יכולה לייצר מפתחות חלשים.
• בחלק מהמערכות המשובצות אין כלל RNG חומרתי. מפתחים נוטים לפעמים לחזור למקורות אנטרופיה מבוססי תוכנה בלבד, שהם חלשים בהרבה ממה שהם נראים.

טעות 5: התייחסות לפלט מעורבב כאקראי באופן אחיד ללא אימות

אם ל-RNG הבסיסי יש פרק זמן קצר יותר ממספר התמורות האפשריות של מערך הנתונים שלך, לא ניתן יהיה לייצר את כל התמורות. חפיסת קלפים סטנדרטית של 52 קלפים מכילה 52! ≈ ^2,226 סדרים אפשריים. מחולל עם זרימה של 32 סיביות יכול לייצר לכל היותר ^2.32 ≈ 4 מיליארד רצפים שונים - חלק קטן להחריד מכלל הערבובים האפשריים. עבור משחקי קלפים עם סכומים אמיתיים, זוהי חולשה קונקרטית וניתנת לניצול.

טעות 6: בלבול בין עצמאות לאחידות

רצף יכול להיות מפוזר באופן אחיד - כל ערך מופיע בתדירות שווה - ועדיין להיות מתואם גבוה בין תוכניות רציפות. רצפי LCG רבים באיכות נמוכה עוברים מבחני תדירות אך נכשלים בבדיקות ספקטרליות מכיוון שערכיהם העוקבים נופלים על מספר קטן של היפר-מישורים במרחב רב-ממדי. ארטיפקט זה, המכונה מבנה הסריג של LCG, הופך אותם ללא מתאימים לאינטגרציה רב-ממדית של מונטה קרלו.

טקטיקות מעשיות לפי שפת תכנות

פִּיתוֹן

• השתמש ב- secrets.token_bytes(n) , secrets.token_hex(n) , או secrets.randbelow(n) עבור כל ערך רגיש לאבטחה.
• השתמשו בפונקציה random.SystemRandom() כתחליף לפונקציה random.Random() כאשר אתם זקוקים לממשק הסטנדרטי המגובה על ידי אנטרופיה של מערכת ההפעלה.
• עבור עבודה מספרית, השתמשו numpy.random.default_rng() אשר מוגדר כברירת מחדל למחולל PCG64, PRNG מודרני באיכות גבוהה שעובר את בדיקת BigCrush.

ג'אווהסקריפט / Node.js

• השתמשו crypto.randomBytes(n) או crypto.getRandomValues() (ממשק API של הצפנת אינטרנט בדפדפנים) לכל מטרות האבטחה.
• לעולם אל תשתמש בפונקציה Math.random() עבור טוקנים, מזהים או כל דבר אחר שיריב עשוי לנסות לחזות.

ג'אווה

• השתמשו ב- java.security.SecureRandom למטרות קריפטוגרפיות. צרו מופע פעם אחת והשתמשו בו שוב - בנייה יקרה.
• השתמש ThreadLocalRandom עבור יישומים שאינם קשורים לאבטחה בעלי תפוקה גבוהה בסביבות מרובות הליכי משנה.
• הימנעו מ- java.util.Random בהקשרים בו-זמניים - הוא משתמש ב-seed משותף שיכול לייצר התנגשויות תחת תחרות.

C / C++

• הימנעו מ- rand() מספריית התקן של C. היא מוגדרת-מימוש, לרוב LCG חלש, ואינה בטוחה בפני הליכי משנה.
• השתמש ב- std::mt19937 מ- <random> שנזרע עם std::random_device לשימוש כללי.
• לשימוש קריפטוגרפי, קראו ישירות לפרימיטיבים של מערכת ההפעלה: getrandom() בלינוקס, BCryptGenRandom בחלונות.

כלים, תוכנה ואוטומציה למחולל מספרים אקראיים

כלי מחולל המספרים האקראיים הנפוצים ביותר נעים בין שירותים מבוססי דפדפן כמו RANDOM.ORG (המפיק אנטרופיה מרעש אטמוספרי) ועד ספריות קריפטוגרפיות המובנות בכל שפת תכנות מרכזית. בחירת הכלי המתאים תלויה במקרה השימוש שלך: סימולציות סטטיסטיות זקוקות למהירות ואיכות סטטיסטית, יישומי אבטחה זקוקים לחוסר יכולת חיזוי קריפטוגרפית, וניסויים פיזיקליים זקוקים לאקראיות חומרתית אמיתית.

כלי RNG מבוססי דפדפן ומקוונים

כלי RNG מקוונים אינם דורשים התקנה ומתאימים להגרלות מזדמנות, הדגמות בכיתה וקבלת החלטות מהירה. האפשרויות המכובדות ביותר כוללות:

• RANDOM.ORG — משתמש ברעש רדיו אטמוספרי כמקור אנטרופיה אמיתי. מציע מחוללי מספרים שלמים, ערבובי רצפים, מחוללי גאוס וממשק API מבוסס-מכסות לגישה תכנותית.
• ה-RNG המובנה של גוגל - חיפוש "מספר אקראי בין 1 ל-100" בגוגל מחזיר תוצאה מיידית באמצעות PRNG שנזרע מאנטרופיית המערכת.
• כלי גלגל בוחר מספרים - ממשקי גלגל מסתובב חזותיים המשתמשים ב-JavaScript Math.random() מתחת למכסה המנוע, מתאימים לבחירות בסגנון כיתתי או משחקי וידאו.
• סקר קש וגלגל שמות - שילוב הזנת רשימה עם בחירה אקראית עבור מטלות צוות, הגרלות פרסים והחלטות קבוצתיות.

מגבלה משמעותית של רוב כלי הדפדפן היא שהם מסתמכים על Math.random() של JavaScript, שהוא PRNG ואינו מאובטח קריפטוגרפית. עבור כל דבר שקשור לאבטחה, טוקנים או החלטות פיננסיות, השתמשו בכלי או ספרייה קריפטוגרפיים ייעודיים במקום זאת.

ספריות שפות תכנות ופונקציות מובנות

כל שפת תכנות מרכזית מגיעה עם לפחות מודול RNG אחד. הטבלה שלהלן מסכמת את האפשרויות הנפוצות ביותר ואת סיווג האבטחה שלהן:

שָׂפָה	PRNG סטנדרטי	RNG קריפטוגרפי	הערות
פִּיתוֹן	אקראי (מרסן טוויסטר)	סודות, os.urandom()	השתמש בסודות עבור טוקנים, סיסמאות ומפתחות
ג'אווהסקריפט	מתמטיקה.אקראי()	crypto.getRandomValues()	ממשק ה-API של Web Crypto זמין בכל הדפדפנים המודרניים
ג'אווה	java.util.Random	java.security.SecureRandom	חסימות SecureRandom עד שתהיה מספיק אנטרופיה זמינה
C / C++	rand() (להימנע בפונקציה של ייצור)	/dev/urandom, הוראת RDRAND	rand() חלש; השתמש באנטרופיה ברמת מערכת ההפעלה לכל דבר רציני.
לָלֶכֶת	מתמטיקה/ראנד	קריפטו/ראנד	קריפטו/ראנד קורא ישירות ממערכת ההפעלה CSPRNG
אוֹדֶם	אקראי (מבוסס MT)	מאובטח אקראי	SecureRandom עוטף את OpenSSL או /dev/urandom
PHP	rand(), mt_rand()	‏random_bytes(), random_int()	random_int() מגובה על ידי CSPRNG מאז PHP 7

התקני RNG חומרה

עבור יישומים הדורשים אנטרופיה באיכות הגבוהה ביותר - כגון יצירת מפתחות של רשות אישורים, מודולי אבטחת חומרה (HSM) או מכשור מדעי - זמינים מחוללי מספרים אקראיים חומרתיים ייעודיים (HRNG):

• Intel RDRAND / RDSEED - הוראות ברמת המעבד הדוגמות רעש תרמי ממעגלים על השבב, זמינות ברוב מעבדי x86 המודרניים מאז Ivy Bridge (2012).
• HRNGs USB ייעודיים - מכשירים כמו OneRNG או TrueRNG מתחברים ליציאת USB ומזינים אנטרופיה למאגר מערכת ההפעלה דרך /dev/random או /dev/urandom בלינוקס.
• מודולי אבטחת חומרה (HSM) - מכשירים ברמה ארגונית מספקים כמו Thales, Entrust ו-AWS CloudHSM המייצרים ומאחסנים מפתחות קריפטוגרפיים באמצעות מקורות אנטרופיה חומרתיים מוסמכים.
• שירותי RNG קוונטיים - ממשקי API לענן של ID Quantique ו-ANU (האוניברסיטה הלאומית האוסטרלית) מספקים ביטים אקראיים הנגזרים מתנודות ואקום קוונטי, ומציעים פלט שאינו דטרמיניסטי שניתן להוכיח.

אוטומציה ושילוב תהליכי עבודה

אוטומציה של יצירת מספרים אקראיים בתוך זרימות עבודה גדולות יותר - צינורות בדיקות A/B, סימולציות מונטה קרלו, הגרלות מתוזמנות או דגימה אקראית של ביקורת - כרוכה בדרך כלל באחת משלוש גישות:

1. שילוב API — RANDOM.ORG מציע API מסוג JSON-RPC שמחזיר מספרים שלמים, רצפים, מחרוזות ומזהי UUID אקראיים אמיתיים. בקשות מאומתות מאפשרות מכסות גבוהות יותר ואקראיות חתומה עם תעודות אותנטיות הניתנות לאימות.
2. זריעת צינורות CI/CD - ניתן להפעיל באופן אוטומטי כלי בדיקה סטטיסטיים כמו TestU01 או Dieharder בצינורות אינטגרציה רציפים כדי לאמת שכל יישום RNG מותאם אישית שומר על איכות סטטיסטית לאורך שינויי קוד.
3. תזמון מקורי לפלטפורמה - פלטפורמות ענן (AWS Lambda, Google Cloud Functions, Azure Functions) יכולות להפעיל תהליכים מבוססי RNG לפי לוח זמנים, לדוגמה כדי לדגום באופן אקראי רשומות יומן עבור ביקורות אבטחה או להקצות קבוצות קוהורט אקראיות יומיות בניסויים התנהגותיים.

כלים כמו AutoSEO מדגימים כיצד אוטומציה יכולה להתרחב אפילו לזרימות עבודה של תוכן ונתונים התלויות בדגימה אקראית. AutoSEO הופך את תהליך הזיהוי, הביקורת וקביעת סדרי עדיפויות של משימות SEO לאוטומטי באמצעות טכניקות דגימה אקראיות לבחירת תת-קבוצות מייצגות של דפים ממערכי נתונים גדולים של סריקה - ובכך מבטיח שבדיקות האיכות אינן מוטות ושלא יופיעו נקודות עיוורות שיטתיות כתוצאה מביקורת מתמדת של אותם דפים בעלי תנועה גבוהה. זה משקף את אותה היגיון המשמש בניסויים מבוקרים אקראיים: על ידי הכנסת אקראיות מובנית לתהליך הבחירה, AutoSEO מייצר הערכות בריאות אתר תקפות יותר מבחינה סטטיסטית מאשר מבקרים דטרמיניסטיים מבוססי כללים.

כיצד למדוד את האיכות וההצלחה של מחולל מספרים אקראיים

מחולל מספרים אקראיים טוב עובר מבחנים סטטיסטיים לאחידות, עצמאות וחוסר יכולת חיזוי. אמות המידה העיקריות הן חבילות בדיקות אמפיריות, ניתוח תקופה תיאורטי, ועבור קבוצות RNG קריפטוגרפיות - עמידות בפני התקפות שחזור מצב.

סוויטות בדיקות סטטיסטיות

לא ניתן להוכיח רצף סופי כאקראי באמת, אך ניתן לבדוק רצפים כדי לוודא שהם אינם אקראיים. חבילות הבדיקה המוסמכות ביותר הן:

• NIST SP 800-22 - חבילה של 15 מבחנים סטטיסטיים שפורסמו על ידי המכון הלאומי לתקנים וטכנולוגיה, המשמשים להערכת קבוצות אות רינגיט (RNG) המוגשות לאישור קריפטוגרפי. המבחנים כוללים בדיקות תדר, ריצות, ספקטרליות (DFT) וסדרתיות.
• TestU01 (BigCrush) - BigCrush, שפותח באוניברסיטת מונטריאול, הוא קבוצת הבדיקות הסטטיסטיות התובענית ביותר הזמינה לציבור. אלגוריתמים כמו LCGs ומחוללי Wichmann-Hill ישנים יותר נכשלים בו; Xoshiro256** ו-PCG עוברים אותו.
• Dieharder - הרחבה בקוד פתוח של סוללת Diehard המקורית של ג'ורג' מרסליה, המריצה מעל 100 בדיקות על דגימות גדולות של תפוקת גנרטור.
• PractRand - חבילת בדיקות מודרנית שמתאימה לגודל מדגם גדול מאוד (טרה-בייט של פלט), המסוגלת לזהות הטיות עדינות שאינן נראות לבדיקות מדגם קטן יותר.

מדדי איכות מרכזיים

• אורך פרק זמן - מספר הערכים שנוצרים לפני שהרצף חוזר על עצמו. ל-Mersenne Twister יש פרק זמן של 2 ¹⁹⁹³⁷ −1, וזה מספיק כמעט לכל היישומים שאינם קריפטוגרפיים.
• התפלגות שווה - האם הערכים מפוזרים באופן אחיד על פני טווח הפלט בממד אחד, בשני ממדים ובהשלכות בעלות ממדים גבוהים יותר.
• רגישות זרעים - האם שינויים קטנים בזרעים מייצרים רצפי פלט שונים לחלוטין (חשוב לשחזור הסימולציה).
• תפוקה - מהירות פלט ב-MB/s או מיליארדי מספרים לשנייה, רלוונטי לעומסי עבודה עתירי ביצועים של מונטה קרלו.
• סודיות קדימה ואחורה - עבור CSPRNGs, האם תוקף שצופה בפלט בזמן T יכול לשחזר פלט מהעבר או מהעתיד. זה נבדק על ידי ניסיון שחזור מצב מסיביות שנצפו.

מדידת הצלחה בהקשרים יישומיים

מעבר לאיכות הטכנית, מדדי הצלחה תלויים בהקשר הפריסה:

• הגרלות והגרלות - מעקבי ביקורת, אימות של צד שלישי ותעודות אקראיות חתומות (זמינים באתר RANDOM.ORG) מדגימים הוגנות כלפי המשתתפים.
• יישומי קריפטוגרפיה - תאימות להסמכות FIPS 140-3 או Common Criteria מאשרת שמקור האנטרופיה ו-CSPRNG עומדים בתקני הממשלה והתעשייה.
• סימולציות מדעיות - שחזור (אותו זרע מייצר אותן תוצאות) ויכולת לעבור BigCrush או PractRand בגדלי המדגם ששימשו בסימולציה.
• בדיקות A/B - בדיקות איזון מאשרות שקבוצות הטיפול והביקורת שקולות סטטיסטית במשתנים שלפני הניסוי, מה שמאשר שההקצאה האקראית הייתה אובייקטיבית.

שאלות נפוצות

מה ההבדל בין מחולל מספרים אקראיים אמיתי לבין מחולל מספרים פסאודו-אקראי?

מחולל מספרים אקראיים אמיתי (TRNG) גוזר אקראיות מתהליך פיזיקלי ובלתי צפוי - כגון רעש תרמי, דעיכה רדיואקטיבית או רעש רדיו אטמוספרי - ומייצר פלט שאינו דטרמיניסטי באמת. מחולל מספרים פסאודו-אקראי (PRNG) משתמש באלגוריתם מתמטי דטרמיניסטי עם ערך התחלתי; בהינתן אותו ערך זרע, הוא תמיד מייצר את אותו רצף. מחוללים של מספרים אקראיים מהירים יותר וניתנים לשחזור, מה שהופך אותם לאידיאליים עבור סימולציות ומשחקים. TRNG איטיים יותר אך נחוצים כאשר חוסר ודאות הוא דרישת אבטחה, כגון יצירת מפתחות קריפטוגרפיים.

האם ‏Math.random() ב-JavaScript בטוח לשימוש למטרות אבטחה?

לא. הפונקציה Math.random() של JavaScript היא קובץ PRNG שתועד במפורש כלא מאובטח קריפטוגרפית. ניתן לשחזר את המצב הפנימי שלה מהפלט שנצפה, ואין להשתמש בה לעולם ליצירת סיסמאות, אסימוני סשן, מפתחות API או כל ערך שבו תוקף שניחוש את הפלט יגרום נזק. עבור יישומים רגישים לאבטחה בדפדפן, השתמש ב- crypto.getRandomValues() מממשק ה-API של Web Crypto, המגובה על ידי CSPRNG של מערכת ההפעלה.

האם מחולל מספרים אקראיים יכול להיות באמת בלתי צפוי?

TRNG מבוסס חומרה שמקורו בתופעות קוונטיות - כגון זמני הגעה של פוטונים או תנודות בוואקום קוונטי - נחשב בלתי צפוי ביסודו על פי מכניקת הקוונטים, כלומר שום אלגוריתם או מידע נוסף לא יוכלו לאפשר לצופה לחזות את התפוקה שלו טוב יותר מהמקרה. PRNGs ורוב CSPRNGs התוכנה אינם צפויים מבחינה חישובית תחת הנחות קריפטוגרפיות סטנדרטיות, כלומר הם מאובטחים בפועל אך לא ניתנים להוכחה לחיזוי במובן הפיזיקלי המוחלט.

כיצד זריעה משפיעה על מחולל מספרים אקראיים?

ה-seed הוא ערך ההתחלה המוזן לאלגוריתם PRNG. אותו seed תמיד מייצר את אותו רצף, וזוהי תכונה במחשוב מדעי משום שהיא הופכת ניסויים לניתנים לשחזור. seed גרוע - כמו שימוש בשנייה הנוכחית כמקור האנטרופיה היחיד - מפחית באופן דרסטי את האקראיות האפקטיבית משום שתוקף יכול למנות את כל ה-seeds הסבירים. נוהג זריעה טוב משלב מספר מקורות אנטרופיה: זמן נוכחי בננו-שניות, מזהה תהליך, כתובות זיכרון ואנטרופיה המסופקת על ידי מערכת ההפעלה מ-/dev/urandom או CryptGenRandom ב-Windows.

באיזה מחולל מספרים אקראיים משתמש מודול האקראי של פייתון?

המודול random של Python משתמש באלגוריתם Mersenne Twister (MT19937), בעל מחזור של 2 ¹⁹⁹³⁷ −1 ועובר את רוב המבחנים הסטטיסטיים. הוא מתאים לסימולציות, משחקים ודגימה סטטיסטית. עם זאת, הוא אינו מאובטח קריפטוגרפית - ניתן לשחזר את המצב הפנימי לאחר התבוננות ב-624 פלטים רצופים של 32 סיביות. עבור עבודה רגישה לאבטחה בפייתון, השתמש במודול secrets , המגובה על ידי os.urandom() ושואב מ-CSPRNG ברמת מערכת ההפעלה.

איך מייצרים מספרים אקראיים בלי מחשב?

לפני מחשבים, מספרים אקראיים נוצרו בשיטות פיזיות: גלגול קוביות, הוצאת כדורים ממוספרים מתוף מסתובב, הטלת מטבעות או ערבוב קלפים. תאגיד ראנד פרסם ספר מפורסם בשנת 1955 בשם "מיליון ספרות אקראיות עם 100,000 סטיות נורמליות" , שנוצר על ידי גלגל רולטה אלקטרוני. טבלאות סטטיסטיות של מספרים אקראיים היו בשימוש נרחב בדגימת סקרים ובניסויים קליניים. כיום, שיטות ידניות עדיין משמשות בכמה הגרלות מוסדרות ובהדגמות בכיתה, אם כי הן איטיות וקשות יותר לביקורת מאשר שיטות אלקטרוניות.

למה צריך לבדוק מחוללי מספרים אקראיים?

אפילו אלגוריתמים שנועדו לייצר פלט שנראה אקראי יכולים להכיל הטיות עדינות, מחזורים קצרים בממדים מסוימים, או קורלציות בין ערכים עוקבים שאינם נראים לבדיקה אגבית אך ניתנים לזיהוי באמצעות בדיקות סטטיסטיות. פגמים אלה יכולים לפסול תוצאות סימולציה, להפחית את האבטחה של מערכות קריפטוגרפיות, או להכניס חוסר הוגנות למשחקים והגרלות. בדיקות עם חבילות כמו NIST SP 800-22, BigCrush או PractRand לוכדות בעיות אלה לפני הפריסה. דוגמאות היסטוריות של גנרטורים פגומים - כולל גרסאות מוקדמות של mt_rand() של PHP ובאג OpenSSL של דביאן משנת 2008 - מראות ש-RNGs שלא נבדקו יכולים לגרום לכשלים של ממש באבטחה.

מהו מחולל מספרים פסאודו-אקראי מאובטח קריפטוגרפית (CSPRNG)?

CSPRNG הוא PRNG שעומד בשתי דרישות אבטחה נוספות מעבר לאיכות סטטיסטית: מבחן הביט הבא (אף אלגוריתם לא יכול לחזות את הביט הבא בהסתברות טובה משמעותית מ-50% בהינתן כל הביטים הקודמים) והתנגדות הרחבה לפשרת מצב (אם תוקף לומד את המצב הפנימי בזמן T, הוא לא יכול לשחזר את הפלט מלפני T). CSPRNG מודרניים כוללים גנרטורים מבוססי ChaCha20 (המשמשים ב-/dev/urandom של לינוקס מאז ליבה 4.8), Fortuna (המשמשת ב-macOS ו-iOS), ו-CTR_DRBG (סטנדרטי על ידי NIST ב-SP 800-90A).

האם מחוללי מספרים אקראיים יכולים לייצר ערכים כפולים?

כן, וזוהי התנהגות צפויה. לתהליך אקראי באמת אין זיכרון של פלטים קודמים, כך שכפילויות מתרחשות באופן טבעי - זה מתואר על ידי בעיית יום ההולדת בתורת ההסתברות. בהגרלה אחידה מ-1 עד N, כפילויות הופכות לסבירות לאחר שגררו בערך √N ערכים. אם היישום שלך דורש ערכים ייחודיים (כגון הקצאת מזהים ייחודיים או ערבוב חפיסת קלפים ללא חזרות), עליך להשתמש באלגוריתם ערבוב כמו פישר-ייטס על קבוצה מוגדרת מראש, או לשמור על קבוצה של ערכים שכבר בשימוש ולדחות כפילויות, במקום להסתמך על פלט RNG גולמי כדי למנוע התנגשויות.

כיצד כלי הגרלות והגרלות מקוונות מבטיחים הוגנות?

כלי הגרלה מקוונים בעלי מוניטין מבטיחים הוגנות באמצעות שילוב של: שימוש במקור אנטרופיה איכותי (רצוי TRNG ולא Math.random()), פרסום האלגוריתם וה-seed לפני ההגרלה כדי שניתן יהיה לאמת את התוצאות באופן עצמאי, מתן תעודות אקראיות חתומות המוכיחות שהמספרים נוצרו לפני סגירת ההגרלה, וביצוע הגרלות בנוכחות מבקרים עצמאיים. RANDOM.ORG מציע שירות הגרלה של צד שלישי שמסמן חותמת זמן וחותם קריפטוגרפית על כל הגרלה, ויוצר רשומה ניתנת לביקורת. עבור הגרלות מוסדרות, רשויות ההימורים הלאומיות דורשות RNGs חומרתיים מוסמכים ואישור מעבדת בדיקה עצמאית לפני שכל מערכת עולה לאוויר.