צופן אל-גמאל

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

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

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

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

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

A\equiv g^a\text{ (mod }p).

אליס מפרסמת את המפתח הציבורי A לכל דורש ושומרת בסוד את a. כעת אם בוב מעוניין להצפין מסר m כלשהו עבור אליס, תחילה הוא בוחר מספר אקראי אחר k (מודולו p) איתו הוא מצפין את המסר ולאחר מכן משמיד אותו. השלם k נקרא מפתח ארעי (ephemeral key) כיוון שנועד אך ורק להצפנת מסר יחיד.

בוב לוקח את המסר m עם המפתח החד-פעמי k והמפתח הציבורי של אליס A ומחשב את זוג הערכים:

c_1\equiv g^k\text{ (mod }p),
c_2\equiv mA^k\text{ (mod }p).

כזכור p ו-g הם פרמטרים ציבוריים כך שלכולם כולל בוב יש נגישות אליהם. הטקסט המוצפן שבוב הכין הוא (c_1,c_2). אפשר להבחין בחיסרון בולט של הצופן, הטקסט המוצפן הוכפל בנפחו. כעת אם אליס מעוניית לפענח את הטקסט המוצפן שקיבלה היא משתמשת במפתח הפרטי שלה כדי לחשב את:

x\equiv c_1^a\text{ (mod }p),

וכן מחשבת את x^{-1}\text{ (mod }p) שהוא ההופכי הכפלי של x מודלו p. ואז מכפילה את c_2 ב-x^{-1} כדי לקבל את m או בניסוח פורמלי.

m\equiv x^{-1}\cdot c_2\text{ (mod }p).

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

כדי לראות מדוע זה עובד מתבוננים בביטוי x^{-1}\cdot c_2, לאחר הרחבה מתקבל:

x^{-1}\cdot c_2\equiv (c_1^a)^{-1}\cdot c_2\text{ (mod }p),
\equiv (g^{ak})^{-1}\cdot (mA^k)\text{ (mod }p),
\equiv (g^{ak})^{-1}\cdot (m(g^a)^k)\text{ (mod }p),
\equiv m

השורה הראשונה נובעת ישירות מהעובדה ש-x\equiv c_1^a\text{ (mod }p). בשורה השנייה הוחלף c_2 בביטוי mA^k\text{ (mod }p) וכן c_1^a הוחלף ב-g^a\cdot g^k=g^{ak} כי לפי תיאור ההצפנה לעיל c_1\equiv g^k, c_2\equiv mA^k (מודולו p). בשורה השלישית הוחלף המפתח הציבורי A בביטוי g^a מהעובדה שאליס חישבה את A\equiv g^a\text{ (mod }p) בתהליך ההכנה. בשורה הרביעית הביטוי g^{ak} הוסר בגלל הכפל בהופכי שלו כי g^{ak}\cdot (g^{ak})^{-1}\equiv 1\text{ (mod }p) וכך נותר m.

כדי להבין מדוע k חייב להיות חד-פעמי ואין להשתמש בו להצפנת שני מסרים עם אותו מפתח. נניח שבוב הצפין את m_1 ו-m_2 עם אותם מפתחות ו-k זהה. לאחר הצפנה מתקבל:

c_1\equiv g^k, c_2\equiv m_1A^k\text{ (mod }p) עבור המסר הראשון,
c_3\equiv g^k, c_4\equiv m_2A^k\text{ (mod }p) עבור המסר השני.

אם המצותתת איב משיגה את שני זוגות הטקסטים המוצפנים שנשלחו על ידי בוב (c_1,c_2),(c_3,c_4) שים לב שמתקיים:

c_4\cdot c_2^{-1}\equiv m_2\cdot m_1^{-1} מזה נובע ש-m_2\equiv c_4\cdot c_2^{-1}m_1 (מודולו p).

כעת אם איב גילתה את m_2 בדרך כלשהי (למשל אם הוא קבוע כלשהו שידוע מראש) היא יכולה בעזרת מידע זה לחשב את m_1. מסיבה זו אסור להצפין שני מסרים עם אותו k.

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

המשימה של איב (המצותתת) היא לנסות לפענח את המסר המוצפן (c_1,c_2) שבוב שלח לאליס. היא יודעת מה הם p ו-g וכן מהו המפתח הציבורי של אליס A כי אילו נתונים ציבוריים. אם איב מסוגלת לפתור את בעיית דיפי הלמן (או בעיית הלוגריתם הדיסקרטי) בקלות, היא יכולה פשוט לחלץ את המפתח הפרטי של אליס מתוך המפתח הציבורי ולפענח את המסר בדיוק כמו שאליס עושה. השאלה היא האם הצפנת אל-גמאל קשה לפיצוח לפחות כפתרון בעיית דיפי-הלמן או שהיא מכילה פגם ניסתר המאפשר לפצח אותה בקלות ללא צורך בפתרון בעיית דיפי-הלמן. ההוכחה לכך מבוססת על דרך המשל, נניח שישנו "אורקל אל-גמאל" ממנו יכולה איב לבקש פענוח באמצעות אלגוריתם אל-גמאל כל טקסט מוצפן שתבחר. אפשר לראות שבעזרתו היא יכולה לפתור את בעיית דיפי-הלמן כדלהלן: כאשר איב מגישה לאורקל את הזוג (c_1,c_2) יחד עם מפתח ציבורי A כלשהו היא מקבלת בחזרה את (c_1^a)^{-1}\cdot c_2\text{ (mod }p) שזהו כביכול הפענוח המבוקש של הטקסט המוצפן עם המפתח הפרטי המתאים ל-A. כזכור בעיית דיפי-הלמן היא למצוא את g^{ab} מתוך A=g^a ו-B=g^b (כאשר a ו-b סודיים). עם האורקל האמור איב יכולה לבצע את הטריק הבא: היא בוחרת c_1=B ו-c_2 אקראי כלשהו ומפתח ציבורי A כלשהו, היא שולחת אותם לאורקל ומבקשת ממנו להחזיר את תוצאת הפענוח שלהם. מה שהיא מקבלת בחזרה הוא כביכול את m שהוא פענוח הטקסט המוצפן המקיים

m\equiv (c_1^a)^{-1}\cdot c_2\equiv (B^a)^{-1}\equiv (g^{ab})^{-1}\cdot c_2\text{ (mod }p).

כעת אם איב תכפיל את c_2 בהופכי הכפלי של m היא תקבל את g^{ab}. הרי שעם מידע זה היא "פתרה" את בעיית דיפי-הלמן. לסיכום מי שיכול לפצח את הצפנת אל-גמאל יכול גם לפתור את בעיית דיפי הלמן כך שהצפנת אל-גמאל בטוחה לפחות כבעיית דיפי-הלמן. כל עוד בעייה זו קשה לפתרון בכלים הקיימים ההצפנה תיוותר בטוחה. יש לשים לב שבהתקפה המתוארת איב לא פתרה את בעיית הלוגריתם הדיסקרטי כלומר לא הצליחה לגלות מה הם a או b אלא רק את g^{ab}. כלומר השאלה נותרה פתוחה האם בעיית דיפי-הלמן קשה כמו בעיית הלוגריתם הדיסקרטי.

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

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

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

לצורך ההדגמה ולמען הפשטות נניח שאליס בוחרת את הראשוני p=467 ואיבר פרימיטיבי g=2. למפתח פרטי היא בוחרת את a=153 ומחשבת את המפתח הציבורי שלה

A\equiv g^a\equiv 2^{153}\equiv 224\text{ (mod }467).

בוב מקבל את המפתח הציבורי A=224 והוא מעוניין להצפין את המסר נניח m=331. תחילה הוא בוחר מספר חד-פעמי k=197 ומחשב את הערכים הבאים:

c_1\equiv 2^{197}\equiv 87\text{ (mod }467),

ואת

c_2\equiv 331\cdot 224^{197}\equiv 57\text{ (mod }467)

את הזוג (c_1,c_2)=(87,57) הוא שולח לאליס.

אליס משתמשת במפתח הפרטי שלה a=153 כדי לחשב את הערכים הבאים:

x\equiv c_1^a\equiv 87^{153}\equiv 367\text{ (mod }467),
x^{-1}\equiv 14\text{ (mod }467).

ואז המסר m מתקבל על ידי חישוב:

m=c_2\cdot x^{-1}\equiv 57\cdot 14\equiv 331\text{ (mod }467).
m=331.

הצפנה היסתברותית וביטחון סמנטי[עריכת קוד מקור | עריכה]

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

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

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

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

דוגמה להצפנת סף עם צופן אל-גמאל[עריכת קוד מקור | עריכה]

נתון הסוד s\in\mathbb{Z}_p. כל משתתף A_i מחזיק בסוד s_i שנוצר לפי שיטת שמיר (ראה חלוקת סוד). כל המשתתף A_i מתחייב לסוד s_i על ידי פרסום המפתח הציבורי h_i=g^{s_i}. ממשפט לגראנז' נובע שהיות ש-\textstyle s=\sum {c_is_i} עבור c_i כלשהו לכן g^s ניתן לחישוב מהמידע הציבורי על ידי \textstyle\prod_{i\in X} (g^{s_i})^{c_i} כאשר X הוא תת-קבוצה של לפחות k רשאים. כעת היות שמתקיים \textstyle h=g^s,s=\sum c_is_i לפענוח (y,x)=(mh^r,g^r) המשתתפים A_i מחשבים כדלהלן:

  1. כל אחד משדר את w_i=x^{s_i} ומוכיח באמצעות פרוטוקול אפס ידיעה שמתקיים \log_g h_i=\log_x w_i.
  2. תהי X תת-קבוצה של k משתתפים הטקסט המוצפן ניתן לפענוח על ידי:
m'=\frac{y}{\prod_{i\in X}w_i^{c_i}}.

זה נכון כי w_i^{c_i}\equiv x^{c_is_i}\equiv g^{rc_is_i} לכן \textstyle m'\equiv mg^{rs}/ \prod {g^{rc_is_i}}\equiv m.

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

למרות שצופן אל-גמאל ניתן ליישום מעל כל חבורה ציקלית סופית \ 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). כך שלמעשה צופן אל-גמאל ניתן לשימוש חופשי הן לצורך הצפנה והן לצורך חתימה דיגיטלית.

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

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