שפת התכנות הראשונה שהכרתי הייתה BASIC, ואחד מהמשחקים הראשונים שכתבתי היה משחק שבו המחשב מגריל מספר והשחקן צריך לנחש אותו. למרבה הצער, שמתי לב לתופעה מאוד מוזרה במשחק שלי - המחשב תמיד הגריל את אותו המספר. לעומת זאת, אם הגדלתי את טווח המספרים שהוא יכל לבחור, הוא פתאום הגריל תמיד מספר אחר. רק אחרי זמן מה למדתי שכדי להבטיח שהמחשב יגריל מספר שונה בכל משחק, עלי לכתוב בתחילת התוכנית RANDOMIZE TIMER. מה זה בכלל אומר? מה הולך כאן?
תמונת מסך של Qbasic (צילום: Zekko)
שורש הבעיה נעוץ בכך שמחשבים הם יצורים דטרמיניסטיים באופיים - בהינתן המצב הנוכחי של תאי הזיכרון שלהם, הקידוד של החומרה שלהם וכו’, המצב הבא נקבע באופן יחיד. אין "הגרלות" שמבוצעות בתוך המחשב - לפחות, כך אנחנו מקווים; התנהגות בלתי צפויה של המחשב (של המחשב עצמו, לא של תוכנה שמריצים עליו) מעידה על תקלה חמורה בו. אם כן, איך אפשר ליצור אקראיות מהדטרמיניזם הזה? האם בכלל יש משמעות למילה הזו, "אקראיות"?
מבחינה פיזיקלית ופילוסופית, הדיון בשאלת האקראיות הוא עמוק ומעניין. למיטב הבנתי את תורת הקוונטים, משתמע ממנה שיש תהליכים בטבע שהם אקראיים באמת ובתמים - לא ניתן לקבוע בודאות מוחלטת מה תהיה תוצאת הסיום שלהם גם אם ידוע המצב ההתחלתי. מכיוון שאיני מבין בפיזיקה או בפילוסופיה, לא אכנס לדיון בנושאים הללו - אסתפק בדיון על מחשבים, שהם, כאמור, דטרמיניסטיים.
דרך אחת להכניס אקראיות למחשבים היא "לרמות". לחבר את המחשב להתקן פיזיקלי שמודד משהו שנחשב אקראי - פליטת קרינה מאטום כלשהו, למשל. גם לזה איני רוצה להיכנס, למרות שזה בהחלט פתרון לגיטימי שגם משתמשים בו בפועל. פרט לסרבול הטכני יש אפילו חסרון רעיוני כלשהו בהסתמכות על התקנים שהם "אקראיים באמת", שכן, כפי שאסביר בהמשך, לפעמים רוצים דווקא לחזור כמה פעמים על אותה סדרת ערכים אקראיים, ובאותם התקנים, ככל הידוע לי, הדרך היחידה לעשות זאת היא לרשום ולזכור את כל הערכים, וזה אינו רצוי.
הפתרון השני הוא להסתמך על גורמים שאינם בדיוק אקראיים מבחינה פיזיקלית, אבל לכל דבר ועניין נראים אקראיים - למשל, הקלדות על המקלדת. מן הסתם יש חוקיות גדולה למדי בהקלדות על המקלדת (למשל, כשכותבים באנגלית, צפוי שמייד אחרי כתיבת q ייכתב u), אבל אם נמדוד את קצב ההקלדה, ובפרט את מספר השניות שעוברות בין כל הקלדה לזו שאחריה, נראה משהו אקראי למדי (שכמובן, נע בתוך תחום מוגדר). באותו אופן גם תנועות העכבר הן "אקראיות" (חשבו על כך שכל תזוזה, ולו הקטנה ביותר של העכבר, נמדדת; כך שגם אם מזיזים את העכבר מנקודה א’ לנקודה ב’, יש אלפי דרכים שונות לעשות זאת, וזו שנבחרת היא "אקראית"). ישנם עוד גורמים "אקראיים" בריצת המחשב, אבל לא נתעמק ברובם; במקום זה נעסוק במקור הפופולרי והנפוץ ביותר לאקראיות, למרות שהחוקיות שבו גדולה מאוד - השעון הפנימי.
לשעון הפנימי יש יתרון ברור אחד - הוא משתנה. בכל שתי גישות לשעון הפנימי, הערך שיוחזר יהיה שונה. במחשב דטרמיניסטי, משהו שהוא תמיד שונה הוא תמיד תרומה מבורכת. עם זאת, ברור שהוא לא יכול לשמש בפני עצמו בתור יצרן של משהו אקראי. אם נדגום ממנו כל שניה, נקבל סדרה עולה עם הפרשים קבועים - לא משהו אקראי במיוחד. צריך לקחת את הפלט שהשעון (או קצב ההקלדה, או העכבר) נתן ולהפעיל עליו "ערבול" נוסף. זה מוביל אותנו לנושא המרכזי והחשוב ביותר של המאמר הזה - מחולל מספרים פסאודו אקראיים.
מחולל מספרים פסאודו אקראיים הוא אלגוריתם שמקבל כקלט מספר, ומוציא כפלט מספר אחר, "אקראי", שנראה בלתי תלוי במספר שהוא קיבל כקלט. למעשה האלגוריתם הוא דטרמיניסטי, בכך שעבור מספר קלט נתון הוא יוציא תמיד אותו מספר פלט - רק שנראה כאילו אין חוקיות. למשל, עבור שני מספרי קלט קרובים, שני מספרי הפלט יכולים להיות רחוקים (אבל לא בהכרח יהיו רחוקים, שהרי גם זו חוקיות!) - ולהפך. לדוגמה, המחולל הפסאודו־אקראי בגרסה אחת של שפת ג'אווה נותן עבור הקלט 0 את הפלט מינוס 1155484576 (תמיד). עבור הקלט 1 הוא נותן את הפלט מינוס 1155869325.
ברוב התוכניות אנו מעוניינים בסדרה של מספרים אקראיים (כי אנחנו מבצעים הרבה הגרלות). לשם כך זוכר המחולל את הפלט שהוא הוציא בפעם האחרונה שבה הוא נקרא, ובפעם הבאה שבה קוראים לו, פועל על המספר הזה בתור הקלט. כך, המחולל שנתן לנו מינוס 1155484576 זוכר את המספר הזה. אם מבקשים ממנו שוב מספר אקראי, הוא משתמש בו כקלט ונותן מינוס 723955400. בפעם הבאה הוא ישתמש במספר הזה וייתן 1033096058 (הפעם פלוס דווקא), וכן הלאה.
כמובן שהמחולל עדיין זקוק לקלט התחלתי כלשהו לפני שיוכל לייצר מספרים אקראיים שישמשו כקלטים בהמשך - לקלט ההתחלתי הזה קוראים ה”גרעין” (seed) של המחולל. בסדרה שהראינו זה עתה, הגרעין הוא 0. אם מזינים למחולל גרעינים שונים, סדרת הערכים שהמחולל יפלוט תהיה שונה בתכלית; ואם ניקח סדרת מספרים שנפלטה על ידי המחולל ונחפש בה חוקיות - נתקשה מאוד לגלות כזו. כל זה, כמובן, בתנאי שהמחולל שווה משהו. כדי שלא תהיה בסדרה חוקיות ברורה, הכרחי שטווח הערכים שהמחולל מסוגל להוציא יהיה גדול מאוד, ושהוא לא יחזור על עצמו - שהרי, ברגע שבו המחולל מוציא ערך שכבר היה בעבר באותה הסדרה, פירוש הדבר שהוא נכנס ללולאה (כי כאמור המחולל דטרמיניסטי, ולכן המשך הסדרה אחרי המופע השני של הערך יהיה זהה להמשך שלה אחרי המופע הראשון שלו).
כל זה טוב ויפה, אבל נניח שאני רוצה מספר אקראי בין 1 ל-6, כלומר הטלת קוביה. מה אני עושה? אני לוקח את הפלט מהפעלה אחת של המחולל, ובמקום להשתמש במספר כמות שהוא (כי כפי שראינו, זה לרוב מספר ענקי, ולפעמים שלילי) אני בודק מה השארית שהמספר הזה נותן בחלוקה ב-6. זה יהיה ערך בין 0 ל-5, שמתפלג באופן אחיד אם המחולל אכן מוצלח (כלומר, אם אחזור על ההגרלה הזו פעמים רבות, אראה שכל מספר התקבל בערך שישית מהפעמים). נותר לי רק להוסיף 1 לתוצאה. בצורה דומה אפשר לקבל מספר טבעי בכל טווח שהוא; אפשר גם להגריל מספרים "ממשיים" בתחום שבין 0 ו-1, פשוט על ידי נרמול - חלוקת המספר האקראי שהמחולל החזיר, במספר המקסימלי שהוא יכול להחזיר. לא כל המספרים בין 0 ל-1 יכולים להתקבל בשיטה זו (למשל, לא יתקבלו מספרים אי־רציונליים), אבל ממילא לא כל אותם המספרים יכולים בכלל להיות מיוצגים במחשב בשיטת היצוג הסטנדרטית.
כאן המקום לתאר כמה מחוללים קונקרטיים, אבל לא אעשה זאת, פשוט כי המתמטיקה של מחוללים טובים היא סבוכה וטכנית. אחד המחוללים הראשונים (אם לא הראשון) והפשוטים ביותר הומצא על ידי ג’ון פון נוימן - קח מספר בן n ספרות, העלה אותו בריבוע וקבל מספר עם 2n ספרות (הוסף 0 בתחילת המספר שהתקבל אם יש צורך), וכעת קח את n הספרות האמצעיות בתור הפלט. הבעיה בשיטה החביבה הזו היא שלולאות צצות יחסית מהר. פון נוימן, שמיוחס לו הציטוט "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin", כנראה לא נזקק למשהו מחוכם יותר, אבל לצורכי הצפנה, ואפילו עבור משחקים, זה לא מספיק טוב. באדיבות xkcd, הנה עוד דוגמה למחולל שכנראה לא כדאי להשתמש בו:
מחולל מספרים אקראיים (מקור: xkcd)
כעת אפשר להסביר מהו ה-Randomize timer של בייסיק. כשקוראים בשפת תכנות כלשהי לפונקציה שמחזירה מספר אקראי, לרוב הפונקציה הזו משתמשת במימוש של מחולל פסאודו אקראי זה או אחר. הגרעין של המחולל הזה מאותחל כאשר התוכנית מתחילה לרוץ - השאלה היא לאיזה ערך הוא יאותחל. אם השפה מאתחלת אותו תמיד ל-0, מן הסתם תמיד נקבל את אותה סדרה "אקראית". לכן כדי לקבל סדרות שונות בכל הרצה, יש להשתמש במקור שמובטח שתמיד ייתן ערך שונה - והשעון הפנימי של המחשב הוא המקור המושלם לכך. הפקודה Randomize timer מאתחלת את הגרעין של המחולל האקראי לערך שמושג מהשעון; בשפות אחרות יש פונקציה בשם srand שעושה את אותו הדבר. אלא שאין הכרח לאתחל דווקא באמצעות השעות; אפשר לאתחל גם באמצעות ערך מספרי שמועבר על ידי המשתמש עצמו, וכאן נכנס לתמונה אחת ההיבטים החביבים ביותר של מחולל פסאודו אקראי - אפשר לשחזר במדוייק את הסדרות האקראיות שהוא מייצר, מבלי לשמור אותן במלואן. פשוט מכניסים שוב את אותו גרעין, ומקבלים את אותה סדרה. בשביל מה זה טוב?
לפני שנים הייתי מכור למשחק מחשב אווילי בשם Worms, שבו השחקן שולט על צוות תולעים אכזריות שמפצפצות לצוותים אחרים של תולעים את הצורה עם בזוקות, רימונים ושאר מרעין בישין. הקרבות התנהלו בשדה קרב שנוצר באופן אקראי. חלק משדות הקרב היו מוצלחים במיוחד (נניח, הם היו עמוסים בצוקים שאם תולעת עומדת עליהם, אפשר לפצפץ אותה לאינסוף ביתר קלות). איך אפשר, אם כן, לשחזר את אותו שדה קרב? פשוט מאוד - לכל שדה קרב שהוגרל היה כתוב באופן מפורש הגרעין של המחולל הפסאודו אקראי שיצר אותו. כדי לקבל את אותו שדה קרב, כל שהיה נחוץ הוא לכתוב מחדש את הגרעין. כמובן, הגרעין נראה כמו ג’יבריש מאוד ארוך, ולא היה מאוד פרקטי לזכור אותו; אבל אפשר היה להכניס גרעינים משלך, פשוט בתור טקסט באנגלית - מאחורי הקלעים בוצעה המרה של הטקסט למספר - ולראות מה קיבלת. כך למשל, אם הייתי כותב "Alamo" הייתי מקבל דבר אחד (שנוצר בצורה אקראית לגמרי, ויכל להיות מוצלח או לא מוצלח, תלוי במזל), ואם הייתי כותב "Waterloo" היה מתקבל משהו שונה; אבל בכל פעם שבה הייתי כותב אותם, הייתי מקבל את אותו שדה קרב כמו בפעם הקודמת. התעלול נפוץ גם במשחקי מחשב אחרים, כמובן.
דוגמה אחרת - נניח שאני מהנדס שרוצה לבדוק עמידות של בתים לרעידות אדמה, באמצעות סימולציה מחוכמת במחשב. מה שאני עושה זה לכתוב אלגוריתם שמדמה רעידת אדמה - אירוע עם הרבה אלמנטים אקראיים בתוכו (כמובן, מה שקורה ברעידה הוא בעצם דטרמיניסטי לגמרי ברמת המקרו, אבל מכיוון שהחישוב הדטרמיניסטי הזה תלוי בפרטים רבים מדי והוא מסובך מדי, אנו מעדיפים למדל אותו עם גורמים אקראיים). כעת אפשר להכניס לסימולציה בית שנבנה בצורה כך וכך, ולבדוק האם הוא קורס ברעידת האדמה או מחזיק מעמד. מכיוון שאני רוצה להשוות אותו לבתים אחרים, אצטרך להכניס גם אותם לסימולציה באותם תנאים בדיוק - כלומר, הם צריכים להיות באותה רעידת אדמה, ובאותו מיקום, כך שאי אפשר להריץ את אותה סימולציה על שני בתים בו זמנית. צריך להריץ את אותה רעידת אדמה כמה וכמה פעמים, כשבכל פעם הפרמטר "איזה בית נרסק היום" משתנה. לכן צריך לזכור את הגרעין שבאמצעותו "הוגרלה" רעידת האדמה.
דוגמה שלישית, דומה ברוחה לדוגמה השניה - כשכותבים תוכנית מחשב, חלק בלתי נפרד מהתהליך הוא מה שנקרא unit testing - הרצת בדיקות "נקודתיות" שבודקות חלקים קטנים וספציפיים בתוכנית. לעתים הבדיקות הללו צריכות להיות אקראיות, שכן המתכנת לא מצליח לחשוב בעצמו על כל המקרים המעניינים. במקרה שבו בדיקה אקראית חושפת תקלה בתוכנית, לעתים קרובות ירצה המתכנת להריץ שוב ושוב את התוכנית עם אותו קלט בעייתי, עד שמתברר מה בדיוק הבעיה ואפשר לתקנה. לכן חשוב שהפלט של הבדיקה, פרט ל”זה וזה נכשל”, יכלול גם את הגרעין שיצר את האקראיות שהובילה לתקלה.
כל הדיון עד כה היה מעשי לגמרי, וכעת ניתן לעבור לתיאוריה. בתיאוריה, לא ידוע ולו על מחולל מספרים פסאודו אקראיים אחד. אין כלום. אפס. נאדה. גורנישט. הסיבה לכך היא שהדרישות של הגישה התיאורטית מחמירות יותר - יש לספק הוכחה פורמלית לכך שהמחולל הוא "כמעט אקראי", וזהו מושג שהגדרתו אינה פשוטה, ועוד פחות ברור איך אפשר להוכיח שמשהו קונקרטי (כדוגמת המחוללים שמשתמשים בהם כיום) מקיים אותה. האינטואיציה הטובה לכך ששאלת קיום מחולל היא קשה מאוד מאוד מגיעה מכך שקיום מחולל שכזה יוכיח תכף ומייד ש-P שונה מ-NP (הכיוון ההפוך אינו נכון - ייתכן ש-P שונה מ-NP אך לא קיימים מחוללים כאלה).
האם ניתן להבחין בזמן סביר בין ההגדרה הפורמלית של מחולל פסאודו אקראי לזו המעשית?
פורמט ה-MP3 חולל מהפכה אדירה בכל הנוגע לתרבות ההאזנה למוזיקה. סוד הקסם שלו היה כיווץ שהקטין מאוד את קבצי המוזיקה, עד לסדר גודל של מגהבייט לדקה. זה הפך את שיתוף קבצי המוזיקה לדבר מעשי ונפוץ. המחיר היה פגיעה כלשהי באיכות המוזיקה - MP3 הוא מה שנקרא "פורמט lossy". הכיווץ שהוא מציע מתבסס על זריקה לזבל של חלק מהמידע על הצליל - מידע שבתקווה אינו מורגש בפועל על ידי השומע. כמובן שטענה נפוצה היא שגם בקידודים איכותיים יחסית של MP3 (כלומר, כאלו שזורקים לזבל רק מעט דברים) עדיין ניתן להרגיש בהבדל. האמנם? האם ניתן להבחין בין קובץ מוזיקה "רגיל" ובין קובץ שכווץ באמצעות MP3? איך?
הפתרון הוא כמובן "מבחן האזנה", בדומה למבחני הטעימות שעושות חברות המזון. נותנים למישהו זוג קבצי מוזיקה של אותו שיר ושואלים אותו מה האמיתי ומה המכווץ. לצורך העניין נניח שהקבצים נראים אותו הדבר והם באותו הגודל - למשל, אם כיווצנו אחד עם MP3 ואז המרנו אותו בחזרה לפורמט ששומר את כל המידע, רק שכעת חסר מידע שהיה בקובץ המקורי והוא ממולא על ידי ביטים שלא משנים כלום בפלט הסופי.
כמובן ששומע בעל הבנה בפורמט של קבצי מוזיקה יכול לעבור על המידע שכתוב בקבצים ולבדוק באיזה קובץ יש יותר מידע רלוונטי. ייתכן שניתן לעשות זאת באמת ובתמים, אך לצורך הדיון נניח שזה דורש יותר מדי עבודה (בקרוב יהיה ברור לאן אני חותר עם כל ההנחות הללו). אם כן, מה שהשומע יעשה הוא פשוט להשמיע את שני הקבצים, ולומר מי מכווץ ומי לא. אם הוא לא מסוגל להבחין ביניהם, נצפה שהוא יטעה בערך ב-50% מהפעמים, כשחוזרים על הניסוי הזה פעמים רבות; אחרת, נצפה לראות הטייה סטטיסטית לטובת התשובה הנכונה.
אם בניסוי אכן נרשמו 50% טעויות, נוכל להגיד כי סטטיסטית, המאזין לא מסוגל להבחין בין קבצי MP3 ובין קבצי מוזיקה רגילים. אם נרצה ממש לקפוץ להסקת מסקנות, נוכל לטעון כי זה אומר שאין הבדל מעשי בין קבצי MP3 ובין קבצי מוזיקה רגילים, בכל הנוגע לאותו מאזין ספציפי. זו כמובן פרשנות של טענה מתמטית ואפשר לא לקבל אותה; אך לטעמי היא הגיונית בהחלט.
הבה נעבור כעת למספרים פסאודו אקראיים. השאלה המרכזית שעולה, כשמשתמשים במספרים פסאודו אקראיים ליישום כלשהו, היא "האם העובדה שאני משתמש במספרים פסאודו אקראיים ולא במספרים אקראיים באמת משנה משהו?".
ובכן, קשה לתת הגדרה פורמלית ל"משהו" הזה. אמרה ידועה היא שהיעד הנכסף של המתמטיקאי אינו משפט טוב כי אם הגדרה טובה. הגישה שאתאר במאמר הזה מנסה לפרמל את ה"משהו" הזה באמצעות משהו דמוי "מבחין ה-MP3" שתיארתי לעיל. נניח כי אני מהנדס תוכנה שקיבל לידיו "קופסה שחורה" של מחולל פסאודו אקראי שאני רוצה לבדוק את איכותו, וכמו כן יש לי גישה למחולל אקראי אמיתי (נניח, כזה שמבוסס על פיזיקה). מה שאעשה יהיה לכתוב תוכנית שלפעמים עונה 1 ולפעמים עונה 0, כתוצאה של חישוב אקראי כלשהו, ולבדוק אמפירית (על ידי זה שאריץ אותה פעמים רבות) מה ההסתברות שהיא תחזיר 1. אם אגלה שההסתברות הזו שונה כאשר האקראיות של התוכנית נובעת ממחולל "אמיתי", לעומת ההסתברות הזו כשהתוכנית משתמש במחולל הפסאודו אקראי, פירוש הדבר הוא שהמחולל הפסאודו אקראי איננו מוצלח - הנה, מצאנו תוכנית ("המבחין" שלי) שעבורה השימוש במחולל פסאודו אקראי באמת משנה משהו.
כדי להבין את הרעיון שלעיל הכרחי לתת דוגמה. אם כן, נניח שהמחולל שאני מנסה לבדוק הוא המחולל המופלא של xkcd שמחזיר תמיד 4, בעוד שמחולל אמיתי צריך להחזיר את הערכים בין 1 ל-6 בהסתברות אחידה. מה תהיה התוכנית שאכתוב? פשוט מאוד - תוכנית שמגרילה מספר בעזרת המחולל, פולטת 1 אם המחולל נתן 4, ו-0 אם הוא נתן משהו אחר. מה הולך כאן?
נניח שהתוכנית משתמשת במחולל האקראי האמיתי. מה ההסתברות שלה לפלוט 1? כמובן, 1/6. לכן אם אריץ אותה הרבה פעמים, אספור כמה פעמים קיבלתי 1 ואחלק במספר ההרצות הכולל, אקבל מספר שקרוב ל-1/6. לעומת זאת, אם התוכנית משתמשת במחולל של xkcd, היא תמיד תחזיר 1, ולכן כשאספור כמה פעמים קיבלתי 1 ואחלק במספר ההרצות הכולל, אקבל 1. ההבדלים כאן ברורים בצורה שאינה משתמעת לשתי פנים.
השאלה המתבקשת כאן היא "איך ידעת לכתוב דווקא את התוכנה הזו ולא, נניח, תוכנה שפולטת 1 אם היא קיבלה מהמחולל 3 או 2?". מן הסתם התוכנית שכתבתי "תפורה" על המחולל הפסאודו אקראי של xkcd, במיוחד כדי להראות בעיה שיש בו (אם כי, שימו לב שהוא מחולל כה גרוע עד שגם התוכנית השניה הזו "תפיל" אותו). עבור מחוללים מסובכים יותר כלל לא ברור שאדע לכתוב תוכנית שיוצרת הבחנה בינו ובין התפלגות אקראית אמיתית; אבל זה שאני לא יודע לכתוב תוכנית כזו לא אומר שהיא לא קיימת. וזו בדיוק הדרישה ממחולל פסאודו אקראי "מתמטי" - שלא תהיה קיימת תוכנית שכזו.
יש מגבלה מהותית נוספת שטרם הזכרתי כאן - דורשים שהתוכנית הנ”ל ("המבחין") תהיה בעלת זמן ריצה פולינומי, כלומר "יעילה" מבחינת זמן הריצה שנדרש לה (מושג זה הוסבר במאמר "עניין של זמן" המקושר לעיל). ההצדקה לכך היא מעשית לגמרי - אם אפשר לשים לב להבדל בין המחולל הפסאודו אקראי שלנו לבין התפלגות אקראית אמיתית, אבל רק ביישומים שהם לא יעילים וכנראה ישימו לב להבדל רק אחרי שהיקום ייחרב - ובכן, זה לא כל כך נורא.
אם כן, הסברתי כיצד קובעים שמחולל פסאודו אקראי הוא מוצלח - ובתורת ההצפנה, כדי שמשהו ייקרא "מחולל פסאודו אקראי" הוא צריך להיות מוצלח - אבל טרם הסברתי מה זה בעצם, מבחינה פורמלית, מחולל שכזה. ובכן, זה אלגוריתם דטרמיניסטי שמקבל קלט, ובונה ממנו פלט ארוך יותר, כך שאם הקלט התפלג באופן אחיד, גם הפלט אמור להיראות כאילו הוא מתפלג באופן אחיד, במובן שהוסבר לעיל. כאשר "משתמשים" במחולל הזה, מניחים שיש מקור של אקראיות "אמיתית" שמספק למחולל הפסאודו אקראי את הקלט הקצר - כאמור, בעולם האמיתי אפשר להשתמש בהתקנים פיזיקליים, בשעון המחשב ובדברים דומים לשם כך. מה שחשוב במחולל הפסאודו אקראי הוא ה"ניפוח" שהוא יוצר. איך זה מתקשר למחוללים אמיתיים, שכל הפלטים שהם מוציאים הם מאותו אורך כמו הגרעין הנוכחי? פשוט מאוד - אנחנו חושבים על הפלט הארוך של המחולל הפסאודו אקראי התיאורטי בתור כל הסדרה האקראית שנוצרת מהגרעין, עד שהיא מתחילה לחזור על עצמה. כלומר, גם על מחוללים "אמיתיים" ניתן לחשוב כעל יצורים שמבצעים "ניפוח" של קלט אקראי קצר.
בואו ניקח דוגמה ממש אווילית. נניח שאני מעביר למחולל קלט בן סיבית אחת - או 0, או 1. נניח שעל 0 הוא מחזיר 11 ועל 1 הוא מחזיר 01. זה אומר שיש לו בדיוק שני פלטים אפשריים מגודל 2, ובפרט שהפלט 00, למשל, לא יופיע אף פעם. זו הבעיה הבסיסית של מחולל פסאודו אקראי - מכיוון שהוא מבצע “ניפוח”, ולכל קלט אפשרי יש פלט אפשרי יחיד, הוא לא יכול לכסות את כל מרחב הפלטים האפשריים, ולכן אף פעם לא ייראה אקראי "לגמרי". תמיד אפשר יהיה להריץ אותו על כל הקלטים האפשריים ולראות איזה ערך של פלט אף פעם לא יכול להתקבל, ואז להשתמש בכך כדי להראות שההתפלגות של המחולל היא לא אחידה "באמת" כי היא פוסחת על ערכים. על כן, מעמידים את המחולל במבחן רק עבור ערכים גדולים מספיק של קלט שעבורם לא ניתן לבצע חיפוש ממצה על כל מרחב הקלטים (ההגדרות הפורמליות קצת יותר עדינות ומחוכמות, כמובן; אבל יהיה קשה להסביר אותן כאן בלי הכנה מוקדמת נוספת).
אחת התוצאות המדהימות הראשונות הנוגעות למחוללים פסאודו אקראיים היא שדי במחולל שכל מה שהוא עושה הוא לנפח את הקלט בביט אחד (כלומר, אם הוא מקבל n ביטים כקלט, הוא מוציא n+1 ביטים כפלט - ביטים שיכולים להיראות שונים לגמרי מהקלט שהתקבל) כדי שניתן יהיה לבנות מחולל עם ניפוח פולינומי כלשהו (נניח, מוציא פלט שגדול פי 5 מהקלט). התוצאה הזו מצמצמת מאוד את ה”אתגר” שבבניית מחולל פסאודו אקראי - כל מה שצריך הוא ניפוח שמגדיל בביט אחד. עם זאת, זה לא עזר - עד היום לא ידוע ולו על מחולל פסאודו אקראי אחד. כמובן, קיימים מחוללים רבים שבהם משתמשים בפועל, גם ביישומים קריפטוגרפיים רגישים; אבל אין הוכחה לכך שהם אכן עונים על ההגדרה הפורמלית, ולכן שאלת קיומו של מחולל פסאודו אקראי נותרה בגדר תעלומה.
כעת אני רוצה להציג שימוש קריפטוגרפי בסיסי של מחוללים פסאודו אקראיים - להצפנה "יעילה". השימוש הזה נחמד, כי הוא מדגים היטב עד כמה חזק הוא היצור הזה. מיותר לציין שהשימוש הזה הוא לא סוף הדרך - מחולל פסאודו אקראי הוא אבן בניין בסיסית שממנו ניתן לבנות יצורים קריפטוגרפיים חשובים אחרים, אך לא אכנס לכל זה כעת.
אם כן, אנו עוסקים בהצפנה באמצעות מפתח סימטרי (כזה שצריך להיות ידוע לשני הצדדים) ושבה התוקף יכול לגלות רק את כתב הסתר (לאחר ההצפנה) והוא רוצה לפענח ממנו את התוכן. אנחנו מניחים כי התוקף מוגבל מבחינה חישובית ויכול לבצע רק חישובים יעילים (אחרת כל מה שנציג הולך לעזאזל). יש הגדרה פורמלית מדוייקת ל"בטיחות" בהינתן המגבלה הזו על התוקף, אבל היא מסובכת יחסית ואין בה צורך.
כמובן, אלו מכם ששמעו קצת על קריפטוגרפיה בוודאי יודעים שיש שיטת הצפנה בטוחה "באופן מושלם" - הצפנה באמצעות פנקס חד־פעמי. הבעיה עם הפנקס החד־פעמי היא שהוא מאוד בזבזני - כל ביט של המפתח מתבזבז על ביט של ההודעה, וזהו. בהצפנות אולטרה־קריטיות זה מחיר סביר, אבל בחיי היום־יום שלנו אנחנו מעדיפים להחזיק מפתח קטן, קבוע, ולהשתמש בו כדי להצפין כמה הודעות שרק נרצה. זה בדיוק מה שמחולל פסאודו אקראי מאפשר לנו לעשות. הרעיון הוא פשוט להחריד - ניקח מפתח קטן אקראי; נשתמש במחולל כדי "לנפח" אותו לכל אורך פולינומי שנרצה (ההנחה היא שלא נוכל לשלוח יותר ממספר הודעות פולינומי בימי חיינו), ואז נשתמש בפלט בתור "פנקס חד פעמי" - כל הודעה שלנו תוצפן עם חלק מהפלט שטרם השתמשנו בו. זה הכל.
למה זה עובד? שוב, מבלי להוכיח פורמלית אלא רק לתת נימוק על קצה המזלג - אם היה אפשר לשבור את ההצפנה הזו בצורה יותר מוצלחת מאשר אפשר היה לשבור הצפנה שבה המפתח מוגרל לכל הודעה בנפרד (להבדיל מכך שהוא נוצר על ידי מחולל פסאודו אקראי), הרי שזה היה מספק לנו "מבחין" עבור המחולל הפסאודו אקראי. נניח שיש אלגוריתם ששובר את ההצפנה - איך היה פועל המבחין שנובע ממנו? בערך - ממש בערך - הוא היה מצפין משהו בעזרת ה-x האקראי שהוא קיבל, נותן לאלגוריתם ש"שובר" את ההצפנה לעבוד, ואם האלגוריתם הצליח ובאמת שבר את ההצפנה, פולט 1. אחרת, הוא פולט 0. אם באמת השימוש במחולל פסאודו אקראי "החליש" את ההצפנה, אנחנו מצפים שבאופן משמעותי, המבחין שלנו יפלוט 1 בהסתברות גבוהה יותר אם מזינים לו ערכים מהמחולל הפסאודו אקראי, מאשר אם מזינים לו ערכים אקראיים "אמיתיים".
האם קיים משהו דומה בפועל? כמובן. כל צפני השטף פועלים באופן דומה - בונים סדרה פסאודו אקראית של מספרים, ומשתמשים בהם להצפנה בסגנון פנקס חד־פעמי. אין הוכחה פורמלית שזה עובד טוב, אבל כשעושים את זה נכון זה עובד מצויין, כל עוד מי שמשתמש בצופן לא מבצע שגיאות מזעזעות בפרוטוקול שנבנה מעליו. זה כמובן נושא למאמר נפרד.
|
קישורים
P שונה מ-NP - "עניין של זמן", על מגבלות המחשב לפתור בעיות בזמן. מאמרו של גדי אלכסנדרוביץ'
מה לא יכול המחשב לעשות - מאמרו של גדי אלכסנדרוביץ'
xkcd קומיקס על מתמטיקה ורומנטיקה
שגיאות מזעזעות באלגוריתם ההצפנה WEP
לא מדויק - הבלוג של גדי אלכסנדרוביץ'
|
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש