מספר אקראי

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

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

מספר אקראי אמיתי

לא ניתן לקרוא למספר "אקראי" ללא הקשר כלשהו. לדוגמה: אם נתונים במכל 49 כדורים זהים הממוספרים מ-1 עד 49 ואם שולפים מתוך המכל (לאחר ערבוב הגון) כדור אחד ועליו מופיע המספר 23 ניתן לומר כי המספר 23 הוגרל באופן אקראי בהתפלגות אחידה מתוך הקבוצה $\ \{1,2,...,49\}$. ההסתברות שהמספר 23 יוגרל היא $\ 1/49$. אם נרשום את המספר המופיע על הכדור, נחזירו למכל ונחזור על תהליך זה מספר פעמים, נקבל רצף אקראי המוגדר מעל הקבוצה $\ \{1,2,...,49\}$. לדוגמה: הסיכוי שיוגרל הרצף: $\ 17,45,1,7,23,35$ (בהנחה שכל כדור מוצא, נרשם ומוחזר שוב) היא $\ (1/49)^{6}$ או $\ 49^{-6}$ שהיא כפולה של ההסתברויות של כל כדורים ברצף.

מחוללים אקראיים

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

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

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

מבחנים סטטיסטיים

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

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

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

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

מספר פסאודו-אקראי

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

תוצאת מחולל סיביות פסאודו-אקראי (PRBG) אינה אקראית לגמרי. למעשה עבור גרעין התחלתי באורך $\ k$, מספר הרצפים שהמחולל מסוגל לייצר באורך $\ l$ מהווה רק חלק קטן מהטווח המקסימלי ליתר דיוק $\ 2^{k}/2^{l}$ של כל הרצפים הבינאריים האפשריים באורך $\ l$. השאיפה היא למצוא שיטה להרחבת גרעין התחלתי קצר לרצף באורך מרבי, באופן שלא ניתן יהיה להבחין בינו לבין רצף באורך זהה המיוצר בעזרת מחולל אמיתי. קיים מגוון עצום של אלגוריתמים ליצירת מספרים פסאודו-אקראיים מסוגים שונים. אולם רבים מהם אינם בטוחים ויש להיזהר בטענת הממציאים באשר לטיב אקראיותם.

אלגוריתמים אקראיים

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

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

מחולל פסאודו-אקראי (PRNG)

אחת השיטות להפקת מספרים פסאודו-אקראי היא באמצעות פונקציה חד-כיוונית. הדוגמה הנפוצה למחולל כזה נקראת Linear congruential generator או בקיצור LCG שהומצאה על ידי Lehmer והפכה לתקן ANSI שיושם בעבר בפונקציה $\ {\mbox{rand()}}$ בשפת c. הרעיון הבסיסי של המחולל פשוט ויעיל ומתבסס על אריתמטיקה מודולרית, משוואתו היא: $\ x_{n}=(ax_{n-1}+b){\mbox{ mod }}m$, כאשר $\ n$ גדול מאפס וערכו של $\ x_{0}$ הנו הגרעין ההתחלתי. הפרמטרים $\ a,b,m$ שולטים באופי התוצאה. בשל השימוש במודולו המחולל מייצר רצף סיביות סופי, כלומר מחזורי. כאשר לאחר מספר מסוים של אלמנטים המחולל חוזר על עצמו. מחזוריות המחולל היא על כן עניין קריטי, בחירת הפרמטרים עבור המחולל חשובה ולמעשה משפיעה ישירות על מחזוריותו. למשל אם $\ m=2^{31},a=1103515245,b=12345$ אזי מחזוריות המחולל תהיה בערך $\ 2^{30}$. ישנן גרסאות משופרות ממשפחת אלגוריתמים אלו כמו אלגוריתם Park-Miller.

למרות שאלגוריתם זה עומד יפה במבחנים סטטיסטיים ידועים לבדיקת אקראיות וגרסאות שונות שלו נפוצות מאוד בשימוש מעשי, הוא אינו בטוח כלל מבחינה קריפטוגרפית. מאחר שהמשכו ניתן לניחוש מתוך רצף קצר יחסית. ג'ואן בויר, קראווציק ואחרים הראו כיצד ניתן לנחש את תוצאות מחולל מסוג זה מתוך רצף קצר (ללא ידיעת הגרעין ההתחלתי), בידיעת חלק מן הפרמטרים ואף בלא ידיעת הפרמטרים כלל. התיעוד המקיף ביותר בנושא זה הוא ספרו של דונלד קנות' "The art of computer programming" (כרך שני). ג'ון פון נוימן צוטט כאומר: "זהו חטא לחשוב כי ניתן לייצר מספרים אקראיים בשיטות מתמטיות".

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

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

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

• שעון מערכת.
• הפרשי זמן בין הקשות מקלדת או קואורדינטות העכבר.
• תכולת אפיק קלט/פלט של המחשב.
• קלט משתמש.
• נתוני מערכת ההפעלה או תיעוד ביצועי רשת.

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

אלגוריתם פסאודו אקראי קריפטוגרפי

ערך מורחב – מחולל פסאודו אקראי קריפטוגרפי

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

אלגוריתם BBS הוא דוגמה טובה למחולל בינארי אקראי-קריפטוגרפי המבוסס על הצפנה אסימטרית. המחולל פועל לפי הנוסחה: $\ x_{i}=x_{i-1}^{2}{\mbox{ mod }}n$. בכל שלב הסיבית הנמוכה של $\ x_{i}$ מהווה חלק מהרצף האקראי, כאשר $\ n$ הנו כפולה של שני מספרים ראשוניים גדולים. ניסיון לנחש את הסיבית הבאה של המחולל שקול לניסיון לפרק את $\ n$ לגורמים. אם הגורמים הראשוניים של $\ n$ אינם ידועים, המחולל יהיה בטוח. מאחר שבטיחות המחולל תלויה בקושי שבפירוק $\ n$ לגורמים, רצוי ש-$\ n$ יהיה גדול ככל האפשר. החיסרון היחידי של האלגוריתם הוא שכל סיבית אקראית דורשת העלאה בריבוע מודולו $\ n$, פעולה יקרה במונחי חישוב. ניתן לשפר את האלגוריתם בכך שפלט האלגוריתם בכל לולאה יהיה מספר מסוים של הסיביות הנמוכות של $\ x_{i}$.

לקריאה נוספת

דונלד קנות', The art of computer programming, Vol 2: Seminumerical Algorithms.

קישורים חיצוניים

• מבדקים סטטיסטיים של מחוללי מספרים אקראיים
• מאה אלף ספרות אקראיות להורדה
• מספרים אקראיים שנוצרו ממדידות על תופעות רדיו-אקטיביות
• מספרים אקראיים ממנורות לבה
• Random.org יצירת מספרים אקראיים מרעש אטמוספירי
• ניתוח מחולל המספרים האקראי של לינוקס
• גדי אלכסנדרוביץ', אז איך מגרילים מספרים במחשב?, באתר "לא מדויק"