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

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

הצפנת קריימר-שוּפּ היא מערכת הצפנה א-סימטרית פרקטית, מוכחת כבטוחה סמנטית נגד התקפת מוצפן-נבחר שהומצאה ב-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\text{ mod }q. בעיית לוגריתם דיסקרטי והגרסאות המנויות ידועות כבעיות קשות שטרם נמצא להם פתרון פולינומי יעיל. קיים מודל המציע ביטחון סמנטי דומה, שיכול להיות מושתת על כל פונקציה חד-כיוונית עם דלת מלכודת, ראה חשילות.

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

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

  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. ואז מחשבים את u_1=20491,u_2=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.

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

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

בתמצית ההוכחה היא כדלהלן. אם קיים תוקף שמסוגל לשבור את המערכת תחת המודל IND-CCA2 הרי שאפשר לבנות אלגוריתם B עם זמן ריצה דומה לתוקף שיוכל להכריע בבעיית דיפי-הלמן. האלגוריתם B יפעל כמו אורקל. מכין זוג מפתחות פרטי וציבורי ושולח לתוקף את המפתח הציבורי, כעת הוא משתמש ברבעיית הערכים (g_1,g_2,u_1,u_2) כדי לשלוח אתגר מוצפן לתוקף כדי שהוא יפענחו. קריימר ושופ מראים שאם הרביעייה האמורה היא בעיית דיפי-הלמן אקראית הרי שהתוקף יצליח לפתור את הבעיה בהסתברות משמעותית. לעומת זאת עם הרביעייה היא ערכים אקראיים ב-G^4 הרי שלתוקף יש יתרון אפס בסיכויי ההצלחה שלו לנצח במשחק. ההבדל הזה בעצם מאפשר ל-B לשבור את המערכת כיוון שהוא מפר את ההנחה היסודית של אי-יכולת הבחנה (IND) מכאן שהמערכת כולה בטוחה.


CS-Lite[עריכת קוד מקור | עריכה]

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

הוריאציה שנקראת CS-Lite היא גרסה פשוטה יותר של מערכת קריימר-שופ ללא פונקציית גיבוב. שהיא בטוחה לפי מודל פחות מחמיר שנקרא IND-CCA1. לפי מודל זה המערכת צריכה להיות בטוחה תחת התקפת מוצפן נבחר לא אדפטיבית שבה התוקף רשאי להגיש שאילתות לאורקל כל עוד לא קיבל לידיו את האתגר שהוא הטקסט המוצפן אותו הוא מעוניין לשבור. מרגע שהגיע האתגר לידיו אין הוא רשאי יותר לפנות לאורקל. ביטחון המערכת CS-Lite עונה להגדרה זו.

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

הכנה:

  1. כמו קודם בוחרים אלמנטים אקראיים: p,q,g_1,g_2,x_1,x_2,z\in G
  2. מחשבים את X=g_1^{x_1}\cdot g_2^{x_2}\text{ mod }p וכן את Z=g_1^z\text{ mod }p
  3. הפרמטרים הציבוריים של המערכת יהיו (p,q,g_1,g_2). המפתח הפרטי הוא (x_1,x_2,z) והמפתח הפומבי הוא (X,Z).

הצפנה:

  1. בוחרים אלמנט אקראי חד פעמי r.
  2. מחשבים את R_1=g_1^r\text{ mod }p
  3. מחשבים את R_2=g_2^r\text{ mod }p
  4. הטקסט המוצפן הוא הצמד R_1,R_2 וכן E=Z^r\cdot M\text{ mod }p ו-V=X^r\text{ mod }p

פענוח:

  1. \text{If }V\not\equiv R_1^{x_1}\cdot R_2^{x_2}(\text{mod }p)\text{ then return null}
  2. \text{Else }M=E\cdot R_1^{-z}\text{ mod }p


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