צופן אל-גמאל

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

אליס בוחרת ראשוני גדול p ויוצר g. היא בוחרת מספר סודי a ומחשבת את המפתח הציבורי A≡g^a (mod p). המפתח הפרטי a נשאר סודי.
כאשר בוב רוצה להצפין הודעה m, הוא בוחר מספר ארעי חד-פעמי k. הוא מחשב את הזוג
c1≡g^k (mod p),
c2≡m·A^k (mod p).
את הזוג (c1,c2) הוא שולח לאליס. לפענוח אליס מחשבת x≡c1^a ומוציאה את ההופכי הכפלי x^{-1} (מודול p). ואז מחשבת m≡x^{-1}·c2 (mod p) ומקבלת את ההודעה המקורית.
חשוב: k חייב להיות חד-פעמי. שימוש חוזר ב-k מאפשר לתוקף להשיג מסרים אחרים.

כי x=c1^a=g^{ak}, ולכן x^{-1}·c2=(g^{ak})^{-1}·m(g^{a})^k=m. זה מראה שפענוח מחזיר את m.

ביטחון האל-גמאל קשור לבעיית דיפי־הלמן והלוגריתם הבדיד. הבעיה הבסיסית היא למצוא את a מתוך A=g^a. אם ניתן לפתור את בעיית דיפי־הלמן בקלות, ניתן לפצח אל-גמאל. קיימת הוכחה שעוזרת להעביר בעיית פיצוח אל-גמאל לפתרון דיפי־הלמן בעזרת אורקל; כלומר, אפשר להראות שאם מישהו יכול לפענח אל-גמאל בקלות אז הוא גם יכול לפתור דיפי־הלמן.
עקב זאת יש לבחור פרמטרים גדולים. הערכה פשוטה מציעה סדר של כמה אלפי ביטים (במדרג המקורי הוזכר סדר של כ-2000 ספרות בינאריות, שזה כ-600 ספרות עשרוניות) כדי למנוע התקפות מבוססות אלגוריתמים מתקדמים. כמו כן, מחשב קוונטי סקלאבילי שיפעיל אלגוריתם שור יוכל לשבור את השיטה בזמן פולינומי.

לדוגמה קצרה: p=467, g=2, a=153 ⇒ A=224. אם m=331 ובוב בוחר k=197 אז
c1=87, c2=57. אליס מחשבת x=367 ו-x^{-1}=14, ואז m=57·14≡331 (mod 467). המספרים ממחישים את השלבים.

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

חסרונות עיקריים: הטקסט המוצפן גדול פי שניים מהמסר. נדרשות שתי העלאות בחזקה מודולריות. אי אפשר להאיץ בעזרת CRT כמו בשיטות אחרות. אפשר לשתף p ו-g בין משתתפים כדי ליעל חישובים.
בשימוש מעשי נהוג לשלב דיפי־הלמן להחלפת מפתחות ואז להשתמש בצופן סימטרי מהיר כמו AES. עם זאת לאל-גמאל יש תכונות חשובות: תמיכה בהצפנה הומומורפית חלקית ובאמצעים של הצפנת סף (threshold encryption).

אל-גמאל ניתן ליישום על חבורה ציקלית סופית. אפשר לעבוד על השדה
\mathbb{F}_p^*, על שדות מסוג \mathbb{F}_{2^m} או על קבוצות נקודות בעקום אליפטי. עקומי אליפטי נותנים מפתחות קטנים ועמידות גבוהה ולכן מועדפים לעיתים.

צופן אל-גמאל אינו מוגן בפטנט כיום. גם דיפי־הלמן אינו תחת פטנט מאז שנות ה-90.

אל-גמאל היא שיטה להצפין הודעות. היא הומצאה ב-1984 על ידי טאהר אל-גמאל.

אליס בוחרת מספר גדול שנקרא p ופרמטר g. היא בוחרת מספר סודי a. היא מחשבת A=g^a ומפרסמת את A. A הוא המפתח הציבורי.
כדי לשלוח הודעה, בוב בוחר מספר סודי חד-פעמי k. הוא עושה שני חישובים וקבל זוג מספרים. הוא שולח את הזוג לאליס.
אליס משתמשת במספר הסודי שלה כדי להחזיר את ההודעה המקורית.
חשוב: אסור להשתמש באותו k יותר מפעם אחת.

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

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

בדוגמה פשוטה: p=467, g=2, a=153 ⇒ A=224. אם m=331 ו-k=197 אז התקבלו (c1,c2)=(87,57). אליס פיצחה וזה חזר ל-331.

אל-גמאל לא מוגן בפטנט. לכן ניתן להשתמש בו חופשי.