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

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

מייצרים מפתח ציבורי ומפתח פרטי כך:
בוחרים מספר ראשוני גדול p ובוחרים אלמנט בסיסי α בחבורת המספרים הכפולים מודול p.
בוחרים סוד a ומחשבים y = α^a מודול p.
המפתח הציבורי הוא (p, α, y). המפתח הפרטי הוא a.

כדי לחתום על מסר m בוחרים מספר אקראי חד־פעמי k (ש-coprime ל-p-1).
מחשבים r = α^k מודול p.
מחשבים את ההופכי של k מודול p-1, ואז s = k^{-1}(H(m) - a·r) מודול p-1.
H(m) היא פונקציית גיבוב קריפטוגרפית, פונקציה שמקצצת כל מסר לערך קבוע ובטוח.
החתימה היא הצמד (r,s).

המקבל משתמש במפתח הציבורי (p, α, y).
בודקים ש-r בטווח הנכון.
מחשבים v1 = y^r · r^s מודול p.
מחשבים v2 = α^{H(m)} מודול p.
החתימה תקפה אם v1 = v2.
זו הסיבה שאדם עם המפתח הפרטי בלבד יכול לייצר חתימה תקפה.

מהמשוואת החתימה מקבלים H(m) ≡ a r + k s מודול p-1.
מכאן α^{H(m)} = (α^a)^r · r^s מודול p, כלומר v1 = v2.

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

ללא פונקציית גיבוב אפשר ליצור זיופים קיימים (existential forgery).
הגיבוב מונע בנייה מתמטית של זוג r,s שיתאימו למסרים מזוים.

התקפות תלויות בגודל p. אם p קטן אפשר להשתמש באלגוריתם תחשיב אינדקסים.
מומלץ ש-p יהיה גדול מאוד (אומדן טיפוסי הוא סדר גודל של כ-2000 ביטים) ושה-p-1 יכיל גורם ראשוני גדול.
עדיף לבחור α שיוצר תת-חבורה מסדר ראשוני כדי להימנע מפגיעויות.

חתימה דורשת העלאה בחזקה מודולרית אחת בדרך כלל.
k^{-1} ניתן לחשב מראש, ואז החתימה דורשת רק שתי כפלות מודולריות.
האימות איטי יותר ודורש לפחות שלוש העלאות בחזקה, אך ניתן לייעל זאת בעזרת העלאות סימולטניות.

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

המנגנון אינו תלוי רק ב-
Z^*_p; אפשר ליישמו על כל חבורה אבלית סופית.
הדרישות הן שתי-ערכיות: פעולות בחבורה חייבות להיות יעילות, ובעיית הלוגריתם הבדיד בחבורה חייבת להיות קשה.

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

מייצרים זוג מפתחות: ציבורי וסודי.
בוחרים מספר גדול p ובוחרים גם בסיס α.
בוחרים סוד a ומחשבים ערך y שאותו ניתן לפרסם.
המפתח הציבורי הוא p, α ו-y. המפתח הפרטי הוא a.

כשחותמים עושים שני דברים חשובים.
בוחרים מספר סודי אקראי k שאינו חוזר.
מחשבים שני ערכים r ו-s בעזרת k וההודעה.
החתימה היא השניים האלה יחד.

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

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

משתמשים בפונקציה שמקצרת את ההודעה לערך קבוע.
הפונקציה הזו עוזרת למנוע זיופים פשוטים.

אם p קטן, אפשר לפרוץ בקלות.
לכן בוחרים p מאוד גדול ומספרים מתאימים.

DSA היא גרסה שמבוססת על אותו רעיון.
אפשר להפעיל את השיטה גם בחבורות אחרות, אם הפעולות שם קלות והבעיה קשה.