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

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

מודל ביטחון

הגדרת ביטחון סמנטי כפי שהוגדרה לראשונה על ידי גולדווסר ומיקלי מייצגת את האינטואיציה המובנת שמתקיף פסיבי לא יוכל ללמוד מאומה על הטקסט המקורי מתוך התבוננות בטקסט המוצפן בלבד. זאת משיגים על ידי הוספת פסאודו-אקראיות לתהליך ההצפנה בדומה להצפנת בלום-גולדווסר. על כל פנים ההגדרה תקפה רק במצב פסיבי ואינה מתמודדת עם איום אקטיבי שבו המתקיף יכול 'להזריק' הודעות, לחסום, לשכפל (replay) או לשנות את תוכנן. ההגדרה של 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^{r}m$
2. $\alpha =H(u_{1},u_{2},e)$ ממירים את תוצאת פונקציית הגיבוב לערך שלם ב-$G$.
3. $v=c^{r}d^{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$ כאשר $p$ ראשוני.
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$

קישורים חיצוניים

• רונלד קריימר וויקטור שופ. "A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack." in proceedings of Crypto 1998, LNCS 1462, p. 13ff (ps,pdf)
• אנציקלופדיה לקריפטוגרפיה ואבטחת מידע