סודיות מושלמת

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

סודיות מושלמת היא מונח קריפטוגרפי אשר הוצג לראשונה על ידי קלוד שנון בשנת 1949 במאמר "Communication Theory of Secrecy Systems", על מנת לאפיין שיטת הצפנה "מושלמת".

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

[עריכה] הגדרה פורמלית

נסמן את מרחב ההודעות המקוריות ב־ $\ P$ , (מהמילה Plaintext) ואת מרחב ההודעות המוצפנות ב $\ C$ (מהמילה Ciphertext) ונגדיר פונקציית הסתברות על $\ P$ אשר תתאר את סבירות קבלתן של ההודעות הבלתי מוצפנות השונות.

מערכת הצפנה תקרא סודית בצורה מושלמת אם לכל הודעה מקורית $\ x\isin P$ ולכל הודעה מוצפנת $\ y\isin C$ , ההסתברות לכך ש־ $\ y$ מייצגת את $\ x$ שווה להסתברות קבלת $\ x$ כהודעה מקורית (כלומר, יריב אשר יירט את ההודעה המוצפנת $\ y$ לא יסיק מכך כל מידע חדש ביחס להודעה המקורית $\ x$ ). כלומר, $\ P(x|y)=P(x)$ . שימוש בחוק בייס מניב שדרישה זו שקולה לדרישה הסימטרית שלכל הודעה מוצפנת ובלתי מוצפנת $\ x\isin P, y\isin C$ , ההסתברות לכך שההודעה $\ x$ תוצפן כ־ $\ y$ שווה להסתברות קבלת $\ y$ כהודעה מוצפנת.

חשוב להבחין שלאחר יירוט הודעה $\ y$ שהוצפנה באמצעות צופן מושלם, אין ההסתברות של כל הודעה $\ x\isin P$ להיות ההודעה המקורית שווה, אלא שהסתברותה להיות ההודעה המקורית היא כהסתברותה להישלח לפני יירוט ההודעה.

[עריכה] פנקס חד פעמי

ערך מורחב – פנקס חד פעמי

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

לשיטה זו שני חסרונות עיקריים:

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

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

לכן, אם ברצוננו להצפין הודעות מאורך נתון כלשהו ולשמור על סודיות מושלמת, יהיה עלינו לייצר מפתחות שאורכם שווה לפחות לאורך זה. (ועל מנת שההסתברויות הנדרשות יהיו שוות באמת, יהיה צורך במחולל מספרים אקראיים שייצר מפתחות ארוכים כאלה באקראי)