Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
אלגוריתם חתימה דיגיטלית של אל-גמאל (ElGamal) הוא מנגנון קריפטוגרפי אקראי לחתימה דיגיטלית עם נספח (שהחתימה מהווה תוספת נפרדת למסר ואינה הצפנה של המסר עצמו). האלגוריתם הוא פרי המצאתו של טאהר אל-גמאל שפרסם ב-1986 את רעיון השימוש במפתח-פומבי ליצירת מנגנון חתימה דיגיטלית המבוסס על בעיית הלוגריתם הבדיד בהשראת עבודתם של דיפי והלמן ב-1976. אף על פי שהשימוש במנגנון המתואר בהמשך לא נפוץ מבחינה מעשית, הוא מהווה בסיס לפיתוחים דומים והוביל בין היתר להמצאת אלגוריתם DSA שהוא למעשה וריאציה של אל-גמאל.
חתימת אל-גמאל נקראת "אקראית" כיוון שהיא מערבת שימוש במספר פסאודו-אקראי שונה עבור כל מסר (ראו להלן). כמו כן חתימת אל-גמאל מחייבת שימוש בפונקציית גיבוב קריפטוגרפית. מנגנון החתימה מייצר 'תווית' הנשלחת יחד עם המסר ליעדה בעוד המסר עצמו נותר קריא. התווית מאפשרת למקבל המסר להבטיח את שלמותו ולאמת את מקורו על ידי פענוח התווית והשוואת תוצאת פונקציית הגיבוב של המסר עם תווית. מכיוון שרק בעל המפתח הפרטי המתאים יכול לייצר את התווית האמורה, ניתן להסיק שהוא מקור המסר. אם מתגלה הבדל כלשהו אזי בסבירות גבוהה מאוד המסר שונה בדרך.
המשתמש מייצר מפתח ציבורי ומפתח פרטי מתאים כדלהלן:
המפתח הציבורי הוא המפתח הפרטי הוא .
תהליך החתימה על המסר :
הוא תוצאת הפעלת פונקציית גיבוב בטוחה כלשהי על המסר לפני החתימה. החתימה על המסר היא צמד הערכים .
תהליך אימות החתימה נעשה בעזרת המפתח הפומבי של החותם .
החתימה מתקבלת כאותנטית אם ורק אם .
אם מכפילים את שני צידי המשוואה בשורה 4 בתהליך החתימה לעיל ב-, מקבלים:
לכן:
מזה נובע:
על כן: .
אם תוקף ינסה לזייף את החתימה על ידי בחירת כזה שמקיים , יהיה עליו לחשב גם את . בעיה זו שקולה לבעיית הלוגריתם הבדיד שהיא כאמור בעיה מתמטית קשה. על כל פנים חובה לבחור שונה עבור כל מסר משום שאם לא כך, יהיה אפשרי לחשוף את המפתח הפרטי של החותם כדלהלן:
אם נתונות המשוואות עבור המסרים ו- בהתאמה:
אזי .
אם לא שקול ל- (מודולו ), יוצא ש-
כעת אם ידוע ניתן לחשב בקלות את . מכאן נובע כי חייב להיות שונה עבור כל מסר שנחתם באמצעות אותו מפתח פרטי .
הצורך בפונקציית גיבוב נובע מהעבודה שמשוואת החתימה (ללא פונקציית הגיבוב) מאפשרת לתוקף לזייף את החתימה כדלהלן: הוא בוחר זוג הערכים כאשר זר ל- ומחשב את השקול ל- וכן . במקרה כזה הערכים יהיו חתימה תקפה עבור המסר היות ש: . בכך הצליח למצוא מסר אחר שעבורו נוצרה חתימה זהה. פונקציית הגיבוב מבטלת בעיה זו.
שימוש באלגוריתם תחשיב אינדקסים כדי לתקוף את מנגנון החתימה אפשרי במקרה ש- קטן. על כן רצוי ש- יהיה גדול דיו כדי לסכל התקפה כזו (ההנחה היא כי סדר גודל של 2000 ספרות בינאריות מספק). כמו כן רצוי של- יהיה גורם ראשוני גדול כדי לסכל התקפה באמצעות אלגוריתם פוליג-הלמן. שיקול בטיחותי נוסף הוא בצורך שהיוצר יהיה יוצר של תת-חבורה של מסדר ראשוני כלשהו במקום יוצר של ישירות. מאחר שמצב זה האחרון מהווה נקודת תורפה אם היוצר הוא מחלק של .
תהליך החתימה של מנגנון אל-גמאל מהיר יחסית ודורש רק העלאה בחזקה מודולרית אחת. יתרה מזו, ניתן להכנה מראש (בעזרת אלגוריתם אוקלידס המורחב) ובמקרה כזה תהליך החתימה דורש רק שתי הכפלות מודולריות. אולם תהליך האימות איטי יותר ודורש לפחות שלוש העלאות בחזקה. שינוי קל של תהליך האימות מאפשר שיפור משמעותי ביעילות. אם משוואת האימות תהיה: והחתימה במקרה כזה תתקבל אם . אזי ניתן יהיה לבצע את שלוש ההעלאות בחזקה במקביל באמצעות אלגוריתם סימולטני.
אלגוריתם אל-גמאל הבסיסי המתואר כאן, למעשה מהווה בסיס למשפחת אלגוריתמים גדולה בה נמנה אלגוריתם DSA, שהמכנה המשותף לה הוא השענות על בעיית לוגריתם בדיד. השוני העיקרי בין הגרסאות השונות הוא בתהליך החתימה.
בהתאמה קלה אפשר לכתוב את השלד הבסיסי של מנגנון החתימה המתואר כאן, כך:
משוואות אילו מתארות את שלב 4 בתהליך החתימה ושלב 3 בתהליך האימות, המתוארים בגרסה הבסיסית לעיל. בתהליך המפורט לעיל הפרמטרים הם: . אולם הפרמטרים ניתנים להחלפה ביניהם, כדי ליצור גרסאות נוספות של אותו מנגנון החתימה. להלן מספר אפשרויות:
חלק מהגרסאות, מאפשר מימוש יעיל יותר מהיבט מעשי ואילו חלקן מאפשר חישוב חד-פעמי, כשלב הכנה מוקדם. דוגמה 1 מעניינת כיוון שבטיחותה נשענת בין היתר גם על , הבעיה הכללית של חישוב עבור קבוע כלשהו, שונה מבעיית לוגריתם בדיד האמורה. אם גדול זו בעיה קשה.
אף על פי שמנגנון החתימה המתואר כאן, הוא מעל החבורה הכפלית . למעשה ניתן ליישמו מעל כל חבורה אבלית סופית. כאמור מנגנון החתימה נשען על בעיית לוגריתם בדיד בחבורה כך שחבורה זו צריכה לענות על 2 תנאים הכרחיים:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.