פנקס חד-פעמי

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

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

אופן ההצפנה[עריכת קוד מקור | עריכה]

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

כדי שההצפנה תהיה בטוחה על התנאים הבאים להתקיים: מפתח ההצפנה צריך להיבחר באופן אקראי, וכן אסור להשתמש בו יותר מפעם אחת. מהדרישה השנייה נגזר שמו של הצופן. שימוש חוזר במפתח יהפוך את הצופן לקל מאוד לשבירה - בהינתן שני מסרים שהוצפנו עם אותו מפתח, ביצוע חיבור בינארי (XOR) על שניהם, יחזיר את תוצאת XOR של שני המסרים (כשהם לא מוצפנים), כלומר יבטל את השפעת המפתח על הצופן ואז בהינתן אחד מהם ניתן לחשוף את השני בקלות. יתרה מזו, מצב זה משמר את תדירויות המסרים המקוריים, קיימות שיטות פשוטות יחסית המבוססות על ניתוח סטטיסטי להפרדתם זה מזה. לדוגמה אם נתונים המסרים \ m_1, m_2 ומפתח \ k והתוצאות לאחר הצפנה \ c_1=m_1\oplus k וכן \ c_2=m_2\oplus k, אפשר לראות ש-c_1\oplus c2 = m_1\oplus m_2 כמו כן c_1\oplus c_2\oplus m_2=m_1 ולהיפך \ c_1\oplus c_2\oplus m_1=m_2.

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

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

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

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

בשיטת הפנקס החד פעמי, הכתבים הגלויים, כתבי הסתר והמפתחות הם כולם מחרוזות ביטים מאותו האורך, למשל \ n. אם \ m הוא כתב גלוי אפשרי כלשהו ו-\ c הוא כתב סתר אפשרי כלשהו, אז קיים בדיוק מפתח יחיד שמעביר את \ m אל \ c: המפתח \ k=m\oplus c. מכאן נובע בפרט שההסתברות לקבלת \ c ככתב סתר היא אחידה לכל כתבי הסתר האפשריים ושווה ל-\ 2^{-n}; שהרי לכל כתב גלוי שנבחר \ m, ההסתברות ש-\ c תתקבל ממנו היא בדיוק ההסתברות שייבחר המפתח היחיד שמעביר את \ m אל \ c, והסתברות זו היא \ 2^{-n}.

כעת נובעת הסודיות המושלמת של הצופן באופן כמעט מיידי: \ P(M=m|C=c)=\frac{P(M=m\wedge C=c)}{P(C=c)}=\frac{2^{-n}P(M=m)}{2^{-n}}=P(M=m) (ה-\ 2^{-n} במונה מגיע מההסתברות לקבל את \ c מתוך \ m; זה שבמכנה מגיע מההסתברות לקבל את \ c בכלל, מכל כתב גלוי אפשרי).

תכונות[עריכת קוד מקור | עריכה]

שנון הוכיח כי תנאי הכרחי לכך שהצפנה תקרא מושלמת (Perfect secrecy) הוא ש-\ H(K) \ge H(M) כלומר רמת אי הוודאות של המפתח תהיה לכל הפחות כרמת אי הוודאות של המסר. לפיכך, במידה והמסרים מתפלגים באופן אחיד, אורך המפתח חייב להיות לכל הפחות כאורך המסר. באופן כללי, גודל מרחב המפתחות האפשריים חייב להיות לפחות כגודל מרחב ההודעות האפשריות.

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

חסרונות השיטה[עריכת קוד מקור | עריכה]

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

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

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

שימושים[עריכת קוד מקור | עריכה]

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Kahn. שוברי הצפנים ‎(The Codebreakers), 715. ISBN 0-684-83130-9.