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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

Diffie-hellman.png

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

היסטוריה[עריכת קוד מקור | עריכה]

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

תיאור הפרוטוקול[עריכת קוד מקור | עריכה]

הכנה חד-פעמית: המשתתפים בפרוטוקול אליס ובוב מסכמים ביניהם באופן גלוי על מספר ראשוני p גדול כך שפתרון בעיית לוגריתם דיסקרטי בחבורה הכפלית \mathbb{Z}^{*}_p יהיה קשה. ויוצר g של \mathbb{Z}^{*}_p (דוגמה בהמשך). אליס בוחרת ערך אקראי סודי 0<x<p-1 ומחשבת את r=g^x\text{ mod }p אותו היא שולחת לבוב. באופן דומה בוב בוחר ערך אקראי סודי 0<y<p-1 ומחשב את s=g^y\text{ mod }p אותו הוא שולח לאליס. בהינתן x ו-s אליס מחשבת את המפתח המשותף K=s^x\text{ mod }p\equiv g^{yx}\text{ (mod }p) וכן בוב באמצעות הערכים y ו-r, מחשב את K=r^y\text{ mod }p\equiv g^{xy}\text{ (mod }p). כעת הם משתפים ביניהם את המפתח הסודי \ K בצורה בטוחה.

אליס ובוב שידרו זה לזה את הערכים r=g^x ו-s=g^y (מודולו p) בהתאמה. המידע שהשיגה המצותתת איב (ראה תרשים) שהאזינה למהלכי הפרוטוקול, כולל את הערכים: g,p,r,s. כאשר הערכים x או y לא שודרו כלל. כדי לחשוף את המפתח המשותף עליה לחשב את K\equiv r^y\equiv s^x\equiv g^{xy}\text{ (mod }p). בעיה זו (חישוב g^{xy} מתוך g^x ו- g^y מודולו p), נקראת בעיית דיפי-הלמן (להלן), אם הערכים נבחרו בקפידה, הדיעה הרווחת היא שאין לה פתרון קל.

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

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

  1. \ \mbox{A} \longrightarrow \mbox{B}: \ \ r=g^x \ \mbox{ mod }p \ \
  2. \ \mbox{A} \longleftarrow \mbox{B}: \ \ s=g^y \ \mbox{ mod }p \ \

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

  1. A בוחר שלם אקראי סודי \ x כאשר \ 1 \le x \le p - 2 ושולח ל-B את מסר 1 לעיל.
  2. B בוחר שלם אקראי סודי \ y כאשר \ 1 \le y \le p - 2 ושולח ל-A את מסר 2 לעיל.
  3. B מקבל את r ומחשב את המפתח המשותף K=r^{y}{\mbox{ mod }}p.
  4. A מקבל את s ומחשב את המפתח המשותף K=s^{x}{\mbox{ mod }}p.

כאמור כל הפעולות מבוצעות מודולו המספר הראשוני \ p. החישוב המודולרי הכרחי לצורך בטיחות הפרוטוקול כיוון שבלעדיו, אליס משדרת את השלם g^x, כאשר g ידוע לכל. במקרה הזה בעיית הלוגריתם הדיסקרטי קלה מאוד לפתרון, מכיוון שמספר הספרות העשרוניות הדרושות לכתיבת g^x קרוב למספר הספרות של g כשהוא מוכפל בנעלם \ x. כדי למצוא את \ x די לחלק את מספרי הספרות זה בזה. מאידך חישוב \ x מתוך השארית לאחר חילוק \ g^x ב-\ p אינו קל.

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

פרוטוקול דיפי-הלמן בעקום אליפטי נקרא בקיצור 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.

המשתתפת אליס בוחרת מפתח סודי שהוא שלם אקראי x והמפתח הציבורי שלה יהיה R=xP (תוצאת כפל סקלארי של הנקודה P ב-x). בוב בוחר מפתח סודי וציבורי y,S באותה דרך. כעת אם הם רוצים לשתף ביניהם את הסוד K הם פועלים כדלהלן:

  1. אליס שולחת לבוב את הנקודה R.
  2. בוב שולח לאליס את הנקודה S.
  3. אליס מחשבת את המפתח המשותף שהוא הנקודה בעקום K=xS.
  4. בוב מחשב את המפתח המשותף באופן דומה K=yR.

הפרוטוקול נכון כי מתקיים K=xS=xyP=yxP=yR. לכן הנקודה K בעקום האליפטי היא נקודה סודית המשותפת רק לשניהם, אותה הם יכולים להמיר למפתח הצפנה.

בעיית דיפי-הלמן[עריכת קוד מקור | עריכה]

בעיית דיפי-הלמן - 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). בעיקרון שיטת כוח גס, דהיינו ניסוי כל האפשרויות עד למציאת פתרון אינה יעילה. קיימים אלגוריתמים מהירים שמוצאים פתרון בזמן קצר יותר מכוח גס. ניתן למנות כמה מהם: תחשיב אינדקסים, שיטת פולרד, אלגוריתם baby step giant step של שנקס אלגוריתם נפת שדה המספרים ועוד. האחרון נחשב לאלגוריתם הטוב ביותר לפתרון בעיית הלוגריתם הדיסקרטי והוא פועל בזמן ריצה תת-מעריכי, מסדר גודל של 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.

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

דוגמה[עריכת קוד מקור | עריכה]

כאמור בפועל ביטחון הפרוטוקול תלוי בכך שהראשוני p יהיה גדול מאוד. לשם המחשה בלבד נניח כי הוסכם על המספר הראשוני p=1187 ויוצר g=429 של החבורה הכפלית \mathbb{Z}^*_{1187}. בחירת יוצר קלה ביותר אם ידועים הגורמים הראשוניים של סדר החבורה במקרה זה p-1=1186. היות ש-1187=2\cdot 593+1 כאשר 593 ראשוני. לפי תורת החבורות היוצר יכול להיות כל ערך המקיים: g^{r_i}\text{ (mod }p-1)\ne 1 עבור כל הגורמים r_i של p-1. כלומר 429^{2}=211 וכן 429^{593}=429 מודולו 1186, על כן 429 יכול לשמש כיוצר (ההסתברות שמספר אקראי יצור את החבורה היא \phi(n)/ n (הפונקציה \phi(n) היא פונקציית אוילר). במקרה זה היות שהגורמים הם p-1=2q מזה נובע ש-\phi(p-1)=q-1, לכן ההסתברות שמספר מסויים הוא יוצר היא \textstyle\frac{q-1}{2q}\approx\frac{1}{2}).

אליס בוחרת ערך סודי x=546 ומחשבת את r=429^{546}\text{ mod }1187=574.
בוב בוחר ערך סודי y=358 ומחשב את s=429^{358}\text{ mod }1187=101.
מסר 1: אליס שולחת לבוב את המספר 574.
מסר 2: בוב שולח לאליס את המספר 101.
אליס מחשבת את המפתח המשותף:
K=101^{546}\text{ mod }1187=730,
בוב מחשב את המפתח המשותף:
K=574^{358}\text{ mod }1187=730.
כעת בידי שניהם מפתח K=730.

הכללות[עריכת קוד מקור | עריכה]

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


מגבלות[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]