חשילות (קריפטוגרפיה)

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

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

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

תיאור כללי

חשילות בתחום המטלורגיה פירושה היכולת לעמוד בלחצים ולשנות צורה מבלי להישבר (או תכונת הפלסטיות). אפשר להמחיש את הרעיון החשילות בהקשר של קריפטוגרפיה על ידי מכרז. לצורך המשל נניח שהמשתתפים במכרז כלשהו יכולים להצפין את הצעותיהם על ידי פונקציית מפתח פומבי $E$ של מפרסם המכרז, זאת כדי שאחרים לא יוכלו ללמוד על הצעותיהם לפני שיוגשו. האינטרס של כל מציע הוא ללמוד את הצעות המתחרים האחרים לפני שיגיש את הצעתו, כך שיוכל לדאוג ששלו תהיה הנמוכה מביניהם וסיכוייה להתקבל יהיו הגבוהים ביותר. תכונת החשילות במקרה זה היא שבהינתן ההצעה $E(A)$ של המציע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , יהיה ביכולתו של המציע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} (שרואה את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(A)} כלומר את ההצעה המוצפנת בלבד) להציע את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(B)} כך שיתקיים בסבירות גבוהה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(B) < E(A)} , זאת מבלי לפענח את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(A)} . ההנחה היא ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} יכול לנסות הצפנה של ערכים שונים בשאיפה למצוא קשר כלשהו בינם ל-$E(A)$ ובכך להצליח להגיש הצעה שתקיים את התנאי האמור בסבירות מסוימת, מבלי לדעת מה היא ההצעה בדיוק.

בהקשר של חתימה דיגיטלית, זיוף קיומי מתייחס למצב שבו בהינתן חתימה לגיטימית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S(m_1)} על המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_1} , המתקיף יוכל בעזרתה לייצר חתימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S(m_2)} שתהיה תקפה עבור מסר אחר כלשהו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_2} , גם אם הוא חסר משמעות.

בצופן סימטרי ניתן לראות תכונת אי-חשילות בעיקר בפרוטוקול תקשורת כמו קרברוס שבו, המשתתפים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ו-$B$ משתפים ביניהם מפתח הצפנה סימטרי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} וכחלק ממהלכי הפרוטוקול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} שולח ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} מסר סתמי (Nonce) מוצפן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{AB}(N)} ומצפה לקבל בתגובה הצפנה של מסר אחר שהוא פונקציה פשוטה שלו: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{AB}(f(N))} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=x+1} למשל. ביטחון הפרוטוקול מסתמך על הנחה (שלא הוכחה) שבהינתן רק הצפנת המסר הראשון, המתקיף לא יוכל לייצר את $K_{AB}(f(N))$ כך שיתקבל כלגיטימי בעיני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} . זוהי בדיוק אי-חשילות בהקשר זה.

בהקשר של הוכחת ידיעה ניתן להגדיר אי-חשילות באופן שהמוודא B לא יוכל להשתמש בהוכחה של A כדי להתחזות אליו כלפי צד שלישי E בדומה להתקפת אדם באמצע. כלומר B ישמש מעין 'תווך' שמעביר את כל ההוכחות שניתנות על ידי A ל-E וכן את כל האתגרים שמציב E בחזרה ל-A. בניסיון להוכיח ל-E שכביכול הוא (B) בעל הידיעה ובעצם להתחזות ל-A.

הגדרה של סכמת התחייבות היא, שצד הגון A המעוניין להתחייב לצד הגון B על קיומה של פיסת מידע כלשהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} מבלי לחשוף בפניו את המידע עצמו. סביר להניח שעלול להימצא קשר או יחס כלשהו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} בינו לבין ערך אחר נניח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} שחושב על ידי צדדים רמאים C,D (שיכולים להיות גם A,B עצמם או אחד מהם), אותו נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(\alpha,\beta)} . אי-חשילות בהקשר זה תהיה התכונה שהפרוטוקול יוכל להבטיח שלא יהיה ניתן ליצור יחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} כזה, שלא ניתן היה לחישוב ללא גישה לצדדים ההגונים A ו-B אלא אם כן $\alpha =\beta$. הדברים האמורים נכונים גם אם A אינו מודע לקיומם של C או D או להפך. ניתן לראות שיש קשר הדוק בין סכמת התחייבות להוכחת אפס-ידיעה.

הגדרה כללית

לצורך הגדרה כללית המתאימה לכל תחומי ההצפנה המדוברים, נניח ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} מתייחס לפרימיטיב קריפטוגרפי מאילו המנויים. נתון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle GP} שהוא מחולל המייצר צמד מפתחות-הצפנה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (e,d)} (פומבי/פרטי בהתאמה). הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_e(b,r)} נקראת הצפנה של הסיבית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b\in \{0,1\}} ומחרוזת אקראית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} באורך $p(n)$ שהיא פונקציה כלשהי של הקלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} והפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_d(c)} היא הפענוח. אזי עבור כל מחרוזת אקראית אפשרית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_d(E_e(b,r))=b} . כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b=0,1} . המערכת המתוארת תקרא בלתי ניתנת להבחנה (indistinguishability), אם עבור כל מכונה דמיונית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} , קיים $c>0$ המקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\Pr[M(e,E_e(0,r))=1] - \Pr[M(e,E_e(1,r))=1]|<1/n^c}

הוכח שאי-יכולת הבחנה היא דרישה חשובה לצורך ביטחון סמנטי בהקשר של התקפת מוצפן-נבחר. בהקשר זה מציאת יחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(\alpha,\beta)} כלשהו שניתן להבחנה בין שני טקסטים מוצפנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha, \beta} אפילו בלא ידיעת מקורם, חשובה כשבירת הצופן. במילים אחרות עבור כל מתקיף אפשרי A קיים סימולטור A' כך שכל יחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(\alpha,\beta)} שניתן לחישוב על ידי A בעזרת פונקציה (רמז או היסטוריה כלשהי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} ) ניתן להפקה על ידי A' מבלי שתהיה לו גישה לתהליך ההצפנה.

לא ניתן לפתור את הבעיה על ידי חתימה דיגיטלית כלומר שהשולח יצרף את חתימתו למשלוח כך $E(m),S_{A}(E(m))$, כיוון שאם אלגוריתם ההצפנה E בר-חשילות אזי התוקף יכול להתעלם מהחתימה ולייצר את הערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(m+1), S_B(E(m+1))} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_B} היא חתימת המתקיף. גם הכנסת החתימה בתוך הטקסט המוצפן לא תועיל.

דוגמאות

בצופן זרם בדרך כלל מבצעים XOR של סיביות הטקסט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} עם פונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} של המפתח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} ומתקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(m)=m\oplus S(k)} . אפשר לראות שניתן בקלות ליצור הצפנה של המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m\oplus x} עבור כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} כיוון ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(m)\oplus x=m\oplus x\oplus S(k)=E(m\oplus x)} .

ב-RSA המתקיף יכול לייצר הצפנה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle mx} מתוך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_e(m)} עבור כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} כיוון שפונקציית ההצפנה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_e(m)=m^e\bmod\ n} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e,n} הם מפתחות פומביים מקיימת את הזהות הבאה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_e(m)\cdot x^e\bmod\ n=(mx)^e\bmod\ n=E_e(mx)} . מסיבה זו נהוג לרפד את המסר לפני ההצפנה. בשני המקרים מתקבל מסר מוצפן אחר לגיטימי גם אם לא בהכרח בשליטה מלאה של התוקף.

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

סכמת הצפנה בטוחה סמנטית כנגד התקפת מוצפן-נבחר

כדי לבנות מודל כזה יש צורך להשתמש בסכמת הוכחת אפס-ידיעה בטוחה. הרעיון הוא ליצור קבוצה גדולה של מפתחות הצפנה ופענוח ולהשתמש רק בחלק מהם בהתאם לערך שמושג על ידי פונקציית גיבוב חד-כיוונית. כדי להבטיח שההצפנה תהיה עקבית, כלומר שמתקיף לא ניסה ערכים שונים על מנת לרמות את המערכת, משתמשים בסכמת התחייבות של הוכחת אפס ידיעה לא אינטראקטיבית, המאפשרת לוודא לאחר מעשה שהערכים מקיימים את התנאי שכל ההצפנות מתייחסות לערך זהה. המפתח הפומבי כולל שלושה מרכיבים, אוסף של זוגות מפתחות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle e_i^0,e_i^1\rangle} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1,...,n} . מחרוזת אקראית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} לצורך הוכחת אפס ידיעה. ומשפחה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} של פונקציות גיבוב חד-כיווניות אוניברסליות. תהליך ההצפנה מורכב מארבעה שלבים:

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

לפענוח מבצעים תהליך הפוך. והחתימה הדיגיטלית צריכה להיות משויכת לחותם באופן מוכח כלשהו. פונקציית הגיבוב מתפקדת כאן כמו בחתימה דיגיטלית, היא מאפשרת להקטין את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} (מספר זוגות המפתחות) מבלי לפגוע בביטחון הסמנטי.

הכנת מפתחות

1. באמצעות המחולל GP מייצרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n} זוגות: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (e_i^0,d_i^0),(e_i^1,d_i^1)} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1,...,n} .
2. מייצרים מחרוזת אקראית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U}
3. מייצרים ערך אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h\in_R H}

המפתח הפומבי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} זוגות: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle h,e_1^0,e_1^1,...,e_n^0,e_n^1,U\rangle} , המפתח הפרטי הוא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle d_1^0,d_1^1,...,d_n^0,d_n^1\rangle} .

הצפנה

הקלט הוא המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m=b_1,...,b_k}

1. מייצרים מפתחות חתימה דיגיטלית, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} מפתח אימות פומבי ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} מפתח חתימה פרטי.
2. מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h(F)} שהיא פונקציית גיבוב, כאשר התוצאה היא מחרוזת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} סיביות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_1,v_2,...,v_n} .
3. עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\le i\le k}
   1. עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\le j\le n}
      1. בוחרים פונקציית גיבוב חד-כיוונית אקראית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{ij}{\in}_R\{0,1\}^{p(n)}}
      2. מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_{ij}=E_{e_j^{v_j}}(b_i,r_{ij})} . הצפנה של הסיבית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} באמצעות מפתח ההצפנה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_j^{v_j}} .
   2. באמצעות הוכחת אפס ידיעה של ערכי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_i=e_1^{v_1},...,e_n^{v_n}} מייצרים את ההוכחות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i} באמצעות העדים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{i1},...,r_{in}} .
4. מייצרים חתימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} על הרצף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (c_i,p_i)} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1,...,k} . והטקסט המוצפן הוא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle F,s,(c_1,p_1),...,(c_k,p_k)\rangle} .

פענוח

1. מוודים שהחתימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} תקפה באמצעות מפתח האימות הפומבי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} שהתקבל ביחד עם המסר המוצפן.
2. עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\le i\le k} מוודים שערכי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_i} עקביים באמצעות הוכחת אפס-הידיעה שניתנה (באמצעות הערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p_1,...,p_k,U)} ).
3. מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h(F)} כשהפלט הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_1,...,v_n} .
4. אם בדיקת אמיתות ההוכחה באפס ידיעה התקבלה עבור כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} הערכים אזי מחלצים את המסר באמצעות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle d_1^{v_1},...,d_n^{v_n}\rangle} עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\le i\le k} כדי לקבל את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} .

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

23340306חשילות (קריפטוגרפיה)