מחולל מספרים פסאודו-אקראיים קריפטוגרפי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Gnome-colors-edit-find-replace.svg יש לשכתב ערך זה. הסיבה לכך היא: מכיל פסקאות שלמות לא נכונות ולא ברורות.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.

מחולל מספרים פסאודו-אקראיים בטוח קריפטוגרפית Cryptographically secure pseudorandom number generator בקיצור CSPRNG, הוא מחולל מספרים פסאודו-אקראיים בעל תכונות המתאימות במיוחד לצורך קריפטוגרפי. תפקיד מחולל פסאודו אקראי מהווה מרכיב חיוני ובלתי נפרד בתהליכי אבטחת מידע - יצירת רצף מספרים (או סיביות) באורך רצוי בעל תכונות אקראיות ואנטרופיה גבוהים. למעשה אין המחולל מייצר מספרים אקראיים אמיתיים אלא באמצעות אלגוריתם מקבל מחרוזת אקראית אמיתית קצרה ו"מותח" אותה למחרוזת פסאודו אקראית באורך הרצוי בעלת אנטרופיה כזו שבהינתן קטע מהמחרוזת לא יצליח יריב בעל כח חישוב פולינומי לחשב או לחלץ סיביות אחרות מהמחרוזת ללא ידיעת הגרעין (seed) ההתחלתי. משמעות הדבר שלא ניתן להבחין תוך שימוש בכח חישוב פולינומי, בין תוצאת המחולל לבין מחרוזת אקראית אמיתית.

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

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

  • ערכים ייחודיים (Unique)
  • ערכים חד פעמיים (Nonce)
  • ניפוח וריפוד (Padding)
  • מפתחות הצפנה (Keys)


אנטרופיה[עריכת קוד מקור | עריכה]

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

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

דרישות בטיחות[עריכת קוד מקור | עריכה]

נניח שהמחולל מותח גרעין התחלתי באורך k סיביות למחרוזת באורך l סיביות. מספר הרצפים הבינאריים האפשריים של המחולל הוא לכל היותר \ 2^k/2^l מתוך כל הרצפים הבינאריים האפשריים באורך \ l. למרות שהמחולל מסוגל לייצר רק קבוצה "קטנה" מתוך כלל 2^l המחרוזות האפשריות, עדיין לא ניתן להבחין בין פלט של המחולל ומחרוזת אקראית לחלוטין באורך l. נאמר שרצף פסאודו-אקראי לא ניתן להבדלה פולינומית ממחרוזת אקראית, אם לא קיים אלגוריתם שמוצא הבדל כלשהו בין הפלט הפסאודו-אקראי לבין רצף אקראי אמיתי בזמן פולינומי, בהסתברות שאינה זניחה.

הגדרה[עריכת קוד מקור | עריכה]

מחולל מספרים פסאודו-אקראיים קריפטוגרפי הוא אלגוריתם דטרמיניסטי (לייתר דיוק: משפחה של אלגוריתמים) G: \{0,1\}^k \to \{0,1\}^l כך שמתקיים:

  1. האורך l חסום פולינומית ב־k, כלומר קיים פולינום p כך ש־l=p(k).
  2. זמן הריצה של G פולינומי ב־k
  3. פלט המחולל לא ניתן להבחנה (ע״י יריב פולינומי) ממחרוזת אקראית:
    לכל אלגוריתם A בעל זמן ריצה פולינומי ב־k ולכל קבוע c>0, עבור k גדול דיו מתקיים
\left | \Pr_{\text{seed} \ \in_R \ \{0,1\}^k} [A(G(\text{seed}))=1] - \Pr_{z\ \in_R \ \{0,1\}^l} [A(z)=1]\right | < \frac{1}{k^c}
כאשר הסימון x \in_R X משמעותו ש־x נבחר אקראית (בהתפלגות אחידה) מתוך הקבוצה X.


הגדרות בטיחות שקולות[עריכת קוד מקור | עריכה]

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

מחולל קריפטוגרפי חייב לעמוד בבדיקת ה"סיבית הבאה" כדלהלן: בהינתן k הסיביות הראשונות שהמחולל הפיק, לא קיים אלגוריתם שמאפשר לנחש בזמן פולינומי את הסיבית k+1, בסיכויי הצלחה גבוהים מחצי. אנדרו יאו הוכיח ב-1982 שאלגוריתם שעובר בהצלחה את בדיקת הסיבית הבאה, יעבור בהצלחה את כל מבחני האקראיות הסטטיסטיים פולינומיים (כלומר, זו הגדרה שקולה להגדרה לעיל).

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

אקראיות לעומת אי-צפיות[עריכת קוד מקור | עריכה]

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

מיקלוס סנטה ואומש וזיראני ‏‏[1] הראו שאפשר לשלב מספר מחרוזות סיביות בעלות אקראיות 'חלשה' יחדיו כדי להפיק מחרוזת 'מעין' אקראית באיכות יותר גבוהה. ג'ון פון ניומן הוכיח‏‏[2] שאפשר באמצעות אלגוריתם פשוט להסיר באופן משמעותי הטיה (bias) סטטיסטית ממחרוזת אקראית ולשפר בכך את איכותה. הנושא נמצא תחת מחקר והוא נקרא "חילוץ אנטרופיה".

אלגוריתמים[עריכת קוד מקור | עריכה]

מחוללים קריפטוגרפיים מתחלקים לשלושה סוגים עקריים:

מחולל מבוסס צופן סימטרי[עריכת קוד מקור | עריכה]

צופן סימטרי בטוח יכול לשמש בתור מחולל קריפטוגרפי (CSPRNG) על ידי הרצתו במצב מונה (Counter mode). דהיינו בוחרים מפתח הצפנה אקראי ומצפינים באמצעותו את המספרים \ 0,1,2,3... בסדר רץ. אפשר להתחיל במספר שרירותי אחר שונה מאפס. כמובן שמחזוריות המחולל תהיה במקרה כזה \ 2^n סיביות עבור צופן גושים בגודל \ n סיביות. כמו כן המצב ההתחלתי דהיינו מפתח ההצפנה במקרה זה חייב להישמר בסוד, אחרת ככל שיהיה הצופן חזק לא יהיה המחולל בטוח כלל משום שעם מפתח ההצפנה ניתן יהיה לשחזר כל רצף שהמחולל ייצר. גם פונקציית גיבוב קריפטוגרפית המופעלת על מונה יכולה לשמש כמחולל קריפטוגרפי לא רע, במקרה זה ערכו ההתחלתי של המונה חייב להיות סודי ואקראי. ייתכן שאם ערכו ההתחלתי של המונה גדול אפשר יהיה להפיק רצף אקראי בעל מחזוריות עצומה. יש מומחים שמזהירים מפני יישום פונקציית גיבוב כמחולל אקראי מאחר שהנושא לא נחקר דיו.

מחולל מבוסס צופן זרם[עריכת קוד מקור | עריכה]

רוב צופני הזרם פועלים עם מחולל מספרים פסאודו-אקראיים מובנה המייצר מחרוזת סיביות אקראית המשמשת כמפתח הצפנה, אותה משלבים (בדרך כלל באמצעות XOR) עם מחרוזת הטקסט הקריא לקבלת טקסט מוצפן. אם מריצים צופן זרם מסוג כזה ומצפינים מספר רץ מקבלים למעשה מחרוזת אקראית חדשה עם מחזוריות גבוהה יותר. הדבר נכון רק אם המחרוזת המקורית בעלת אקראיות באיכות גבוהה, מה שלא תמיד נכון (ראה RC4). מחולל קריפטוגרפי אחד מסוג זה נכלל בתקן ANSI X9.17 ואף אומץ כתקן FIPS על ידי הממשל האמריקאי. המחולל פועל כדלהלן:

קלט: גרעין התחלתי \ s בגודל 64 סיביות, ומפתח הצפנה \ k של DES-משולש. ו-\ D המייצג את הזמן הנוכחי בשעון המערכת ברזולוציה הגבוהה ביותר האפשרית. כאשר נדרש רצף אקראי:

  • מחשבים את \ I=\mbox{DES}_k(D)
  • הפלט יהיה: \ x=\mbox{DES}_k(I \oplus s)
  • מעדכנים את הגרעין \ s בערך \ \mbox{DES}_k(x \oplus I)

אפשר לשפר את האלגוריתם המתואר באמצעות שימוש בצופן סימטרי אחר טוב יותר כמו AES.

מחולל מבוסס הצפנה אסימטרית[עריכת קוד מקור | עריכה]

אלגוריתם Blum Blum Shub הוא מחולל מספרים פסאודו-אקראיים עם מאפייני בטיחות חזקים, המבוסס על הקושי שבפירוק מספרים לגורמים. בטיחותו מותנת בהשערה כי בעיית פירוק לגורמים קשה ויעילותו נמוכה ממרבית המחוללים האחרים. המחולל הומצא על ידי לינור ומנואל בלום ומייקל שב ב-1986 ותיאורו פשוט. הסיבית הבאה של המחולל מחושבת על ידי:

\ x_{n+1}=x^2_n\mbox{ mod }m

כאשר \ m=pq, כפולה של שני ראשוניים גדולים, שווים בגודלם בקירוב השקולים ל-3 מודולו 4. המספר x_0 הוא הגרעין, והוא נדרש להיות שונה מ־1 וזר ל־m. בכל שלב הסיבית הנמוכה של \ x_n מהווה חלק מהרצף האקראי. אפשר לשפר את יעילות האלגוריתם על ידי חילוץ \ c \log \log x_n סיביות נמוכות של \ x_n (הערך \ c קבוע קטן לא מוגדר). הסיבה שהראשוניים \ p ו-\ q צריכים להיות שקולים ל-3 מודולו 4 היא להבטיח שלכל שארית ריבועית של \ x_n יש רק שורש ריבועי אחד שגם הוא שארית ריבועית. כמו כן כדי לקבל מחזוריות גבוהה רצוי ש-\ \mbox{gcd}(\phi(p-1),\phi(q-1)) יהיה קטן.

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

מחוללים ייעודיים[עריכת קוד מקור | עריכה]

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

אלגוריתם Yarrow[עריכת קוד מקור | עריכה]

מקור שמו של האלגוריתם הוא פרח שמקורו בסין שהגבעול שלו שימש את הסינים בעת העתיקה לצורך נבואות. האלגוריתם פותח על ידי ברוס שנייר, נילס פרגוסון וג'ון קלסי מחברת Counterpane. אלגוריתם Yarrow מנצל פרימיטיבים קריפטוגרפיים קיימים ומורכב מארבעה רכיבים עצמאיים; אוגר אנטרופיה שתפקידו לאסוף נתונים אקראיים שונים ביניהם קלט משתמש ונתוני מערכת שונים לתוך מאגרים מיוחדים (pools). מנגנון גירעון שמחליף מעת לעת את מפתח ההצפנה של המחולל באמצעות אנטרופיה חדשה. מנגנון חילול שמייצר פלט אקראי באמצעות מפתח ההצפנה עם אלגוריתם 3DES במצב מונה (Counter mode) ופונקציית גיבוב SHA-1 וכן מנגנון בקרת גרעון שאמור לקבוע מתי יש צורך לחדש אנטרופיה כדי למנוע מתוקף לנחש את מצבו הפנימי של המחולל. האלגוריתם מכיל ליתר דיוק שני מאגרים בגודל 160 סיביות כל אחד, הנקראים "מאגר איטי" ו"מאגר מהיר" המתאימים לפלט SHA-160. המאגר המהיר מרענן את המחולל באנטרופיה חדשה בתדירות כזו שאם מפתח הצפנה אחד נחשף, פרק הזמן של החשיפה יהיה קצר ככל האפשר. המאגר האיטי מבצע רענון יסודי אחת לפרק זמן ארוך ליתר ביטחון. כמו כן האלגוריתם מכיל מנגון פנימי להערכת אנטרופיה. האלגוריתם שולב במערכת ההפעלה Mac OS X

על בסיס Yarrow פותח אלגוריתם משופר ומתקדם יותר Fortuna שאינו מכיל רכיב הערכת אנטרופיה.

dev/random[עריכת קוד מקור | עריכה]

המחולל dev/random נכלל במערכת ההפעלה UNIX ליצירת מספרים אקראיים המתאימים לצורך קריפטוגרפי. האלגוריתם מורכב משלושה תהליכים א-סינכרוניים. בתהליך הראשון נאספים נתוני ליבה (kernel) מתוך אירועים כמו מקלדת, עכבר, כונן קשיח ופסיקות. נתונים אילו מהווים את האנטרופיה הבסיסית של המחולל. בתהליך השני הנתונים מועברים למאגר בגודל 512 בתים דמוי LFSR באמצעות פונקציות ערבוב כלשהי. המצב הפנימי של המחולל נשמר בשני מאגרים נוספים כאשר חלק מהסיביות מוחזרות למאגרים לאחר גיבוב. כאשר יש צורך במספר אקראי התהליך השלישי נכנס לפעולה ומעביר את הרצף הגולמי המופק מהמאגר דרך פונקציית גיבוב SHA-1 ואז מופק פלט אקראי. בגרסאות קודמות של המחולל התגלו ליקויים שנבעו מאופן הניצול של האנטרופיה מהמערכת.

הפונקציה CryptGenRandom[עריכת קוד מקור | עריכה]

מערכות ההפעלה של מיקרוסופט כוללות את אלגוריתם CryptoGenRandom המובנה בתשתית API קריפטוגרפית הנקראת CSP (קיצור של Cryptographic Service Provider. האלגוריתם פועל על עיקרון דומה; תחילה מופק גרעין אקראי אמיתי, שנשמר בנפרד עבור כל יישום המשתמש במחולל. הגרעין נאסף ממקורות שונים במערכת; נתוני תזמון של קלט מקלדת ועכבר של המשתמש המעורבבים יחד עם מקבץ של נתוני מערכת; Process ID, Thread ID, שעון מערכת, זמן, מונה מערכת, מצב זיכרון, אשכולות פנויים בכונן הקשיח וגיבוב של בלוק סביבת המשתמש. כל זה מועבר בפונקציית גיבוב SHA-1 והפלט משמש כמפתח לצופן RC4. פלט הצופן משמש בחלקו לעדכון הגרעין. המערכת מאפשרת למשתמש להזין נתונים לתוך החוצץ האקראי לפני קריאה לפונקציה.

אלגוריתם ISSAC[עריכת קוד מקור | עריכה]

ISAAC פותח על ידי רוברט ג'נקינס ב-1996 ושמו הוא קיצור של Indirection, Shift, Accumulate, Add, Count. זהו למעשה צופן זרם שעוצב במיוחד לשמש כמחולל מספרים פסאודו-אקראיים קריפטוגרפי. האלגוריתם מבוסס על ואריאציה של צופן זרם RC4, הוא משתמש במערך של 256 כניסות כל אחת בגודל 32 סיביות. ומשתמש בשלושה פרמטרים שערכיהם הראשוניים קבועים ואינם סודיים; a - אוגר אנטרופיה, b - זוכר את המספר האקראי הקודם ו-c - מונה. האלגוריתם בונה מערך עזר נוסף בגודל זהה ומזין אותו בערכים אקראיים בהתאם לפרמטרים a,b,c בשילוב פעולות XOR, הזזה (SHIFT) וחיבור מודולו 32 סיביות. התוצאה היא מערך של מספרים אקראיים שכאשר מנוצל עד תום, חוזרים על פעולת האלגוריתם.

למרות שהתגלתה התקפה על האלגוריתם שיעילה מחיפוש השורש הריבועי של כל הערכים ההתחלתיים האפשריים בסיבוכיות של \ 4.67 \times 10^{1024}, האלגוריתם עדיין בטוח לשימוש מבחינה מעשית. בנוסף התגלו מספר גדול של ערכים התחלתיים "חלשים" במובן שבהינתן ערכים אילו האלגוריתם מייצר מספרים אקראיים עם הטייה.

תקנים[עריכת קוד מקור | עריכה]

תקנים למחוללי מספרים פסאודו-אקראיים (PRNG):

  • תקן FIPS 186-2
  • NIST SP 800-90
  • ANSI X9.17-1985
  • ANSI X9.62-2005

תקנים לבדיקות סטטיסטיות: ערכת בדיקה סטטיסטית של NIST גרסה 800-22

מקורות[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Generating Quasi-Random Sequences from Slightly-Random Sources. Miklos Santha, Umesh V. Vazirani University of California Berkeley, CA 94720.‏
  2. ^ ‏J. von Neumann: "Various techniques used in connection with random digits" National Bureau of Standards Applied Mathematics Series 12 (1951), 36-38.‏