מספר פסאודו אקראי הוא מספר מיוחד שנוצר על ידי מחולל מיוחד. מחולל סיביות אקראיות דטרמיניסטיות (PRNG), הידוע גם בשם מחולל סיביות אקראיות דטרמיניסטיות (DRBG), הוא אלגוריתם להפקת רצף של מספרים שתכונותיו מתקרבות למאפיינים של רצפי מספרים אקראיים. רצף ה-PRNG שנוצר אינו אקראי באמת, מכיוון שהוא נקבע לחלוטין על ידי ערך זריעה הנקרא זרעי PRNG, שעשוי לכלול ערכים אקראיים באמת. למרות שניתן ליצור רצפים שקרובים יותר לאקראיים באמצעות מחוללי מספרים אקראיים בחומרה, מחוללי מספרים פסאודו-אקראיים חשובים בפועל למהירות יצירת המספרים ושחזורם.
Application
PRNGs הם מרכזיים ליישומים כמו סימולציה (למשל עבור מונטה קרלו), משחקים אלקטרוניים (למשל ליצירת פרוצדורות) והצפנה. יישומים קריפטוגרפיים דורשים את הפלטהנתונים לא היו ניתנים לחיזוי ממידע קודם. נדרשים אלגוריתמים מורכבים יותר שאינם יורשים את הליניאריות של PRNGs פשוטים.
תנאים והגבלות
מאפיינים סטטיסטיים טובים הם דרישה מרכזית להשגת PRNG. באופן כללי, יש צורך בניתוח מתמטי קפדני כדי לוודא שה-RNG יוצר מספרים שקרובים מספיק לאקראיים כדי להתאים לשימוש המיועד.
ג'ון פון נוימן הזהיר מפני פירוש שגוי של PRNG כמחולל אקראי באמת והתלוצץ כי "כל מי ששוקל שיטות אריתמטיות להפקת מספרים אקראיים בהחלט נמצא במצב של חטא."
השתמש
PRNG ניתן להפעיל ממצב התחלתי שרירותי. זה תמיד יפיק את אותו רצף כאשר הוא מאותחל במצב זה. תקופת PRNG מוגדרת באופן הבא: מקסימום על פני כל המצבים ההתחלתיים של אורך קידומת הרצף שאינה חוזרת. התקופה מוגבלת במספר המצבים, הנמדדים בדרך כלל בסיביות. מכיוון שאורך התקופה עשוי להכפיל את עצמו עם כל סיביות "מצב", קל ליצור PRNGs עם תקופות גדולות מספיק עבור יישומים מעשיים רבים.
אם המצב הפנימי של ה-PRNG מכיל n סיביות, התקופה שלו יכולה להיות לא יותר מ-2n תוצאות, היא קצרה בהרבה. עבור חלק מה-PRNGs, ניתן לחשב את משך הזמן מבלי לעקוף את כל התקופה. אוגרי משוב ליניאריים (LFSRs) הם בדרך כללנבחרים כך שיהיו נקודות השווה ל-2n − 1.
לגנרטורים קוגרונטיים ליניאריים יש תקופות שניתן לחשב באמצעות פירוק. למרות שה-PPP יחזור על תוצאותיו לאחר שיגיעו לתום התקופה, תוצאה חוזרת אינה אומרת שהושג סוף התקופה, שכן מצבו הפנימי עשוי להיות גדול מהתפוקה; זה בולט במיוחד עבור PRNGs עם פלט סיביות בודדות.
שגיאות אפשריות
שגיאות שנמצאו על ידי PRNGs פגומים נעות בין עדינות (ולא ידועות) לשגיאות ברורות. דוגמה לכך היא אלגוריתם המספרים האקראיים RANDU, שנמצא בשימוש במיינפריים במשך עשרות שנים. זה היה חיסרון רציני, אבל חוסר ההתאמה שלו נעלם מעיניו במשך תקופה ארוכה.
בתחומים רבים, מחקרי מחקר שהשתמשו בבחירה אקראית, סימולציות של מונטה קרלו או שיטות אחרות המבוססות על RNG הם הרבה פחות אמינים ממה שיכול להיות תוצאה של GNPG באיכות ירודה. גם כיום, לעיתים נדרשת זהירות, כפי שמעידה האזהרה באנציקלופדיה הבינלאומית למדע סטטיסטי (2010).
מחקר מקרה מוצלח
כדוגמה, שקול את שפת התכנות Java בשימוש נרחב. נכון לשנת 2017, ג'אווה עדיין מסתמכת על המחולל קוגרונטי ליניארי (LCG) עבור ה-PRNG שלו.
היסטוריה
ה-PRNG הראשון שנמנע מבעיות רציניות ועדיין פועל די מהר,היה ה-Mersenne Twister (הנדון להלן), שפורסם ב-1998. מאז, פותחו PRNGs באיכות גבוהה אחרים.
אבל ההיסטוריה של מספרים פסאודו-אקראיים לא מסתיימת שם. במחצית השנייה של המאה ה-20, המחלקה הסטנדרטית של אלגוריתמים ששימשה עבור PRNGs כללה מחוללים קוגרונטיאליים ליניאריים. האיכות של ה-LCG הייתה ידועה כלא מספקת, אך שיטות טובות יותר לא היו זמינות. Press et al (2007) תיארו את התוצאה באופן הבא: "אם כל המאמרים המדעיים שתוצאותיהם מוטלות בספק בגלל [LCGs וקשורים] ייעלמו ממדפי הספרייה, יהיה פער בגודל האגרוף שלך בכל מדף."
ההישג העיקרי ביצירת מחוללים פסאודו-אקראיים היה הכנסת שיטות המבוססות על מחזוריות ליניארית בשדה שני אלמנטים; מתנדים כאלה מחוברים לאוגרי משמרת משוב ליניארי. הם שימשו כבסיס להמצאת חיישני מספרים פסאודו-אקראיים.
במיוחד, ההמצאה של Mersen Twister משנת 1997 נמנעה רבות מהבעיות עם גנרטורים קודמים. למרסן טוויסטר יש תקופה של 219937-1 איטרציות (≈4.3 × 106001). הוכח שהוא מופץ באופן אחיד ב-(עד) 623 ממדים (עבור ערכים של 32 סיביות), ובזמן הצגתו היה מהיר יותר ממחוללים אחרים בעלי תקינות סטטיסטית המייצרים רצפי מספרים פסאודו-אקראיים.
בשנת 2003, ג'ורג' מרסאגליה הציג משפחה של מחוללי xorshift המבוססים גם הם על חזרה ליניארית. גנרטורים אלה הם מאודהם מהירים ובשילוב עם פעולה לא ליניארית - הם עוברים מבחנים סטטיסטיים קפדניים.
בשנת 2006 פותחה משפחת מחוללי WELL. מחוללי WELL משפרים במובן מסוים את האיכות של Twister Mersenne, שיש לו מרחב מצב גדול מדי והתאוששות איטית מאוד מהם, ומייצרים מספרים פסאודו אקראיים עם הרבה אפסים.
קריפטוגרפיה
PRNG המתאים ליישומים קריפטוגרפיים נקרא PRNG מאובטח קריפטוגרפי (CSPRNG). הדרישה ל-CSPRNG היא שלתוקף שלא מכיר את ה-seed יש רק יתרון שולי בהבחנה בין רצף הפלט של המחולל מרצף אקראי. במילים אחרות, בעוד ש-PRNG נדרש רק כדי לעבור מבחנים סטטיסטיים מסוימים, CSPRNG חייב לעבור את כל המבחנים הסטטיסטיים המוגבלים לזמן פולינומי בגודל זרע.
למרות שההוכחה למאפיין זה היא מעבר לרמה הנוכחית של תיאוריית המורכבות החישובית, ניתן לספק ראיות חזקות על ידי הפחתת ה-CSPRNG לבעיה שנחשבת קשה, כמו פירוק של מספרים שלמים. באופן כללי, ייתכן שיידרשו שנים של בדיקה לפני שניתן יהיה לאשר אלגוריתם כ-CSPRNG.
הוכח שסביר להניח שה-NSA הכניס דלת אחורית א-סימטרית למחולל המספרים הפסאודו-אקראי ה-Dual_EC_DRBG המאושר על ידי NIST.
אלגוריתמים פסאודו אקראייםמספרים
רוב האלגוריתמים של PRNG מייצרים רצפים שמתפזרים באופן שווה על ידי כל אחד מכמה בדיקות. זו שאלה פתוחה. זה אחד המרכזיים בתיאוריה ובפרקטיקה של קריפטוגרפיה: האם יש דרך להבחין בין הפלט של PRNG איכותי מרצף אקראי באמת? בהגדרה זו, הפותר יודע שנעשה שימוש באלגוריתם PRNG ידוע (אך לא המצב שבו הוא אותחל), או שנעשה שימוש באלגוריתם אקראי באמת. עליו להבחין ביניהם.
האבטחה של רוב האלגוריתמים והפרוטוקולים ההצפנה המשתמשים ב-PRNGs מבוססת על ההנחה שאי אפשר להבחין בין שימוש ב-PRNG מתאים לבין שימוש ברצף אקראי באמת. הדוגמאות הפשוטות ביותר לתלות זו הן צפני זרמים, שלרוב פועלים על ידי השמטה או שליחת הודעת הטקסט הפשוט עם פלט PRNG, ומייצרים את הטקסט המוצפן. עיצוב PRNG הולם מבחינה קריפטוגרפית הוא קשה ביותר מכיוון שהם חייבים לעמוד בקריטריונים נוספים. גודל התקופה שלו הוא גורם חשוב בהתאמה הקריפטוגרפית של PRNG, אבל לא היחיד.
PRNG מחשב מוקדם שהוצע על ידי ג'ון פון נוימן ב-1946 ידוע כשיטת הריבועים הממוצעים. האלגוריתם הוא כדלקמן: קח כל מספר, ריבוע אותו, הסר את הספרות האמצעיות של המספר המתקבל כ"מספר אקראי", ולאחר מכן השתמש במספר זה כמספר ההתחלתי לאיטרציה הבאה. לדוגמה, ריבוע המספר 1111 נותן1234321, שניתן לכתוב כ-01234321, מספר בן 8 ספרות הוא הריבוע של מספר בן 4 ספרות. זה נותן 2343 כמספר "אקראי". התוצאה של חזרה על נוהל זה היא 4896 וכן הלאה. פון נוימן השתמש במספרים בני 10 ספרות, אבל התהליך היה זהה.
חסרונות של "הריבוע האמצעי"
הבעיה בשיטת "המרובע הממוצע" היא שכל הרצפים חוזרים בסופו של דבר, חלקם מהר מאוד, למשל: 0000. פון נוימן ידע על כך, אבל הוא מצא גישה מספיקה למטרותיו, וחשש שה "תיקונים" במתמטיקה פשוט יסתירו את השגיאות במקום להסיר אותן.
פון נוימן מצא שמחוללי מספרים אקראיים ופסאודו-אקראיים בחומרה אינם מתאימים: אם הם לא מתעדים את הפלט שנוצר, לא ניתן יהיה לבדוק אם יש שגיאות מאוחר יותר. אם הם היו רושמים את התוצאות שלהם, הם היו ממצים את הזיכרון הזמין המוגבל של המחשב ובכך את יכולתו של המחשב לקרוא ולכתוב מספרים. אם מספרים היו כתובים על כרטיסים, הם היו לוקחים הרבה יותר זמן לכתוב ולקרוא אותם. במחשב ה-ENIAC הוא השתמש בשיטת "הריבוע האמצעי" וביצע את תהליך השגת מספרים פסאודו אקראיים מהר פי כמה מאות מקריאת מספרים מכרטיסים מחוררים.
הריבוע הממוצע הוחלף מאז על ידי גנרטורים מורכבים יותר.
שיטה חדשנית
חידוש אחרון הוא שילוב הריבוע הממוצע עם רצף Weil. שיטה זו מבטיחה מוצרים באיכות גבוהה בפניםתקופה ארוכה. זה עוזר לקבל את הנוסחאות הטובות ביותר של מספרים פסאודו-אקראיים.
