פונקציה פסבדו-אקראית קריפטוגרפית

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

נביט על כלל הפונקציות מתחום בגודל n ביטים, לטווח של ביט יחיד, כלומר f: n \to 1. קיימות 2^{2^n} פונקציות כאלו. משפחת פונקציות פסבדו-אקראיות הינה קבוצה של 2^n פונקציות כאלו בלבד, שלא ניתן להבדיל ביניהם לבין משפחת "כלל הפונקציות", למרות גודלה הקטן, יחסית, של הקבוצה.

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

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

תהי F= \{ f_1 , \ldots, f_{I} \}, משפחה של פונקציות f_{i\in 1,..,I}:n\to 1, ותהי U קבוצת כלל הפונקציות מ-n ביטים לביט בודד. הקבוצה F תיקרא משפחת פונקציות פסבדו אקראית אם לכל מכונת טיורינג הסתברותית A, ולכל c>0 מתקיים עבור n גדול דיו

\left | \Pr_{f\in F}[A(f)=1]-\Pr_{u\in U}[A(u)=1]\right | < \frac{1}{n^c}

האינדקס i נקרא גרעין האקראיות (seed)‏ והוא משמש לבחירת הפונקציה הספציפית מתוך המשפחה הפסבדו-אקראית. ניתן להרחיב את מושג הפונקציה הפסבדו-אקראית לפונקציות בעלות טווח גדול יותר, למשל f:n\to n, או באופן כללי f:n\to p(n) לכל פולינום p(\cdot).

תמורה (פרמוטציה) פסבדו-אקראית[עריכת קוד מקור | עריכה]

באופן שקול, ניתן להגדיר משפחה של תמורות פסבדו אקראיות. במקרה זה קיימות שתי דרישות נוספות:

  1. הפונציה f נדרשת להיות f:n\to n
  2. הפונקציה נדרשת להיות פרמוטציה.

בהגדרה זו, הקבוצה U הינה קבוצת כלל הפרמוטציות בגודל n (קיימות n! פונקציות כאלו).

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

בשנת 1986 הראו צוות חוקרים כיצד ניתן לבנות פונקציה פסבדו-אקראית f:n\to k אם נתון מחולל פסבדו אקראי G כך שהפלט של המחולל G הינו באורך כפול מגרעין האקראיות (seed) המוזן למחולל.[1] הרעיון העומד מאחורי הבניה הוא להפעיל את המחולל שוב ושוב - בכל הפעלה כזו יתקבל פלט הארוך פי שניים מהקלט אל המחולל. חוזרים על הפעולה עד אשר מתקבל פלט באורך k2^n. כעת ניתן לחלק את פלט המחולל ל2^n חלקים שווים, כל אחד באורך k. פלט הפונקציה הפסבדו אקראית f(x) הינו החלק שמספרו הסידורי הוא x. מכיוון שקיימים לכל היותר 2^n ערכי x אפשריים, הרי שהפונקציה הפסבדו-אקראית מוגדרת היטב. במידה וההפעלה החוזרת של המחולל מבוצעת בצורה יעילה (במבנה של עץ) מתקבל כי בנייה זו אפשרית בזמן פולינומי.

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

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

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

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

על מנת להצפין את ההודעה m, מגרילים מספר כלשהו i ושולחים את המידע ENC_k(m)=(i, f_k(i) \oplus m).

מפתח ההצפנה k קובע את הפונקציה f_k(\cdot) הספציפית בה עושים שימוש, מבין כלל הפונקציות במשפחה F.

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

בשנת 1985 הציעו מיכאל לובי וצ'ארלס ראקוף שיטה[2] בה ניתן להשתמש בפונקציה פסבדו-אקראית על מנת לבנות צופן בלוקים הבטוח כנגד התקפת גלוי נבחר (Chosen Plaintext Attack). השיטה מבוססת על מבנה פייסטל תלת-שלבי. באופן מפתיע, מבנה דומה בעל 2 שלבים בלבד אינו מספיק על-מנת ליצור סכמה בטוחה.

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

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

  1. ^ 1.0 1.1 עודד גולדרייך, שפי גולדווסר וסילביו מיקאלי, How to construct pseudorandom functions
  2. ^ Michael Luby, Charles Rackoff. "How to construct pseudo-random permutations from pseudo-random functions", 1985. [1] [2]