פנקס חד פעמי

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

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

קטע מפנקס חד-פעמי, במשמעותו הפשוטה: פנקס שבו מודפס רצף אקראי של אותיות

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

תוכן עניינים

1 אופן ההצפנה
2 סודיות מושלמת
3 חסרונות השיטה
4 שימושים
- 4.1 יישום פנקס חד-פעמי באמצעות הצפנה קוונטית
5 קישורים חיצוניים

[עריכה] אופן ההצפנה

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

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

[עריכה] סודיות מושלמת

למשך שנים רבות מאז המצאתו נחשב פנקס חד פעמי ל"קשה מאוד לשבירה", אך לא הייתה הוכחה מתמטית שהוא אינו ניתן לשבירה כלל. את ההוכחה לכך סיפק קלוד שנון, אבי תורת האינפורמציה, במאמר משנת 1949. שנון הגדיר "סודיות מושלמת" כהצפנה שבה ידיעת המסר המוצפן לא מוסיפה שום אינפורמציה לידיעת המסר המקורי. פירושו הוא שההסתברות שמסר $\ M$ מסוים הוצפן, שווה להסתברות המותנית שהמסר $\ M$ הוצפן בהינתן ידיעה של הצופן המקביל. למעשה, כל המסרים האפשריים סבירים במידה שווה. בניסוח מתמטי, אם $\ M,\ C,\ K$ הם משתנים מקריים המייצגים את המסר, המפתח והצופן בהתאמה, כאשר $\ H()$ מייצגת את פונקציית האנטרופיה אזי, $\ H(M|C)=H(M)$ וכן $\ I(M;C)=0$ . כלומר הצופן אינו תורם שום מידע לגבי המסר המקורי. שנון הוכיח כי תנאי הכרחי שהצפנה זו תקרא מושלמת (Perfect secrecy) היא ש- $\ H(K) \ge H(M)$ כלומר רמת אי הוודאות של המפתח תהיה לכל הפחות כרמת אי הוודאות של המסר. אם המפתח עצמאי ובאורך המסר אזי $\ H(K) = k$ , כלומר האנטרופיה שלו שווה למסר. לכן לפי שנון, אם $\ k \ge H(M)$ הצופן יקרא מושלם.

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

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

פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיפדיה ולהשלים אותו. ראו פירוט בדף השיחה.

[עריכה] חסרונות השיטה

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

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

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

[עריכה] שימושים

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

פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיפדיה ולהשלים אותו. ראו פירוט בדף השיחה.

[עריכה] יישום פנקס חד-פעמי באמצעות הצפנה קוונטית

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