פנקס חד-פעמי

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

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

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

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

הצפנה: \ c=m\oplus k

פענוח: \ m=c\oplus k

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

לדוגמה, אם נתונים המסרים \ m_1, m_2 ומפתח \ k והתוצאות לאחר הצפנה הם \ c_1=m_1\oplus k וכן \ c_2=m_2\oplus k בהתאמה, אפשר לראות ש-

c_1\oplus c_2 = 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.

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

Postscript-viewer-shaded.png ערך מורחב – סודיות מושלמת

שנים רבות מאז המצאתו נחשב פנקס חד-פעמי ל"קשה מאוד לשבירה", אך לא הייתה הוכחה מתמטית שהוא אינו ניתן לשבירה כלל. את ההוכחה לכך סיפק קלוד שנון, אבי תורת האינפורמציה, במאמר משנת 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 כדי להעביר את המסר עצמו. פתרון זה לא יועיל במקרה של הצפנת מפתח חד-פעמי מכיוון שהקושי בהעברת המפתח זהה לקושי שבהעברת המסר עצמו.

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

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

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

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

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

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

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

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

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