צופן אל-גמאל

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

[עריכה] הצפנה

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

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

[עריכה] פענוח

בעזרת המפתח הפרטי אליס מחשבת תחילה את: $\ \gamma^{p-1-a} \mbox{ mod }p$ .
אליס משחזרת את $\ 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$

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

אליס בוחרת ראשוני $\ p=467$ ויוצר $\ \alpha=336$ , בוחרת מפתח פרטי $\ a=181$ ואז מחשבת את $\ 336^{181} \mbox{ mod }467 = 411$ . על כן המפתח הפומבי הוא $\ (467,336,411)$ המפתח הפרטי הוא $\ 181$ . לצורך הצפנה בוב בוחר מספר אקראי $\ k=144$ ומצפין את המסר $\ m=123$ עבור אליס כדלהלן. הוא מחשב את: $\ 336^{144} \mbox{ mod }467 = 360$ ואת $\ 123 \cdot 411^{144} \mbox{ mod }467 = 38$ ושולח לאליס את $\ (38,360)$ . כדי לפענח את המסר שקיבלה, תחילה מחשבת אליס את $\ 360^{130} \mbox{ mod }467 = 163$ ואז $\ m = 163 \cdot 38 \mbox{ mod }467 = 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 ספרות עשרוניות. האלגוריתם הטוב ביותר הידוע כיום לפתרון בעיית לוגריתם דיסקרטי הוא Index calculus (תחשיב אינדקסים). הקטע העיקרי באלגוריתם הוא איסוף מאגר של לוגריתמים של גורמי בסיס ראשוניים. הכנת טבלת לוגריתמים זו מאפשרת חישוב כל לוגריתם בחבורה $\ \mathbb{Z}^*_p$ יחסית בקלות. לכן חשוב ש- $\ p$ יהיה גדול ככל האפשר כדי למנוע התקפה כזו.

[עריכה] יעילות

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

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

[עריכה] הכללות

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

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

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

[עריכה] זכויות

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

[עריכה] קישורים חיצוניים

המאמר של טאהר אל-גמאל

[עריכה] ראו גם

מקור: http://he.wikipedia.org../../../%D7%A6/%D7%95/%D7%A4/%D7%A6%D7%95%D7%A4%D7%9F_%D7%90%D7%9C-%D7%92%D7%9E%D7%90%D7%9C.html

קטגוריות: הצפנה | מפתח ציבורי