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

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

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

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

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

בשנות ה-70 חוקרים כמו קרטר וווגמן הגדירו את רעיון ה"פונקציה האוניברסלית". זו משפחה של פונקציות שבהן, אם בוחרים פונקציה באקראי מהמשפחה, ההסתברות ששני מופעים שונים יתמפו לאותו פלט קטנה (למשל לא יותר מ-1/N).
דוגמה מעשית היא משפחה של פונקציות מהצורה h_{m,n}(x) = ((m x + n) mod p) mod b, שמפזרת היטב ערכים אם p ראשוני. כדי לחסוך פעולות חלוקה כבדות משתמשים בטריקים חישוביים, למשל בחירת p מיוחד או שימוש בהזזות ובחירה של הביטים המתאימים.

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

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

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

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

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

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

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