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

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

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

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

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

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

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

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

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

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

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

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

Chained Hashing (פונקציית גיבוב משורשרת)[עריכת קוד מקור | עריכה]

פונקציות גיבוב ויישומן לצורך איחזור מידע, נחקרו לראשונה על ידי ארנולד דמי (A.I. Dumey) ב-1956. במדובר באופן כללי בשיטות היוריסטיות שנותנות פתרון לבעיה שנקראת 'בעיית המילון', שהיא הבעיה הבסיסית שפונקציית גיבוב אמורה לפתור. בהינתן המרחב U של כל אלמנטים האפשריים - מתוכם צריך לאחסן N אלמנטים, המטרה היא למצוא פונקציה שממפה אלמנטים מהמרחב U למערך כניסות בזיכרון A[1..N] כך ששלושת הפונקציות הבסיסיות: \text{INSERT}(x,k), \text{DELETE}(k) ו-\text{LOOKUP}(x) דהיינו הוספה, מחיקה או חיפוש ערכים, צריכות להתבצע און-ליין במהירות האפשרית ובמינימום זיכרון אפשרי. k הוא המפתח לערך ו-x הוא המידע המשויך אליו.

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

h : U\rightarrow \{1,...,N\},

שתמפה את הערכים באקראי, כך שכל כניסה i במערך A[1..N] תכיל רשימה מקושרת (מכאן השם), של מפתחות k (אם במקרה קיימים שניים או יותר באותה כניסה) כך שמתקיים h(k)=i. לכל מפתח מצמידים את המידע המשויך אליו. לצורך הפונקציה הראנדומלית הציע דמי פונקציה פשוטה כמו h(x)=x\text{ modulo }p כאשר p ראשוני. בממוצע הפונקציה פועלת כמצופה והערכים מתפזרים היטב על פני המערך. הסיכוי שיימצאו מספר גדול של מפתחות בכניסה אחת במקרה הממוצע, נמוך. אפשר לראות שמציאת ערך בטבלה היא בערך בסיבוכיות של O(1).

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

ב-1975 פרסמו לורנס קרטר ומרק ווגמן מאמר‏[1] רב השפעה שחוקר את פונקציות הגיבוב מהיבט תאורתי. הם הטביעו לראשונה את המושג פונקציית גיבוב אוניברסלית (Universal Hash Function) והראו שלוש מחלקות אפשריות של פונקציות כאלו וכן הוכיחו שפונקציה העונה להגדרה זו, קרובה למינימום התאורטי האפשרי, כלומר עם מינימום התנגשויות ללא תלות באופי הקלט וכן ניתנת לחישוב באופן יעיל.

תהי \mathcal{H} מחלקה של פונקציות מהצורה h : U\rightarrow A[1..N] כאשר h שנבחרה באקראי מתוך המרחב \mathcal{H} הממפה ערכים מ-U ל-A כאשר |U|>|A|. אומרים ש-h אוניברסלית אם עבור כל x,y\in U כאשר x\ne y מתקיים:

\Pr[h(x)=h(y)]\le \frac{1}{N}

כלומר ההסתברות שתהיה התנגשות (שהפונקציה h תמפה שני ערכים לאותה כניסה) נמוכה או שווה ל-1/N וכן אומרים שהפונקציה h 'כמעט אוניברסלית' אם היא מקיימת \textstyle \Pr[h(x)=h(y)]\le \frac{2}{N}.

לדוגמה אם נתונה קבוצה A=\{0,1,...,a-1\} עם a אלמנטים והקבוצה B=\{0,1,...,b-1\} עם b אלמנטים ונתון מספר ראשוני p\ge a והפונקציה g שממפה אלמנטים מ-Z_p לקבוצה B (מסיבות של יעילות רצוי ש-g תהיה השארית מחילוק ב-b אם b=2^k אין צורך לבצע חילוק בפועל אלא נוטלים את k הסיביות הפחות משמעותיות של האלמנט ומתעלמים מהיתר). נתונים שני אלמנטים m ו-n מתוך Z_p כאשר m\ne0. אז הפונקציה

h_{m,n}(x)=((mx+n)\text{ mod }p)\text{ mod }b

היא פונקציית גיבוב אוניברסלית.

כדי להימנע מפעולת הצמצום המודלורי שהיא פעולה לא יעילה במונחי מיחשוב אפשר לבצע את הטריק הבא: אם p=2^j-1 עבור j כלשהו (למשל 2^{11}-1 הוא מספר ראשוני), אם x ניתן לייצוג על ידי 2j סיביות אזי קיימים x_1,x_2<2^j כך שמתקיים x= 2^jx_1+x_2 במילים אחרות x_1 הוא j הסיביות המשמעותיות ביותר של x ו-x_2 הוא j הסיביות הפחות משמעותיות. היות ש-2^j\equiv 1 \ (\text{ mod }p) מתקיים:

x\equiv x_1+x_2 \ (\text{ mod }p)

פועל יוצא הוא שהערך x אותו מעוניינים למפות מצטמצם מודולו p למספר בגודל j+1 סיביות. כי כדי לחשב את x(\text{mod }p) מספיק לחשב את x_1+x_2, לבצע בדיקה אם הוא גדול מ-p ולכל היותר יידרש חיסור אחד של p. לסיכום אם b הוא חזקה של 2, כל התהליך מצטמצם לכפל אחד, שתי פעולות חיבור, הזזה (shift) ופעולה לוגית אחת ואין צורך במודולו כלל.

דרך אחרת להימנע מחילוק הוצעה על ידי Dietzfelbinger. נוטלים את הסיביות המשמעותיות של התוצאה. לדוגמה אם k=32, אם התוצאה בגודל 64 סיביות, נוטלים רק את 32 הסיביות המשמעותיות, או בניסוח אחר: h_{m,n}(x)=(mx+n) \gg k כאשר \gg הוא הזזה לימין (shift right), אזי הפונקציה h_{m,n}(x) אוניברסלית.


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

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

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

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

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

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

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

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

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

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

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

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

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

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