מודל אורקל אקראי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 1:
ב[[קריפטואנליזה]], '''מודל אורקל אקראי''' (Random oracle model) הוא [[פרדיגמה]] לבניית [[פרוטוקול קריפטוגרפי]] עם ביטחון מוכח שהוצעה לראשונה ב-1995 על ידי [[מיהיר בלייר]] מ[[אוניברסיטת קליפורניה בסן דייגו]] ו[[פיליפ רוגווי]] מ[[אוניברסיטת קליפורניה בדייוויס]]{{הערה|[http://cseweb.ucsd.edu/~mihir/papers/ro.pdf Bellare, Mihir and Philip Rogaway (1993). “Random oracles are practical: A paradigm for designing efficient protocols.”]}}. מודל אורקל אקראי מהווה מעין ממוצע בין מצב שבו קיימת הוכחת ביטחון מוצקה לפי המודל הסטנדרטי לבין מצב שלא קיימת הוכחה כלל. בעוד שהמודל אינו משקף את המציאות לגמרי, לפחות הוא מספק ביטחון רב יותר באמינות הפרוטוקול על פי המודל, לעומת מצב שבו לא קיימת הוכחה כלשהי מעבר לעובדה שמפתחי האלגוריתם הצהירו כי לא מצאו שיטה טובה לשבירתו. או כפי שניסחו המחברים "מודל אורקל אקראי מהווה גשר בין קריפטוגרפיה תאורטית לבין קריפטוגרפיה מעשית".
==אורקל אקראי==
בקריפטוגרפיה מודרנית נוח להשתמש באובייקט תיאורתי הנקרא [[אורקל (מדעי המחשב)|אורקל]]. אפשר לחשוב עליו כעל [[קופסה שחורה (הנדסה)|קופסה שחורה]] שמקבלת כקלט מחרוזת בינארית ומחזירה מחרוזת בינארית. המבנה הפנימי של הקופסה "מסתורי" ואינו ידוע לאיש. כל אחד, כולל היריב רשאי להפעיל את הקופסה. הקופסה פועלת כפונקציה המקבלת את <math>x</math> ומחזירה את <math>y</math>. בהקשר זה <math>x</math> נקרא [[שאילתה (תוכנה)|שאילתה]]. למען הפשטות מבלי לוותר על הכלליות מניחים כמה הנחות יסוד לגבי האורקל:
*המבנה הפנימי של האורקל אינו ידוע לאיש. כל מה שידוע הוא שאילתות שהוגשו עד עתה והתשובות שהתקבלו.
*כל שאילתה שמוגשת לאורקל פרטית במובן שרק האורקל ומגיש השאילתה יודעים מהי. זו הנחה טבעית כי במציאות הגשת שאילתה לאורקל מתאימה להפעלת פונקציית גיבוב באופן מקומי.
*האורקל עיקבי. האורקל תמיד יחזיר את אותה תשובה <math>y</math> בהינתן אותה שאילתה <math>x</math>. כי למעשה רואים באורקל כביכול הוא מיישם פונקציה <math>H</math>. מסיבה זו אפשר להתייחס לאורקל כאל הפונקציה <math>H</math> עצמה.
*האורקל יקרא '''אורקל אקראי''' אם הפונקציה <math>H</math> נבחרה באקראי בהתפלגות אחידה מתוך כל הפונקציות <math>H(x)</math> הממפות <math>n</math> סיביות ל-<math>\ell(n)</math> סיביות, כאשר <math>x\in\{0,1\}^n</math> והפלט <math>H(x)\in\{0,1\}^{\ell(n)}</math>. בסך הכול קיימות <math>2^{\ell(n)\cdot 2^n}</math> פונקציות שונות עם קלט ופלט באורך המצויין.
==רעיון כללי==
מהיבט תיאורתי עדיף היה לפתח ולנתח פרוטוקול באופן כזה שניתן יהיה להוכיח לפי מודל סיבוכיות סטנדרטי (אסימפטוטי) שהוא אכן בטוח לשימוש בהתבסס על השערה מתמטית חזקה. אולם במציאות המצב הוא שפרוטוקול כזה נוטה להיות לא יעיל ולמרבה הצער מרבית המשתמשים נוטים לוותר על האבטחה כליל מאשר לסבול פרוטוקול שזמן ביצועו מתארך יתר על המידה וגורם לקפאון המחשב. לפי המודל הסטנדרטי כמעט לא קיימים פרוטוקולים קריפטוגרפיים מוכחים שהם גם יעילים. בעוד שקריפטוגרפים עמלים במרץ על פיתוח שיטות הצפנה בטוחות יותר, מפתחים תיאוריות ומספקים השערות חדשות ושיטות פיצוח חדשות, בה בעת נוצר מצב שבמציאות נשארים עם יותר שאלות מאשר תשובות לגבי מה בטוח ומה לא. לכן נאלצים להתפשר על שיטות [[אד הוק]] שמסתמכות בעיקר על גאונות ותחכום הממציא ושאין להם כל הוכחה מתמטית מפורשת באשר לטענות לגבי בטחונן.
רעיון מודל אורקל אקראי מנסה לגשר על הפער הזה על ידי תוספת
*תחילה שיטת ההצפנה מפותחת ומוכחת כבטוחה במסגרת מודל אורקל אקראי. כלומר מניחים שקיים אורקל אקראי מדומה ומנסים לבנות אלגוריתם בהתבסס על הנחה זו ומוכיחים שהוא בטוח מבחינה תאורטית. מבלי להוציא מהכלל הוכחות סטנדרטיות בדרך מקובלת כפי שנהוג.
*בשלב השני כאשר מנסים ליישם את הפרוטוקול בפועל כיוון שאורקל אקראי לא קיים במציאות מנסים להחליפו בפונקציית גיבוב מתאימה (למשל וריאציה של [[SHA-2]]). כך שבכל נקודה בפרוטוקול שבה מופיעה שאליתה לאורקל אקראי עם <math>x</math>, היא תוחלף בפונקציית הגיבוב <math>\hat H(x)</math>.
| |||