מהו אלגוריתם החלפת המפתחות של דיפי הלמן?

נתחיל בחידה, דמיינו שיש שני אנשים, בוב ואליס. 

אליס רוצה להעביר לבוב מכתב סודי המכיל מידע רגיש אבל בוב נמצא במקום מרוחק.

ישנה חברת שליחויות שיכולה להעביר דברים בינהם אבל ידוע שהשליחים שם חטטנים ועלולים לקרוא את תוכן המכתב אם יוכלו. 

כיצד בוב ואליס יכולים להעביר את המכתב מבלי להסתכן שהשליחים יקראו אותו? 

פתרון - 

• אליס שמה את המכתב בתוך קופסה נעולה ושולחת לבוב עם שליח זדוני. 

• בוב מקבל את הקופסה, שם מנעול נוסף ושולח חזרה לאליס.

• אליס מורידה את המנעול שלה ושולחת לבוב את הקופסה נעולה רק עם המנעול שלו

• בוב פותח את המנעול שלו ומקבל את המכתב.

בכל מעבר באמצעות שליח, הקופסה נעולה ולכן המכתב נשאר מוגן.

האלגוריתם

אלגוריתם דיפי הלמן הינו אחת ההתפתחויות החשובות ביותר בעולם הקריפטוגרפיה והוא עדיין נמצא בשימוש בפרוטוקולי הקריפטוגרפיה עד היום.

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

באמצעות שיטות מתמטיות, שני הצדדים מייצרים את ה״מנעולים״ הדרושים כדי להעביר את המסר שלהם בצורה בטוחה.

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

דיפי הלמן מבוססת על ביצוע פעולות מתמטיות על מספרים ראשוניים גדולים מאוד, כדי להבטיח רמת אבטחה מסוימת, נבחר מספר ראשוני באורך 2048 ביטים, לדוגמה:

4 1 5 3 6 8 7 5 7 6 2 8 7 3 6 5 9 8 4 2 5 9 3 8 2 4 7 5 6 9 8 4 3 7 6 5 8 2 7 6 3 4 8 7 9 1 2 8 3 7 5 8 2 7 3 6 5 9 2 8 7 3 6 8 4 2 7 3 6 8 4 7 2 8 9 3 8 5 7 2 9 8 3 7 5 9 2 8 3 4 7 5 9 3 4 8 7 5 9 3 8 4 7 5 9 2 8 4 7 5 9 2 8 7 3 9 5 8 7 2 4 9 5 8 7 2 9 8 7 3 9 5 8 7 2 9 8 3 5 7 9 2 8 7 5 9 8 2 7 9 5 8 3 7 5 2 9 8 7 6 3 4 8 2 7 3 6 8 5 7 2 9 8 4 3 5 7 9 3 4 8 7 9 5 8 2 7 9 3 8 5 7 9 2 8 7 3 9 5 4 8 7 7 2 3 9 7 5 9 2 8 3 7 5 9 2 4 7 8 5 9 3 8 6 7 0 4 5 9 8 6 7 9 2 3 8 4 7 3 7 8 2 6 7 3 5 2 6 7 3 5 4 7 6 2 3 5 6 8 7 3 4 8 6 9 3 8 6 9 4 5 6 7 3 4 5 6 8 2 7 6 5 9 4 9 8 0 6 3 8 4 9 0 2 4 8 7 5 8 0 9 6 0 3 9 4 7 9 0 2  7 9 4 5 9 82 7 3 0 1 8 7 4 3 9 7 5 9 2 8 4 6 2 0 9 5 0 2 9 3 7 5 9 2 8 7 0 4 9 5 0 2 9 3 8 0 5 8 9 2 0 9 8 3 9 4 5 8 7 2   0 9 4 8 6 0 2 9 8 4 9 1 2 8 3 7 5 0 2 9 4 8 0 1 9 3 7 1 0 9 2 4 8 0 1 9 3 5 8 1 0 3 7 9 9 5 8 1 0 9 3 7 5 0 1 9 3 8 5 0 7 9 1 3 9 5 7 1 0 9 3 7 5 9 7 0 1 9 3 8 5 0 8 9 1 0 3 9 5 1 07  3 0 5 8 7 1 0 3 9 3 7 0 19 3 4 7 0 1 9 3 8 0 9 1 8 0 3 9 8 4 0 9 1 8 0 4 9 8 1 0 9 3 8 0 1 9 8 5 0 1 3 9 8 4 0 1 9 8 3 5 0 9 1 8 3 5 0 1 9 8 3 0 9 1 0 7 9 1 8 0 3 9 5 8 1 0 3 9 5 1 9 0 3 9 5 1 8 0 9 3 5  8 1 0 9 3 8 5 0 1 9 8 4 0 1 9 3 5 8 0 1 9 3 8 4 0 1 9 8 3 4 0 9 1 8 0 9 3 8 5 1 0 9 8 3 0 9 1 8 0 0 1 9

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

תחילה, בוב ואליס מסכימים (באופן פומבי) על שני מספרים: הבסיס (g) ושדה (Z).

במציאות, השדה יהיה בגודל מספר ראשוני גדול (שמשרה חבורה ציקלית) והבסיס יהיה יוצר (generator) של חבורה ציקלית, חבורה ציקלית הינה חבורה שכל אחד מהאיברים בה הוא חזקה של איבר יוצר - לדוגמה בשדה Z7 (ללא אפס, כלומר מכיל 1,2,3,4,5,6) עם פעולת הכפל, 3 הינו איבר יוצר מכיוון ש:

• 3 בחזקת 1 מודולו 7 -> 3

• 3 בחזקת 2 מודולו 7 -> 2

• 3 בחזקת 3 מודולו 7 -> 6

• 3 בחזקת 4 מודולו 7 -> 4

• 3 בחזקת 5 מודולו 7 -> 5

• 3 בחזקת 6 מודולו 7 -> 1

בדוגמה שלנו, ניקח את הבסיס להיות 4 ואת השדה להיות Z17 (4 אכן יוצר את כל המספרים בין 1 ל-16 בשדה F*17).

לאחר שבוב ואליס מסכימים על המספרים (4 ו-17) כל אחד מהם בוחר מספר סודי לעצמו, נניח שאליס בחרה את המספר a = 3 ובוב בחר את המספר b = 6. 

אליס מבצעת את החישוב הבא כדי להכין את המסר שהיא מעבירה לבוב.

A = g^a mod p  -(הבסיס - 4 בחזקת המספר של אליס - 3 מודולו 17)

A = 4^3 mod 17

A = 64 mod 17

A = 13

נעשה את אותו דבר עם המספר של בוב:

B = 4^6 mod 17

B = 4096 mod 17

B = 16

אליס שולחת לבוב את A ובוב שולח לאליס את B. כעת כל אחד מהם ישיג את המספר הסודי s באמצעות המסר מהשני והמספר הסודי שלהם:

החישוב של אליס:

s = B^a mod p

s = 16^3 mod 17

s = 4,096 mod 17

s = 16

החישוב של בוב:

s = A^b mod p

s = 13^6 mod 17

s = 4,826,809 mod 17

s = 16

כמו שאתם יכולים לראות, שני הצדדים סיימו עם אותה תוצאה s = 16. אך לכל מי שראה את התעבורה ביניהם אין את כל הנתונים על מנת לחשב בזמן סביר את המספר הזה. B ו-s יצאו אותו דבר במקרה הזה אבל זה רק צירוף מקרים, לרוב כאשר נשתמש במספרים גדולים מאוד המספרים לא יצאו אותו דבר באלגוריתם.

מדוע האלגוריתם באמת מאובטח?

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

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