כמו כן, אם איב מסוגלת לחשב את formula_9 מתוך הערך formula_28, היא יכולה לחשוף את ה'סוד' של אליס ובוב. חישוב formula_9 מתוך formula_28 נקרא בעיית הלוגריתם הבדיד ואף היא נחשבת לבעיה קשה. מי שיכול לפתור את בעיית הלוגריתם הבדיד באופן יעיל, בוודאי יכול לפתור גם את בעיית דיפי־הלמן באופן יעיל. ההפך אינו ידוע, טרם נמצאה הוכחה לכך שהיכולת לפתור את בעיית דיפי־הלמן שקולה ליכולת לפתור את בעיית הלוגריתם הבדיד.
מסרי הפרוטוקול:
פעולות הפרוטוקול:
כאמור כל הפעולות מבוצעות מודולו המספר הראשוני formula_45. החישוב המודולרי הכרחי לצורך בטיחות הפרוטוקול כיוון שבלעדיו, אליס משדרת את השלם formula_28, כאשר formula_3 ידוע לכל. במקרה הזה בעיית הלוגריתם הבדיד קלה מאוד לפתרון, מכיוון שמספר הספרות העשרוניות הדרושות לכתיבת formula_28 קרוב למספר הספרות של formula_3 כשהוא מוכפל בנעלם formula_37. כדי למצוא את formula_37 די לחלק את מספרי הספרות זה בזה. מאידך חישוב formula_37 מתוך השארית לאחר חילוק formula_53 ב־formula_45 אינו קל.
דוגמה במספרים קטנים.
לצורך הדגמה בלבד, נניח שהוסכם על המספר הראשוני formula_55 ויוצר formula_56 של החבורה הכפלית formula_57. בחירת יוצר היא מלאכה קלה כפי שיוסבר להלן. מהלכי הפרוטוקול הם:
מציאת יוצר של החבורה הציקלית.
בחירת יוצר קלה ביותר אם ידועים הגורמים הראשוניים של סדר החבורה במקרה של הדוגמה לעיל formula_67. היות ש־formula_68 כאשר formula_69 ראשוני. לפי תורת החבורות היוצר יכול להיות כל ערך המקיים: formula_70 עבור כל הגורמים formula_71 של formula_72. כלומר formula_73 וכן formula_74 מודולו formula_75, על כן formula_76 יכול לשמש כיוצר (ההסתברות שמספר אקראי יצור את החבורה היא formula_77 (הפונקציה formula_78 היא פונקציית אוילר). במקרה זה היות שהגורמים הם formula_79 מזה נובע ש־formula_80, לכן ההסתברות שמספר מסוים הוא יוצר היא formula_81).
פרוטוקול דיפי־הלמן בעקום אליפטי.
פרוטוקול דיפי־הלמן בעקום אליפטי נקרא בקיצור ECDH אנלוגי לפרוטוקול דיפי הלמן המתואר לעיל. נתונים פרמטרי התחום של העקום לפי הגדרות התקן: formula_82, העקום האליפטי הוא formula_83 כאשר formula_84 הסדר של השדה formula_85 וכן formula_86 מקדמים של משוואת העקום, formula_87 היא נקודת הבסיס, formula_88 הסדר הראשוני של נקודת הבסיס, formula_89 פקטור משלים כך שמתקיים formula_90 ו־formula_91 מייצג את מספר הנקודות בעקום formula_92.
המשתתפת אליס בוחרת מפתח סודי שהוא שלם אקראי formula_9 והמפתח הציבורי שלה יהיה formula_94 (תוצאת כפל סקלארי של הנקודה formula_87 ב־formula_9). בוב בוחר מפתח סודי וציבורי formula_97 באותה דרך. כעת אם הם רוצים לשתף ביניהם את הסוד formula_98 הם פועלים כדלהלן:
הפרוטוקול נכון כי מתקיים formula_103. לכן הנקודה formula_98 בעקום האליפטי היא נקודה סודית המשותפת רק לשניהם, אותה הם יכולים להמיר למפתח הצפנה.
דוגמה במספרים קטנים. נניח שאליס ובוב הסכימו ביניהם על הפרמטרים המשותפים הבאים:
לצורך ההתקשרות ביניהם נניח שאליס בחרה את המפתח הסודי: formula_110 ובוב בחר את המפתח הסודי formula_111, כעת לפי כללי האריתמטיקה בעקום האליפטי אליס מחשבת את:
בוב מחשב את:
אליס שולחת לבוב את formula_17 ובוב שולח לאליס את formula_14. לבסוף, אליס מחשבת את:
בוב מחשב את:
כעת הם משתפים ביניהם את הנקודה הסודית formula_118. מקובל להתעלם מהקואורדינטה formula_119 ולקחת רק את formula_120 כערך סודי משותף.
בעיית דיפי־הלמן.
בעיית דיפי־הלמן - Diffie-Hellman problem בקיצור DHP היא בעיה מתמטית קשה שהועלתה לראשונה על ידי ויטפילד דיפי ומרטין הלמן בהקשר של קריפטוגרפיה. הסיבה לאטרקטיביות הבעיה היא העובדה שהיא מהווה על פניה, פונקציה חד-כיוונית. ויש עניין רב בקריפטוגרפיה בפונקציות חד־כיווניות כיוון שהן הבסיס המתמטי למרבית האלגוריתמים האסימטריים. פונקציה חד־כיוונית מאפשרת ביצוע תהליך הצפנה שהוא קל יחסית בכיוון אחד אבל קשה בכיוון ההפוך, דהיינו פענוח. אלא אם כן קיים מידע נסתר בידי המפענח שמקל על מלאכתו. המידע הנסתר קרוי מפתח פענוח או מפתח פרטי.
בעיית דיפי־הלמן היא כדלהלן:
באופן פורמלי formula_3 הוא יוצר של חבורה ציקלית (מעל שדה סופי מסדר ראשוני, שדה בינארי מורחב או מעל עקום אליפטי) והערכים formula_128 ו־formula_119 שלמים אקראיים כלשהם.
ביטחון.
ביטחון פרוטוקול דיפי־הלמן מסתמך על ההשערה שקשה לפתור את בעיית דיפי־הלמן או את בעיית הלוגריתם הדיסקרטי בחבורות מסוימות יותר מהעלאה בחזקה. מסיבה זו חשוב לבחור חבורה מתאימה כי בחבורות מסוימות פתרון הבעיות הללו עלול להיות טריוויאלי או קל במידה ניכרת. החבורות העיקריות הידועות כיום כבטוחות לשימוש הן חבורה כפלית המבוססת על:
הוכח שהקושי בפתרון בעיית הלוגריתם הבדיד תלוי בגורם הראשוני הגדול ביותר של סדר החבורה (אם סדר החבורה ראשוני, הכוונה לסדר החבורה פחות 1). בעיקרון שיטת כוח גס, דהיינו ניסוי כל האפשרויות עד למציאת פתרון אינה יעילה. קיימים אלגוריתמים מהירים שמוצאים פתרון בזמן קצר יותר מכוח גס. ניתן למנות כמה מהם: תחשיב אינדקסים, אלגוריתם רו של פולרד, אלגוריתם צעד-קטן צעד-גדול של דייוויד שנקס, אלגוריתם נפת שדה המספרים ועוד. האחרון נחשב לאלגוריתם הטוב ביותר לפתרון בעיית הלוגריתם הבדיד והוא פועל בזמן ריצה תת־מעריכי, מסדר גודל של formula_133. על כל פנים הממצאים בתחום עדיין לא שלמים.
תקן SP 800-57 של NIST (גרסה 3 - יולי 2012) משווה בין החוזק של אלגוריתמים סימטריים ואלגוריתמים אסימטריים המקבילים להם. המלצות התקן גורסות שהראשוני formula_1 צריך להיות בגודל בין 1024 סיביות ל־15,360 סיביות בהתאם לחוזק אלגוריתמים סימטריים המקבילים (בין 80 סיביות ל־256 סיביות). למשל להשגת חוזק זהה לאלגוריתם AES עם מפתח בגודל 128 סיביות יש לבחור ראשוני באורך 3,072 סיביות. מעל קבוצת הנקודות בעקום אליפטי התקן ממליץ על טווח אורכים בין 160 ל־512 סיביות. הסיבה היא שהאלגוריתמים הטובים ביותר הידועים, אינם ישימים בעקום אליפטי.
פרוטוקול דיפי הלמן ניתן לשינוי באופן שיספק גם אימות זהויות, על ידי קביעת הערכים formula_135 ו־formula_136 מודולו formula_45 כמפתחות ציבוריים של כל משתמש ואז על ידי חתימה על המפתחות (באמצעות סרטיפיקט) ניתן להבטיח את שייכותם לכל משתמש בהתאמה. פרוטוקול MQV הוא דוגמה טובה להרחבה של פרוטוקול דיפי הלמן המספקת גם אימות זהויות עקיף.
פרוטוקול דיפי הלמן אינו מבטיח למשתתפים הגנה על אופן בחירת המפתח ואינו מונע שליטה חד צדדית. למעשה אחד הצדדים יכול בקלות להשפיע על אופן בחירת המפתח על ידי בחירת formula_138 או formula_139 קטנים במכוון. לדוגמה אם המעריך formula_140 המפתח הסודי המשותף formula_98 יהיה formula_136. באופן דומה הפרוטוקול פגיע במיוחד להתקפה הבאה: אם formula_143 (כאשר formula_144 קטן כגון formula_145 ו־formula_84 ראשוני), אזי formula_147 הוא מסדר formula_144 (ואז formula_149). תוקף אקטיבי יכול להחליף את המסרים ששלחו המשתתפים בערכים formula_150 וכן formula_151 בהתאמה, בכך לגרום למפתח המשותף להיות formula_152. וכתוצאה formula_19 יהיה בטווח formula_154 או formula_155.
בכללות מומלץ לבצע בדיקת תקפות של הערכים כדי להבטיח שהם בטווח המותר וכי שלא שונו בידי גורם זדוני כלשהו או עקב שגיאה, במהלך חילופי המסרים של הפרוטוקול.
התקפת אדם באמצע.
נניח שהמצותתת איב אינה רק צופה פאסיבית אלא ביכולתה ליירט ולשנות מסרים בעודם בדרכם ליעדם מבלי שהמתקשרים הלגיטימיים יבחינו בכך. מצב כזה אפשרי בכל ערוץ תקשורת שאינו מאומת באופן קריפטוגרפי. במקרה כזה איב יכולה לבצע התקפה הידועה בשם התקפת האדם באמצע באופן הבא: כזכור אליס מעוניינת לשלוח לבוב את המפתח הציבורי שלה formula_20 (כאשר formula_9 הוא המפתח הפרטי) ובוב מעוניין לשלוח לאליס את המפתח הציבורי שלו formula_21. איב תחילה מכינה מפתחות משלה, נניח formula_159, ואז כאשר הם מתקשרים ביניהם היא מיירטת את המסרים מאליס לבוב ומבוב לאליס ומחליפה אותם ב־formula_92. כעת איב משתפת עם אליס ועם בוב בנפרד את המפתחות formula_161 ו־formula_162 בהתאמה בעוד שהם מאמינים כי הם שיתפו את המפתחות formula_163 ו־formula_164 בהתאמה, כמתואר בתרשים.
כעת אם אליס או בוב ישלחו זה לזה מסר מוצפן כלשהו עם מפתח ההצפנה formula_165 או formula_166 בהתאמה, איב יכולה ליירטו ולפענחו עם המפתח הפרטי המתאים שברשותה formula_161 או formula_162 בהתאמה. יתרה מזו, כדי שהמתקשרים הלגיטמיים לא יבחינו במתרחש היא חוזרת ומצפינה את המסר עם המפתח הפרטי שהיא שיתפה עם הצד השני ושולחת אותו ליעדו כאילו כלום לא קרה. כדי לסכל התקפה כזו על המתקשרים לאמת בדרך כלשהי את המסרים העוברים ביניהם, גם כדי להבטיח כי הגיעו מהמקור שהם סבורים וכן שהמסרים לא שונו באופן זדוני בדרכם ליעדם. מסיבה זו אימות והבטחת שלמות הם נושאים קריטיים באבטחת מידע. פרוטוקול MQV מספק מענה חלקי לבעיה. אפשר כמובן לחתום על כל המסרים עם החתימה הדיגיטלית המתאימה של כל צד.
הכללות.
במקום לעבוד בחבורה הכפלית של המספרים מודולו הראשוני formula_1 (שהיא חבורת אוילר של formula_1), אפשר לעבוד בכל חבורה ציקלית אחרת. השותפים צריכים לפרסם את החבורה formula_171 ואת האיבר formula_9, ואז לחזור על התהליך כמתואר לעיל. הבעיות הניצבות בפני המאזין הסמוי נקראות 'בעיית דיפי־הלמן' ו'בעיית הלוגריתם הבדיד' בחבורה formula_171, בהתאמה.