פונקציה חד כיוונית
מתוך ויקיפדיה, האנציקלופדיה החופשית
בתורת ההצפנה, פונקציה חד כיוונית היא פונקציה שממירה קלט לפלט, באופן שקשה מאד, מבחינה חישובית, לשחזר את הקלט מתוך הפלט. כלומר, בהינתן קלט M אפשר לקבל את הפלט E על ידי הפעלת הפונקציה החד כיוונית f(M) = E בזמן פולינומיאלי מסדר נמוך, דהיינו במהירות וביעילות. אולם שיחזור הקלט, על ידי חישוב הפונקציה ההפוכה f − 1(E) = M, היא משימה קשה מאוד חישובית (ממחלקת NP). לעתים קרובות הפונקציות משולבות בפונקציות גיבוב, להשגת חתימה ייחודית על הקלט. לפונקציות כאלה יש שימושים רבים באבטחת מידע.
תוכן עניינים |
[עריכה] קיום
טרם הוכחה (או הופרכה) מתמטית שאלת קיומן של פונקציות חד כיווניות. למעשה, הוכחת קיומן תוכיח שלא מתקיים P=NP ובכך יינתן מענה לבעיה פתוחה חשובה במדעי המחשב.
[עריכה] פונקציות מועמדות
ישנן מספר פונקציות מועמדות להיות חד כיווניות. המועמדת הידועה ביותר אולי, היא פעולת הפירוק לגורמים ראשוניים של מספר טבעי. בטיחותו של אלגוריתם ההצפנה RSA מבוססת על ההנחה שזוהי אכן פונקציה חד כיוונית.
[עריכה] שימושים
[עריכה] הצפנת מפתח ציבורי
הצפנה בשיטת מפתח ציבורי (Public Key Encryption), שמכונה גם הצפנה א-סימטרית, עושה שימוש בפונקציות חד כיווניות מסוג מסוים, פונקציות מלכודת חד כיווניות (Trapdoor one-way function). לפונקציות אלה התכונה שישנו מידע אשר ידוע רק לנמען המורשה של ההודעה (המפתח הפרטי) שבעזרתו קל לחשב את הפונקציה ההופכית, כלומר לבצע את פענוח ההודעה המוצפנת. מי שאין בידו המידע הזה ומנסה לפענח את ההודעה המוצפנת, עומדת לפניו משימה חישובית קשה מאוד. אלגוריתם RSA הנזכר לעיל עושה שימוש בפונקציה מסוג זה.
[עריכה] העברת סיסמה מוצפנת
מקובל להשתמש בפונקציית גיבוב חד כיוונית כדי להעביר סיסמה למחשב המאמת (השרת). דוגמה: השרת המאמת שולח משפט למחשב ברשת, זה האחרון לוקח את המשפט, מוסיף אליו את הסיסמה לאימות ומעביר אותם לפונקציית גיבוב חד כיוונית. את הפלט (המהווה הסיסמה המוצפנת) הוא שולח לשרת. השרת מבצע את אותה הפעולה בדיוק. במידה ושני הפלטים זהים - יאשר השרת כי הסיסמה נכונה.
[עריכה] ראו גם
קטגוריות: מחשבים | מדעי המחשב | הצפנה

