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

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

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

[עריכה] חתימה

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

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

החתימה על המסר $\ m$ היא צמד הערכים $\ r,s$ .

[עריכה] אימות

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

תחילה מוודאים כי $\ r$ בטווח הנכון כלומר $\ 0 < r < p$ .
מחשבים את $\ v_1 = y^r \cdot r^s \mbox{ mod }p$ .
מחשבים את $\ 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$ . בכך הצליח למצוא מסר אחר שעבורו נוצרה חתימה זהה. פונקציית הגיבוב מבטלת בעיה זו.

[עריכה] התקפות

שימוש באלגוריתם Index calculus כדי לתקוף את מנגנון החתימה אפשרי במקרה ש- $\ 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$ ניתנים להחלפה ביניהם, כדי ליצור גרסאות נוספות של אותו מנגנון החתימה. להלן מספר אפשרויות:

$\ u = H(m),\ v = s,\ w = r$
$\ u = s,\ v = H(m),\ w = r$
$\ u = r,\ v = s,\ w = H(m)$

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

[עריכה] הכללות

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