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

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

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

${\begin{aligned}K&\equiv A^{b}{\bmod {p}}\equiv (g^{a}{\bmod {p}})^{b}{\bmod {p}}\\&\equiv g^{ab}{\bmod {p}}\equiv (g^{b}{\bmod {p}})^{a}\equiv B^{a}{\bmod {p}}\end{aligned}}$

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

היסטוריה ורקע

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

תיאור הפרוטוקול

הכנה חד־פעמית: להלן תיאור הפרוטוקול בשדה ראשוני. המשתתפים בפרוטוקול אליס ובוב מסכמים ביניהם באופן גלוי על מספר ראשוני $p$ גדול כך שפתרון בעיית הלוגריתם הבדיד בחבורה הכפלית $\mathbb {F} _{p}^{*}$ יהיה קשה. ויוצר $g$ של $\mathbb {F} _{p}^{*}$ (דוגמה בהמשך). אם $p$ ראשוני לשדה $\mathbb {F} _{p}$ יש $\phi (p-1)$ יוצרים כאשר $\phi$ היא פונקציית אוילר. בחירת יוצר יכולה להתבצע תוך דגימה אקראית והסיכויים גבוהים למצוא יוצר תוך מספר ניסיונות קצר. אליס בוחרת ערך אקראי סודי $a$ כאשר $0<a<p-1$ ומחשבת את $A=g^{a}{\bmod {p}}$ אותו היא שולחת לבוב. באופן דומה בוב בוחר ערך אקראי סודי $b$ כאשר $0<b<p-1$ ומחשב את $B=g^{b}{\bmod {p}}$ אותו הוא שולח לאליס. בהינתן $a,B$ אליס מחשבת את המפתח המשותף $K=B^{a}\equiv (g^{b})^{a}\,(\!{\bmod {p}})$ וכן בוב באמצעות הערכים $b,A$, מחשב את $K=A^{b}\equiv (g^{a})^{b}\,(\!{\bmod {p}})$. כעת הם משתפים ביניהם את המפתח הסודי $K$ בצורה בטוחה.

אליס ובוב שידרו זה לזה את הערכים $A=g^{a},B=g^{b}$ (מודולו $p$) בהתאמה. המידע שהשיגה המצותתת איב שהאזינה למהלכי הפרוטוקול (כמתואר בתרשים), כולל את הערכים: $g,p,A,B$. כאשר הערכים $a$ או $b$ לא שודרו כלל. כדי לחשוף את המפתח המשותף עליה לחשב את $K\equiv A^{b}\equiv B^{a}\equiv g^{ab}\,(\!{\bmod {p}})$. בעיה זו (חישוב $g^{ab}$ מתוך $g^{a},g^{b}$ מודולו $p$), נקראת בעיית דיפי־הלמן (להלן), אם הערכים נבחרו בקפידה, הדעה הרווחת היא שאין לה פתרון קל.

כמו כן, אם איב מסוגלת לחשב את $a$ מתוך הערך $g^{a}$, היא יכולה לחשוף את ה'סוד' של אליס ובוב. חישוב $a$ מתוך $g^{a}$ נקרא בעיית הלוגריתם הבדיד ואף היא נחשבת לבעיה קשה. מי שיכול לפתור את בעיית הלוגריתם הבדיד באופן יעיל, בוודאי יכול לפתור גם את בעיית דיפי־הלמן באופן יעיל. ההפך אינו ידוע, טרם נמצאה הוכחה לכך שהיכולת לפתור את בעיית דיפי־הלמן שקולה ליכולת לפתור את בעיית הלוגריתם הבדיד.

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

1. ${\text{Alice}}\longrightarrow {\text{Bob}}:\quad A=g^{a}{\bmod {p}}$
2. ${\text{Alice}}\longleftarrow {\text{Bob}}:\quad B=g^{b}{\bmod {p}}$

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

1. אליס בוחרת שלם אקראי סודי $a$ כאשר $1\leq a\leq p-2$ ושולחת לבוב את מסר 1 לעיל.
2. בוב בוחר שלם אקראי סודי $\ b$ כאשר $1\leq b\leq p-2$ ושולח לאליס את מסר 2 לעיל.
3. בוב מקבל את $A$ ומחשב את המפתח המשותף $K=A^{b}{\bmod {p}}$.
4. אליס מקבלת את $B$ ומחשבת את המפתח המשותף $K=B^{a}{\bmod {p}}$.

כאמור כל הפעולות מבוצעות מודולו המספר הראשוני $p$. החישוב המודולרי הכרחי לצורך בטיחות הפרוטוקול כיוון שבלעדיו, אליס משדרת את השלם $g^{a}$, כאשר $g$ ידוע לכל. במקרה הזה בעיית הלוגריתם הבדיד קלה מאוד לפתרון, מכיוון שמספר הספרות העשרוניות הדרושות לכתיבת $g^{a}$ קרוב למספר הספרות של $g$ כשהוא מוכפל בנעלם $a$. כדי למצוא את $a$ די לחלק את מספרי הספרות זה בזה. מאידך חישוב $a$ מתוך השארית לאחר חילוק $g^{a}$ ב־$p$ אינו קל.

דוגמה במספרים קטנים

לצורך הדגמה בלבד, נניח שהוסכם על המספר הראשוני $p=1187$ ויוצר $g=429$ של החבורה הכפלית $\mathbb {F} _{1187}^{*}$. בחירת יוצר היא מלאכה קלה כפי שיוסבר להלן. מהלכי הפרוטוקול הם:

אליס בוחרת ערך סודי $a=546$ ומחשבת את $A=429^{546}{\bmod {1}}187=574$.

בוב בוחר ערך סודי $b=358$ ומחשב את $B=429^{358}{\bmod {1}}187=101$.

מסר 1: אליס שולחת לבוב את המספר $574$.

מסר 2: בוב שולח לאליס את המספר $101$.

אליס מחשבת את המפתח המשותף:

$K=101^{546}{\bmod {1}}187=730$,

בוב מחשב את המפתח המשותף:

$K=574^{358}{\bmod {1}}187=730$

כעת בידי שניהם מפתח $K=730$.

מציאת יוצר של החבורה הציקלית

בחירת יוצר קלה ביותר אם ידועים הגורמים הראשוניים של סדר החבורה במקרה של הדוגמה לעיל $p-1=1186$. היות ש־$1187=2\cdot 593+1$ כאשר $593$ ראשוני. לפי תורת החבורות היוצר יכול להיות כל ערך המקיים: $g^{r_{i}}{\bmod {p}}-1)\neq 1$ עבור כל הגורמים $r_{i}$ של $p-1$. כלומר $429^{2}=211$ וכן $429^{593}=429$ מודולו $1186$, על כן $429$ יכול לשמש כיוצר (ההסתברות שמספר אקראי יצור את החבורה היא ${\frac {\phi (n)}{n}}$ (כאשר $\phi (n)$ פונקציית אוילר). במקרה זה היות שהגורמים הם $p-1=2q$ מזה נובע כי $\phi (p-1)=q-1$, לכן ההסתברות שמספר מסוים הוא יוצר היא ${\frac {q-1}{2q}}\approx {\frac {1}{2}}$).

פרוטוקול דיפי־הלמן בעקום אליפטי

פרוטוקול דיפי־הלמן בעקום אליפטי נקרא בקיצור ECDH אנלוגי לפרוטוקול דיפי הלמן המתואר לעיל. נתונים פרמטרי התחום של העקום לפי הגדרות התקן: $(q,a,b,P,n,h)$, העקום האליפטי הוא $E(\mathbb {F} _{q})$ כאשר $q$ הסדר של השדה $\mathbb {F} _{q}$ וכן $a,b$ מקדמים של משוואת העקום, $P$ היא נקודת הבסיס, $n$ הסדר הראשוני של נקודת הבסיס, $h$ פקטור משלים כך שמתקיים $\textstyle n={\frac {|E|}{h}}$ ו־$|E|$ מייצג את מספר הנקודות בעקום $E$.

המשתתפת אליס בוחרת מפתח סודי שהוא שלם אקראי $a$ והמפתח הציבורי שלה יהיה $A=aP$ (תוצאת כפל סקלארי של הנקודה $P$ ב־$a$). בוב בוחר מפתח סודי וציבורי $(b,B=bP)$ באותה דרך. כעת אם הם רוצים לשתף ביניהם את הסוד $K$ הם פועלים כדלהלן:

1. אליס שולחת לבוב את הנקודה $A$.
2. בוב שולח לאליס את הנקודה $B$.
3. אליס מחשבת את המפתח המשותף שהוא הנקודה בעקום $K=aB$.
4. בוב מחשב את המפתח המשותף באופן דומה $K=bA$.

הפרוטוקול נכון כי מתקיים $K=aB=a(bP)=baP=b(aP)=bA$. לכן הנקודה $K$ בעקום האליפטי היא נקודה סודית המשותפת רק לשניהם, אותה הם יכולים להמיר למפתח הצפנה.

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

1. המספר הראשוני $q=3851$,
2. מקדמי משוואת העקום $a=324,b=1287$,
3. העקום האליפטי $E:Y^{2}=X^{3}+324X+1287$,
4. והנקודה הציבורית $P=(920,303)$ מעל $E(\mathbb {F} _{3851})$.

לצורך ההתקשרות ביניהם נניח שאליס בחרה את המפתח הסודי: $a=1194$ ובוב בחר את המפתח הסודי $y=1759$, כעת לפי כללי האריתמטיקה בעקום האליפטי אליס מחשבת את:

$A=1194P=(2067,2178)\in E(\mathbb {F} _{3851})$,

בוב מחשב את:

$B=1759P=(3684,3125)\in E(\mathbb {F} _{3851})$.

אליס שולחת לבוב את $A$ ובוב שולח לאליס את $B$. לבסוף, אליס מחשבת את:

$aB=1194\cdot (3684,3125)=(3347,1242)\in E(\mathbb {F} _{3851})$,

בוב מחשב את:

$bA=1759\cdot (2067,2178)=(3347,1242)\in E(\mathbb {F} _{3851})$.

כעת הם משתפים ביניהם את הנקודה הסודית $K=(3347,1242)$. מקובל להתעלם מהקואורדינטה $y$ ולקחת רק את $a=3347$ כערך סודי משותף.

בעיית דיפי־הלמן

בעיית דיפי־הלמן - Diffie-Hellman problem בקיצור DHP היא בעיה מתמטית קשה שהועלתה לראשונה על ידי ויטפילד דיפי ומרטין הלמן בהקשר של קריפטוגרפיה. הסיבה לאטרקטיביות הבעיה היא העובדה שהיא מהווה על פניה, פונקציה חד-כיוונית. ויש עניין רב בקריפטוגרפיה בפונקציות חד־כיווניות כיוון שהן הבסיס המתמטי למרבית האלגוריתמים האסימטריים. פונקציה חד־כיוונית מאפשרת ביצוע תהליך הצפנה שהוא קל יחסית בכיוון אחד אבל קשה בכיוון ההפוך, דהיינו פענוח. אלא אם כן קיים מידע נסתר בידי המפענח שמקל על מלאכתו. המידע הנסתר קרוי מפתח פענוח או מפתח פרטי.

בעיית דיפי־הלמן היא כדלהלן:

נתונים ראשוני ${\boldsymbol {p}}$, יוצר ${\boldsymbol {g}}$ של החבורה ${\boldsymbol {\mathbb {Z} }}_{p}^{*}$ והערכים ${\boldsymbol {g}}^{x}$ ו־${\boldsymbol {g}}^{y}$, מצא את ${\boldsymbol {g}}^{xy}$?

באופן פורמלי $g$ הוא יוצר של חבורה ציקלית (מעל שדה סופי מסדר ראשוני, שדה בינארי מורחב או מעל עקום אליפטי) והערכים $x$ ו־$y$ שלמים אקראיים כלשהם.

ביטחון

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

• שדה סופי מסדר ראשוני גדול $\mathbb {Z} _{p}^{*}$
• שדה בינארי מורחב $\mathbb {F} _{2^{m}}$. כאשר $m$ גדול.
• עקום אליפטי מעל שדה ראשוני.

הוכח שהקושי בפתרון בעיית הלוגריתם הבדיד תלוי בגורם הראשוני הגדול ביותר של סדר החבורה (אם סדר החבורה ראשוני, הכוונה לסדר החבורה פחות 1). בעיקרון שיטת כוח גס, דהיינו ניסוי כל האפשרויות עד למציאת פתרון אינה יעילה. קיימים אלגוריתמים מהירים שמוצאים פתרון בזמן קצר יותר מכוח גס. ניתן למנות כמה מהם: תחשיב אינדקסים, אלגוריתם רו של פולרד, אלגוריתם צעד-קטן צעד-גדול של דייוויד שנקס, אלגוריתם נפת שדה המספרים ועוד. האחרון נחשב לאלגוריתם הטוב ביותר לפתרון בעיית הלוגריתם הבדיד והוא פועל בזמן ריצה תת־מעריכי, מסדר גודל של $L_{q}[1/3,(64/9)^{1/3}]$. על כל פנים הממצאים בתחום עדיין לא שלמים.

תקן SP 800-57 של NIST (גרסה 3 - יולי 2012) משווה בין החוזק של אלגוריתמים סימטריים ואלגוריתמים אסימטריים המקבילים להם. המלצות התקן גורסות שהראשוני $p$ צריך להיות בגודל בין 1024 סיביות ל־15,360 סיביות בהתאם לחוזק אלגוריתמים סימטריים המקבילים (בין 80 סיביות ל־256 סיביות). למשל להשגת חוזק זהה לאלגוריתם AES עם מפתח בגודל 128 סיביות יש לבחור ראשוני באורך 3,072 סיביות. מעל קבוצת הנקודות בעקום אליפטי התקן ממליץ על טווח אורכים בין 160 ל־512 סיביות. הסיבה היא שהאלגוריתמים הטובים ביותר הידועים, אינם ישימים בעקום אליפטי.

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

פרוטוקול דיפי הלמן אינו מבטיח למשתתפים הגנה על אופן בחירת המפתח ואינו מונע שליטה חד צדדית. למעשה אחד הצדדים יכול בקלות להשפיע על אופן בחירת המפתח על ידי בחירת $\ x$ או $\ y$ קטנים במכוון. לדוגמה אם המעריך $x=0$ המפתח הסודי המשותף $K$ יהיה $g^{y}$. באופן דומה הפרוטוקול פגיע במיוחד להתקפה הבאה: אם $\ p=Rq+1$ (כאשר $\ R$ קטן כגון $\ R=2$ ו־$q$ ראשוני), אזי $h=g^{q}=g^{(p-1)/R}$ הוא מסדר $\ R$ (ואז $h=-1$). תוקף אקטיבי יכול להחליף את המסרים ששלחו המשתתפים בערכים $\ (g^{x})^{q}$ וכן $\ (g^{y})^{q}$ בהתאמה, בכך לגרום למפתח המשותף להיות $K=g^{xyq}=h^{xy}$. וכתוצאה $\ K$ יהיה בטווח $\ 1$ או $\ -1$.

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

התקפת אדם באמצע

ערך מורחב – התקפת אדם באמצע

נניח שהמצותתת איב אינה רק צופה פאסיבית אלא ביכולתה ליירט ולשנות מסרים בעודם בדרכם ליעדם מבלי שהמתקשרים הלגיטימיים יבחינו בכך. מצב כזה אפשרי בכל ערוץ תקשורת שאינו מאומת באופן קריפטוגרפי. במקרה כזה איב יכולה לבצע התקפה הידועה בשם התקפת האדם באמצע באופן הבא: כזכור אליס מעוניינת לשלוח לבוב את המפתח הציבורי שלה $A=g^{a}$ (כאשר $a$ הוא המפתח הפרטי) ובוב מעוניין לשלוח לאליס את המפתח הציבורי שלו $B=g^{b}$. איב תחילה מכינה מפתחות משלה, נניח $E=g^{e}$, ואז כאשר הם מתקשרים ביניהם היא מיירטת את המסרים מאליס לבוב ומבוב לאליס ומחליפה אותם ב־$E$. כעת איב משתפת עם אליס ועם בוב בנפרד את המפתחות $A^{e}$ ו־$B^{e}$ בהתאמה בעוד שהם מאמינים כי הם שיתפו את המפתחות $B^{a}$ ו־$A^{b}$ בהתאמה, כמתואר בתרשים.

התקפת אדם באמצע על פרוטוקול דיפי־הלמן

כעת אם אליס או בוב ישלחו זה לזה מסר מוצפן כלשהו עם מפתח ההצפנה $E^{a}$ או $E^{b}$ בהתאמה, איב יכולה ליירטו ולפענחו עם המפתח הפרטי המתאים שברשותה $A^{e}$ או $B^{e}$ בהתאמה. יתרה מזו, כדי שהמתקשרים הלגיטמיים לא יבחינו במתרחש היא חוזרת ומצפינה את המסר עם המפתח הפרטי שהיא שיתפה עם הצד השני ושולחת אותו ליעדו כאילו כלום לא קרה. כדי לסכל התקפה כזו על המתקשרים לאמת בדרך כלשהי את המסרים העוברים ביניהם, גם כדי להבטיח כי הגיעו מהמקור שהם סבורים וכן שהמסרים לא שונו באופן זדוני בדרכם ליעדם. מסיבה זו אימות והבטחת שלמות הם נושאים קריטיים באבטחת מידע. פרוטוקול MQV מספק מענה חלקי לבעיה. אפשר כמובן לחתום על כל המסרים עם החתימה הדיגיטלית המתאימה של כל צד.

הכללות

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

ראו גם

• MQV
• חתימה דיגיטלית
• מפתח ציבורי
• החלפת מפתחות קוונטית

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

מדיה וקבצים בנושא פרוטוקול דיפי-הלמן בוויקישיתוף

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