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

מחולל מספרים פְּסֵאוֹדוֹ-אקראיים (באנגלית: Pseudorandom number generator; בראשי תיבות: PRNG) הוא אלגוריתם במחשב המייצר סדרת מספרים או אלמנטים המדמים בקירוב תכונות של רצף אקראי שנוצר באמצעות מחולל מספרים אקראיים אמיתי. לאמיתו של דבר, רצף פסאודו-אקראי אינו אקראי היות שהוא נוצר בשיטה דטרמיניסטית מתוך קבוצה קטנה יחסית של אלמנטים הנקראת גרעין (seed) או מצב התחלתי (initial state) ובהינתן מידע זה ניתן לשחזור מדויק, מסיבה זו מכונה "פסאודו" דהיינו "מדומה". באמצעות אלגוריתמים המיועדים לכך, ניתן לייצר רצפים פסאודו אקראיים, הקרובים מאוד באיכותם לרצפים שנוצרו באמצעות מחולל אמיתי, באופן שקשה מאוד מבחינה סטטיסטית חישובית להבדיל ביניהם. מחוללים פסאודו אקראיים משחקים תפקיד חשוב בסימולציה לצורך מדעי, הימורים, משחקי מחשב וקריפטוגרפיה.

בין משפחות האלגוריתמים הנפוצים כיום נמנים גרסאות של Linear Congruential Generators בקיצור LCG המחולל הנפוץ ביותר המבוסס על אריתמטיקה מודולרית. משפחת מחוללי Lagged Fibonacci generator בקיצור LFG המבוסס על סדרת פיבונאצ'י וכן Linear Feedback Shift Generator בקיצור LFS שהוא אוגר הזזה-החזרה המיושם בחומרה בדרך כלל ונפוץ בגרסאות מסוימות של צופני זרם. כמו כן קיימים מחוללים אקראיים חדשים כמו Blum Blum Shub (בקיצור BBS) המבוסס על אריתמטיקה מודולרית וכן Fortuna, Mersene Twister ו-Multiply-with-carry של ג'ורג' מרסגליה הידוע גם בשל פיתוח סוללת Diehard (שמרן) - אוסף של מבחנים סטטיסטיים שונים לבדיקת אקראיות.

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

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

מחזוריות

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

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

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

היסטוריה

אחת השיטות המוקדמות ליצירת מספרים פסאודו אקראיים באמצעות מחשב, הייתה של ג'ון פון נוימן ב-1946. השיטה הייתה מאוד פשוטה והיא נקראה "אמצע הריבוע", כדלהלן; מעלים מספר כלשהו בריבוע ונוטלים חלק מספרותיו האמצעיות כחלק מרצף אקראי, איתו משתמשים לאחר מכן כגרעין לחישוב הבא וחוזר חלילה. לדוגמה אם מעלים בריבוע את המספר 1111 מתקבל 1234321 אם מוסיפים אפס בהתחלה אפשר לשלוף את ארבע הספרות האמצעיות "2343" כמספר אקראי. אם מעלים את 2343 בריבוע, מוסיפים אפס מתקבל מספר שארבע ספרותיו האמצעיות הם 4896 וכן הלאה. פון נוימן השתמש במספר בן 10 ספרות.

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

מחוללים פסאודו אקראיים

Linear congruential generator

שיטת Linear congruential היא השיטה הוותיקה והפופולרית ביותר כיום. היא הוצעה לראשונה על ידי דריק הנרי להמר ב-1949. הרעיון מאחורי משפחה זו של אלגוריתמים (הנקראת בקיצור LCG) פשוט בתכלית ובדרך כלל קל ליישום. המחולל מוגדר על ידי נוסחת הנסיגה: $\ X_{n+1}=(aX_{n}+c){\mbox{ mod }}m$ כאשר $\ X_{n}$ הוא האיבר ה-$\ n$ בסדרת המספרים הפסאודו-אקראית המופקת. הפרמטר $\ m$ מכונה מודולוס, $\ a$ נקרא "כופל" ו-$\ c$ נקרא "מקדם" (במקרה של $\ c=0$ מתקבל אלגוריתם פארק-מילר שנמצא בשימוש נרחב, בין היתר, במערכות ההפעלה של מקינטוש). $\ X_{0}$ נקרא "מצב התחלתי" או גרעין התחלתי ובדרך כלל צריך להיות ממקור אקראי כלשהו. השפעת הפרמטרים $\ a,m,c$ על פלט המחולל מכרעת.

LCG אינו מתאים לצורך קריפטוגרפי,מחקרים מראים שניתן לנחש את המשך הרצף מתוך קטע קצר יחסית גם ללא ידיעת הפרמטרים. הסוגים השונים של משפחה זו נבדלים בעיקר בערכי הפרמטרים. מחזוריות המחולל תלויה בראש ובראשונה בפרמטר $\ m$. למשל גרסת המחולל של פארק-מילר עם המודולוס $\ m=2^{31}-1$ (שהוא מספר מרסן ראשוני) והפרמטרים $\ a=16807$, $\ c=0$ מגיעה למחזוריות בסדר גודל של $\ m-1$.

להלן קוד C++ של המחולל הפסאודו אקראי המובנה בסביבת הפיתוח של מיקרוסופט ויז'ואל סטודיו, המבוסס על LCG עם הפרמטרים $\ m=2^{32},a=214013,c=2531011$:

return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);

הערך 0x7FFF משמש לצמצום מודולרי. המחולל מפיק מספר פסאודו אקראי בגודל 15 סיביות.

Lagged Fibonacci generator

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

Mersenne twister

אלגוריתם Mersenne twister הומצא ב-1997 על ידי מקוטו מטסומוטו וטאקוג'י נישימורה. הרעיון של האלגוריתם מבוסס על גרסה מפותלת של אוגר הזזה (בדומה ל-LFSR) מעל השדה הבינארי $\ F_{2}$. האלגוריתם מייצר רצף פסאודו אקראי באיכות גבוהה והוא בעל מחזוריות גבוהה ביותר, בסדר גודל של $\ 2^{19937}-1$ (שהוא מספר צירופים עצום, הרבה מעבר למספר החישובים שניתן לעשות בכל שנות קיומו של היקום). האלגוריתם מהיר ויעיל מכל מחולל אקראי אחר והפך לאחד האלגוריתמים המועדפים כיום לצורכי סימולציה סטטיסטית מדעית. חסרונו הוא מורכבותו ליישום והעובדה שאינו מתאים בגרסתו הבסיסית לקריפטוגרפיה.

Multiply-with-Carry

Multiply-with-Carry הוא אלגוריתם ליצירת מספרים פסאודו אקראיים עם מחזוריות משתנה, שהומצא על ידי ג'ורג' מרסגליה. האלגוריתם מכונה גם "Mother of all pseudorandom generators" והוא מבוסס אריתמטיקה מודולרית בדומה ל-LCG. בגרסה הבסיסית האלגוריתם כולל "בסיס" $\ b$ (בדרך כלל $\ b=2^{32}$ או $\ 2^{32}-1$), פרמטר $\ a$ שנקרא "כופל", "גרעין" התחלתי אקראי הכולל קבוצה של $\ r$ ערכים $\ x_{0},x_{1},...x_{r-1}$ הנקראים "שאריות" ופרמטר $\ c$ הנמוך מ-$\ a$ הנקרא "נשא". פלט האלגוריתם בכל שלב הוא הזוגות $\ x_{n},c_{n}$ המחושבים על ידי הנוסחה:

• $\ x_{n}=(ax_{n-r}+c_{n-1}){\mbox{ mod }}b$
• $\ c_{n}=\left\lfloor {\frac {ax_{n-r}+c_{n-1}}{b}}\right\rfloor$

כאשר $\ n\geq r$ והפלט הוא $\ x_{r},x_{r+1},x_{r+2},...$. מחזוריות המחולל היא בעצם הסדר של $\ b$ בחבורה הכפלית מודולו $\ ab^{r}-1$ (נהוג לבחור $\ ab^{r}-1$ כך שהוא יהיה ראשוני). המחזוריות יכולה להגיע לסדר גודל עצום של $\ 2^{2000000}$. קיימת בעיה אחת עם הגרסה הבסיסית של המחולל, שהסיבית הגבוהה ביותר שלו סובלת מהטיה קלה.

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

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

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

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

• צופן זרם
• צופן בלוקים הפועל במצב Counter Feedback או Output Feedback .
• צופן אסימטרי.

דוגמה למחולל פסאודו אקראי קריפטוגרפי המבוסס על הצפנה אסימטרית הוא Blum Blum Shub (בקיצור BBS) שבטיחותו מוכחת, למרות שהיא מותנית בכך שהפרמטרים הפנימיים ישמרו בסוד. נוסחת האלגוריתם היא מהצורה: $\ x_{n+1}=x_{n}^{2}{\mbox{ mod }}m$ כאשר $\ m$ הוא מכפלה של שני מספרים ראשוניים גדולים. המחולל BBS נחשב לאיטי יחסית ואינו מתאים בכל המקרים, אך הוכח שבטיחותו שקולה לבעיית פירוק לגורמים. דהיינו ניחוש הסיבית הבאה שהאלגוריתם ייצר שקולה לפירוק $\ m$ לגורמים.

בין האלגוריתמים הייעודיים שעוצבו במיוחד לצורך קריפטוגרפי נמנה CryptoGenRandom של מיקרוסופט כחלק מתשתית API, המפיק גרעין התחלתי מתוך מספר נתוני מערכת ולאחר מכן מעביר את הפלט בפונקציית גיבוב MD4 וצופן RC4. וכן אלגוריתם Yarrow המובנה במערכת ההפעלה Mac OS X ו-Free BSD ואלגוריתם Fortuna.

קריטריון BSI

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

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

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

מחולל אקראי בעל התפלגות נורמלית

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

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

• גדי אלכסנדרוביץ', איך מגרילים מספרים במחשב, באתר "האייל הקורא"