בתשובה לדורפל, 14/06/08 4:03
 |
|
 |
||
|
||||
 |
זה נושא מעניין, אז אנסה להרחיב עליו, מהמעט שלמדתי: לא טריוויאלי להגדיר בטיחות של סכמת הצפנה - באותה סכמת הצפנה עשויה להשתמש בסיטואציות שונות (מצפינים אחת מתוך קבוצה קטנה של הודעות ידועות מראש [כן/לא, עכשיו/מחר], קבוצה גדולה [ספרים שכתובים באנגלית ושמורים בפורמט ידוע] או כל הודעה אפשרית?), בצורות שונות (שולחים עוד הודעות שמוצפנות באותו המפתח?), התוקף את ההצפנה עשוי להשתמש בכלים שונים (שהגדרת הבטיחות צריכה לקחת בחשבון את כולם, מבלי להניח מראש מה הם, לפני שהיא נותנת את חותמת הכשרות), וכן הלאה. הכי חשוב - מה נחשב לנפילה של סכמת ההצפנה? אם התוקף יודע שאותו המסר נשלח פעם שניה, האם זה כשלון? בסיטואציות מסויימות כן (למשל, אם ראינו שהמשחתת חזרה לנמל, סביר שזה גם מה שיקרה בפעם הבאה שתקבל את אותו המסר), באחרות לא (העותק של הארי פוטר נשלח לשני אנשים שונים בחברה המוציאה לאור? איך זה עוזר לי להתחיל להדפיס עותקים פיראטיים בסין?). וזו רק דוגמה אחת (אחרות: אורך ההודעה? היוניפורמיות של התוכן? שפת התוכן? האם התוכן הוא קידוד של תמונה כלשהי, טקסט באנגלית או קובץ וידאו? דמיון כלשהו להודעה קודמת [מתנהל משא ומתן על משכורת?]?). אז יש כמה מודלים בסיסיים שסכמת הצפנה עשויה להיות בטוחה עבורם או לא. ביניהם - הצפנה חד-פעמית, הצפנה רב-פעמית, הצפנה שבה לתוקף יש אפשרות, מבלי לדעת את המפתח, לבקש ולקבל הצפנה של מסר לבחירתו באמצעות אותו המפתח (מן הסתם יש כמה וריאנטים לכל אחד מאלה, אבל אני למדתי רק וריאנט אחד של כל אחד מאלה, והם נשמעו לי מוצלחים, אז אני מאמין שהם סטנדרטים שמקובלים על הרוב). בכדי להניח את המינימום האפשרי על צרכי התוקף ומה שמהווה עבורו שבירה של ההצפנה, מאמצים עמדה פסימית במיוחד - הצפנה חד-פעמית נחשבת כשבורה אם תוקף יכול לבחור שתי הודעות, ואז אחת מהן - הוא לא יודע איזו - מוצפנת, והוא מסוגל לנחש, בהנתן ההצפנה, איזו משתי ההודעות שלו הוצפנה. ההיגיון - אם אפילו כשהוא בוחר את ההודעות בעצמו, אף תוקף לא יכול להבחין, אז הרי שהסכימה טובה לכל הודעה תחת כל התקפה. כל מידע שהוא עשוי לרצות לשלוף מההודעה - שפת התוכן, מספר הפעמים שמופיעה האות ג' - אם אפשר היה לשלוף מהקובץ המוצפן, הרי שהוא יכל לבקש להצפין שתי הודעות שנבדלות בתכונה הזאת, ובאמצעות הדרך שכביכול יש לו לשליפת המידע הזה מהקובץ המוצפן, יכל היה להבחין איזו משתי ההודעות שבחר הוצפנה. אם נצליח להוכיח שאף תוקף (הגדרת התוקף מכילה בתוכה את זוג ההודעות שיבחר) לא מסוגל להבחין[*], הרי שהסכמה בטוחה. עכשיו, לגבי מה שאמרתי מקודם בקשר לכך שכל הצפנה ראויה לשמה מכילה אלמנט של אקראיות - המבחן לבטיחות של סכמת הצפנה שמתיימרת להיות בטוחה גם אם משתמשים בה, עם אותו המפתח, מספר פעמים, היא שהתוקף בוחר שני רצפים של הודעות, אחד מהרצפים מוצפן (כל הודעה ברצף מוצפנת בנפרד, אבל עם אותו המפתח) והצפנתו מוחזרת לתוקף, והוא אמור לנחש איזה משני הרצפים הוצפן. אם אין אלמנט של אקראיות, הרצה של אלגוריתם ההצפנה פעמיים על אותו הקלט תיתן את אותה התוצאה, ולכן התוקף יכול פשוט לתת רצף אחד שמורכב משתי הודעות שונות, ורצף שני שמורכב מאותו הודעה פעמיים, ובצורה זו להבחין איזה מהרצפים הוצפן - אם שתי ההודעות ברצף ההצפנה המוחזר לו זהות, זה השני, ואחרת, זה הראשון. באופן טריוויאלי, כל סכמת הצפנה שתהיה בטוחה להצפנות חוזרות ונשנות, חייבת להכיל אלמנט של אקראיות, כך שהצפנה כפולה של הודעה תיתן [בהסתברות גבוהה] תוצאות שונות (וכך, כמובן, לא ידע התוקף כשהודעה נשלחה פעמיים). (באופן דומה לגבי המודל השלישי - אם התוקף יכול לבחור מה להצפין, הוא יכול לבחור להצפין שוב את ההודעה הראשונה, ובמידה והיא זהה להצפנה שקיבל, זו ההודעה שלו שהוצפנה, ואחרת, זו השניה.) דוגמה לניסיון של ההגדרה להמנע מהנחות לגבי *יכולותיו* של התוקף - המודל השלישי שהזכרתי מדבר על תוקף שיש לו אפשרות לקבל הצפנה של הודעות לבחירתו. זה לא מצב סביר במיוחד, אבל זה מידול פסימי מאוד (ולכן מצויין) של יכולות שקשה מאוד למדל אחרת של תוקף בעולם האמיתי להשפיע על המתקשרים באופן מוצפן והמידע העובר ביניהם, ולהשתמש בכך לשם פיענוח התקשורת ביניהם. דוגמה דבילית משהו, אבל קצרה - אם יש לי את האפשרות להאט את התקשורת בין המתקשרים באופן מוצפן, אני עשוי לגרום למשפט "אני סובל מאיטיות בתקשורת" להתווסף לשיחה. איך נמדל השפעה שכזאת כשאנחנו מנסים להוכיח שסכמת הצפנה בטוחה? איך נתייחס לאינספור האפשרויות הנוספות? הכי פשוט ויעיל למדל את ההשפעה המירבית שיכולה להיות לתוקף - הוא קובע את *כל* מה שיאמר בהודעה אחת שמוצפנת עם אותו המפתח - ואם הסכמה בטוחה אפילו בפני זה, היא כמובן בטוחה בפני השפעות חלשות יותר, כמו העלאת הסיכוי שאומר משהו ספיציפי, ושימוש שלו במידע הזה להסקת המפתח. --- * היות ותמיד אפשר להטיל מטבע, ב"לא יכול לנחש איזו משתי ההודעות שבחר הוצפנה", הכוונה הייתה שלא יכול לעשות זאת עם הסתברות להצלחה גדולה מחצי (במקרה של סודיות מושלמת) או גדולה משמעותית מחצי (במקרה של סודיות חישובית - אותה אנסה להסביר רק אם מישהו רוצה). --- מי שהנושא מעניין אותו, יכול לקרוא יותר בספר הבא - http://www.amazon.com/Introduction-Cryptography-Chap... אני מקווה שהסברתי מעט מהנושא עם מינימום טעויות ובאופן סביר, ושהודעתי לא עושה שירות דוב למחברי הספר. |
 |
 |
 |
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |