פנקס חד-פעמי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
גל ארגוב סופר (שיחה | תרומות) מ תקלדה, הגהה |
Orielno Bot (שיחה | תרומות) מ clean up, replaced: ← [[התפלגות אחידה בדידה| (2) באמצעות [[ויקיפדיה:AutoWikiBrowser|AWB |
||
שורה 5:
לצורך הפשטות מניחים שהמסר להצפנה מיוצג כ[[מחרוזת (מדעי המחשב)|מחרוזת]] [[בסיס בינארי|בינארית]] (שהוא הייצוג הטבעי ב[[מחשב]]). המפתח המשמש להצפנה מיוצג גם הוא כמחרוזת בינארית שאורכה כאורך הקלט. ההצפנה מבוצעת על ידי פעולת [[XOR]] ([[חשבון מודולרי|חיבור מודולו 2]] המיוצג באמצעות הסמל <math>\oplus</math>) של המסר עם המפתח [[סיבית]] אחר סיבית. הפענוח מבוצע באותה דרך, אך עם הצופן והמפתח. בהצגה מתמטית:
'''הצפנה''': <math>\ c=m\oplus k</math>
'''פענוח''': <math>\ m=c\oplus k</math>
לדוגמה אם נתון המסר <math>m</math> והמפתח <math>k</math> שניהם באורך 32 סיביות תוצאת ההצפנה של <math>m</math> עם <math>k</math> היא <math>c</math> כך:
שורה 48:
כמו כן <math>c_1\oplus c_2\oplus m_2=m_1</math> ולהפך <math>\ c_1\oplus c_2\oplus m_1=m_2</math>.
הסיבה לשימוש ב-XOR במקום פעולה בינארית אחרת כמו [[OR]] או [[AND]], נובעת מהעובדה ש-XOR משמר אקראיות. אפשר להוכיח זאת בכמה דרכים, אבל מספיק להתבונן בטבלת האמת של XOR ולראות שהיא מכילה בדיוק 50% אפס ו-50% אחד, לעומת הפעולות OR ו-AND בהן היחס הוא 1 ל-3. כלומר התפלגות התוצאות של פעולת חיבור סיביות מודולו 2 אחידה.
קל להבין זאת במקרה של סיבית בודדת. אם נתון [[משתנה מקרי]] <math>Y</math> מעל <math>\{0,1\}</math> בהתפלגות שאינה בהכרח אחידה, כלומר הסיכויים שיתקבל "0" הם <math>p_0</math> והסיכויים שיתקבל "1" הם <math>p_1</math>, כאשר <math>p_0+p_1=1</math>, ונניח שנתון משתנה מקרי בלתי תלוי <math>X</math> בהתפלגות אחידה (סיכויים של <math>1/2</math> לאפס או אחד כמו ב[[הטלת מטבע]]). אפשר לראות שההסתברות ש-<math>Z=X\oplus Y</math> שווה "0" שווה להסתברות ש-<math>(x,y)=(0,0)</math> ועוד ההסתברות ש-<math>(x,y)=(1,1)</math> (כי לפי טבלת האמת של XOR רק בשני מקרים אלו התוצאה תהיה אפס). במקרה הראשון למשל ההסתברות היא <math>p_0</math> כפול <math>1/2</math>. בחשבון פשוט יוצא אם כך ש-<math>\textstyle\frac{p_0}{2}+\frac{p_1}{2}=1/2</math>. כלומר לא משנה מה הייתה ההתפלגות של <math>Y</math>, התוצאה <math>Z</math> תתפלג תמיד באופן אחיד.
==פנקס רב-פעמי==
תנאי הכרחי בפנקס חד-פעמי שהוא ישמש להצפנת מסר אחד בלבד. אם משתמשים באותו פנקס להצפנת שני מסרים מה שקרוי "פנקס דו-פעמי" או יותר, גורמים כאמור לשבירה מוחלטת של הצופן. למרות זאת לאורך השנים לא תמיד הקפידו על כך. המקרה הראשון והמפורסם ביותר היה המחדל הסובייטי בפרשת [[מסמכי וינונה]]. בגלל התהליך המפרך של הכנת פנקס חד פעמי (בזמנו הדבר בוצע באמצעות [[קוביית משחק|הטלת קוביות]]), המפעילים התעצלו ו"מיחזרו" פנקסים שכבר נעשה בהם שימוש. מה שאפשר למודיעין האמריקאי לפענח במשך שנים רבות תשדורות סודיות של מרגלים רוסים.
מקרה אחר מהתקופה האחרונה קשור בפרוטוקול [[PPTP]] של [[מיקרוסופט]] שנקרא MS-PPTP שבגרסה הראשונה שלו, הצפנת כל המסרים שנשלחו מהלקוח לשרת ומהשרת ללקוח בוצעה באמצעות אותו מפתח. הבעיה הייתה שהצופן איתו עשו מיקרוסופט שימוש היה [[RC4]] שהוא צופן זרם. כדי לפרוץ את הפרוטוקול כל מה שהמתקיף נדרש לעשות הוא לבצע XOR בין המסרים המוצפנים של השרת לבין המסרים המוצפנים של הלקוח, בכך אפקטיבית הוא מסיר את ההצפנה. הפרוטוקול המביך הזה הכיל מלבד זאת כשלים רבים וגם לאחר שתוקן לא היה בטוח יותר.
דוגמה נוספת גרועה אף יותר היא פרוטוקול [[WEP]] שבגרסאות הראשונות שלו הכנת המפתח לצורך הצפנה הייתה באמצעות [[וקטור אתחול]] שיחד עם המפתח הסודי מוזן ל-RC4 המייצר את זרם המפתח לצורך הצפנת הפריים ב-XOR. כל פריים הוצפן עם מפתח אחר שהוא פונקציה של המפתח הסודי הקבוע יחד עם וקטור אתחול שונה. היו שתי בעיות חמורות. ראשית, וקטור האתחול היה בעצם מספר סידורי של הפריים והוא שודר בגלוי, היות שווקטור האתחול היה באורך 24 סיביות המשמעות היא שהוא מתאפס אחרי <math>2^{24}</math> או 16 מיליון פריימים שזה לא הרבה במונחים של ימינו. שנית, בכרטיסים מסוימים לאחר כיבוי והפעלה וקטור האתחול היה מתאפס. בשני מקרים אילו מה שקרה זה שמסרים שונים הוצפנו עם אותו מפתח, כשהמשמעות היא שבירה מוחלטת של הפרוטוקול. פרוטוקול זה הכיל כשלים רבים נוספים מה שהוביל לבסוף להחלפתו בפרוטוקול [[WPA]].
שורה 64:
==סודיות מושלמת==
{{הפניה לערך מורחב|סודיות מושלמת}}
שנים רבות מאז המצאתו נחשב פנקס חד-פעמי ל"קשה מאוד לשבירה", אך לא הייתה הוכחה מתמטית שהוא אינו ניתן לשבירה כלל. את ההוכחה לכך סיפק [[קלוד שנון]], אבי [[תורת האינפורמציה]], במאמר משנת [[1949]]. שנון הגדיר "סודיות מושלמת" כהצפנה שבה ידיעת המסר המוצפן לא מוסיפה שום אינפורמציה לידיעת המסר המקורי. תנאי זה ניתן לתיאור במספר דרכים שקולות. שנון התבסס על מושג ה[[אנטרופיה (סטטיסטיקה)|אנטרופיה]] שאותו הגדיר, אשר מהווה במובן מסוים [[כימות]] של כמות האינפורמציה המצויה בהתפלגות נתונה. בנוסף, ניתן לנסח את התנאי באופן ישיר וללא שימוש באנטרופיה.
לצורך ההגדרה משתמשים ב[[מרחב הסתברות]] שבו הטקסט הגלוי נבחר באקראי (מתוך [[התפלגות]] כלשהי, לאו דווקא [[התפלגות אחידה בדידה|אחידה]]) ומוצפן על ידי [[מפתח (קריפטוגרפיה)|מפתח]] שהוגרל באקראי (באופן [[התפלגות אחידה בדידה|אחיד]]). אם <math>\ M,\ C,\ K</math> הם [[משתנה מקרי|משתנים מקריים]] של מרחב הסתברות המייצגים את המסר, המפתח והצופן בהתאמה, אז סודיות מושלמת מתקיימת אם מתקיים <math>\ P(M|C)=P(M)</math>, כלומר ההסתברות לכך שהוגרל מסר מסוים אם '''ידוע''' [[כתב סתר|כתב הסתר]] המתאים לו, שווה להסתברות שאותו מסר הוגרל מבלי שידוע שום מידע נוסף עליו. במילים אחרות, המשתנה המקרי שמייצג את ההודעות שנבחרות באקראי, והמשתנה המקרי שמייצג את כתבי הסתר שנוצרים באקראי הם [[תלות (סטטיסטיקה)|בלתי תלויים]]. בניסוחו השקול של שנון, אם <math>\ H()</math> מייצגת את פונקציית [[אנטרופיה (סטטיסטיקה)|האנטרופיה]] אזי התנאי לסודיות מושלמת הוא <math>\ H(M|C)=H(M)</math> - כלומר, שהאינפורמציה שבמשתנה המקרי <math>\ M</math> שווה לאינפורמציה שבמשתנה המקרי המותנה <math>\ M|C</math>. (תנאי זה ניתן להצגה באופן שקול כ-<math>\ I(M;C)=0</math>, כלומר האינפורמציה המשותפת של שני המשתנים היא 0).
לדוגמה, אם ידוע כי תשובה לשאלה כלשהי, שיכולה להיות "כן" או "לא", הוצפנה, וידוע שההסתברות של כל "כן" היא 1/3 ושל "לא" היא 2/3 (ולכן ההסתברות של מילים אחרות, למשל "ים" היא 0), הרי ששיטת ההצפנה תיחשב מושלמת אם בהינתן ידיעת ההודעה המוצפנת (למשל, "םר") ההסתברות ש"כן" היא המילה שהוצפנה היא עדיין 1/3 וההסתברות ש"לא" הוצפנה היא עדיין 2/3.
שורה 82:
הצורך במפתח שאורכו כאורך המסר המיועד להצפנה, הוא חיסרון בולט שהופך שליחת מסרים ארוכים לבעייתית. הן בשל הקושי בייצור כמות גדולה של חומר מפתח והן בשל הקושי להשמיד את המפתח לאחר השימוש בו כדי שלא ייפול לידיים הלא נכונות (ידוע שגם אם גורסים [[DVD]], שמכיל מפתח, לחלקים קטנים, עדיין אפשר לשחזר מתוכם כמות לא מועטה של חומר מפתח), כמו כן ידוע שגם לאחר מחיקה של קטע הזיכרון בכונן הקשיח המכיל את המפתח אפשר לשחזרו עם ציוד מתאים, אפילו לאחר זמן רב ואפילו אם נדרס במידע אחר.
בעיה מרכזית נוספת היא [[בעיית הפצת מפתחות|בעיית העברת מפתח]] האופיינית לכל שיטת [[הצפנה סימטרית]] - כדי ששני הצדדים יוכלו להיתקשר ביניהם עליהם לשתף מפתח, לשם כך הם צריכים למצוא 'ערוץ בטוח' להעברת המפתח הסודי מאחד לשני (אם על ידי פגישה פיזית או באמצעות שליח מהימן). אם הצדדים ימצאו דרך בטוחה להעביר ביניהם מפתח סודי כאורך המסר, הרי שהם לא זקוקים להצפנה כלל, כי הם יכולים לנצל דרך זו להעברת המסר עצמו.
שיטות ההצפנה ה[[מפתח ציבורי|א-סימטריות]] ובראשן [[RSA]] פותרות חלקית את הבעיה. אפשר להשתמש בהצפנה אסימטרית, כדי לשתף מפתח (קטן יחסית) ולאחר מכן להשתמש בצופן סימטרי מהיר כמו [[AES]] כדי להעביר את המסר עצמו. פתרון זה לא יועיל במקרה של הצפנת מפתח חד-פעמי מכיוון שהקושי בהעברת המפתח זהה לקושי שבהעברת המסר עצמו.
שורה 96:
}}.
{{להשלים}}
===יישום פנקס חד-פעמי באמצעות הצפנה קוונטית===
| |||