פיתוח מחולל פסידו אקראי המתאים ליישום קריפטוגרפי הוא משימה קשה. מבחינה מעשית, פלט מחוללים פסידו אקראיים נפוצים סובל מפגמים רבים שמתגלים במבחנים סטטיסטיים. ביניהם מחזוריות קצרה מן הצפוי של מצב התחלתי מסוים או קורלציה. מצב התחלתי הגורם למחזוריות הרצף להיות קצרה מהצפוי נקרא 'חלש' במובן שבהינתן מצב התחלתי הזה פלט המחולל אינו בעל התפלגות אחידה ועל כן אקראיותו לקויה. לעיתים עולה במבחנים סטטיסטיים שהמחולל אינו מפיק פלט הדומה בתכונותיו לפלט אקראי אמיתי. לדוגמה אלגוריתם RANDU, שזכה לתפוצה רחבה בעיקר בשנות השישים של המאה ה–20, במערכות הפעלה של מחשבים מרכזיים. האלגוריתם יישם את רעיון מחולל LCG עם פרמטרים שנבחרו באופן לקוי, עקב כך מעריכים שנגרם לא אחת נזק למחקרים שהסתמכו על המחולל.
היסטוריה.
אחת השיטות המוקדמות ליצירת מספרים פסידו אקראיים באמצעות מחשב, הייתה של ג'ון פון נוימן ב-1946. השיטה הייתה מאוד פשוטה והיא נקראה "אמצע הריבוע", כדלהלן; מעלים מספר כלשהו בריבוע ונוטלים חלק מספרותיו האמצעיות כחלק מרצף אקראי, איתו משתמשים לאחר מכן כגרעין לחישוב הבא וחוזר חלילה. לדוגמה אם מעלים בריבוע את המספר 1111 מתקבל 1234321 אם מוסיפים אפס בהתחלה אפשר לשלוף את ארבע הספרות האמצעיות "2343" כמספר אקראי. אם מעלים את 2343 בריבוע, מוסיפים אפס מתקבל מספר שארבע ספרותיו האמצעיות הם 4896 וכן הלאה. פון ניומן השתמש במספר בן 10 ספרות.
הבעיה עם שיטה זו היא שמספרים התחלתיים מסוימים נוטים להפיק מחזוריות קצרה מדי. פון ניומן היה מודע לכך אולם הסתפק בשיטה זו לצרכיו. הוא היה מודאג יותר בשל החשש שתיקונים מתמטיים כלשהם עלולים יותר להסתיר את הבעיה מאשר לתקנה. פון ניומן נמנע משימוש במחולל מבוסס חומרה בשל העובדה שכדי לבדוק אקראיות היה צורך באחסון מספרים רבים בזיכרון והמחשבים שהוא השתמש בהם אז כמו ENIVAC היו מוגבלים מאוד בזיכרון מה שהיה עלול לגרום להאטה חמורה בביצועים. השיטה שאימץ למרות היותה לקויה היוותה מעין פשרה סבירה. כמובן שכיום השיטות הידועות ליצירת מספרים אקראיים מהירות ויעילות מהשיטה של פון ניומן.
מחוללים פסידו אקראיים.
Linear congruential generator.
שיטת Linear congruential היא השיטה הוותיקה והפופולרית ביותר כיום. היא הוצעה לראשונה על ידי דריק הנרי להמר ב-1949. הרעיון מאחורי משפחה זו של אלגוריתמים (הנקראת בקיצור LCG) פשוט בתכלית ובדרך כלל קל ליישום. המחולל מוגדר על ידי נוסחת הנסיגה: formula_5 כאשר formula_6 הוא האיבר ה-formula_1 בסדרת המספרים הפסידו-אקראית המופקת. הפרמטר formula_8 מכונה מודולוס, formula_9 נקרא "כופל" ו-formula_10 נקרא "מקדם" (במקרה של formula_11 מתקבל אלגוריתם פארק-מילר שנמצא בשימוש נרחב, בין היתר, במערכות ההפעלה של מקינטוש). formula_12 נקרא "מצב התחלתי" או גרעין התחלתי ובדרך כלל צריך להיות ממקור אקראי כלשהו. השפעת הפרמטרים formula_13 על פלט המחולל מכרעת.
LCG אינו מתאים לצורך קריפטוגרפי,מחקרים מראים שניתן לנחש את המשך הרצף מתוך קטע קצר יחסית גם ללא ידיעת הפרמטרים. הסוגים השונים של משפחה זו נבדלים בעיקר בערכי הפרמטרים. מחזוריות המחולל תלויה בראש ובראשונה בפרמטר formula_8. למשל גרסת המחולל של פארק-מילר עם המודולוס formula_15 (שהוא מספר מרסן ראשוני) והפרמטרים formula_16, formula_11 מגיעה למחזוריות בסדר גודל של formula_18.
להלן קוד C++ של המחולל הפסידו אקראי המובנה בסביבת הפיתוח של מיקרוסופט ויז'ואל סטודיו, המבוסס על LCG עם הפרמטרים formula_19:
return (((holdrand = holdrand * 214013L + 2531011L) » 16) &amp; 0x7fff);
הערך 0x7FFF משמש לצמצום מודולרי. המחולל מפיק מספר פסידו אקראי בגודל 15 סיביות.
Lagged Fibonacci generator.
מחולל מסוג זה מבוסס על הכללה של סדרת פיבונאצ'י. האלמנט הבא ברצף הפסידו אקראי הוא תוצאה של פעולה בינארית כלשהי (כמו חיבור או כפל) על שני אלמנטים קודמים לא בהכרח עוקבים (מודולו מספר מסוים). התאוריה מאחורי מחולל זה די מורכבת וגם הוא רגיש מאוד לשינויים במצב ההתחלתי. בחירה לא מושכלת של פרמטרים עלולה להוביל לתוצאות גרועות. מחולל זה יכול להגיע למחזוריות בסדר גודל של formula_20 כאשר formula_21 מציין את אינדקס ההפרש המקסימלי במחולל ו- formula_22 המודולוס.
Mersenne twister.
אלגוריתם Mersenne twister הומצא ב-1997 על ידי מקוטו מטסומוטו וטאקוג'י נישימורה. הרעיון של האלגוריתם מבוסס על גרסה מפותלת של אוגר הזזה (בדומה ל-LFSR) מעל השדה הבינארי formula_23. האלגוריתם מייצר רצף פסידו אקראי באיכות גבוהה והוא בעל מחזוריות גבוהה ביותר, בסדר גודל של formula_24 (שהוא מספר צירופים עצום, הרבה מעבר למספר החישובים שניתן לעשות בכל שנות קיומו של היקום). האלגוריתם מהיר ויעיל מכל מחולל אקראי אחר והפך לאחד האלגוריתמים המועדפים כיום לצורכי סימולציה סטטיסטית מדעית. חסרונו הוא מורכבותו ליישום והעובדה שאינו מתאים בגרסתו הבסיסית לקריפטוגרפיה.
Multiply-with-Carry.
Multiply-with-Carry הוא אלגוריתם ליצירת מספרים פסידו אקראיים עם מחזוריות משתנה, שהומצא על ידי ג'ורג' מרסגליה. האלגוריתם מכונה גם "Mother of all pseudorandom generators" והוא מבוסס אריתמטיקה מודולרית בדומה ל-LCG. בגרסה הבסיסית האלגוריתם כולל "בסיס" formula_25 (בדרך כלל formula_26 או formula_27), פרמטר formula_9 שנקרא "כופל", "גרעין" התחלתי אקראי הכולל קבוצה של formula_29 ערכים formula_30 הנקראים "שאריות" ופרמטר formula_10 הנמוך מ-formula_9 הנקרא "נשא". פלט האלגוריתם בכל שלב הוא הזוגות formula_33 המחושבים על ידי הנוסחה:
כאשר formula_36 והפלט הוא formula_37. מחזוריות המחולל היא בעצם הסדר של formula_25 בחבורה הכפלית מודולו formula_39 (נהוג לבחור formula_39 כך שהוא יהיה ראשוני). המחזוריות יכולה להגיע לסדר גודל עצום של formula_41. קיימת בעיה אחת עם הגרסה הבסיסית של המחולל, שהסיבית הגבוהה ביותר שלו סובלת מהטיה קלה.
מחוללים פסידו אקראיים קריפטוגרפיים.
מחולל אקראי שמוגדר בטוח לצורך קריפטוגרפיה (בקיצור CSPRNG) שונה בכמה היבטים. ההבדל העיקרי הוא שהאלגוריתם צריך להיות מתוכנן כך שיעמוד בפני התקפות המנצלות חולשות באלגוריתם על מנת לנחש את המשך הרצף האקראי. דבר שצריך להיבחן היטב במשך זמן רב על ידי קריפטוגרפים מומחים. אפילו בדיקות מדוקדקות במשך שנים אינן מבטיחות כי האלגוריתם בטוח לחלוטין מבחינה קריפטוגרפית, התקפות חדשות שיתגלו בעתיד עלולות למצוא את האלגוריתם לא מוכן ולא בטוח לשימוש. באלגוריתם MD4 שנחשב במשך שנים לאלגוריתם בטוח, התגלו לא מזמן ליקויים ועקב כך אינו מומלץ כיום לשימוש למטרות קריפטוגרפיות.
בדרך כלל אלגוריתמים לייצור מספרים פסידו אקראיים לצורך קריפטוגרפי מיושמים באמצעות פרימיטיבים קריפטוגרפיים ידועים בבטיחותם כמו צופן זרם או צופן סימטרי אחר כמו AES. מאחר שצופן סימטרי מטבעו מכיל את התכונה שהוא קשה לניחוש, כמעט כל צופן בטוח מתאים להכנת מחולל קריפטוגרפי. אחת השיטות היא להצפין ערך קבוע (בדרך כלל מחרוזת אפסים) באמצעות מפתח הצפנה הנגזר מגרעין התחלתי אקראי ולהשתמש בפלט הצופן או בחלקו כרצף אקראי. מחוללים פסידו אקראיים קריפטוגרפיים בדרך כלל נבנים מ:
דוגמה למחולל פסידו אקראי קריפטוגרפי המבוסס על הצפנה אסימטרית הוא Blum Blum Shub (בקיצור BBS) שבטיחותו מוכחת, למרות שהיא מותנית בכך שהפרמטרים הפנימיים ישמרו בסוד. נוסחת האלגוריתם היא מהצורה: formula_42 כאשר formula_8 הוא מכפלה של שני מספרים ראשוניים גדולים. המחולל BBS נחשב לאיטי יחסית ואינו מתאים בכל המקרים, אך הוכח שבטיחותו שקולה לבעיית פירוק לגורמים. דהיינו ניחוש הסיבית הבאה שהאלגוריתם ייצר שקולה לפירוק formula_8 לגורמים.
בין האלגוריתמים הייעודיים שעוצבו במיוחד לצורך קריפטוגרפי נמנה CryptoGenRandom של מיקרוסופט כחלק מתשתית API, המפיק גרעין התחלתי מתוך מספר נתוני מערכת ולאחר מכן מעביר את הפלט בפונקציית גיבוב MD4 וצופן RC4. וכן אלגוריתם Yarrow המובנה במערכת ההפעלה Mac OS X ו-Free BSD ואלגוריתם Fortuna.
קריטריון BSI.
המשרד הפדרלי הגרמני לאבטחת מידע (BSI) קבע קריטריון המחולק לארבעה מרכיבים לבחינת איכות מחוללי מספרים אקראיים דטרמיניסטיים המבוסס על מחקרים שנעשו עד כה בתחום:
החלק האחרון חשוב בעיקר לצורך קריפטוגרפיה. רק אם המחולל עמיד להתקפה מסוג כזה, שבה התוקף מסוגל לנחש או לחשב אלמנטים שיופיעו ברצף או הופיעו בעבר מתוך מצב פנימי בשלב נתון כלשהו של הרצף, ייקרא בטוח מבחינה קריפטוגרפית.
מחולל אקראי בעל התפלגות נורמלית.
התפלגות סטטיסטית לא אחידה (כמו התפלגות ריילי או התפלגות פואסון) אפשר לייצר באמצעות שילוב של מחולל PRNG בעל התפלגות סטטיסטית אחידה ופונקציה אי-ליניארית כלשהי. למשל ההיפוך של פונקציית התפלגות מצטברת עם מחולל PRNG אידיאלי וטווח קלט (0,1), יפיק רצף ערכים בהתפלגות נורמלית. אולם יש צורך לחתוך את הזנב האינסופי של ההתפלגות לערך סופי. אפשר לצמצם את ההתפלגות הנורמלית המצטברת באמצעות אלגוריתם כמו זיגורט (Ziggurat).
קריית ויז'ניץ
קריית ויז'ניץ (או שיכון ויז'ניץ; השם המקורי: שיכון אהבת ישראל ואור החיים) היא שכונה בבני ברק המשמשת כמרכז לחסידות ויז'ניץ בישראל.
היסטוריה.