פרוטוקול דיפי-הלמן

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

בקריפטוגרפיה, פרוטוקול דיפי-הלמן (Diffie-Hellman) הוא הפתרון המעשי הראשון לבעיית הפצת המפתחות, ביתר פירוט לבעיית "שיתוף מפתח". הפרוטוקול מאפשר לשני משתתפים שלא נפגשו מעולם ואינם חולקים ביניהם סוד משותף כלשהו מראש, להעביר ביניהם מעל גבי ערוץ פתוח (שאינו מאובטח) סוד כלשהו כך שאיש מלבדם אינו יודע. פרוטוקול דיפי-הלמן מתמודד עם בעיה זו בשיטה אסימטרית. הפרוטוקול פוטר מהצורך לשמור מפתחות הצפנה סודיים לאורך זמן; תחת זאת המצפין יכול להכין מפתח הצפנה ארעי, להעבירו באמצעות הפרוטוקול לצד השני ואז התקשורת ביניהם יכולה להיות מוצפנת באמצעות צופן סימטרי מהיר כמו AES כאשר מפתח ההצפנה הוא הסוד המשותף או מפתח אחר שנגזר ממנו באמצעות פונקציה מוסכמת ובגמר השימוש בו המפתח מושמד.

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

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

Diffie-hellman.jpg

הגרסה הבסיסית היא כדלהלן:

הכנה חד-פעמית: המשתתפים בפרוטוקול אליס ובוב, לצורך העניין (A ו-B) בוחרים ומפיצים באופן ציבורי, ראשוני \ p גדול ויוצר \ \alpha של \ \mathbb{Z}^{*}_p כאשר \ 2 \le \alpha \le p - 2. בסיום הפרוטוקול A ו-B משתפים ביניהם מפתח הצפנה \ K, בצורה מאובטחת (כך שאף גורם זר לא יכול לדעת מהו). מפתח זה יכול לשמש להצפנת מסרים באמצעות אלגוריתם סימטרי כלשהו.

מסרי הפרוטוקול:

  1. \ \mbox{A} \rightarrow \mbox{B}: \ \ \alpha^x \ \mbox{ mod }p \ \
  2. \ \mbox{A} \leftarrow \mbox{B}: \ \ \alpha^y \ \mbox{ mod }p \ \

פעולות הפרוטוקול:

  1. A בוחר שלם אקראי סודי \ x כאשר \ 1 \le x \le p - 2 ושולח ל-B את מסר 1 לעיל.
  2. B בוחר שלם אקראי סודי \ y כאשר \ 1 \le y \le p - 2 ושולח ל-A את מסר 2 לעיל.
  3. B מקבל את  \ \alpha^x ומחשב את המפתח המשותף כ-\ K = (\alpha^x)^y \mbox{ mod } p.
  4. A מקבל את \ \alpha^y ומחשב את המפתח המשותף כ-\ K =(\alpha^y)^x \mbox{ mod }p.

אליס ובוב שידרו זה לזה את הערכים \ \alpha^x ו-\ \alpha^y (מודולו p) בהתאמה. נניח שמאזין נסתר הצליח לקלוט את שני המספרים הללו. המאזין נאלץ לחשב בעזרתם את \ \alpha^{xy} \text{ mod }p (כאשר \ p ו- \ \alpha פומביים), מכיוון ש- \ x ו- \ y אינם ידועים לו (שכן הם מעולם לא שודרו). בעיה זו (חישוב \ \alpha^{xy} מתוך \ \alpha^x ו- \ \alpha^y) (מודולו p), נקראת בעיית דיפי-הלמן, ונחשבת לבעיה קשה אם \ p הוא מספר גדול.

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

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

בעיית דיפי-הלמן[עריכת קוד מקור | עריכה]

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

בעיית דיפי-הלמן היא כדלהלן:

בהינתן אלמנט מספר ראשוני \ p, יוצר \ \alpha של החבורה \ \mathbb{Z}^{*}_p, והערכים \ \alpha^x ו-\ \alpha^y מהו \ \alpha^{xy}?

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

ביטחון[עריכת קוד מקור | עריכה]

דרך אחת ליישום הפרוטוקול היא בחבורה הכפלית \ \mathbb{Z}^{*}_p או החבורה הכפלית \ \mathbb{F}_{2^m}. הרעיון הוא שבחבורה זו חישוב לוגריתמים קשה יותר מבחינה חישובית מהעלאה בחזקה, קיימים אלגוריתמים פולינומיים לחישוב חזקות גדולות מודולו \ p. מצד שני קיימים אלגוריתמים תת-מעריכיים לתקיפת הפרוטוקול באמצעות פתרון לוגריתמים בחבורות שמגיעים לתוצאות טובות מכוח גס מסיבה זו כמו בכל שיטת מפתח-פומבי המתבססת על בעיה דומה, בטיחות הפרוטוקול תלויה בעצם בגודל המספר הראשוני \ p ובכוח המחשוב הנוכחי. מקובל כיום ש-\ p יהיה לפחות בסדר גודל של כ-2000 סיביות. דרך אחרת ליישום פרוטוקול דיפי-הלמן היא, מעל קבוצת הנקודות בעקומה אליפטית מעל שדה סופי דוגמת MQV, רעיון זה הוא חלק ממערכת ECC שנחשבת כיעילה מאוד ויחודה הוא בגודל המפתח, שיכול להיות קטן באופן משמעותי, זאת מבלי לאבד מבטיחותו.

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

פרוטוקול דיפי הלמן אינו מבטיח למשתתפים הגנה על אופן בחירת המפתח ואינו מונע שליטה חד צדדית. למעשה אחד הצדדים יכול בקלות להשפיע על אופן בחירת המפתח על ידי בחירת \ x או \ y קטנים במכוון. לדוגמה אם המעריך \ x = 0 שהמפתח יהיה \ \alpha^y. באופן דומה הפרוטוקול פגיע במיוחד להתקפה הבאה: אם \ p = Rq + 1 (כאשר \ R קטן כגון \ R = 2 ו-\ q ראשוני), אזי \ \beta = \alpha^q = \alpha^{(p - 1)/R} הוא מסדר \ R (ואז \ \beta = -1). תוקף אקטיבי יכול להחליף את המסרים ששלחו המשתתפים בערכים \ (\alpha^x)^q וכן \ (\alpha^y)^q בהתאמה, בכך לגורום למפתח המשותף \ K להיות \ K = \alpha^{xyq} = \beta^{xy}. וכתוצאה \ K יהיה בטווח \ 1 או \ -1. כלומר יש להבטיח שהמעריכים \ x ו-\ y יהיו בטווח המותר וכן שלא שונו בידי גורם זדוני כלשהו במהלך הפרוטוקול.

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

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

נבחר את המספר הראשוני \ p = 113 ו- \ \alpha = 3 הוא יוצר של \ \mathbb{Z}^*_{113}.

A בוחר את \ x = 45.
B בוחר את \ y = 63.
A שולח ל-B את \ 3^{45} \equiv 55 \pmod{113}.
B שולח ל-A את \ 3^{63} \equiv 73 \pmod{113}.
המשתתפים מחשבים את המפתח המשותף כדלהלן.
B מחשב את:
\ K = 55^{63} \equiv 78 \pmod{113},
A מחשב גם הוא את:
\ K = 73^{45} \equiv 78 \pmod{113}.
כעת בידי שניהם מפתח \ K זהה.

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

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


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

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

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

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