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

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

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

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

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

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

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

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

בטיחות

פרוטוקול דיפי הלמן מתבסס כאמור על בעיית הלוגריתם הדיסקרטי בחבורות. הדרך העדיפה היא ליישמו מעל החבורה הכפלית $\ \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, בהתאמה.

מגבלות

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

ראו גם

• צופן אל-גמאל
• אל-גמאל (חתימה דיגיטלית)
• החלפת מפתחות קוונטית

קישורים חיצוניים

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