צופן אל-גמאל – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←הוכחת נכונות: עריכה |
מ תיקון כיווניות הערת שוליים |
||
שורה 1:
'''הצפנת אל גמאל''' ('''ElGamal encryption''') היא שיטת [[הצפנה]] [[מפתח ציבורי|אסימטרית]] [[הצפנה הסתברותית|אקראית]] שהומצאה ב-[[1984]] על ידי [[טאהר אל-גמאל]], [[קריפטוגרפיה|קריפטוגרף]] [[ארצות הברית|אמריקאי]] ממוצא [[מצרים|מצרי]]{{הערה|[http://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms], Taher Elgamal, 1984 |שמאל=כן}}. בדומה ל[[פרוטוקול דיפי-הלמן]], ביטחונה מסתמך על הקושי המשוער שב[[בעיית הלוגריתם הבדיד]] ו[[פרוטוקול דיפי-הלמן#בעיית דיפי-הלמן|בעיית דיפי-הלמן]]. והיא יכולה לשמש הן להצפנה והן ל[[חתימה דיגיטלית]]. צופן אל-גמאל היה בשימוש בתוכנות חופשיות [[GNU Privacy Guard|GPG]] וכן [[PGP]] ומערכות אחרות. אלגוריתם חתימה דיגיטלית [[DSA]] הוא וריאציה של [[אל-גמאל (חתימה דיגיטלית)|חתימה דיגיטלית של אל-גמאל]].
אף על פי ש-[[RSA]] קדמה לה, להצפנת אל-גמאל חשיבות היסטורית מאחר שהיא הצפנת מפתח-ציבורי הנחשבת המשך ישיר למאמר המפורסם של דיפי והלמן מ-1979 "כיוונים חדשים בהצפנה"{{הערה|[https://www-ee.stanford.edu/~hellman/publications/24.pdf New Directions in Cryptography], Whitfield Diffie and Martin E. Hellman, IEEE |שמאל=כן}} שהעלה לראשונה את ההצפנה האסימטרית וחתימה דיגיטלית על המפה. אפשר ליישם את הצפנת אל-גמאל מעל [[שדה סופי]] <math>\mathbb{F}_p^*</math> או מעל [[חבורה (מבנה אלגברי)|חבורת]] [[הצפנה מבוססת עקום אליפטי|עקום אליפטי]]. וכן זוהי ההצפנה הראשונה שיישמה [[הצפנה הסתברותית]], כלומר מוכחת כ[[ביטחון סמנטי|בטוחה סמנטית]] תחת מודל [[התקפת מוצפן-נבחר]], בהנחה שבעיית דיפי-הלמן היא בעיה קשה.
==תיאור האלגוריתם==
תיאור הצופן מהספר An Introduction to Mathematical Cryptography{{הערה|1=[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182.9999&rep=rep1&type=pdf An Introduction to Mathematical Cryptography], Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, Springer 2008|שמאל=כן}}. כמו בכל הצפנת מפתח ציבורי, בהצפנת אל-גמאל המקבלת אליס מכינה לעצמה שני מפתחות, מפתח סודי שנשאר אצלה ומיועד לפענוח ומפתח ציבורי שאותו היא שולחת לבוב, או מפרסמת אותו לכל דורש. כדי להכין את המפתחות, תחילה עליה לבחור [[מספר ראשוני]] <math>p</math> [[מחולל מספרים פסאודו-אקראיים קריפטוגרפי|אקראי]] גדול. היות שביטחון ההצפנה מסתמך על בעיית הלוגריתם הבדיד [[שדה סופי|בשדה הראשוני]] אליס צריכה לבחור ראשוני מספיק גדול כך שפתרון הבעיה יהיה "קשה". בביטוי קשה מתכוונים שהניסיון לנחש את המפתח הסודי מתוך המפתח הציבורי השקול לפתרון בעיית הלוגריתם הבדיד, עם מיטב האלגוריתמים הידועים יהיה [[סימון אסימפטוטי|אסימפטוטית]] ב[[סיבוכיות]] מעריכית, כלומר אינו מעשי. וכן צריכה לבחור אלמנט <math>g</math> מ[[סדר (תורת החבורות)|סדר]] ראשוני גבוה שנקרא [[יוצרים של חבורה|יוצר]]. את שני המספרים הללו היא יכולה להכין ולפרסם בעצמה או להשתמש בסט מספרים קבוע שפורסם על ידי [[צד שלישי]] נאמן. כעת כמו בפרוטוקול דיפי-הלמן היא בוחרת מספר אקראי <math>a</math> המשמש כמפתח פרטי ומחשבת את הערך:
:<math>A\equiv g^a\text{ (mod }p)</math>.
אליס מפרסמת את המפתח הציבורי <math>A</math> לכל דורש ושומרת בסוד את <math>a</math>. כעת אם בוב מעוניין להצפין מסר <math>m</math> כלשהו עבור אליס, תחילה הוא בוחר מספר חד פעמי <math>k</math> (מודולו <math>p</math>) איתו הוא מסתיר את המסר ולאחר מכן משמיד אותו. השלם <math>k</math> נקרא מפתח ארעי (ephemeral key) כיוון שנועד אך ורק להצפנת מסר יחיד.
שורה 13:
כזכור <math>p</math> ו-<math>g</math> הם פרמטרים ציבוריים כך שלכולם יש נגישות אליהם. הטקסט המוצפן שבוב הכין הוא הזוג <math>(c_1,c_2)</math> אותם הוא שולח לאליס בערוץ ציבורי. אפשר להבחין בחיסרון בולט של הצופן, הטקסט המוצפן הוכפל בנפחו. כעת אם אליס רוצה לפענח את הטקסט המוצפן שקיבלה היא משתמשת במפתח הפרטי שלה כדי לחשב את:
:<math>x\equiv c_1^a\text{ (mod }p)</math>,
וכן מחשבת את <math>x^{-1}\text{ (mod }p)</math> שהוא [[הופכי כפלי מודולרי|ההופכי הכפלי]] של <math>x</math> מודולו <math>p</math>. ואז מכפילה את <math>c_2</math> ב-<math>x^{-1}</math> כדי לקבל את <math>m</math> או בניסוח פורמלי.
:<math>m\equiv x^{-1}\cdot c_2\text{ (mod }p)</math>.
שורה 37:
{|
|-
|
|}
שורה 54:
כעת כדי לקבל את <math>g^{ab}</math> היא יכולה לחשב את:
:<math>m^{-1}\cdot c_2\equiv g^{ab}\text{ (mod }p)</math>
הרי שלכאורה עם מידע שהתקבל מאורקל אל-גמאל היא "פתרה" את בעיית דיפי-הלמן. זוהי הוכחה שמי שיכול לפצח את הצפנת אל-גמאל יכול גם לפתור את בעיית דיפי הלמן כך שהצפנת אל-גמאל בטוחה לפחות כבעיית דיפי-הלמן. כל עוד בעיה זו קשה לפתרון בכלים הקיימים ההצפנה תיוותר בטוחה. יש לשים לב שבהתקפה המתוארת איב לא פתרה את בעיית הלוגריתם הבדיד כלומר לא הצליחה לגלות מה הם <math>a</math> או <math>b</math> אלא רק את <math>g^{ab}</math>. כלומר השאלה נותרה פתוחה האם בעיית דיפי-הלמן קשה כמו בעיית הלוגריתם הבדיד.
ההתקפה המתוארת נקראת [[התקפת גלוי-נבחר]], מזה נובע שהצפנת אל-גמאל עמידה במודל ביטחון מחמיר בתנאי שפתרון בעיית דיפי-הלמן יהיה קשה בשדה הנבחר. מסיבה זו רצוי שסדר השדה יהיה גדול, כלומר יש לבחור מספר ראשוני כזה שניסיון לנחש את המפתח הסודי ב[[כוח גס]] או באמצעות האלגוריתם הטוב ביותר הידוע כיום לפתרון הבעיה, יהיה מעבר ליכולת המחשוב הנוכחית. ידוע שאלגוריתם [[תחשיב אינדקסים]] פותר את בעיית הלוגריתם הבדיד (ומכאן גם את בעיית דיפי-הלמן) בזמן תת-מעריכי. כלומר היכן שהוא באמצע הדרך בין זמן פולינומי לזמן מעריכי. אלגוריתם [[נפת שדה מספרים|נפת שדה המספרים]] יכול גם הוא להתאים לפתרון בעיית הלוגריתם הבדיד ונחשב כיום כאלגוריתם הטוב ביותר למטרה זו. אלגוריתמים אילו מציגים זמן ביצוע טוב בהרבה מכוח גס. לאור עובדה זו בהערכה גסה רצוי שגודל הסדר הראשוני יהיה לפחות כ-2000 ספרות בינאריות (שזה בערך מספר בן 600 ספרות עשרוניות).
שורה 67:
ואת
:<math>c_2\equiv 331\cdot 224^{197}\equiv 57\text{ (mod }467)</math>
את הזוג <math>(c_1,c_2)=(87,57)</math> הוא שולח לאליס.
אליס משתמשת במפתח הפרטי שלה <math>a=153</math> כדי לחשב את הערכים הבאים:
| |||