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

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

שימושים

טבלת גיבוב

ערך מורחב – טבלת גיבוב

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

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

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

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

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

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

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

Chained Hashing (פונקציית גיבוב משורשרת)

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

תאורטית אפשר להקצות שטח זיכרון כגודל המרחב ${\displaystyle U}$ ואז כל אלמנט יהיה ממופה לעצמו לפי סדר רץ כלשהו (כל אלמנט יכול להיות אינדקס של עצמו). אולם במקרה זה צריכת הזיכרון תהיה בזבזנית כי אם ${\displaystyle N}$ קטן משמעותית מ-${\displaystyle U}$ שטח הזיכרון לא ינוצל במלואו. מלבד זאת ייתכן שיהיה בלתי מעשי להקצות כמות כזו של זיכרון אם המרחב גדול. הפתרון של דמי פשוט; מגדירים פונקציה ${\displaystyle h}$ שהיא פונקציה "אקראית", "כאוטית"^{[דרושה הבהרה]}, "משוגעת"^{[דרושה הבהרה]}:

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

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

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

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

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

${\displaystyle \Pr[h(x)=h(y)]\leq {\frac {1}{N}}}$

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

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

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

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

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

${\displaystyle x\equiv x_{1}+x_{2}\ ({\text{ mod }}p)}$

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

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

בדיקת שגיאות

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

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

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

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

ערך מורחב – פונקציית גיבוב קריפטוגרפית

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

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

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

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

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

ראו גם

• גיבוב קוקייה
• Globally Unique Identifier (GUID) (בעברית)
• פונקציית גיבוב מתגלגלת

קישורים חיצוניים

מדיה וקבצים בנושא פונקציית גיבוב בוויקישיתוף

• מה ההבדל בין הצפנה ו-hash?
• פונקציית גיבוב, באתר MathWorld (באנגלית)

הערות שוליים

1. Universal Classes of Hash Functions