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

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

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

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

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

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$ צריכה להיות קשה מבחינה חישובית.

ראו גם

• צופן אל-גמאל

לקריאה נוספת

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