מחולל מספרים פְּסֵידוֹ-אקראיים קריפטוגרפי או מחולל פסידו-אקראי קריפטוגרפי (Cryptographically secure pseudorandom number generator) או בקיצור CSPRNG הוא מחולל פסידו אקראי עם תכונות המתאימות במיוחד לשימוש בקריפטוגרפיה. מחולל פסידו אקראי מהווה מרכיב חיוני ובלתי נפרד במערכות אבטחת מידע. פרימיטיבים קריפטוגרפיים רבים זקוקים לרצף מספרים אקראיים (או סיביות) כחלק מפעולתם, ביניהם:
מחולל פסידו אקראי.
קיימים מספר דרכים ליצירת מספרים אקראיים אמיתיים באמצעות מכשירים מיוחדים המבוססים על מכניקת הקוונטים, לדוגמה התקן שממיר רעש תרמי או דעיכה רדיואקטיבית לרצף מספרים. אך לרוב הם יקרים ולעיתים הפלט שלהם סובל מהטיות סטטיסטיות (התפלגותו אינה אחידה). מלבד זאת לפעמים תנאי הכרחי הוא שיהיה ניתן לשחזר את הרצף בדיוק, תכונה שאינה אפשרית במחולל אמיתי. דרך אחרת היא להשתמש במחולל פסידו אקראי בקיצור PRNG. זוהי פונקציה דטרמיניסטית כלשהי במחשב, שלאחר אתחול באמצעות ערך אקראי ראשוני שנקרא "גרעין", מפיקה רצף מספרים שנראה על פניו כאקראי במובן שהצופה מן הצד שאינו יודע מהו הגרעין ההתחלתי, לא יוכל להבחין בין הפלט שלה לבין פלט מחולל אקראי אמיתי. חשוב לשים לב שבהינתן אותו מצב התחלתי, הפונקציה לעולם תייצר את אותו הרצף בדיוק. זוהי תכונה רצויה ואפילו הכרחית. בצופן זרם המקבל חייב לשחזר את הרצף הפסידו-אקראי שנוצר בזמן ההצפנה אחרת לא יוכל לפענח.
מחוללים פסידו-אקראיים שימושיים במספר רחב של תחומים ביניהם; סימולציה, סטטיסטיקה, אלגוריתמים הסתברותיים, משחקי מחשב, משחקי הימורים ועוד. ממחולל כזה מצפים שיהיה בעל התפלגות סטטיסטית קרובה לרצף אקראי אמיתי. אך כדי שיתאים לקריפטוגרפיה אין די בתכונות אקראיות טובות, עליו לעמוד בקריפטואנליזה שבה המנתח או המתקיף מנסה לנחש רצף עתידי בהינתן הרצף שהתקבל עד כה או להפך, לנחש מתוך הרצף הנוכחי רצף קודם שהופק מהמחולל. המחוללים הקלאסיים אינם בנויים לסוג כזה של איום.
איכות האקראיות הדרושה משתנה בהתאם לייעוד. לצורך ערך ייחודי וחד פעמי איכות נמוכה מספקת ואילו ליצירת מפתח הצפנה יש צורך באיכות הגבוהה ביותר האפשרית. הוכחת הבטיחות של צופן פנקס חד-פעמי מהיבט תאורטי נכונה רק תחת ההנחה שמפתח ההצפנה הוא מספר אקראי "אמיתי", מספרים אקראיים שנוצרו על ידי תוכנת מחשב אינם אקראיים אמיתיים. גם מחולל אמיתי צריך להיות מוכח מעל לכל ספק שאינו סובל מהטיות סטטיסטיות או סטיות כלשהן. מעשית כמעט לא ניתן לקיים דרישה כזו. למעשה PRNG הוא מעין פשרה, המחולל אמור לקבל רצף אקראי אמיתי קצר וממנו לייצר מחרוזת פסידו אקראית באורך הרצוי, כך שבהינתן קטע מהמחרוזת לא יצליח יריב בעל עצמת חישוב פולינומית לנחש סיביות עתידיות או סיביות שהופקו קודם, ללא ידיעת הגרעין ההתחלתי. כלומר שלא יצליח להבחין בזמן פולינומי בין תוצאת המחולל לבין מחרוזת אקראית אמיתית.
מבנה כללי.
PRNG בנוי באופן כללי משלושה רכיבים עיקריים:
גרעין התחלתי.
המאגר מאותחל בגרעין אקראי אמיתי שנאסף ממקור חיצוני אחד או יותר. מקורות אפשריים יכולים להיות; מחולל אקראי אמיתי או מפתח סודי. הדרך הזולה והזמינה ביותר והיא המקובלת כיום, היא לנצל תהליכים בלתי צפויים בתוך המחשב. כמו תכולת זיכרון, חוצץ המקלדת, קואורדינטות העכבר, פסיקות ונתוני מערכת הנשמרים בכונן הקשיח, אפיקי קלט/פלט, יומני תיעוד של המערכת ועוד. הגרעין הוא בעל אנטרופיה גבוהה בדרך כלל (דהיינו קשה לניחוש) אך מאידך עלול להיות בעל התפלגות סטטיסטית ירודה. פונקציית העדכון אחראית לספק התפלגות סטטיסטית אחידה ככל האפשר ולשמר אנטרופיה גבוהה.
דוגמה למחולל פסידו-אקראי שאינו מתאים לקריפטוגרפיה כלל, הוא המחולל הנפוץ בפונקציות ספרייה של שפות תכנות שנקרא Linear congruential generator. בדרך כלל המחולל מופעל בקריאה לפונקציה formula_1 והוא פועל באופן כללי כך:
כאשר formula_3 הוא הגרעין הקודם, formula_4 ו-formula_5 פרמטרים קבועים כלשהם. במהדר GCC קיימת גרסה של פרמטרים: formula_6, formula_7, formula_8.
פלט מחולל מסוג זה נראה על פניו כאקראי, אך ניתן לחיזוי בקלות. בהינתן formula_9 סיביות מהרצף, אפשר בעזרת הנוסחה formula_10 לחשב כל ערך שיהיה או שהיה.
אנטרופיה.
מחולל קריפטוגרפי משתמש כבסיס באנטרופיה ממקור המכונה "גרעין" (seed). בהקשר של תורת האינפורמציה אנטרופיה היא כלי למדידת כמות המידע הטמון ברצף נתון, כלומר מידת אי-הוודאות לגביו לפני שהתקבל או הקושי בחיזויו. היות שרצף של PRNG נקבע לפי הגרעין ההתחלתי, מידת אי-הוודאות שלו זהה למידת אי-הוודאות של הגרעין. במילים אחרות ניחוש כל חלק של הרצף אינו קשה יותר מניחוש הגרעין ולא משנה מה אורך הרצף. לכן חשוב שניחוש הגרעין ההתחלתי בכוח גס יהיה מעבר לעוצמת המחשוב הנוכחית. נכון לשנת 2015 אורך של 256 סיביות מספק מרווח ביטחון ראוי לדעת מומחים רבים.
פונקציית האנטרופיה של שאנון נמדדת לפי מספר הסיביות לסמל מתוך האלפבית formula_11:
כאשר formula_13 היא פונקציית הסתברות המייצגת את התפלגות השפה או הסתברות שמתשנה מקרי formula_14 שווה formula_15, בניסוח רשמי: formula_16. כלומר לפי שאנון כמות המידע המינימלית ההכרחית כדי לשדר את formula_15 היא formula_18 סיביות. האנטרופיה של התפלגות השפה האנגלית מעל קבוצת האותיות A עד Z היא 2.62, אף על פי ש-formula_19, מזה נובע שבשפה זו ישנן בערך שתי סיביות יתירות בכל סמל.
Min Entropy.
אנטרופיה מינימלית formula_20, ממשפחת אנטרופיות רניי שהן הכללה של אנטרופיית שאנון, היא הדרך השמרנית ביותר למדידת קושי בניחוש. אפשר לנסחה כלוגריתם השלילי של התוצאה בעלת ההסתברות הגבוהה ביותר. או לחלופין מדידת המקרה הגרוע ביותר של ההתפלגות:
יש להביא בחשבון שיכול להיות מצב שלהתפלגות נתונה תהיה אנטרופיית שאנון גבוהה אך אנטרופיה מינימלית נמוכה. למשל אם עבור formula_15 כלשהו ההסתברות היא חצי ובכל היתר הסתברות קטנה מאוד.
אנטרופיה ואקראיות הם מושגים חופפים אך לא בהכרח מחייבים הדדית. אקראיות ככל שתהיה טובה אינה מבטיחה קושי בניחוש. כדי להבין זאת מספיק להתבונן בדוגמה הבאה; נתון מחולל אקראי שבוחר מספר כלשהו מתוך מאגר של מאה מספרים אקראיים, גם אם השיטה בה נבחר תהיה בעלת תכונת אקראיות גבוהה ביותר, קל ביותר לנחש את תוצאת המחולל פשוט על ידי ניסוי כל מאה האפשרויות.
דרישות ביטחון.
מחולל פסידו אקראי מיושם במחשב בצורת אוטומט סופי בעל זיכרון שנקרא "מצב פנימי" שנשמר בין הקריאות. כל מספר פסידו-אקראי שמופק מן המחולל הוא פונקציה של המצב הפנימי. לאור זאת, מובן שכל מחולל פסידו-אקראי חייב להיות מחזורי, כלומר בהכרח באיזה שהוא שלב המחולל יחזור על ערך שכבר הופק בעבר (לא בהכרח הראשון) ומנקודה זו ואילך הרצף יחזור על עצמו בהעתק מדויק, במעין מעגל אין סופי. אורך המחזור תלוי במחולל, וחסום על ידי formula_23, כאשר formula_24 הוא מספר הסיביות במחולל. בשל פרדוקס יום ההולדת, אורך המחזור של פונקציה מקרית הוא בדרך כלל מסדר הגודל של formula_25 דווקא. בהצפנה, חשוב מאוד לא להשמש במחולל מעבר לאורך המחזור המקסימלי שלו, כיוון שאז יהיה קל למתקיף לנחש את המשך הרצף מאחר שכבר הופיע בנקודת זמן כלשהי בעבר.
ישנם שני הבדלים מהותיים בין מחולל פסידו-אקראי לבין מחולל אקראי אמיתי:
דרישות הביטחון המינימליות בכל מחולל פסידו-אקראי קריפטוגרפי הן:
דוגמאות.
להלן פירוט מקצת המחוללים הקיימים כיום.
מחולל פסידו אקראי בחומרה.
מחולל פשוט ויעיל הנקרא LFSR הוא רכיב חומרה הכולל אוגר שהוא מערך תאי זיכרון המסוגלים לאחסן סיביות, שעון ופונקציית היזון שמחברת ב-XOR מספר תאים לא בהכרח עוקבים כדי להפיק את "סיבית ההזנה". בכל פעימת שעון תכולת כל תאי האוגר מוזזת פוזיציה אחת (תכולת כל תא מועתקת לתא שלידו) כאשר תכולת התא הראשון שנפלט מהווה חלק מהרצף הפסידו-אקראי ואילו התא העליון שהתפנה מוזן בסיבית שחושבה על ידי פונקציית העדכון. LFSR קל ויעיל למימוש בחומרה והוכח מתמטית שהוא יכול לייצר בתנאים הנכונים רצף פסידו-אקראי המקסימלי שניתן וכן בעל תכונות סטטיסטיות טובות. אולם בשל הליניאריות שלו כשלעצמו אינו מתאים לקריפטוגרפיה כי הוא קל לניחוש. הטכניקה להתגברות על הבעיה היא הוספת אי-ליניאריות. למשל שליטה בפלט שני LFSR באמצעות פונקציה אי-ליניארית כלשהי, או שליטה בשעון של LFSR אחד באמצעות LFSR אחר, או שילוב של LFSR אם תאומו NFSR (אוגר זיזה ממושב אי-ליניארי) ועוד. למעשה קיימים צפני זרם מודרניים רבים שפועלים על עיקרון זה, ביניהם כאלו המותאמים לחומרה כמו גריין ו-MICKEY או כאלו שמותאמים לתוכנה כמו SNOW ו-SOSEMANUK.
מחולל מבוסס אריתמטיקה מודולרית.
Blum-Blum-Shub בקיצור BBS הוא מחולל PRNG חזק, מבוסס אריתמטיקה מודולרית שפותח על ידי מנואל בלום, לינור בלום ומייקל שוב. בוחרים שלם formula_24 שהוא כפולה של שני מספרים ראשוניים גדולים וסודיים באופן שקשה לפרק את formula_24 לגורמים וגרעין התחלתי כלשהו. בכל פעם שנדרשת סיבית אקראית הפלט יהיה הסיבית הכי פחות חשובה של תוצאת העלאה בריבוע מודולו formula_24 של הערך הפנימי. האלגוריתם הוכח כבטוח, כלומר ניחוש הסיבית הבאה קשה לפחות כפירוק לגורמים של formula_24. החסרון העיקרי שלו הוא שכדי להפיק סיבית אחת יש לבצע העלאה בחזקה מודולרית של מספר גדול מאוד שהיא פעולה לא יעילה במונחי מחשוב. הצפנת בלום-גולדווסר מבוססת על מחולל זה.
מחולל מבוסס צופן סימטרי.