פונקציה חד-כיוונית

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

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

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

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

באופן פורמלי, פונקציה f(\cdot) תיקרא חד-כיוונית (במובן החזק) אם מתקיימים התנאים הבאים:

  1. f(\cdot) ניתנת לחישוב בזמן פולינומי
  2. לכל מכונת-טיורינג מטילת מטבעות  A ולכל קבוע c, עבור קלטים ארוכים מספיק x\in \{0,1\}^n, מתקיים, \Pr[ A(f(x)) = f^{-1}(f(x))] < \frac{1}{n^c}[1]
  3. קיימים קבועים c_1, c_2 כך ש n^{c_1} \le |f(x)| \le n^{c_2}

הסבר:
תנאי (1) קובע שהפונקציה "קלה לחישוב", כלומר בעלת סיבוכיות פולינומית. תנאי (3) קובע כי קיים קשר פולינומי בין אורך הקלט לאורך הפלט [למעשה, תנאי זה נובע משאר התנאים, אך מהווה תכונה חשובה של פונקציה חד-כיוונית]. תנאי (2) הינו עיקר ההגדרה, הקובע כי לכל יריב בעל כח חישוב פולינומי לכל היותר, הסיכוי שהיריב יצליח "להפוך" את הפונקציה הינו זניח. כלומר, אם ליריב ידוע f(x), הסיכוי שהיריב יימצא y כך שf(y)=f(x), הינו זניח. יש לשים לב כי ייתכן שישנם קלטים רבים אשר ממופים על ידי f לאותו ערך. על כן היריב נדרש למצוא אחד מהם y\in f^{-1}(f(x)) ולאו דווקא את הערך המקורי x.

באופן דומה ניתן להגדיר פרמוטציה חד כיוונית, בה תנאי (3) מוחלף בתנאי בו |f(x)|=n, והפונקציה נדרשת להיות חח"ע ועל.


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

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

ניתן להראות שקיומה של פונקציה חד-כיוונית במובן החלש מעיד על קיומה של פונקציה חד-כיוונית במובן החזק, כלומר, בעזרת פונקציה f שהינה חד-כיוונית במובן חלש, ניתן לבנות פונקציה F שהינה חד-כיוונית במובן החזק[דרוש מקור].

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

קיומן של פונקציות חד-כיווניות מחייב שקיימות בעיות חישוביות אשר שייכות ל-NP ואינן שייכות ל-BPP (מחלקת הבעיות אשר ניתנות לפתרון בזמן ריצה פולינומי עם אלגוריתמים אקראיים), מאחר שלא ידוע האם \ BPP = NP (שאלה מעט יותר חלשה, ומפורסמת יותר, היא האם P=NP), לא ניתן להצביע על קיומן של פונקציות כאלה. יתר על כן, ייתכן ש-\ P \neq NP, ובכל זאת לא יהיו קיימות פונקציות חד כיווניות. (כיוון שנדרש מהן שהיפוכן קשה במקרה הממוצע ולא רק במקרה הקשה)

קיום פונקציות חד-כיווניות הוא תנאי הכרחי לקיום רוב הפרימיטיבים בהצפנה.

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

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

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

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

הצפנה בשיטת מפתח ציבורי (Public Key Encryption), שמכונה גם הצפנה א-סימטרית, עושה שימוש בפונקציות חד-כיווניות מסוג מסוים, פונקציות מלכודת חד-כיווניות (Trapdoor one-way function). לפונקציות אלה התכונה שישנו מידע אשר ידוע רק לנמען המורשה של ההודעה (המפתח הפרטי) שבעזרתו קל לחשב את הפונקציה ההופכית, כלומר לבצע את פענוח ההודעה המוצפנת. מי שאין בידו המידע הזה ומנסה לפענח את ההודעה המוצפנת, עומדת לפניו משימה חישובית קשה מאוד. אלגוריתם RSA הנזכר לעיל עושה שימוש בפונקציה מסוג זה.

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

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

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

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

  • Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. פרקים מהספר באתר המחבר
  • Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography.

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

  1. ^ ההסתברות הינה על כלל הקלטים ועל הטלות המטבע של המכונה A.‏
  2. ^ ההסתברות הינה על כלל הקלטים ועל הטלות המטבע של המכונה A.‏