הצפנת קריימר-שופ

מתוך ויקיפדיה, האנציקלופדיה החופשית
(הופנה מהדף הצפנת קריימר-שאופ)
קפיצה אל: ניווט, חיפוש

הצפנת קריימר-שוּפּ היא מערכת הצפנה א-סימטרית פרקטית, מוכחת כבטוחה סמנטית נגד התקפת מוצפן-נבחר שהומצאה ב-1998 על ידי רונלד קריימר מהמכון הטכנולוגי של ציריך וויקטור שופ ממעבדות IBM והוצגה בוועידת CRYPTO '98 בקליפורניה. ביטחונה מסתמך על קושיה המשוער של בעיית הכרעה דיפי-הלמן והיא הרחבה של צופן אל-גמאל. שבניגוד לאחרון שנקרא חשיל ואינו מוגן כלל כנגד התקפת מוצפן-נבחר (בקיצור CCA), לגרסת קריימר-שופ נוספו כמה אלמנטים כדי להבטיח אי-חשילות (Non-malleability) ועמידות כנגד התקפת CCA בשילוב של פונקציית גיבוב חד-כיוונית אוניברסלית ומחולל מספרים אקראיים בטוח.

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

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

בעיית הכרעת דיפי-הלמן[עריכת קוד מקור | עריכה]

בעיית הכרעת דיפי-הלמן ניתנת להצגה באופן הבא: נתונה חבורה G מסדר ראשוני q גדול. ונתונות שתי ההתפלגויות:

  • ההתפלגות R של רביעיות אקראיות (g_1,g_2,u_1,u_2)\in G^4,
  • ההתפלגות D של הרביעיות (g_1,g_2,u_1,u_2)\in G^4 כאשר g_1,g_2 אקראיים ואילו u_1=g_1^r וכן u_2=g_2^r עבור r אקראי כלשהו.

הבעיה היא להכריע בשאלה האם ניתן להבחין בהבדל סטטיסטי משמעותי כלשהו בין שתי ההתפלגויות המתוארות. אם נחליף את הערכים הללו בערכים: g_1=g, g_2=g^x, u_1=g^y,u_2=g^{xy}, אפשר לצמצם את בעיית ההכרעה המתוארת לבעיית דיפי-הלמן בהינתן g^x, g^y חשב את g^{xy} וכן לבעיית הלוגריתם הדיסקרטי שהיא חישוב x מתוך g^x (מודולו q). כאן לצורך הבעיה g יכול להיות קבוע. לכן בעיית הכרעת דיפי-הלמן שקולה לבעיה הכללית, כלומר במקרה הגרוע כאשר נתונים g^x,g^y,g^z קשה להכריע עם סטייה הסתברותית זניחה אם z=xy\pmod{ q}. בעיית לוגריתם דיסקרטי והגרסאות המנויות ידועות כבעיות קשות שטרם נמצא להם פתרון פולינומי יעיל. לאחרונה התפרסם[דרוש מקור] שנמצאה פריצת דרך בפתרון מקרה פרטי של בעיית הלוגריתם הדיסקרטי ולא ידוע נכון למאי 2014 כיצד הממצא ישפיע על ביטחון האלגוריתם. קיים מודל המציע ביטחון סמנטי דומה, שיכול להיות מושתת על כל פונקציה חד-כיוונית עם דלת מלכודת, ראה חשילות.

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

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

  1. בוחרים שלמים אקראיים g_1,g_2\in G וכן את הערכים האקראיים x_1,x_2,y_1,y_2,z\in Z_q.
  2. מחשבים את c=g_1^{x_1}g_2^{x_2}, d=g_1^{y_1}g_2^{y_2},h=g_1^z
  3. המפתח הפומבי הוא הסט: (g_1,g_2,c,d,h) ופונקציית גיבוב ידועה ומוסכמת H. והמפתח הפרטי הוא הסט: (x_1,x_2,y_1,y_2,z).

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

להצפנת המסר m\in G בוחרים שלם אקראי r\in Z_q ומחשבים:

  1. u_1=g_1^r, u_2=g_2^r, e=h^rm
  2. \alpha=H(u_1,u_2,e) ממירים את תוצאת פונקציית הגיבוב לערך שלם ב-G.
  3. v=c^rd^{r\alpha}

הטקסט המוצפן הוא הרביעייה: (u_1,u_2,e,v).

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

נתון הטקסט המוצפן (u_1,u_2,e,v).

  1. תחילה מחשבים את ערך הגיבוב \alpha=H(u_1,u_2,e)
  2. בודקים אם מתקיים v=u_1^{x_1+y_1\alpha}u_2^{x_2+y_2\alpha}, במידה שלא מחזירים הודעת שגיאה.
  3. הטקסט המקורי הוא m=e/u_1^z.

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

היות ש-u_1=g_1^r ו-u_2=g_2^r מתקבל

u_1^{x_1}u_2^{x_2}=g_1^{rx_1}g_2^{rx_2}=c^r

וכן לגבי u_1^{y_1}u_2^{y_2}=d^r ו-u_1^z=h^r לכן הבדיקה בשורה 2 צריכה להחזיר אמת והטקסט הוא למעשה e/h^r.

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

נניח שהראשוני q=21523 והערכים האקראיים שנבחרו הם:

z=2112,x_1=11341,x_2=5844,y_1=13399,y_2=10981,g_1=17716,g_2=5611

הערכים שחושבו הם: c=20419,d=17636,h=10910

  1. כעת להצפנת המסר m=12345 תחילה נבחר r=19438
  2. ואז מחשבים את u1=20491,u2=12522
  3. מחשבים את e=8282 ואת ערך הגבוב a=\mbox{H}(12345)=193 (כאן לצורך הדוגמה נלקח רק הבית הראשון של תוצאת פונקציית הגיבוב SHA-1).
  4. מחשבים את v=4870

הטקסט המוצפן לפי הסדר הוא: (20491,12522,8282,4870).

לפענוח תחילה בודקים שאכן

  1. v=
20491^{11341+13399\cdot 193}\cdot 12522^{5844+10981\cdot 193} ומפענחים,
  2. m=8211\cdot 8282=12345 \pmod{21523}

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

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

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

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