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

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

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

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

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

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

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

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

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

$\ \mbox{A} \rightarrow \mbox{B}$ : $\ \alpha^x \mbox{ mod }p$
$\ \mbox{A} \leftarrow \mbox{B}$ : $\ \alpha^y \mbox{ mod } p$

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

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

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

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

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

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

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