הבדלים בין גרסאות בדף "פונקציית גיבוב"

אין תקציר עריכה
מ (הוספת תבנית:MathWorld בקישורים חיצוניים (תג) (דיון))
ב[[תקשורת ספרתית]] וב[[מדעי המחשב]], '''פונקציית גִּבּוּב''' (ב[[אנגלית]]: '''Hash function'''; לעיתים '''פונקציית ערבול''', '''פונקציית תמצות''' ואף '''פונקציית טחינה''') היא פונקציה שממירה [[קלט]] חופשי באורך משתנה ל[[פלט]] באורך קבוע, בדרך כלל קצר בהרבה. אין זה רצוי, אך עם זאת בלתי נמנע, שפונקציית גיבוב תתןתיתן לעיתים פלט זהה לקלטים שונים, ולכן פונקציות גיבוב נמדדות בהסתברות להפקת [[פלט]] זהה. לפונקציות גיבוב יש שימושים בבעיות אלגוריתמיות רבות, ובהן [[מיון (מדעי המחשב)|מיון]] וחיפוש בטקסטים ארוכים וב[[קריפטוגרפיה|ובהצפנההצפנה]].
 
== שימושים ==
=== טבלת גיבוב ===
{{הפניה לערך מורחב|טבלת גיבוב}}
פונקציית גיבוב היא מרכיב חשוב בבניית [[טבלת גיבוב]]. הפונקציה משמשת [[אינדקס (מחשב)|אינדקס]] (מפתח) לאיברי [[טבלת גיבוב|טבלת הגיבוב]] והיא "המנוע" הקובע את מהירות הגישה בשליפה ואחסון איברים בטבלה. בהקשר זה, לפונקציית גיבוב ישנם שני תפקידים:
 
א. הפיכת המפתח, שבו משתמשים כדי לאחסן איברים בטבלאות גיבוב, לערך מספרי. לדוגמה, כשהמפתח הוא [[מחרוזת (מדעי המחשב)|מחרוזת]], יש להשתמש בפונקציית גיבוב שממירה מחרוזת למספר.
דוגמה לפונקציית גיבוב מסוג זה נתונה על ידי האלגוריתם הבא:
 
* אתחלאתחלו את הסכום ל-0;
* עבורעברו על כל האותיות במחרוזת. לכל אות:
** הכפלהכפילו את הסכום הנוכחי ב-256, והוסףוהוסיפו לסכום את קוד האסקייה-[[ASCII]] של האות;
* החזרהחזירו את ערכו של הסכום, [[חשבון מודולרי|מודולו]] גודל הטבלה (20).
 
בספרות ניתן למצוא פונקציות גיבוב מורכבות יותר, המחזירות פיזור אחיד יותר.
פונקציות גיבוב ויישומן לצורך איחזור מידע, נחקרו לראשונה על ידי [[ארנולד דמי]] (A.I. Dumey) ב-1956. במדובר באופן כללי בשיטות [[היוריסטיקה|היוריסטיות]] שנותנות פתרון לבעיה שנקראת 'בעיית המילון', שהיא הבעיה הבסיסית שפונקציית גיבוב אמורה לפתור. בהינתן המרחב <math>U</math> של כל אלמנטים האפשריים - מתוכם צריך לאחסן <math>N</math> אלמנטים, המטרה היא למצוא פונקציה שממפה אלמנטים מהמרחב <math>U</math> ל[[מערך (מבנה נתונים)|מערך]] כניסות בזיכרון <math>A[1..N]</math> כך ששלוש הפונקציות הבסיסיות: <math>\text{INSERT}(x,k)</math>, <math>\text{DELETE}(k)</math> ו-<math>\text{LOOKUP}(k)</math> דהיינו הוספה, מחיקה או חיפוש ערכים, צריכות להתבצע און-ליין במהירות האפשרית ובמינימום זיכרון אפשרי. <math>k</math> הוא המפתח לערך ו-<math>x</math> הוא המידע המשויך אליו.
 
תאורטית אפשר להקצות שטח זיכרון כגודל המרחב <math>U</math> ואז כל אלמנט יהיה ממופה לעצמו לפי סדר רץ כלשהו (כל אלמנט יכול להיות [[אינדקס (מחשב)|אינדקס]] של עצמו). אולם במקרה זה צריכת הזיכרון תהיה בזבזנית כי אם <math>N</math> קטן משמעותית מ-<math>U</math> שטח הזיכרון לא ינוצל במלואו. מלבד זאת ייתכן שיהיה בלתי מעשי להקצות כמות כזו של זיכרון אם המרחב גדול. הפתרון של דמי פשוט, מגדירים פונקציה <math>h</math> שהיא פונקציה [[מספר אקראי|ראנדומליתאקראית]] '"כאוטית'", '"משוגעת'":
:<math>h : U\rightarrow \{1,...,N\}</math>,
שתמפה את הערכים באקראי, כך שכל כניסה <math>i</math> במערך <math>A[1..N]</math> תכיל [[רשימה מקושרת]] (מכאן השם), של מפתחות <math>k</math> (אם במקרה קיימים שניים או יותר באותה כניסה) כך שמתקיים <math>h(k)=i</math>. לכל מפתח מצמידים את המידע המשויך אליו. לצורך הפונקציה הראנדומלית הציע דמי פונקציה פשוטה כמו <math>h(x)=x\text{ modulo }p</math> כאשר <math>p</math> [[מספר ראשוני|ראשוני]]. בממוצע הפונקציה פועלת כמצופה והערכים מתפזרים היטב על פני המערך. הסיכוי שיימצאו מספר גדול של מפתחות בכניסה אחת במקרה הממוצע, נמוך. אפשר לראות שמציאת ערך בטבלה היא בערך ב[[סיבוכיות]] של <math>O(1)</math>.
בדומה לכך, בהעתקת קבצים ייבדק המקטע המועתק כדי להבטיח את שלמות ההעתקה. פונקציות דומות משמשות גם לאיתור [[וירוס מחשב|וירוסים]] בקבצים ששותפו באינטרנט וגם כדי לוודא שגורם שלישי לא שינה את המידע בדרך (ראו גם [[התקפת אדם בתווך]]).
 
פונקציה נפוצה לבדיקה ותיקון שגיאות היא [[בדיקת יתירות מחזורית | CRC]].
 
אלגוריתם חישוב [[ספרת ביקורת]] הוא דוגמה לפונקציית גיבוב.
==פונקציית גיבוב קריפטוגרפית==
{{ערך מורחב|פונקציית גיבוב קריפטוגרפית}}
'''פונקציית גיבוב קריפטוגרפית''' היא [[פונקציה חד-כיוונית]] הממירה [[קלט]] באורך כלשהו ל[[פלט]]לפלט באורך קבוע וידוע מראש. פונקציית גיבוב קריפטוגרפית מתוכננת כך שכל שינוי בקלט יגרום לשינוי משמעותי בפלט. בדרך זו ניתן להתמודד עם בעיית הבטחת שלמות מסרים גדולים, על ידי השוואת הערך המגובב שלהם במקום להשוותם ישירות. בשל היותו קטן משמעותית, קל יותר להגן על הערך המגובב מאשר על המסר המקורי.
 
פונקציות גיבוב קריפטוגרפיות הן מאבני הבסיס של ה[[קריפטוגרפיה]]ההצפנה המודרנית ומשמשות כ[[חתימה דיגיטלית|חתימות דיגיטליות]], [[קוד אימות מסרים|קודי אימות]], [[סיסמה#ניפוח סיסמה (Salting)|שמירת סיסמאות]] ו[[מחולל פסבדומספרים אקראיפסידו-אקראיים]]. ביישומים שאינם קריפטוגרפיים הן משמשות לעיתים כמזהה ייחודי של קובץ לצורך בדיקת [[קוד תיקון שגיאות|שלמותו או נכונותו]] וכן לזיהוי קבצים זהים.
 
פונקציית גיבוב קריפטוגרפית בטוחה מקיימת את התנאים הבאים:
1,354

עריכות