חתימה דיגיטלית אל-גמאל

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

אלגוריתם חתימה דיגיטלית אל-גמאל (ElGamal) הנו מנגנון חתימה דיגיטלית אקראי (ראו להלן) עם נספח (פירושו שהחתימה מהווה תוספת נפרדת למסר ואינה מהווה הצפנה של המסר עצמו). האלגוריתם הוא פרי המצאתו של טאהר אל-גמאל קריפטוגרף אמריקאי ממוצא מצרי, שפרסם (ב-1986) את רעיון השימוש במפתח-פומבי ליצירת מנגנון חתימה דיגיטלית המבוסס על בעיית לוגריתם דיסקרטי, בהשראת עבודתם של דיפי והלמן ב-1976. למרות שהשימוש במנגנון המתואר בהמשך לא נפוץ מבחינה מעשית, הוא מהווה בסיס לפיתוחים דומים והוביל בין היתר להמצאת אלגוריתם DSA על ידי ה-NSA, שהוא למעשה וריאציה של אל-גמאל.

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

הכנת מפתחות עבור חתימת אל-גמאל:[עריכת קוד מקור | עריכה]

המשתמש מייצר מפתח ציבורי ומפתח פרטי מתאים כדלהלן:

  1. בוחר ראשוני אקראי גדול \ p ויוצר \ \alpha של החבורה הכפלית \ \mathbb{Z}^*_p.
  2. בוחר שלם אקראי \ a הנמוך מ- \ p-1.
  3. ומחשב את \ y = \alpha^a \mbox{ mod }p.

המפתח הציבורי הוא (p,\,\alpha,\,y) המפתח הפרטי הוא \ a.

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

תהליך החתימה על המסר \ m:

  1. בוחרים שלם אקראי סודי וחד-פעמי \ k הנמוך מ- \ p-1 כך שמתקיים \ \mbox{gcd}(k, p-1) = 1 (פירושו ש-\ k זר ל-\ p-1).
  2. מחשבים את \ r = \alpha^k \mbox{ mod }p.
  3. מחשבים את \ k^{-1} \mbox{ mod }(p-1).
  4. ומחשבים את \ s = k^{-1}(H(m)-a \cdot r) \mbox{ mod }(p-1).

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

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

תהליך אימות החתימה נעשה בעזרת המפתח הפומבי של החותם (p,\,\alpha,\,y).

  1. תחילה מוודאים כי \ r בטווח הנכון כלומר \ 0 < r < p.
  2. מחשבים את \ v_1 = y^r \cdot r^s \mbox{ mod }p.
  3. מחשבים את \ v_2 = \alpha^{H(m)} \mbox{ mod }p.

החתימה מתקבלת כאותנטית אך ורק אם \ v_1 = v_2.

הוכחה לנכונות תהליך האימות:[עריכת קוד מקור | עריכה]

אם מכפילים את שני צידי המשוואה בשורה 4 בתהליך החתימה לעיל ב-\ k, מקבלים:

\ ks \equiv H(m)-a \cdot r \quad (\mbox{mod }p-1).

לכן:

\ H(m) \equiv ar + ks \quad (\mbox{mod }p-1)

מזה נובע:

\ \alpha^{H(m)} \equiv \alpha^{ar+ks} \equiv (\alpha^a)^r \cdot r^s (\mbox{mod }p).

על כן: \ v_1 = v_2.

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

אם ינסה תוקף לזייף את החתימה על ידי בחירת \ k כזה המקיים \ r = \alpha^k \mbox{ mod }p. יהיה עליו לחשב גם את \ s = k^{-1}(H(m)-ar) \mbox{  mod }(p-1). בעיה זו שקולה לבעיית לוגריתם דיסקרטי שהיא כאמור בעיה מתמטית קשה. על כל פנים חובה לבחור \ k שונה עבור כל מסר משום שאם לא כך, יהיה אפשרי לחשוף את המפתח הפרטי של החותם כדלהלן:

אם נתונות המשוואות עבור המסרים \ m_1 ו-\ m_2 בהתאמה:

\ s_1 = k^{-1}(H(m_1)-ar) \mbox{ mod }(p-1) וכן,
\ s_2 = k^{-1}(H(m_2)-ar) \mbox{ mod }(p-1),

אזי \ (s_1-s_2) \cdot k \equiv H(m_1)-H(m_2) \  (\mbox{mod }p-1).

אם \ s_1 - s_2 לא שקול ל-\ 0 (מודולו \ p-1), יוצא ש-

\ k = (s_1-s_2)^{-1}(H(m_1)-H(m_2))\mbox{ mod }(p-1).

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

פונקציית גיבוב[עריכת קוד מקור | עריכה]

הצורך בפונקציית גיבוב נובע מהעבודה שמשוואת החתימה \ s = k^{-1}(m-ar)\mbox{ mod }(p-1) (ללא פונקציית הגיבוב) מאפשרת לתוקף לזייף את החתימה כדלהלן: הוא בוחר את זוג הערכים \ u,v כאשר \ v זר ל-\ p-1 ומחשב את \ r = \alpha^u \cdot y^v \mbox{ mod }p השקול ל- \ \alpha^u+av \mbox{ mod }p וכן \ s = -rv^{-1} \mbox{ mod }(p-1). במקרה כזה הערכים \ r,s יהיו חתימה תקפה עבור המסר \ m = su \mbox{ mod }(p-1) היות ש: \ (\alpha^m \cdot \alpha^{-ar})^{s^{-1}} = \alpha^u \cdot y^v = r. בכך הצליח למצוא מסר אחר שעבורו נוצרה חתימה זהה. פונקציית הגיבוב מבטלת בעיה זו.

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

שימוש באלגוריתם תחשיב האינדקסים כדי לתקוף את מנגנון החתימה אפשרי במקרה ש-\ p קטן. על כן רצוי ש-\ p יהיה גדול דיו כדי לסכל התקפה כזו (ההנחה היא כי סדר גודל של 2000 ספרות בינאריות מספק). כמו כן רצוי של-\ (p-1) יהיה גורם ראשוני גדול כדי לסכל התקפה באמצעות אלגוריתם פוליג-הלמן. שיקול בטיחותי נוסף הוא בצורך שהיוצר \ \alpha יהיה יוצר של תת-חבורה של \ \mathbb{Z}^*_p מסדר ראשוני כלשהו במקום יוצר של \ \mathbb{Z}^*_p ישירות. מאחר שמצב זה האחרון מהווה נקודת תורפה אם היוצר \ \alpha הנו מחלק של \ (p-1).

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

תהליך החתימה של מנגנון אל-גמאל מהיר יחסית ודורש רק העלאה בחזקה מודולרית אחת. יתרה מזו, \ k^{-1} ניתן להכנה מראש (בעזרת אלגוריתם אוקלידס המורחב) ובמקרה כזה תהליך החתימה דורש רק שני הכפלות מודולריות. אולם תהליך האימות איטי יותר ודורש לפחות שלוש העלאות בחזקה. שינוי קל של תהליך האימות מאפשר שיפור משמעותי ביעילות. אם משוואת האימות תהיה: \ v_1 = \alpha^{-H(m)} \cdot y^r \cdot r^s \mbox{ mod }p והחתימה במקרה כזה תתקבל אם \ v_1 = 1. אזי ניתן יהיה לבצע את שלוש ההעלאות בחזקה במקביל באמצעות אלגוריתם סימולטני.

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

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

בהתאמה קלה אפשר לכתוב את השלד הבסיסי של מנגנון החתימה המתואר כאן, כך:

חתימה: \ \boldsymbol{u = av + kw \mbox{ mod }(p-1)}
אימות: \ \boldsymbol{\alpha^u = (\alpha^a)^v \cdot r^w}

משוואות אילו מתארות את שלב 4 בתהליך החתימה ושלב 3 בתהליך האימות, המתוארים בגרסה הבסיסית לעיל. בתהליך המפורט לעיל הפרמטרים הם: \ u = H(m), v = r, w = s. אולם הפרמטרים \ u,v,w ניתנים להחלפה ביניהם, כדי ליצור גרסאות נוספות של אותו מנגנון החתימה. להלן מספר אפשרויות:

  1. \ u = H(m),\  v = s,\  w = r
  2. \ u = s,\  v = H(m),\  w = r
  3. \ u = r,\  v = s,\  w = H(m)

חלק מהגרסאות, מאפשר מימוש יעיל יותר מהיבט מעשי ואילו חלקן מאפשר חישוב חד-פעמי, כשלב הכנה מוקדם. דוגמה 1 מעניינת כיוון שבטיחותה נשענת בין היתר גם על \ r^r, הבעיה הכללית של חישוב \ x^x \equiv c (\mbox{mod }p) עבור \ c קבוע כלשהו, שונה מבעיית לוגריתם דיסקרטי האמורה. אם \ p גדול זו בעיה קשה.

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

למרות שמנגנון החתימה המתואר כאן, הוא מעל החבורה הכפלית \ \mathbb{Z}^*_p. למעשה ניתן ליישמו מעל כל חבורה אבלית סופית. כאמור מנגנון החתימה נשען על בעיית לוגריתם דיסקרטי בחבורה \ G כך שחבורה זו צריכה לענות על 2 תנאים הכרחיים:

  1. מטעמי יעילות, פעולות בחבורה \ G צריכות להיות קלות יחסית.
  2. מטעמי בטיחות, בעיית לוגריתם דיסקרטי בחבורה \ G צריכה להיות קשה מבחינה חישובית.

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

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