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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

Postscript-viewer-shaded.png ערך מורחב – תמורה פסאודו-אקראית

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

  1. הפונציה נדרשת להיות
  2. הפונקציה נדרשת להיות פרמוטציה.

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

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

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

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

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

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

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

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

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

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

בשנת 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]