הרעיון הוא שכדי לייצר מספר פסידו-אקראי אפשר להשתמש בתוצאת פונקציה חד-כיוונית כלשהי או פונקציה פסידו אקראית של הגרעין ההתחלתי או חלק ממנה. צופן סימטרי או פונקציית גיבוב מהווים מועמדים טובים לפונקציה כזו. בגלל פרדוקס יום ההולדת שמאפשר התקפת איזון זמן/זיכרון ביטחון מחולל כזה מוגבל לפקטור של מחצית מסיביות המפתח. למשל אם משתמשים בצופן בלוקים מסוג AES עם בלוק בגודל 128 סיביות ומפתח בגודל 256 סיביות אפשר להגיע לביטחון מקסימלי של 128 סיביות בקירוב.
תקן NIST למחולל פסידו אקראי קריפטוגרפי.
תקן ANSI X9.17 (או FIPS 186) הישן מיישם עיקרון זה, הוא משתמש בצופן סימטרי בטוח או פונקציית גיבוב לפי בחירה כדי לייצר ערך אקראי על ידי הצפנה של גרעין התחלתי בעל אנטרופיה גבוהה. המצב הפנימי מעודכן על ידי הצפנת מונה כלשהו עם הגרעין ההתחלתי והפלט או חלק ממנו נהיה המצב הפנימי החדש.
תקן SP800-90A (גרסת יוני 2015 רביזיה 1) של NIST הוא ממשיכם של FIPS PUB 140-2, ANSI X9.31, X9.62. התקן מפרט כמה שיטות ליצירת מחולל פסידו אקראי בטוח לצורך קריפטוגרפי שנקרא DRBG לפי השלד המתואר בתרשים משמאל. כאשר פונקציית המחולל (Generate Function) יכולה להיות בכמה אופציות. בתקן המקורי פורסמו שלוש שיטות 1. פונקציה מבוססת פונקציית גיבוב 2. פונקציה מבוססת צופן סימטרי 3. פונקציה מבוססת עקום אליפטי שנקראת Dual EC DRBG. במשך שנים היו שמועות שבמחולל השלישי הוחדרה דלת אחורית שהייתה ידועה רק למפתחי האלגוריתם ול-NSA. בעקבות חשיפות מסמכי סנודן חלק מהטענות התבררו כנכונות ובעקבות זאת ובעקבות מחקרים נוספים הוחלט להסיר את האופציה השלישית Dual_EC_DRBG מהרשימה המומלצת. רמות הביטחון של המחולל מושגות בהתאם לפרימיטיב הקריפטוגרפי שבבסיסו. למשל פונקציית גיבוב SHA-3 או צופן AES עם מפתח 256 סיביות מספקים רמת ביטחון מקסימלית.
dev/random.
המחולל dev/random פותח בהשראת המחולל הפסידו-אקראי של PGP עבור מערכות הפעלה תואמי UNIX ליצירת מספרים אקראיים המתאימים לצורך קריפטוגרפי. ב-1994 ייושם האלגוריתם בלינוקס על ידי תיאודור צו. המחולל dev/random מורכב משלושה תהליכים א-סינכרוניים והוא שוכן בליבת המערכת כך שגישה אליו ברמת משתמש מוגבלת. בתהליך הראשון נאספים נתוני ליבה (kernel) מתוך מנהלי התקנים כמו מקלדת, עכבר, כונן קשיח ואירועים אחרים. נתונים אילו מהווים את האנטרופיה הבסיסית של המחולל. בתהליך השני הנתונים מועברים למאגר בגודל 512 בתים באמצעות פונקציות ערבוב דמוית CRC. המצב הפנימי של המחולל נשמר בשני מאגרים נוספים כאשר חלק מהסיביות מוחזרות למאגרים לאחר גיבוב. המחולל נחסם כאשר האנטרופיה נגמרת וממתין עד שנאגרת מחדש מספיק אנטרופיה מההתקנים האמורים, לצורך כך קיים מונה שמנהל מעקב אחר כמות הסיביות שהופקו מהעדכון האחרון. כאשר יש צורך במספר אקראי התהליך השלישי נכנס לפעולה ומעביר את הרצף הגולמי המופק מהמאגר דרך פונקציית גיבוב SHA-1 ואז מופק פלט אקראי. בגרסאות קודמות של המחולל התגלו ליקויים שנבעו מאופן ניצול האנטרופיה מהמערכת.
הפונקציה CryptGenRandom.
מערכות ההפעלה של מיקרוסופט כוללות את אלגוריתם CryptoGenRandom המובנה בתשתית API קריפטוגרפית הנקראת CSP (קיצור של Cryptographic Service Provider והוא מבוסס על הפונקציה RtlGenRandom מהספרייה Advapi32.dll. האלגוריתם פועל על עיקרון דומה לתקן FIPS 186-2. תחילה מופק גרעין אקראי אמיתי, שנשמר בנפרד עבור כל יישום המשתמש במחולל. הגרעין נאסף ממקורות שונים במערכת;
כל זה מועבר בפונקציית גיבוב SHA-1 ארבע פעמים והפלט משמש כמפתח לצופן RC4 איתו מצפינים את המצב הפנימי. פלט הצופן משמש לעדכון המצב הפנימי. ופלט פונקציית הגיבוב מוחזר למשתמש כסיביות פסידו-אקראיות. המערכת מאפשרת למשתמש להזין נתונים לתוך החוצץ האקראי לפני קריאה לפונקציה.
אף על פי שהמפרט של המחולל מעולם לא פורסם על ידי מיקרוסופט מלבד תיאור כללי. פורסמה ב-2007 קריפטואנליזה שלו על ידי ליאו דורנדורף, צבי גוטרמן ובני פינקס מהאוניברסיטה העברית שבו הם מציגים שלושה פגמים רציניים במחולל שהותקן בגרסאות של Windows 2000, לאחר שהצליחו להנדס לאחור את קוד המקור שלו. (1) בהינתן מצב פנימי של המחולל אפשר לנחש את המצב הפנימי הקודם בזמן של formula_30. (2) המחולל פועל ברמת משתמש ולא ברמת מערכת מה שמאפשר גישה ישירה לזיכרון שלו. (3) כל תהליך מריץ עותק אחר של המחולל והמצב הפנימי שלו, מה שמאפשר התקפת גלישת חוצץ.
האלגוריתמים Yarrow, Fortuna.
Yarrow פותח ב-1999 על ידי ברוס שנייר, נילס פרגוסון וג'ון קלסי מחברת Counterpane. הוא מנצל פרימיטיבים קריפטוגרפיים קיימים כמו 3DES או SHA-1 ומורכב מארבעה רכיבים עצמאיים; אוגר אנטרופיה שתפקידו לאסוף נתונים אקראיים שונים ביניהם קלט משתמש ונתוני מערכת שונים לתוך מאגרים מיוחדים (pools). מנגנון גירעון שמחליף מעת לעת את מפתח ההצפנה של המחולל באמצעות אנטרופיה חדשה. מחולל שמייצר פלט אקראי באמצעות מפתח ההצפנה עם אלגוריתם 3DES במצב מונה (Counter mode) ופונקציית גיבוב SHA-1 וכן מנגנון בקרת גרעון שאמור לקבוע מתי יש צורך לחדש אנטרופיה כדי למנוע מתוקף לנחש את מצבו הפנימי של המחולל. האלגוריתם מכיל ליתר דיוק שני מאגרים בגודל 160 סיביות כל אחד, הנקראים "מאגר איטי" ו"מאגר מהיר" המתאימים לפלט SHA-160. המאגר המהיר מרענן את המחולל באנטרופיה חדשה בתדירות כזו שאם מצב פנימי אחד נחשף, פרק הזמן של החשיפה יהיה קצר ככל האפשר. המאגר האיטי מבצע רענון יסודי אחת לפרק זמן ארוך ליתר ביטחון. האלגוריתם מכיל מנגנון פנימי להערכת אנטרופיה וכן כולל אופציה לשמירת קובץ המכיל ערכים אקראיים עם אנטרופיה גבוהה לצורך אתחול המחולל לאחר כיבוי והדלקה של המחשב. האלגוריתם שולב במערכות ההפעלה Mac OS X ו-iOS 7 וכן FreeBSD.
Yarrow הוחלף ב-2003 על ידי Fortuna. בניגוד לקודמו אינו מכיל רכיב הערכת אנטרופיה. במקום זאת, כדי לפתור את בעיית הרענון, מכיל 32 מאגרים (pools). הרענון מתפרס באופן אחיד ככל האפשר על פני כל המאגרים. כל מקור אנטרופיה שנקרא "אירוע" מבצע עדכון של מאגר אחד מתוך האוסף לפי אינדקס שהוא בוחר, בסגנון Round-Robin (ראה ריבוי משימות).
מקור השם Yarrow הוא פרח שמקורו בסין שהגבעול שלו שימש בעת העתיקה לצורך נבואות. מקור השם Fortuna הוא אילת המזל מהמיתולוגיה הרומית.
אלגוריתם ISSAC.
ISAAC פותח על ידי רוברט ג'נקינס ב-1996 ושמו הוא קיצור של Indirection, Shift, Accumulate, Add, Count. זהו למעשה צופן זרם שעוצב במיוחד לשמש כמחולל מספרים פסידו-אקראיים קריפטוגרפי. האלגוריתם מבוסס על וריאציה של צופן זרם RC4, הוא משתמש במערך של 256 כניסות כל אחת בגודל 32 סיביות. ומשתמש בשלושה פרמטרים שערכיהם הראשוניים קבועים ואינם סודיים; a - אוגר אנטרופיה, b - זוכר את המספר האקראי הקודם ו-c - מונה. האלגוריתם בונה מערך עזר נוסף בגודל זהה ומזין אותו בערכים אקראיים בהתאם לפרמטרים a,b,c בשילוב פעולות XOR, הזזה (SHIFT) וחיבור מודולו 32 סיביות. התוצאה היא מערך של מספרים אקראיים שכאשר מנוצל עד תום, חוזרים על פעולת האלגוריתם.
אף על פי שהתגלתה התקפה על האלגוריתם שיעילה מחיפוש השורש הריבועי של כל הערכים ההתחלתיים האפשריים בסיבוכיות של formula_31, האלגוריתם עדיין בטוח לשימוש מבחינה מעשית. בנוסף התגלו מספר גדול של ערכים התחלתיים "חלשים" במובן שבהינתן ערכים אילו האלגוריתם מייצר מספרים אקראיים עם הטיה.
בדיקת אקראיות.
כל מחולל חייב להיבדק שאכן הוא מפיק פלט קרוב בהתפלגותו ככל האפשר לפלט אקראי וכן אינו מכיל ליקויים נסתרים. ישנם מבחנים סטטיסטיים שנועדו למטרה זו. המבחנים אינם מוכיחים מעל לכל ספק שהמחולל אקראי אלא רק מצביעים על ליקויים אם ישנם. גם מחולל פסידו-אקראי קריפטוגרפי חייב לעבור מבחנים כאלה. להלן פירוט מספר כלים ידועים לבדיקת אקראיות:
מבחן הסיבית הבאה.
מבחן הסיבית הבאה הוא מבחן אוניברסלי שמגדיר את טיב אקראיות הרצף על ידי הניסוי הבא: בהינתן המחולל formula_32 עם גרעין התחלתי formula_11 באורך formula_24 המסוגל לייצר רצף של formula_35 סיביות פסידו אקראיות. המחולל יעבור את מבחן הסיבית באה אם בהינתן רצף של formula_36 סיביות כאשר formula_37, לא קיים אלגוריתם formula_38 שמסוגל בזמן ריצה formula_39 לנחש את הסיבית formula_40 בהסתברות העולה על חצי בשיעור formula_41 שהוא פרמטר ביטחון כלשהו או טווח שגיאה. בניסוח רשמי:
ארכיטקטורה למחולל פסידו-אקראי קריפטוגרפי.