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

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

[עריכה] שימושים

[עריכה] טבלת גיבוב

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

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

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

פונקציה נפוצה לבדיקה ותיקון שגיאות היא Cyclic Redundancy Check (‏CRC).

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

[עריכה] השוואה בין קבצים

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

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

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

בהגדרה הכללית, פונקציית גיבוב קולטת ערך באורך שרירותי כלשהו ומפיקה פלט ייחודי באורך מוגדר וקבוע הנקרא ערך גיבוב או קוד גיבוב. בניסוח מתמטי: הפונקצייה $\ h$ ממפה מחרוזת סיביות באורך $\ t$ למחרוזת סיביות באורך $\ n$ . לכן עבור התחום $\ D$ והטווח $\ R$ מתקבל: $\ h : D \rightarrow R$ כאשר $\ |D|>|R|$ או $\ t > n$ . בשל עובדה זו קיומם של התנגשויות (Collision) בלתי נמנע. כלומר קיימים מספר קלטים המפיקים פלט זהה. אם הפונקציה האמורה מתנהגת כפונקציה אקראית במובן שכל פלט אפשרי בהסתברות שווה, אזי בסבירות גבוהה $\ 2^{t-n}$ קלטים ימופו באופן זהה. כמו כן ההסתברות ששני קלטים שנבחרו אקראית יפיקו פלט זהה היא $\ 2^{-n}$ , ללא תלות ב- $\ t$ .

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

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

התכונות הבסיסיות של כל פונקציית גיבוב הן:

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

פונקציות גיבוב קריפטוגרפיות מחייבות תכונות נוספות כדי שיהיו בטוחות:

עמידות מקור ראשון, פירושו: עבור כל פלט נתון, יהיה קשה עד בלתי אפשרי מבחינה חישובית למצוא את הקלט המקורי לפונקציה שהפיקה פלט זה. כלומר בהינתן $\ y$ , למצוא $\ x$ המקיים $\ h(x)=y$ .
עמידות מקור שני, פירושו: עבור כל קלט נתון, יהיה קשה עד בלתי אפשרי מבחינה חישובית למצוא קלט אחר שעבורו הפונקציה מפיקה פלט זהה. כלומר בהינתן $\ x$ כלשהו למצוא $\ x'$ (אחר) המקיים $\ h(x)=h(x')$ .
עמידות בפני התנגשות, פירושו שיהיה קשה עד בלתי אפשרי מבחינה חישובית למצוא כל זוג קלטים אפשרי שעבורם יופק פלט זהה. כלומר למצוא $\ x$ ו- $\ x'$ שרירותיים המקיימים $\ h(x)=h(x')$ .

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

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

[עריכה] סוגי פונקציות גיבוב

קיימים מספר סוגים של פונקציות גיבוב. חלקם מנצלים אלגוריתם הצפנה סימטרי או אריתמטיקה מודולרית. אך מרבית האלגוריתמים הפופולריים הנם אלגוריתמים ייעודיים המעוצבים במיוחד למטרה זו, ללא שימוש בכל אלגוריתם נוסף. הבסיס לאלגוריתמים אילו הוא MD4, הרביעי בסדרה של אלגוריתמי גיבוב שפותחו על ידי רונלד ריבסט ב-1990, הנקראים Message Digest (תמצית מסרים). לאחריו יצא MD5 שהוא תוצר ישיר של קודמו, בשיפורים קלים להגברת בטיחותו. על בסיס הידע שנצבר בעקבות המצאת MD4 הומצאו אלגוריתמים רבים נוספים כמו אלגוריתם גיבוב בטוח (SHA) וגרסאותיו פרי פיתוח של ה-NSA וכן RIPEMD שהומצא על ידי דן בויר בחסות הפרויקט האירופאי RIPE. קיימים אלגוריתמים חדשים שטרם זכו לביקורת מספקת כמו אלגוריתם Tiger של אלי ביהם.

[עריכה] בטיחות

ישנם שני סוגי התקפות עיקריים על פונקציות גיבוב, האחת היא יכולת היריב למצוא ערך ספציפי לפי בחירתו, אשר יניב פלט זהה והשנייה היא היכולת למצוא ערך כלשהו לאו דוקא לפי בחירה אשר יניב ערך דומה, ללא יכולת שליטה על הערך עצמו. ההתקפה המפורסמת ביותר על פונקציות גיבוב הינה התקפת יום הולדת של גדעון יובל, יעילותה היא $\ O(2^{n/2})$ עבור ערך גיבוב באורך n סיביות והיא מבוססת על פרדוקס יום ההולדת. הרעיון הוא ליצור טבלה של $\ 2^{n/2}$ גרסאות שונות של המסר המקורי והמסר המזוייף (בשינויים קלים) יחד עם ערך הגיבוב שלהם, למיינם לפי ערך הגיבוב באופן שיאפשר חיפוש מהיר ואז לחפש התאמות בין זוגות שונים. כאמור התאמה כזו חייבת להופיע בשלב כלשהו. אפשר לשפר את ההתקפה ולהימנע משימוש בזיכרון בהסתמך על תכונות ידועות של פונקציה אקראית. כמו באמצעות אלגוריתם מציאת מחזוריות של פלויד. התקפה נוספת כנגד פונקציות גיבוב נקראת התקפת שרשור (Chaining attack). בהתקפה זו מנצלים את האופי המחזורי של פונקציות הגיבוב הידועות, במיוחד כאלו העושות שימוש במשתני שרשור (Chaining variable), תוך התמקדות בחלק הכיווץ של הפונקצייה במקום בפונקצייה כולה. על כל פנים התקפות אילו אינן מעשיות במיוחד כאשר פונקציית הגיבוב מתוכננת היטב ומפיקה ערך גיבוב בגודל 64 סיביות ומעלה.

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

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

מקלט נתון ניתן לחשב את הפלט באופן מהיר.
מפלט נתון קשה מאוד (מבחינה חישובית) לשחזר קלט תואם.

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

פונקציות נפוצות בשימוש:

[עריכה] 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.

[עריכה] ראו גם

[עריכה] קישורים חיצוניים

פונקציות גיבוב חד כיווניות (בוויקיפדיה האנגלית)

מקור: http://he.wikipedia.org../../../%D7%A4/%D7%95/%D7%A0/%D7%A4%D7%95%D7%A0%D7%A7%D7%A6%D7%99%D7%99%D7%AA_%D7%92%D7%99%D7%91%D7%95%D7%91.html

קטגוריות: תוכנה | מדעי המחשב