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

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

פונקציה פסאודו-אקראית בקיצור PRF בקריפטוגרפיה, היא כינוי למשפחה של פונקציות המדמות אורקל ראנדומלי באופן שלא קיים אלגוריתם יעיל שיכול להבחין עם יתרון משמעותי, בין פונקציה שנבחרה ממשפחה זו לבין אורקל אקראי אמיתי. אורקל אקראי הוא מעין קופסה שחורה, פונקציה F\to \{0,1\}^n המחזירה תמיד, ללא תלות בקלט מחרוזת אקראית לגמרי מתוך תחום הפונקציה. לפונקציה פסאודו-אקראית חשיבות רבה בקריפטוגרפיה והיא מאבני הבניין של ההצפנה מודרנית, באמצעותה ניתן לבנות פרימיטיבים קריפטוגרפיים וסכמות הצפנה בטוחות. אפשר לבנות פונקציה כזו באמצעות מחולל פסבדו אקראי קריפטוגרפי[1] או אלגוריתם הצפנה סימטרי בטוח כמו AES.

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

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

לכל n, מספר הפונקציות המקבלות כקלט מלה בת n סיביות ומחזירות סיבית בודדת הוא 2^{2^n}. משפחת הפונקציות הפסאודו-אקראיות מאכלסת רק תת-קבוצה קטנה מתוך התחום, שהיא 2^n פונקציות אפשריות בלבד

Ambox blue question.svg
שלום לך,
בוויקיפדיה אנו נדרשים לערוך אך ורק עריכות מבוססות, והשינוי שביצעת בדף ההגדרה אינה חלה על פונקציה בודדת אינו עומד בסטנדרטים אלה.
אודה לך אם תסביר/י מדוע בוצע שינוי זה ועל סמך מה.

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

נחשוב על הניסוי הבא: נניח שקיים אלגוריתם פולינומי 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).

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

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

  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]