פונקציית גיבוב

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

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

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

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

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

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

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

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

דוגמה לפונקציית גיבוב מסוג זה נתונה על ידי האלגוריתם הבא:

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

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

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

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

פונקציה נפוצה לבדיקה ותיקון שגיאות היא CRC.

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

השוואה בין קבצים[עריכת קוד מקור | עריכה]

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

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

Postscript-viewer-shaded.png ערך מורחב – פונקציית גיבוב קריפטוגרפית

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

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

פונקציית גיבוב קריפטוגרפית בטוחה מקיימת את התנאים הבאים:

  1. בהינתן פלט מסוים, מציאת ערך קלט מתאים (כלומר קלט כזה שהפעלת הפונקציה עליו תייצר את הפלט הזה), קשה מבחינה חישובית (Preimage).
  2. בהינתן קלט כלשהו קשה חישובית למצוא קלט אחר המוביל לאותו פלט (Second preimage).
  3. מציאת שני קלטים שונים המובילים לאותו פלט קשה מבחינה חישובית (התנגשות, Collision).

קשה, ואולי אפילו בלתי אפשרי להוכיח שפונקציית גיבוב מסוימת היא בטוחה, וקורה שפונקציה מסוימת נחשבת "בטוחה", ומאוחר יותר מתברר שאינה כזו, כאשר נמצאת שיטה יעילה יחסית (כלומר שיטה שעלותה החישובית נמוכה משמעותית מגודל הפלט) למצוא Preimage,‏ Second Preimage או התנגשות. במקרה כזה נזנח השימוש בפונקציית הגיבוב הזו לצרכים קריפטוגרפיים. גורל כזה פקד למשל את הפונקציה MD5.

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