תעתועי האקראיות

(אני לא הולך לעסוק בספר המעניין והמומלץ של נאסים טאלב שנקרא בשם זה, אלא בשימוש במספרים אקראיים בתוכנה)

ברוב שפות התכנות יש אפשרות לבקש מהסביבה 'להגריל' עבורנו מספר אקראי. היכולת להגריל מספרים אקראיים היא חשובה במגוון גדול של יישומים החל במשחקים, דרך סימולציות מדעיות ועד להצפנה ואבטחה. כשחושבים על זה, היכולת לבקש תוצאה רנדומלית ממחשב שהוא מכונה דטרמיניסטית היא דבר לא טריוויאלי. בפוסט נכיר כמה מושגים בתחום עם דוגמאות ופרקטיקות בשפת ג'אווה.

ראנדומליות א-פורמלית ואלגוריתמים פסוודו רנדומאליים

השאלה הראשונה היא מהן הדרישות שלנו מתוכנה שמייצרת מספרים אקראיים. התנאים הבסיסיים ביותר הם:

  • התפלגות אחידה של התוצאות על פני הטווח שמתוכו בוחרים
  • חוסר יכולת לצפות (במאמץ סביר) את המספר הבא שיוגרל על ידי צפייה במספר תוצאות שהוגרלו

את הדרישות האלה ניתן לספק בעזרת מה שנקרא אלגוריתם פסוודו רנדומלי (PRNG). זהו אלגוריתם שמבוסס על פעולה אריתמטית שקולטת מספר, "מערבלת" אותו ופולטת מספר אחר באופן שקשה לשחזר את הקלט. אם נבצע מספר איטרציות שבכל אחת הקלט הוא הפלט מהשלב הקודם נקבל רצף של מספרים שעונה על הדרישות לאקראיות שהגדרנו. יש מספר אלגוריתמים כאלה ומאחר שנכתב על זה רבות, גם בעברית, אני לא הולך להרחיב. העניין שחשוב להבין הוא שאקראיות כזו נקראת א-פורמלית מכיוון שאם נשחזר את הצעדים שעשינו (כולל שימוש באותו 'זרע' כלומר הקלט של האיטרציה הראשונה) נקבל את אותו רצף בדיוק.

Random random = new Random(12345);

System.out.println(random.nextLong());//same every time

ניתן לשפר את זה מעט על ידי שימוש בקלט ראשוני שונה בכל פעם. השיטה הנאיבית ביותר היא להשתמש בשעון

Random random = new Random(System.currentTimeMillis());

ולמעשה גם אם נבנה את Random ללא ארגומנטים (דרך הבנאי הדיפולטיבי) זה בדיוק מה שיקרה. זה אומנם מבטיח רצף שונה בכל פעם, אבל עדיין נחשב בגדר רנדומליות א-פורמלית.

ראנדומליות בעלת חוזק הצפנה

דרגה גבוהה יותר של רנדומליות נקראת רנדומליות בעלת חוזק הצפנה (CSPRNG). בדרגה זו מצטרפת הגדרה נוספת לקריטריון והיא שגם אם למישהו יש ידע מלא על אופן יצירת המחולל הרנדומלי הוא עדיין לא יוכל לשחזר את סדרת המספרים. אחת הדרכים לעשות זאת היא קבלת נתונים אקראיים אמיתיים מבחוץ (נתוני אנטרופיה) ואז שימוש בהם כקלט ראשוני של מחולל פסוודו רנדומלי. דבר זה מבטיח להקשות על שחזור הסידרה, שכן נתוני האנטרופיה יהיו שונים בכל פעם. הדרך לעשות זאת בג'אווה היא להשתמש במחלקה SecureRandom. מחלקה זו מאתחלת את המחולל בעזרת נתוני אנטרופיה שמתקבלים מהתקן של מערכת ההפעלה (נגזרים ממהירות ההקלדה והעכבר, העומס על המעבד, המרחק שעבר הדיסק וכו'). ישנן כמה שיטות לעשות זאת וזה כמובן תלוי סביבת ריצה (למשל בלינוקס ברירת המחדל היא קריאה מההתקן dev/random/ בעוד שבחלונות נעשה שימוש בCryptoAPI של מיקרוסופט), בכל מקרה ניתן לשלוט על הקונפיגורציה של זה דרך הקובץ java.security בספרית ההתקנה של ג'אווה.

אורך המחזור

מושג נוסף שחשוב להכיר נקרא מחזור. אם נסתכל שוב על מה שכתוב בנושא מחולל פסוודו רנדומלי, נגלה שלא ניתן להתחמק ממחזוריות. זה נובע מכך שבשלב מסוים נקבל כתוצאה את המספר בו השתמשנו בתור 'זרע' ומכאן הסידרה תתחיל לחזור על עצמה. אחת הדרישות מאלגוריתם רנדומלי טוב היא מחזור ארוך ללא תלות בזרע (בניגוד לאלגוריתמים רגישים שעבור זרעים מסויימים יפיקו סידרה בעלת מחזור קצר) אבל המחזוריות תמיד תהיה שם. זו אחת הסיבות שבאפליקציות מומלץ לאתחל את המחולל מחדש בתנאים מסוימים, וכך להימנע מחזרות.

לשמור על פרופורציות

לפעמים אנחנו לא צריכים את כל טווח התוצאות, אלא מעוניינים בטווח קטן יותר. לדוגמא, אנחנו רוצים לדמות תוצאה של סיבוב רולטה. הנטייה במקרים כאלה עלולה להיות ביצוע פעולת מודולו על התוצאה. פעולה כזו יוצרת סטייה קטנה מהתפלגות אחידה. למשל, אם המחולל שלנו בוחר מספרים בין 1 ל 100 ואנו מבצעים מודולו 36, הרי שלמספר 1 יש 3 הזדמנויות להופיע בעוד שלמספר 35 יש רק שתיים (הבדל של 50% ! ). כמובן שהסטייה הזו קטנה עם היחס בין הטווח הרצוי לנו לטווח הכללי, אבל באופן כללי עדיף להשתמש בשיטות שלא יוצרות את העיוות הזה (למשל לחלק ב100 ולהכפיל ב36). כדי לא לייצר עיוותים צריך פשוט להשתמש במטודה המתאימה

//use this instead of mod

rand.nextInt(36);

ומשהו קטן לקינוח

כמו שראינו יש קשרים בין עולם ההצפנה והאבטחה לעולם של מחוללי מספרים אקראיים. יש תוכנות מסוימות (למשל putty) שדורשות 'לקשקש' עם העכבר בזמן ההתקנה על מנת לאתחל את המחולל שלהן. לסיום הפוסט אני רוצה להאיר את הקשר הזה מזווית קצת אחרת.

אחת השיטות להצפנת מסרים היא שימוש בטבלת החלפה שמציינת עבור כל אות באיזו אות יש להחליף אותה. במציאות זו שיטה חלשה מאוד שכן ניתן לפצח את הצופן מהר תוך התבססות על שכיחות של אותיות במסרים מוצפנים לעומת השכיחות הצפויה במסרים לא מוצפנים באותה שפה.

שיטה הרבה יותר קשה לפיצוח תחליף את הצופן תוך כדי הקידוד. למשל, נחשוב על צופן שמורכב מ22 טבלאות החלפה כאלה. את האות הראשונה מחליפים לפי הלוח הראשון ואז מדלגים ללוח שתואם לאות שהחלפנו (כלומר אם המסר מתחיל באות 'ג' את האות השניה נחליף לפי לוח מספר שלוש וכן הלאה). זה יוצר הצפנה הרבה יותר חזקה שכן אין קוד קבוע אלא הוא משתנה לפי ההקשר. הצופן הזה יוצר רצפים שנראים אקראיים, אך למעשה אם אנחנו יודעים את האלגוריתם (הלוחות) ואת תנאי ההתחלה (הסדר שלהם) אנחנו יכולים לשחזר את הרצף – בדיוק כמו שראינו לגבי מחולל פסוודו אקראי!. העיקרון הזה דומה לעקרון לפיו עבדה אניגמה,  מכונת הצופן הגרמנית ממלחמת העולם השניה, שפוצחה בין היתר על ידי אלן טיורינג, אחד מאבות מדעי המחשב, במאמץ שלפי מספר דעות היה בעל השפעה מכרעת על תוצאות המלחמה. למי שקצת מתעניין בזה יש ספר מדע פופולארי נחמד בשם 'סודות ההצפנה' שעוסק בהיסטוריה של צפנים ופיצוח, ומסביר קצת על הרקע של התחום.

כתיבת תגובה

הזינו את פרטיכם בטופס, או לחצו על אחד מהאייקונים כדי להשתמש בחשבון קיים:

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s