פונקציית גיבוב
מתוך ויקיפדיה, האנציקלופדיה החופשית
בתקשורת ספרתית ובמדעי המחשב, פונקציית גיבוב (באנגלית: Hash function; לעיתים פונקציית ערבול, פונקציית תמצות ואף פונקציית טחינה) היא פונקציה שממירה קלט חופשי באורך משתנה לפלט באורך קבוע, בדרך כלל קצר בהרבה. שינוי בקלט יגרום לפונקציה, בהסתברות גבוהה, להפיק פלט שונה. לפונקציות כאלה יש שימושים בבעיות אלגוריתמיות רבות, וביניהן מיון וחיפוש בטקסטים ארוכים.
תוכן עניינים |
[עריכה] שימושים
[עריכה] טבלת גיבוב
פונקציית גיבוב היא מרכיב חשוב בבניית טבלת גיבוב. הפונקציה משמשת אינדקס (מפתח) לאיברי טבלת הגיבוב והיא "המנוע" הקובע את מהירות הגישה בשליפה ואחסון איברים בטבלה.
[עריכה] בדיקת שגיאות
בהעברת מידע ברשת, יבדוק הצד המקבל את שלמות המידע תוך השוואת פלט פונקציית הגיבוב עם הצד השולח. במידה והפלט לא שווה, ישלח המקטע הפגום מחדש. בדומה לכך, בהעתקת קבצים ייבדק המקטע המועתק כדי להבטיח את שלמות ההעתקה.
פונקציה נפוצה לבדיקה ותיקון שגיאות היא Cyclic Redundancy Check (CRC).
אלגוריתם חישוב ספרת ביקורת הוא דוגמה לפונקציית גיבוב.
[עריכה] השוואה בין קבצים
יצירת חתימה לקובץ מאפשרת מעקב אחר שינויים שחלו בו. כך אפשר לדעת אם הקובץ נפגם, נדבק בווירוס או שונה במכוון.
[עריכה] פונקציות גיבוב חד כיווניות
זוהי תת-משפחה חשובה של משפחת פונקציות הגיבוב שיש לה מספר מאפיינים ייחודיים:
- מקלט נתון ניתן לחשב את הפלט באופן מהיר.
- מפלט נתון קשה מאוד (מבחינה חישובית) לשחזר קלט תואם.
פונקציות אלה משמשות בעיקר כמרכיבים בהצפנה, אבטחה ואימות נתונים.
פונקציות נפוצות בשימוש:
[עריכה] MD5
אלגוריתם MD5 (ראשי תיבות של Message-Digest 5), שפותח בשנת 1991 על־ידי רונלד ריבסט, מחזיר פלט של 128 סיביות. קדמו לו הגרסאות MD2 ו־MD4, אך נתגלו בהם חולשות רבות ולכן לא מקובל להשתמש בהם עוד.
[עריכה] SHA-1
אלגוריתם SHA-1 (ראשי תיבות של: Secure Hash Algorithm) תוכנן על־ידי ה־NSA והופץ על־ידי ממשלת ארצות הברית בשנת 1995. במקור נקרא SHA אבל התגלתה בו פרצה חמורה וכדי שיהיה ניתן להבדיל בין הגרסאות נקראה הגרסה המתוקנת SHA-1. SHA-1 מחזיר פלט של 160 סיביות.
דוגמה מעשית לפלט (חתימה) של SHA-1:
SHA1("The quick brown fox jumps over the lazy dog") = 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
SHA1("The quick brown fox jumps over the lazy cog") = de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
הסבר: ההודעה נמצאת בתוך המרכאות. הפלט הוא מחרוזת טקסט ייחודית אך חסרת משמעות.
[עריכה] SHA-2
ל־SHA קיימות גרסאות שמחזירות פלט בגדלים שונים, המסומנות SHA-xxx כאשר xxx הוא מספר סיביות הפלט. גרסאות אילו מכונות לעתים SHA-2, ובהן SHA-224, SHA-256, SHA-384, SHA-512.
[עריכה] ראו גם
[עריכה] קישורים חיצוניים
- פונקציות גיבוב חד כיווניות (בוויקיפדיה האנגלית)

