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

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

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

הגדרה פורמלית

לצורך ההגדרה הפורמלית של סודיות מושלמת יש צורך להגדיר מספר מושגים בסיסיים. אלגוריתם הצפנה מורכב משלושה אלגוריתמים;

• אלגוריתם הכנת מפתח Gen שמפיק מפתח הצפנה $k$ מתוך מרחב המפתח ${\mathcal {K}}$ באופן הסתברותי בהתפלגות מסוימת, בדרך כלל התפלגות אחידה.
• אלגוריתם הצפנה Enc שמקבל כקלט $k\in {\mathcal {K}}$ ו-$m\in {\mathcal {M}}$, מצפין את $m$ עם המפתח $k$ ומחזיר את $c\in {\mathcal {C}}$. באופן פורמלי $c={\text{Enc}}_{k}(m)$. יש לציין שאלגוריתם ההצפנה יכול להיות הסתברותי במובן שעבור אותו מסר ואותו מפתח יכול להיות פלט שונה בכל הרצה של האלגוריתם. כדי להבדיל בין שני המקרים יש כאלו שמסמנים את ההצפנה ההסתברותית: $c\longleftarrow {\text{Enc}}_{k}(m)$.
• אלגוריתם פענוח Dec הוא אלגוריתם דטרמיניסטי שמקבל את $c\in {\mathcal {C}}$ ואת $k\in {\mathcal {K}}$ ומחזיר תמיד את $m\in {\mathcal {M}}$ שהוצפן עם $k$.

ההנחה היא שהאלגוריתם שלם במובן שתמיד מתקיים ${\text{Dec}}_{k}(c)=m$ בהסתברות 1. במילים אחרות

${\text{Dec}}_{k}({\text{Enc}}_{k}(m))=m$.

עבור כל מפתח $k\in {\mathcal {K}}$ מסמנים את ההסתברות שהמפתח שנבחר על ידי האלגוריתם Gen הוא $k$ בביטוי $\Pr[K=k]$. באותו אופן, ההסתברות שטקסט גלוי ספציפי יישלח היא $\Pr[M=m]$ וההסתברות שטקסט מוצפן כלשהו יופק על ידי האלגוריתם היא $\Pr[C=c]$. יש לציין ראשית, שהתפלגות הטקסט הגלוי $m$ נפרדת ובלתי תלויה בהתפלגות המפתח $k$. יתרה מזו, המפתח נקבע ומשותף לשני הצדדים לפני שנודע מהו הטקסט הגלוי. בנוסף יש לציין שההנחה היא שההתפלגות של $m$ ידועה. המתקיף או מנתח הצופן, אינו יודע בוודאות איזה טקסט גלוי יישלח אחרת אין כל טעם בהצפנה. לעומת זאת יש בידו מידע כללי בהסתברות מסוימת לגבי הסיכויים שטקסט מסוים יישלח לעומת טקסט אחר. לדוגמה עשוי להיות מצב שהמתקיף יודע שהטקסט הגלוי "attack tomorrow" יישלח בהסתברות של שבעים אחוז לעומת "don't attack" בהסתברות של 30 אחוז. לכן $\Pr[M={\text{''attack tomorrow''}}]=0.7$ וכן $\Pr[M={\text{''don't attack''}}]=0.3$. ללא הגבלת הכלליות ההנחה היא שההתפלגויות תמיד גדולות מאפס.

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

בניסוח פורמלי: סכימת הצפנה $({\text{Gen}},{\text{Enc}},{\text{Dec}})$ מעל מרחב המסרים ${\mathcal {M}}$ תקרא בעלת סודיות מושלמת אם ורק אם עבור כל התפלגות של ${\mathcal {M}}$, כל טקסט גלוי $m\in {\mathcal {M}}$ וכל טקסט מוצפן $c\in {\mathcal {C}}$ מתקיים:

${\boldsymbol {\Pr[C=c|M=m]=\Pr[C=c]}}$.

הכוונה היא שההסתברות שיתקבל $c$ מסוים בהינתן $m$ מסוים שווה להסתברות שיתקבל $c$ ללא ידיעת $m$.

הוכחה: נתונה התפלגות מסוימת של ${\mathcal {M}}$ ונתונים $m\in {\mathcal {M}}$ ו-$c\in {\mathcal {C}}$. אם מכפילים את שני האגפי המשוואה האמורה ב-$\Pr[M=m]/\Pr[C=c]$ מתקבל

${\frac {\Pr[C=c|M=m]\cdot \Pr[M=m]}{\Pr[C=c]}}=\Pr[M=m]$.

לפי חוק בייס האגף השמאלי שווה בדיוק ל-$\Pr[M=m|C=c]$ לכן $\Pr[M=m|C=c]=\Pr[M=m]$ ולכן הצופן מושלם. הדברים נכונים גם בכיוון ההפוך.

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

$|{\mathcal {K}}|\geq |{\mathcal {M}}|$.

ההוכחה לכך היא נניח שהתנאי האמור לא מתקיים ו-$|{\mathcal {K}}|<|{\mathcal {M}}|$. יהי ${\mathcal {M}}(c)$ קבוצת כל המסרים האפשריים שהם פענוח אפשרי של $c$. כלומר

${\mathcal {M}}(c){\overset {\underset {\mathrm {def} }{}}{=}}\{{\hat {m}}|{\hat {m}}={\text{Dec}}_{\hat {k}}(c){\text{ for }}{\hat {k}}\in {\mathcal {K}}\}$

היות שפונקציית הפענוח דטרמיניסטית, עבור כל מסר ${\hat {m}}$ קיים לפחות מפתח אחד ${\hat {k}}$ כך שמתקיים ${\hat {m}}={\text{Dec}}_{\hat {k}}(c)$ מזה נובע $|{\mathcal {M}}(c)|\leq |{\mathcal {K}}|$. בהנחה ש-$|{\mathcal {K}}|<|{\mathcal {M}}|$ נכון בהכרח קיים $m'\in {\mathcal {M}}$ שאינו נמנה עם ${\mathcal {M}}(c)$. אבל

$\Pr[M=m']|C=c]=0\neq \Pr[M=m']$,

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

משפט שאנון

במאמר המפורסם מ-1949 הניח קלוד שאנון את היסודות לתורת האינפורמציה וההצפנה המודרנית. מהיבט של תורת האינפורמציה, בהינתן סכימת הצפנה $({\text{Gen}},{\text{Enc}},{\text{Dec}})$ מעל מרחב המסרים ${\mathcal {M}}$ כך שמתקיים $|{\mathcal {M}}|=|{\mathcal {K}}|=|{\mathcal {C}}|$ (כלומר אורכי הקלט, הפלט והמפתח זהים). הצופן יקרא בעל "סודיות מושלמת" אם ורק אם:

1. כל מפתח $k\in {\mathcal {K}}$ נבחר על ידי האלגוריתם Gen בהתפלגות $1/|{\mathcal {K}}|$.
2. עבור כל $m\in {\mathcal {M}}$ ועבור כל $c\in {\mathcal {C}}$, קיים מפתח יחיד $k$ כך שמתקיים ${\text{Dec}}_{k}(m)=c$.

האינטואיציה מאחורי משפט זה היא, אם הצופן מקיים את התנאי השני אז כל טקסט מוצפן נתון יכול להיות תוצאת הצפנה של כל טקסט גלוי אפשרי. זאת משום שעבור כל טקסט גלוי $m$ קיים מפתח $k$ שממפה אותו ל-$c$. בשילוב העובדה שמפתח אחד בלבד ממפה את $m$ ל-$c$ ולפי התנאי הראשון שכל מפתח נבחר בסיכויים שווים אפשר להוכיח שהצופן מושלם כמו בפנקס חד-פעמי. מצד שני אם $|{\mathcal {M}}|=|{\mathcal {K}}|=|{\mathcal {C}}|$ אז קיים בהכרח רק מפתח אחד הממפה כל $m$ ל-$c$. אחרת, או שקיים $m$ שלא ממופה לאף $c$ או שקיים $m$ שממופה על ידי יותר מ-$k$ אחד ל-$c$. מה שמפר את הגדרת הסודיות המושלמת. לכן, בהכרח סיכוייו של כל מפתח להיבחר שווים, אחרת טקסט גלוי כלשהו יהיה בעל הסתברות שונה מהאחרים. מכאן התנאי הראשון.

פנקס חד פעמי

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

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

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

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

הערות שוליים

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