צופן אל-גמאל

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

אלגוריתם אל-גמאל הבסיסי[עריכת קוד מקור | עריכה]

הכנת מפתחות[עריכת קוד מקור | עריכה]

  1. אליס בוחרת מספר ראשוני \ p גדול ויוצר \ \alpha של החבורה הכפלית \ \mathbb{Z}^*_p של השלמים מודולו \ p.
  2. אליס בוחרת שלם אקראי \ a בטווח \ 1 \le a \le p-2 ומחשבת את \ \alpha^a \mbox{ mod }p.
  3. המפתח הפומבי של אליס הוא \ (p,\alpha,\alpha^a) והמפתח הפרטי הוא \ a.

הצפנה[עריכת קוד מקור | עריכה]

בוב משיג עותק אותנטי של המפתח הפומבי של אליס ומצפין את המסר \ m כדלהלן:

  1. בוחר שלם אקראי \ k בטווח \ 1 \le k \le p-2.
  2. מחשב את \ \gamma = \alpha^k \mbox{ mod }p,
  3. ואת \ \delta=m\cdot (\alpha^a)^k \mbox { mod }p.
  4. בוב שולח את הצופן \ c = (\gamma,\delta) לאליס.

פענוח[עריכת קוד מקור | עריכה]

  1. בעזרת המפתח הפרטי אליס מחשבת תחילה את: \ \gamma^{p-1-a} \mbox{ mod }p.
  2. אליס משחזרת את \ m על ידי חישוב \ (\gamma^{-a}) \cdot \delta \mbox{ mod }p.
הערה: שים לב ש: \ \gamma^{p-1-a} = \gamma^{-a} = \alpha^{-ak}.

כיצד זה עובד[עריכת קוד מקור | עריכה]

כאמור בשיטת דיפי-הלמן לשיתוף מפתח הצפנה, המשתתפים אליס ובוב משתפים ביניהם מפתח \ K כך: נניח שאליס ובוב מסכמים ביניהם מראש באופן פומבי, על ראשוני \ p ויוצר \ \alpha קבועים כלשהם. אליס מחזיקה במפתח סודי \ a ובוב מחזיק במפתח סודי \ b אותם הם שומרים כל אחד בנפרד. אליס יכולה לשלוח לבוב את \ \alpha^a ובוב בתורו ישלח לאליס את \ \alpha^b ואז המפתח המשותף להם יהיה \ K = \alpha^{ab}. שים לב ש-\ a ו-\ b עצמם מעולם לא שודרו בערוץ הפתוח. בעיה זו כידוע מורכבת משני בעיות, האחת היא חילוץ \ \alpha^{ab} מתוך \ \alpha^a ו-\ \alpha^b (לשם כך דרושים \ a או \ b לפחות אחד מהם) והשנייה היא חישוב \ a מתוך \ \alpha^a שתיהן בעיות קשות שאין להן פתרון יעיל (ברור שכל החישובים נעשים מודולו \ p). על בסיס רעיון זה, אם בוב רוצה לשלוח מסר \ m לאליס הוא יכול לבצע זאת כך: תחילה הוא מחשב את המפתח המשותף \ K על ידי העלאת \ \alpha^a שקיבל מאליס בחזקת \ b ואז הוא שולח לאליס את \ \gamma = \alpha^b ואת \ \delta = K \cdot m. אליס יכולה לשחזר את \ m תחילה על ידי חילוץ מפתח ההצפנה המשותף \ K. כזכור היא יכולה לעשות זאת כיוון ש-\ a ידוע לה, לכן \ K=(\alpha^b)^a = \gamma^a. לאחר מכן היא יכולה לשחזר את המסר פשוט על ידי חילוק ב-\ K (הפעולה ההפוכה לזו שביצע בוב). על כן מתקיים:

\ \frac{\delta}{\gamma^a} = \frac{m \cdot (\alpha^a)^b}{\alpha^{ab}} = \frac{m \cdot \alpha^{ab}} {\alpha^{ab}} = m

דוגמה במספרים קטנים[עריכת קוד מקור | עריכה]

יהיו הפרמטרים הציבוריים, הראשוניים \ q=487, \ p=4\cdot q+1=1949, והיוצר \ \alpha=1687. אליס בוחרת לעצמה שלם אקראי וסודי למשל \ a=895 המשמש כמפתח פרטי ומחשבת את \ \alpha^a\mbox{ mod }p=1639. המפתח הפומבי של אליס יהיה השלישייה \ (1949,1687,1639) והמפתח הפרטי: \ 895. כעת כדי להצפין את המסר \ m=123, בוב בוחר שלם אקראי (חד פעמי) \ k=1931 ונעזר במפתחות הפומביים של אליס כדלהלן:

  • מחשב את \ \gamma=\alpha^k\mbox{ mod }p=1687^{1931}\mbox{ mod }1949=1616,
  • ומחשב את \ \delta=(\alpha^a)^k\mbox{ mod }p=1639^{1931}\mbox{ mod }1949=1187,
  • והטקסט המוצפן הוא \ c=(\delta\cdot m)\mbox{ mod }p=(1187\cdot 123)\mbox{ mod }1949=1775. יחד עם \ \gamma=1616 (שים לב שנפח הצופן הוכפל).

כעת אליס מפענחת את הצופן שהתקבל כדלהלן:

  • מחשבת את \ w=\gamma^{p-1-a}\mbox{ mod }p=1616^{1949-1-895}\mbox{ mod }1949=1041
  • ואז \ m=(w\cdot c)\mbox{ mod }p=(1041\cdot 1775)\mbox{ mod }1949=123

הערה: שים לב שהחילוק מוסתר כאן בהכפלה בהופכי כפלי של \ a כלומר במקום לחלק במפתח המשותף \ \alpha^{ak} אפשר פשוט להכפיל ב-\ \alpha^{-ak}.

צופן אקראי[עריכת קוד מקור | עריכה]

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

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

בטיחות[עריכת קוד מקור | עריכה]

  • שיטת אל-גמאל משלבת את אלגוריתם דיפי-הלמן להעברת המפתח עם הצפנה באמצעות אותו מפתח. פיצוח השיטה, קרי, שחזור \ m בהינתן \ p, \alpha, \alpha^a, \gamma,\delta שקול לפתרון בעיית דיפי-הלמן. בעיית הלוגריתם הדיסקרטי קרובה לבעיית דיפי-הלמן (וקשה לפחות כמוה), ומשערים שהבעיות שקולות.
  • שיטת אל-גמאל מחייבת שימוש במספר אקראי \ k עם כל הצפנה של מסר שונה. אם לא משתמשים ב-\ k אקראי ושונה עבור כל מסר אפשר לראות שניתן בקלות לפצח את השיטה. נניח כי \ m_1 ו-\ m_2 הם מסרים כלשהם אשר \ (\gamma_1,\delta_1) ו-\ (\gamma_2,\delta_2) הם הטקסטים המוצפנים הנוצרים מהם.
אזי: \ \frac{\gamma_1}{\gamma_2} = \frac{m_1}{m_2}
ולכן ניתן לחלץ את \ m_2 אם \ m_1 ידוע.
עובדה זו מאפשרת התקפת טקסט מוצפן נבחר (chosen ciphertext attack) מסוימת. בהינתן הטקסט המוצפן \ (\gamma, \delta) של מסר \ m כלשהו ניתן ליצור טקסט מוצפן \ (\gamma, 2 \cdot \delta) של המסר \ 2m גם בלא ידיעת \ m עצמו.
  • כדי שצופן אלגמאל יהיה בטוח יש צורך שלמספר \ p-1 יהיה לפחות גורם ראשוני אחד גדול. אם ל-\ p-1 יש רק גורמים ראשוניים קטנים אזי ניתן לחשב לוגריתם דיסקרטי בחבורה \ \mathbb{Z}^*_p בקלות.

נכון להיום מבחינת היכולת הטכנולוגית, כדי שצופן אל-גמאל יחשב כבטוח, יש צורך בראשוני בסדר גודל של כ-600 ספרות עשרוניות. האלגוריתם הטוב ביותר הידוע כיום לפתרון בעיית לוגריתם דיסקרטי הוא תחשיב האינדקסים. הרעיון המרכזי באלגוריתם הוא איסוף מאגר של לוגריתמים של גורמי בסיס ראשוניים. הכנת טבלת לוגריתמים זו מאפשרת חישוב כל לוגריתם בחבורה \ \mathbb{Z}^*_p יחסית בקלות. לכן חשוב ש-\ p יהיה גדול ככל האפשר כדי למנוע התקפה כזו.

יעילות[עריכת קוד מקור | עריכה]

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

כדי לייעל את הצופן, ניתן לשתף מספר ראשוני ויוצר בין מספר משתתפים. במקרה כזה מפרסמים את \ p ו-\ \alpha כפרמטרים ציבוריים. כך שהמפתח הפומבי יהיה רק \ \alpha^a. לעובדה זו יתרון נוסף כיוון שאפשר לנצל זאת כדי להאיץ את תהליך ההצפנה בעזרת טכניקות לחישוב העלאה בחזקה המנצלות את העובדה שבסיס החזקה (היוצר במקרה זה) קבוע.

הכללות[עריכת קוד מקור | עריכה]

למרות שצופן אל-גמאל ניתן ליישום מעל כל חבורה ציקלית סופית \ G, בתנאי שפעולות אריתמטיות בחבורה זו קלות יחסית בעוד שפתרון בעיית לוגריתם דיסקרטי בה קשה מאוד. לא כל חבורה בטוחה ליישום צופן אל-גמאל, החבורה \ G תהיה בטוחה רק אם היא עומדת בהגבלות מסוימות. למשל החבורה \ \mathbb{Z}_p אינה בטוחה אם \ p אינו מספר ראשוני בטוח. מספר ראשוני יקרא בטוח רק אם ל-\ p-1 יש לפחות גורם ראשוני אחד גדול. להלן מספר חבורות המתאימות ליישום אלגוריתם אל-גמאל:

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

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

זכויות[עריכת קוד מקור | עריכה]

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ראו גם[עריכת קוד מקור | עריכה]