הצגת המקור של הדף "סודיות מושלמת"

ב[[תורת האינפורמציה]] וב[[קריפטוגרפיה]], '''סודיות מושלמת''' (perfect secrecy) היא מונח המאפיין '''שיטת הצפנה בלתי ניתנת לשבירה''', גם אם מנתח הצופן או היריב הוא בעל עוצמת מחשוב בלתי מוגבלת וגם אם ברשותו [[מחשב קוונטי]]. זאת משום שבהינתן הטקסט המוצפן, פשוט אין בידי היריב מספיק מידע כדי לחלץ פרט מועיל כלשהו אודות הטקסט המקורי, לכן יירוט ההודעה המוצפנת לא תורם לו דבר. במילים אחרות מניתוח הטקסט המוצפן עולה שכל טקסט גלוי היה יכול להיות המקור במידה שווה. ההוכחה הפורמלית למונח מסתמכת על [[תורת ההסתברות]]. המונח הוטבע לראשונה על ידי [[קלוד שאנון]] ב-1949 במאמר{{הערה|[http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf Communication Theory of Secrecy Systems]}} הנחשב לפורץ דרך בתולדות ה[[הצפנה]] המודרנית.

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

==הגדרה פורמלית==
לצורך ההגדרה הפורמלית של סודיות מושלמת יש צורך להגדיר מספר מושגים בסיסיים{{הערה|[http://www.cs.umd.edu/~jkatz/imc.html Introduction to Modern Cryptography (2nd edition)], Jonathan Katz and Yehuda Lindell}}. [[אלגוריתם]] הצפנה מורכב משלושה אלגוריתמים;
*'''אלגוריתם הכנת מפתח Gen''' שמפיק מפתח הצפנה <math>k</math> מתוך [[מרחב הסתברות|מרחב]] המפתח <math>\mathcal{K}</math> באופן הסתברותי ב[[התפלגות]] מסוימת, בדרך כלל [[התפלגות אחידה בדידה|התפלגות אחידה]].
*'''אלגוריתם הצפנה Enc''' שמקבל כקלט <math>k\in\mathcal{K}</math> ו-<math>m\in\mathcal{M}</math>, מצפין את <math>m</math> עם המפתח <math>k</math> ומחזיר את <math>c\in\mathcal{C}</math>. באופן פורמלי <math>c=\text{Enc}_k(m)</math>. יש לציין שאלגוריתם ההצפנה יכול להיות [[אלגוריתם הסתברותי|הסתברותי]] במובן שעבור אותו מסר ואותו מפתח יכול להיות פלט שונה בכל הרצה של האלגוריתם. כדי להבדיל בין שני המקרים יש כאלו שמסמנים את ההצפנה ההסתברותית: <math>c\longleftarrow\text{Enc}_k(m)</math>.
*'''אלגוריתם פענוח Dec''' הוא [[אלגוריתם דטרמיניסטי]] שמקבל את <math>c\in\mathcal{C}</math> ואת <math>k\in\mathcal{K}</math> ומחזיר תמיד את <math>m\in\mathcal{M}</math> שהוצפן עם <math>k</math>.

ההנחה היא שהאלגוריתם שלם במובן שתמיד מתקיים <math>\text{Dec}_k(c)=m</math> בהסתברות 1. במילים אחרות
<center>
:<math>\text{Dec}_k(\text{Enc}_k(m))=m</math>.
</center>
עבור כל מפתח <math>k\in\mathcal{K}</math> מסמנים את ההסתברות שהמפתח שנבחר על ידי האלגוריתם Gen הוא <math>k</math> בביטוי <math>\Pr[K=k]</math>. באותו אופן, ההסתברות שטקסט גלוי ספציפי יישלח היא <math>\Pr[M=m]</math> וההסתברות שטקסט מוצפן כלשהו יופק על ידי האלגוריתם היא <math>\Pr[C=c]</math>. יש לציין ראשית, שהתפלגות הטקסט הגלוי <math>m</math> נפרדת ובלתי תלויה בהתפלגות המפתח <math>k</math>. יתרה מזו, המפתח נקבע ומשותף לשני הצדדים לפני שנודע מהו הטקסט הגלוי. בנוסף יש לציין שההנחה היא שההתפלגות של <math>m</math> ידועה. המתקיף או מנתח הצופן, אינו יודע בוודאות איזה טקסט גלוי יישלח אחרת אין כל טעם בהצפנה. לעומת זאת יש בידו מידע כללי [[הסתברות#מידת הסתברות|בהסתברות מסוימת]] לגבי הסיכויים שטקסט מסוים יישלח לעומת טקסט אחר. לדוגמה עשוי להיות מצב שהמתקיף יודע שהטקסט הגלוי '''"attack tomorrow"''' יישלח בהסתברות של שבעים אחוז לעומת '''"don't attack"''' בהסתברות של 30 אחוז. לכן <math>\Pr[M=\text{''attack tomorrow''}]=0.7</math> וכן <math>\Pr[M=\text{''don't attack''}]=0.3</math>. [[ללא הגבלת הכלליות]] ההנחה היא שההתפלגויות תמיד גדולות מאפס.

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

'''בניסוח פורמלי:''' סכימת הצפנה <math>(\text{Gen},\text{Enc},\text{Dec})</math> מעל מרחב המסרים <math>\mathcal{M}</math> תקרא בעלת סודיות מושלמת [[אם ורק אם]] עבור כל התפלגות של <math>\mathcal{M}</math>, כל טקסט גלוי <math>m\in\mathcal{M}</math> וכל טקסט מוצפן <math>c\in\mathcal{C}</math> מתקיים:
<center>
:<math>\boldsymbol{\Pr[C=c|M=m]=\Pr[C=c]}</math>.
</center>
הכוונה היא שההסתברות שיתקבל <math>c</math> מסוים בהינתן <math>m</math> מסוים שווה להסתברות שיתקבל <math>c</math> ללא ידיעת <math>m</math>.

'''הוכחה:'''
נתונה התפלגות מסוימת של <math>\mathcal{M}</math> ונתונים <math>m\in\mathcal{M}</math> ו-<math>c\in\mathcal{C}</math>. אם מכפילים את שני האגפי המשוואה האמורה ב-<math>\Pr[M=m]/\Pr[C=c]</math> מתקבל
<center>
:<math>\frac{\Pr[C=c|M=m]\cdot\Pr[M=m]}{\Pr[C=c]}=\Pr[M=m]</math>.
</center>
לפי [[חוק בייס]] האגף השמאלי שווה בדיוק ל-<math>\Pr[M=m|C=c]</math> לכן <math>\Pr[M=m|C=c]=\Pr[M=m]</math> ולכן הצופן מושלם. הדברים נכונים גם בכיוון ההפוך.

[[קלוד שאנון|שאנון]] הוכיח שכדי שצופן יקרא מושלם חובה שאורך מפתח ההצפנה יהיה לפחות כאורך הטקסט המיועד להצפנה. בניסוח פורמלי:
<center>
:<math>|\mathcal{K}|\ge|\mathcal{M}|</math>.
</center>
ההוכחה לכך היא נניח שהתנאי האמור לא מתקיים ו-<math>|\mathcal{K}|<|\mathcal{M}|</math>. יהי <math>\mathcal{M}(c)</math> קבוצת כל המסרים האפשריים שהם פענוח אפשרי של <math>c</math>. כלומר
<center>
:<math>\mathcal{M}(c)\overset{\underset{\mathrm{def}}{}}{=}\{\hat m|\hat m=\text{Dec}_{\hat k}(c)\text{ for }\hat k\in\mathcal{K}\}</math>
</center>
היות שפונקציית הפענוח דטרמיניסטית, עבור כל מסר <math>\hat m</math> קיים לפחות מפתח אחד <math>\hat k</math> כך שמתקיים <math>\hat m=\text{Dec}_{\hat k}(c)</math> מזה נובע <math>|\mathcal{M}(c)|\le|\mathcal{K}|</math>. בהנחה ש-<math>|\mathcal{K}|<|\mathcal{M}|</math> נכון בהכרח קיים <math>m'\in\mathcal{M}</math> שאינו נמנה עם <math>\mathcal{M}(c)</math>. אבל
<center>
:<math>\Pr[M=m'|C=c]=0\ne\Pr[M=m']</math>,
</center>
מה שמפר את הסודיות המושלמת של הצופן. מזה אפשר להסיק שכל מערכת הצפנה שבה מפתח ההצפנה קטן מהטקסט הגלוי אינה יכולה להיקרא מושלמת בשום אופן. יתרה מזו אפשר להוכיח גם שכדי שההצפנה תהיה מושלמת לא ניתן להשתמש באותו מפתח להצפנת שני מסרים או יותר.
<!-- נסמן את מרחב ההודעות המקוריות ב־<math>\ P</math>, (מהמילה Plaintext) ואת מרחב ההודעות המוצפנות ב<math>\ C</math> (מהמילה Ciphertext) ונגדיר [[הסתברות#מידת הסתברות|פונקציית הסתברות]] על <math>\ P</math> אשר תתאר את סבירות קבלתן של ההודעות הבלתי מוצפנות השונות.

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

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

==משפט שאנון==
במאמר המפורסם מ-1949 הניח [[קלוד שאנון]] את היסודות ל[[תורת האינפורמציה]] וההצפנה המודרנית. מהיבט של תורת האינפורמציה, בהינתן סכימת הצפנה <math>(\text{Gen},\text{Enc},\text{Dec})</math> מעל מרחב המסרים <math>\mathcal{M}</math> כך שמתקיים <math>|\mathcal{M}|=|\mathcal{K}|=|\mathcal{C}|</math> (כלומר אורכי הקלט, הפלט והמפתח זהים). הצופן יקרא בעל "סודיות מושלמת" אם ורק אם:
#כל מפתח <math>k\in\mathcal{K}</math> נבחר על ידי האלגוריתם Gen בהתפלגות <math>1/|\mathcal{K}|</math>.
#עבור כל <math>m\in\mathcal{M}</math> ועבור כל <math>c\in\mathcal{C}</math>, קיים מפתח '''יחיד''' <math>k</math> כך שמתקיים <math>\text{Dec}_k(c)=m</math>.
האינטואיציה מאחורי משפט זה היא, אם הצופן מקיים את התנאי השני אז כל טקסט מוצפן נתון יכול להיות תוצאת הצפנה של כל טקסט גלוי אפשרי. זאת משום שעבור כל טקסט גלוי <math>m</math> קיים מפתח <math>k</math> שממפה אותו ל-<math>c</math>. בשילוב העובדה שמפתח אחד בלבד ממפה את <math>m</math> ל-<math>c</math> ולפי התנאי הראשון שכל מפתח נבחר בסיכויים שווים אפשר להוכיח שהצופן מושלם כמו בפנקס חד-פעמי. מצד שני אם <math>|\mathcal{M}|=|\mathcal{K}|=|\mathcal{C}|</math> אז קיים בהכרח רק מפתח אחד הממפה כל <math>m</math> ל-<math>c</math>. אחרת, או שקיים <math>m</math> שלא ממופה לאף <math>c</math> או שקיים <math>m</math> שממופה על ידי יותר מ-<math>k</math> אחד ל-<math>c</math>. מה שמפר את הגדרת הסודיות המושלמת. לכן, בהכרח סיכוייו של כל מפתח להיבחר שווים, אחרת טקסט גלוי כלשהו יהיה בעל הסתברות שונה מהאחרים. מכאן התנאי הראשון.

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

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

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}

[[קטגוריה:הצפנה]]