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

מתוך ויקיפדיה, האנציקלופדיה החופשית
תוכן שנמחק תוכן שנוסף
←‏שימושים: הוספת נקודה בין משפטים
Halfon3100 (שיחה | תרומות)
שורה 64: שורה 64:
==פונקציית גיבוב קריפטוגרפית==
==פונקציית גיבוב קריפטוגרפית==
{{ערך מורחב|פונקציית גיבוב קריפטוגרפית}}
{{ערך מורחב|פונקציית גיבוב קריפטוגרפית}}
'''פונקציית גיבוב קריפטוגרפית''' היא [[פונקציה חד-כיוונית]] הממירה [[קלט]] באורך כלשהו ל[[פלט]] באורך קבוע וידוע מראש. בניגוד ל[[פונקציית גיבוב]] רגילה, פונקציית גיבוב קריפטוגרפית מתוכננת כך שכל שינוי בקלט יגרום לשינוי משמעותי בפלט. בדרך זו ניתן להתמודד עם בעיית הבטחת שלמות מסרים גדולים, על ידי השוואת הערך המגובב שלהם במקום להשוותם ישירות. בשל היותו קטן משמעותית, קל יותר להגן על הערך המגובב מאשר על המסר המקורי.
'''פונקציית גיבוב קריפטוגרפית''' היא [[פונקציה חד-כיוונית]] הממירה [[קלט]] באורך כלשהו ל[[פלט]] באורך קבוע וידוע מראש. בניגוד ל[[פונקציית גיבוב]] רגילה, פונקציית גיבוב קריפטוגרפית מתוכננת כך שכל שינוי בקלט יגרום לשינוי משמעותי בפלט. בדרך זו ניתן להתמודד עם בעיית אבטחת שלמות מסרים גדולים, על ידי השוואת הערך המגובב שלהם במקום להשוותם ישירות. בשל היותו קטן משמעותית, קל יותר להגן על הערך המגובב מאשר על המסר המקורי.


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

גרסה מ־08:08, 7 ביוני 2016

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

שימושים

טבלת גיבוב

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

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

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

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

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

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

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

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

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

פונקציות גיבוב ויישומן לצורך איחזור מידע, נחקרו לראשונה על ידי ארנולד דמי (A.I. Dumey) ב-1956. במדובר באופן כללי בשיטות היוריסטיות שנותנות פתרון לבעיה שנקראת 'בעיית המילון', שהיא הבעיה הבסיסית שפונקציית גיבוב אמורה לפתור. בהינתן המרחב של כל אלמנטים האפשריים - מתוכם צריך לאחסן אלמנטים, המטרה היא למצוא פונקציה שממפה אלמנטים מהמרחב למערך כניסות בזיכרון כך ששלוש הפונקציות הבסיסיות: , ו- דהיינו הוספה, מחיקה או חיפוש ערכים, צריכות להתבצע און-ליין במהירות האפשרית ובמינימום זיכרון אפשרי. הוא המפתח לערך ו- הוא המידע המשויך אליו.

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

,

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

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

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

תהי מחלקה של פונקציות מהצורה כאשר שנבחרה באקראי מתוך המרחב הממפה ערכים מ- ל- כאשר . אומרים ש- אוניברסלית אם עבור כל כאשר מתקיים:

כלומר ההסתברות שתהיה התנגשות (שהפונקציה תמפה שני ערכים לאותה כניסה) נמוכה או שווה ל- וכן אומרים שהפונקציה 'כמעט אוניברסלית' אם היא מקיימת .

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

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

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

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

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


בדיקת שגיאות

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

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

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

השוואה בין קבצים

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

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

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

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

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

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

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

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

ראו גם

הערות שוליים