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

From האנציקלופדיה היהודית
Jump to navigation Jump to search

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

הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K\equiv A^b\text{ mod }p\equiv (g^a\text{ mod }p)^b\text{ mod }p\equiv} הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^{ab}\text{ mod }p\equiv (g^b\text{ mod }p)^a\equiv B^a\text{ mod }p}

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

היסטוריה ורקע[edit | edit source]

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

תיאור הפרוטוקול[edit | edit source]

הכנה חד-פעמית: להלן תיאור הפרוטוקול בשדה ראשוני. המשתתפים בפרוטוקול אליס ובוב מסכמים ביניהם באופן גלוי על מספר ראשוני הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} גדול כך שפתרון בעיית הלוגריתם הבדיד בחבורה הכפלית הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}^{*}_p} יהיה קשה. ויוצר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} של הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}^{*}_p} (דוגמה בהמשך). אם הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} ראשוני לשדה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_p} יש הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(p-1)} יוצרים כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} היא פונקציית אוילר. בחירת יוצר יכולה להתבצע תוך דגימה אקראית והסיכויים גבוהים למצוא יוצר תוך מספר ניסיונות קצר. אליס בוחרת ערך אקראי סודי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0<a<p-1} ומחשבת את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=g^a\text{ mod }p} אותו היא שולחת לבוב. באופן דומה בוב בוחר ערך אקראי סודי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0<b<p-1} ומחשב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=g^b\text{ mod }p} אותו הוא שולח לאליס. בהינתן הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} אליס מחשבת את המפתח המשותף הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=B^a\equiv(g^{b})^a\text{ (mod }p)} וכן בוב באמצעות הערכים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , מחשב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=A^b\equiv(g^{a})^b\text{ (mod }p)} . כעת הם משתפים ביניהם את המפתח הסודי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ K} בצורה בטוחה.

אליס ובוב שידרו זה לזה את הערכים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=g^a} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=g^b} (מודולו הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} ) בהתאמה. המידע שהשיגה המצותתת איב שהאזינה למהלכי הפרוטוקול (כמתואר בתרשים), כולל את הערכים: הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g,p,A,B} . כאשר הערכים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} או הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} לא שודרו כלל. כדי לחשוף את המפתח המשותף עליה לחשב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K\equiv A^b\equiv B^a\equiv g^{ab}\text{ (mod }p)} . בעיה זו (חישוב הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^{ab}} מתוך הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^a} ו- הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^b} מודולו הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} ), נקראת בעיית דיפי-הלמן (להלן), אם הערכים נבחרו בקפידה, הדעה הרווחת היא שאין לה פתרון קל.

כמו כן, אם איב מסוגלת לחשב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} מתוך הערך הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^a} , היא יכולה לחשוף את ה'סוד' של אליס ובוב. חישוב הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} מתוך הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^a} נקרא בעיית הלוגריתם הבדיד ואף היא נחשבת לבעיה קשה. מי שיכול לפתור את בעיית הלוגריתם הבדיד באופן יעיל, בוודאי יכול לפתור גם את בעיית דיפי-הלמן באופן יעיל. ההפך אינו ידוע, טרם נמצאה הוכחה לכך שהיכולת לפתור את בעיית דיפי-הלמן שקולה ליכולת לפתור את בעיית הלוגריתם הבדיד.

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

  1. הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{Alice} \longrightarrow \mbox{Bob}: \ \ A=g^a \ \mbox{ mod }p \ \ }
  2. הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{Alice} \longleftarrow \mbox{Bob}: \ \ B=g^b \ \mbox{ mod }p \ \ }

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

  1. אליס בוחרת שלם אקראי סודי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1 \le a \le p - 2} ושולחת לבוב את מסר 1 לעיל.
  2. בוב בוחר שלם אקראי סודי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b} כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1 \le b \le p - 2} ושולח לאליס את מסר 2 לעיל.
  3. בוב מקבל את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ומחשב את המפתח המשותף הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=A^b \mbox{ mod }p} .
  4. אליס מקבלת את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} ומחשבת את המפתח המשותף הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=B^a \mbox{ mod }p} .

כאמור כל הפעולות מבוצעות מודולו המספר הראשוני הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} . החישוב המודולרי הכרחי לצורך בטיחות הפרוטוקול כיוון שבלעדיו, אליס משדרת את השלם הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^a} , כאשר ידוע לכל. במקרה הזה בעיית הלוגריתם הבדיד קלה מאוד לפתרון, מכיוון שמספר הספרות העשרוניות הדרושות לכתיבת קרוב למספר הספרות של כשהוא מוכפל בנעלם . כדי למצוא את די לחלק את מספרי הספרות זה בזה. מאידך חישוב מתוך השארית לאחר חילוק ב- אינו קל.

דוגמה במספרים קטנים[edit | edit source]

כאמור בפועל ביטחון הפרוטוקול תלוי בכך שהראשוני יהיה גדול מאוד. לשם המחשה בלבד נניח כי הוסכם על המספר הראשוני ויוצר של החבורה הכפלית . בחירת יוצר קלה ביותר אם ידועים הגורמים הראשוניים של סדר החבורה במקרה זה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1=1186} . היות ש-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1187=2\cdot 593+1} כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 593} ראשוני. לפי תורת החבורות היוצר יכול להיות כל ערך המקיים: הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^{r_i}\text{ (mod }p-1)\ne 1} עבור כל הגורמים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_i} של הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1} . כלומר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 429^{2}=211} וכן הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 429^{593}=429} מודולו הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1186} , על כן הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 429} יכול לשמש כיוצר (ההסתברות שמספר אקראי יצור את החבורה היא הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(n)/ n} (הפונקציה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(n)} היא פונקציית אוילר). במקרה זה היות שהגורמים הם הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1=2q} מזה נובע ש-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(p-1)=q-1} , לכן ההסתברות שמספר מסוים הוא יוצר היא הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle\frac{q-1}{2q}\approx\frac{1}{2}} ).

אליס בוחרת ערך סודי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=546} ומחשבת את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=429^{546}\text{ mod }1187=574} .
בוב בוחר ערך סודי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b=358} ומחשב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=429^{358}\text{ mod }1187=101} .
מסר 1: אליס שולחת לבוב את המספר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 574} .
מסר 2: בוב שולח לאליס את המספר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 101} .
אליס מחשבת את המפתח המשותף:
הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=101^{546}\text{ mod }1187=730} ,
בוב מחשב את המפתח המשותף:
הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=574^{358}\text{ mod }1187=730} .
כעת בידי שניהם מפתח הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=730} .

פרוטוקול דיפי-הלמן בעקום אליפטי[edit | edit source]

פרוטוקול דיפי-הלמן בעקום אליפטי נקרא בקיצור ECDH אנלוגי לפרוטוקול דיפי הלמן המתואר לעיל. נתונים פרמטרי התחום של העקום לפי הגדרות התקן: הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (q,a,b,P,n,h)} , העקום האליפטי הוא הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(\mathbb{F}_q)} כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} הסדר של השדה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} וכן הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b} מקדמים של משוואת העקום, הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} היא נקודת הבסיס, הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} הסדר הראשוני של נקודת הבסיס, הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} פקטור משלים כך שמתקיים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle n=\frac{|E|}{h}} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |E|} מייצג את מספר הנקודות בעקום הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} .

המשתתפת אליס בוחרת מפתח סודי שהוא שלם אקראי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} והמפתח הציבורי שלה יהיה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=aP} (תוצאת כפל סקלארי של הנקודה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} ב-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} ). בוב בוחר מפתח סודי וציבורי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b,B=bP)} באותה דרך. כעת אם הם רוצים לשתף ביניהם את הסוד הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} הם פועלים כדלהלן:

  1. אליס שולחת לבוב את הנקודה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} .
  2. בוב שולח לאליס את הנקודה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} .
  3. אליס מחשבת את המפתח המשותף שהוא הנקודה בעקום הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=aB} .
  4. בוב מחשב את המפתח המשותף באופן דומה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=bA} .

הפרוטוקול נכון כי מתקיים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=aB=a(bP)=baP=b(aP)=bA} . לכן הנקודה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} בעקום האליפטי היא נקודה סודית המשותפת רק לשניהם, אותה הם יכולים להמיר למפתח הצפנה.

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

  1. המספר הראשוני הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q=3851} ,
  2. מקדמי משוואת העקום הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=324, b=1287} ,
  3. העקום האליפטי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E:Y^2=X^3+324X+1287} ,
  4. והנקודה הציבורית הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P=(920,303)} מעל הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(\mathbb{F}_{3851})} .

לצורך ההתקשרות ביניהם נניח שאליס בחרה את המפתח הסודי: הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=1194} ובוב בחר את המפתח הסודי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y=1759} , כעת לפי כללי האריתמטיקה בעקום האליפטי אליס מחשבת את:

הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=1194P=(2067,2178)\in E(\mathbb{F}_{3851})} ,

בוב מחשב את:

הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=1759P=(3684,3125)\in E(\mathbb{F}_{3851})} .

אליס שולחת לבוב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ובוב שולח לאליס את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} . לבסוף, אליס מחשבת את:

הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle aB=1194\cdot (3684,3125)=(3347,1242)\in E(\mathbb{F}_{3851})} ,

בוב מחשב את:

הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle bA=1759\cdot (2067,2178)=(3347, 1242)\in E(\mathbb{F}_{3851})} .

כעת הם משתפים ביניהם את הנקודה הסודית הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=(3347,1242)} . מקובל להתעלם מהקואורדינטה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} ולקחת רק את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=3347} כערך סודי משותף.

בעיית דיפי-הלמן[edit | edit source]

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

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

נתונים ראשוני הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol p} , יוצר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol g} של החבורה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol\mathbb{Z}^{*}_p} והערכים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol g^x} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol g^y} , מצא את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol g^{xy}} ?

באופן פורמלי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} הוא יוצר של חבורה ציקלית (מעל שדה סופי מסדר ראשוני, שדה בינארי מורחב או מעל עקום אליפטי) והערכים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} שלמים אקראיים כלשהם.

ביטחון[edit | edit source]

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

  • שדה סופי מסדר ראשוני גדול הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}^{*}_p}
  • שדה בינארי מורחב הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{2^m}} . כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} גדול.
  • עקום אליפטי מעל שדה ראשוני.

הוכח שהקושי בפתרון בעיית הלוגריתם הבדיד תלוי בגורם הראשוני הגדול ביותר של סדר החבורה (אם סדר החבורה ראשוני, הכוונה לסדר החבורה פחות 1). בעיקרון שיטת כוח גס, דהיינו ניסוי כל האפשרויות עד למציאת פתרון אינה יעילה. קיימים אלגוריתמים מהירים שמוצאים פתרון בזמן קצר יותר מכוח גס. ניתן למנות כמה מהם: תחשיב אינדקסים, אלגוריתם רו של פולרד, אלגוריתם צעד-גדול צעד-קטן של דיויד שנקס, אלגוריתם נפת שדה המספרים ועוד. האחרון נחשב לאלגוריתם הטוב ביותר לפתרון בעיית הלוגריתם הבדיד והוא פועל בזמן ריצה תת-מעריכי, מסדר גודל של הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_q[1/3,(64/9)^{1/3}]} . על כל פנים הממצאים בתחום עדיין לא שלמים.

תקן SP 800-57 של NIST (גרסה 3 - יולי 2012) משווה בין החוזק של אלגוריתמים סימטריים ואלגוריתמים אסימטריים המקבילים להם. המלצות התקן גורסות שהראשוני הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} צריך להיות בגודל בין 1024 סיביות ל-15,360 סיביות בהתאם לחוזק אלגוריתמים סימטריים המקבילים (בין 80 סיביות ל-256 סיביות). למשל להשגת חוזק זהה לאלגוריתם AES עם מפתח בגודל 128 סיביות יש לבחור ראשוני באורך 3,072 סיביות. מעל קבוצת הנקודות בעקום אליפטי התקן ממליץ על טווח אורכים בין 160 ל-512 סיביות. הסיבה היא שהאלגוריתמים הטובים ביותר הידועים, אינם ישימים בעקום אליפטי.

פרוטוקול דיפי הלמן ניתן לשינוי באופן שיספק גם אימות זהויות, על ידי קביעת הערכים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^x} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^y} מודולו הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} כמפתחות ציבוריים של כל משתמש ואז על ידי חתימה על המפתחות (באמצעות סרטיפיקט) ניתן להבטיח את שייכותם לכל משתמש בהתאמה. פרוטוקול MQV הוא דוגמה טובה להרחבה של פרוטוקול דיפי הלמן המספקת גם אימות זהויות עקיף.

פרוטוקול דיפי הלמן אינו מבטיח למשתתפים הגנה על אופן בחירת המפתח ואינו מונע שליטה חד צדדית. למעשה אחד הצדדים יכול בקלות להשפיע על אופן בחירת המפתח על ידי בחירת הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} או הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} קטנים במכוון. לדוגמה אם המעריך הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = 0} המפתח הסודי המשותף הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} יהיה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g^y} . באופן דומה הפרוטוקול פגיע במיוחד להתקפה הבאה: אם הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p = Rq + 1} (כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R} קטן כגון הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R = 2} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} ראשוני), אזי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h= g^q = g^{(p - 1)/R}} הוא מסדר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R} (ואז הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h= -1} ). תוקף אקטיבי יכול להחליף את המסרים ששלחו המשתתפים בערכים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (g^x)^q} וכן הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (g^y)^q} בהתאמה, בכך לגרום למפתח המשותף להיות הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K = g^{xyq} = h^{xy}} . וכתוצאה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ K} יהיה בטווח הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1} או הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ -1} .

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

התקפת אדם באמצע[edit | edit source]

Postscript-viewer-shaded.png ערך מורחב – התקפת אדם באמצע

נניח שהמצותת איב אינה רק צופה פאסיבית אלא ביכולתה ליירט ולשנות מסרים בעודם בדרכם ליעדם מבלי שהמתקשרים הלגיטימיים יבחינו בכך. מצב כזה אפשרי בכל ערוץ תקשורת שאינו מאומת באופן קריפטוגרפי. במקרה כזה איב יכולה לבצע התקפה הידועה בשם התקפת האדם באמצע באופן הבא: כזכור אליס מעוניינת לשלוח לבוב את המפתח הציבורי שלה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=g^a} (כאשר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} הוא המפתח הפרטי) ובוב מעוניין לשלוח לאליס את המפתח הציבורי שלו הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=g^b} . איב תחילה מכינה מפתחות משלה, נניח הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E=g^e} , ואז כאשר הם מתקשרים ביניהם היא מיירטת את המסרים מאליס לבוב ומבוב לאליס ומחליפה אותם ב-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} . כעת איב משתפת עם אליס ועם בוב בנפרד את המפתחות הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^e} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B^e} בהתאמה בעוד שהם מאמינים כי הם שיתפו את המפתחות הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B^a} ו-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^b} בהתאמה, כמתואר בתרשים.

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

כעת אם אליס או בוב ישלחו זה לזה מסר מוצפן כלשהו עם מפתח ההצפנה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E^a} או הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E^b} בהתאמה, איב יכולה ליירטו ולפענחו עם המפתח הפרטי המתאים שברשותה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^e} או הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B^e} בהתאמה. יתרה מזו, כדי שהמתקשרים הלגיטמיים לא יבחינו במתרחש היא חוזרת ומצפינה את המסר עם המפתח הפרטי שהיא שיתפה עם הצד השני ושולחת אותו ליעדו כאילו כלום לא קרה. כדי לסכל התקפה כזו על המתקשרים לאמת בדרך כלשהי את המסרים העוברים ביניהם, גם כדי להבטיח כי הגיעו מהמקור שהם סבורים וכן שהמסרים לא שונו באופן זדוני בדרכם ליעדם. מסיבה זו אימות והבטחת שלמות הם נושאים קריטיים באבטחת מידע. פרוטוקול MQV מספק מענה חלקי לבעיה. אפשר כמובן לחתום על כל המסרים עם החתימה הדיגיטלית המתאימה של כל צד.

הכללות[edit | edit source]

במקום לעבוד בחבורה הכפלית של המספרים מודולו הראשוני הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} (שהיא חבורת אוילר של הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} ), אפשר לעבוד בכל חבורה ציקלית אחרת. השותפים צריכים לפרסם את החבורה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} ואת האיבר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} , ואז לחזור על התהליך כמתואר לעיל. הבעיות הניצבות בפני המאזין הסמוי נקראות 'בעיית דיפי-הלמן' ו'בעיית הלוגריתם הבדיד' בחבורה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , בהתאמה.


ראו גם[edit | edit source]

קישורים חיצוניים[edit | edit source]

ערך זה מוגש באדיבות ויקיפדיה העברית. (הדף המקורי, רשימת התורמים)
הערך בוויקיפדיה קטן מערך זה ב -675 תווים

לעדכון מוויקיפדיה, לחץ כאן.

NivdakVeushar.png