הצגת המקור של הדף "חתימה דיגיטלית אל-גמאל"

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

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

==הכנת מפתחות עבור חתימת אל-גמאל==
המשתמש מייצר מפתח ציבורי ומפתח פרטי מתאים כדלהלן:
# בוחר ראשוני אקראי גדול <math>\ p</math> ו[[יוצרים של חבורה|יוצר]] <math>\ \alpha</math> של ה[[חבורה (מבנה אלגברי)|חבורה]] הכפלית <math>\ \mathbb{Z}^*_p</math>.
# בוחר שלם אקראי <math>\ a</math> הנמוך מ- <math>\ p-1</math>.
# ומחשב את <math>\ y = \alpha^a \mbox{ mod }p</math>.

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

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

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

==אימות==
תהליך אימות החתימה נעשה בעזרת המפתח הפומבי של החותם <math>(p,\,\alpha,\,y)</math>.
# תחילה מוודאים כי <math>\ r</math> בטווח הנכון כלומר <math>\ 0 < r < p</math>.
# מחשבים את <math>\ v_1 = y^r \cdot r^s \mbox{ mod }p</math>.
# מחשבים את <math>\ v_2 = \alpha^{H(m)} \mbox{ mod }p</math>.

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

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

:<math>\ ks \equiv H(m)-a \cdot r \quad (\mbox{mod }p-1)</math>.

לכן:

:<math>\ H(m) \equiv ar + ks \quad (\mbox{mod }p-1)</math>

מזה נובע:

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

על כן: <math>\ v_1 = v_2</math>.

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

אם נתונות המשוואות עבור המסרים <math>\ m_1</math> ו-<math>\ m_2</math> בהתאמה:
:<math>\ s_1 = k^{-1}(H(m_1)-ar) \mbox{ mod }(p-1)</math> וכן, 
:<math>\ s_2 = k^{-1}(H(m_2)-ar) \mbox{ mod }(p-1)</math>,

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

אם <math>\ s_1 - s_2</math> לא שקול ל-<math>\ 0</math> (מודולו <math>\ p-1</math>), יוצא ש-
:<math>\ k = (s_1-s_2)^{-1}(H(m_1)-H(m_2))\mbox{ mod }(p-1)</math>.

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

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

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

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

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

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

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

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

# <math>\ u = H(m),\  v = s,\  w = r</math>
# <math>\ u = s,\  v = H(m),\  w = r</math>
# <math>\ u = r,\  v = s,\  w = H(m)</math>

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

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

==ראו גם==
*[[צופן אל-גמאל]]
== לקריאה נוספת ==
* המאמר של טאהר אל-גמאל, [http://crypto.csail.mit.edu/classes/6.857/papers/elgamal.pdf "מערכת מפתח-פומבי וחתימה דיגיטלית המבוססת על לוגריתם בדיד"], בהוצאת [[Springer Verlag]] פלו-אלטו [[קליפורניה]] 1998.

{{קריפטוגרפיה}}

[[קטגוריה:מפתח ציבורי]]
[[קטגוריה:חתימה דיגיטלית]]