מחשבון הצפנת ElGamal

אודות מחשבון זה

מערכת ההצפנה של ElGamal, שפרסם Taher Elgamal ב-1985, היא סכמת הצפנה במפתח ציבורי שאבטחתה נשענת על בעיית הלוגריתם הדיסקרטי בחבורה ציקלית סופית — בהינתן מספר ראשוני p ויוצר g, קשה חישובית לשחזר את x מתוך y = g^x mod p. יצירת המפתחות בוחרת מפתח פרטי x ומפרסמת את y = g^x mod p כמפתח הציבורי; ההצפנה בוחרת אז לכל הודעה מפתח ארעי אקראי חדש k ומפיקה זוג טקסט מוצפן (c₁, c₂) = (g^k mod p, m·y^k mod p), כך שאותו טקסט גלוי לעולם אינו מוצפן לאותו טקסט מוצפן פעמיים.

המחשבון עובר על החשבון הזה צעד אחר צעד: מזינים מספר ראשוני קטן p, יוצר g, מפתח פרטי x, מפתח ארעי k והודעה שלמה m, והוא מפיק את המפתח הציבורי ואת זוג הטקסט המוצפן המתקבל בדיוק כפי שהאלגוריתם היה עושה. סטודנטים להצפנה, מרצים למדעי המחשב ומהנדסי אבטחה משתמשים בדוגמאות צעצוע כאלה כדי לפתח אינטואיציה להצפנה א-סימטרית ולבסיס הלוגריתם הדיסקרטי שעומד גם בבסיס החלפת המפתחות של Diffie-Hellman ושל סכמת החתימה DSA — מערכות אמיתיות משתמשות במספרים ראשוניים באורך מאות ספרות, הרבה מעבר לחישוב ידני או במחשבון.