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