צופן ורנם

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

ראשיתו של צופן זרם

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

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

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

בטיחות מושלמת

כדי שצופן ורנם יספק כאמור בטיחות מושלמת, על המפתח להיות אקראי אמיתי וחד פעמי, כלומר לא ניתן להצפין מידע נוסף באמצעות מפתח זה. כדי לראות מדוע, אם נכנה את המסר $\ m$ וזרם המפתח $\ k$ אזי צופן ורנם מצפין את המסר $\ m$ לקבלת הטקסט המוצפן $\ c$ בדרך זו:

$\ c=m\oplus k$

מכיוון ש-xor קומוטטיבי לכן חזרה על הפעולה האחרונה עם $\ c$ תניב:

$\ m=c\oplus k$

שזהו בעצם תהליך הפענוח. כעת נניח כי בידי המצפין המסרים $\ m_{1}$ ו-$\ m_{2}$ אותם הוא מעוניין להצפין, אם המצפין משתמש במפתח $\ k$ זהה כדי להצפין את שני המסרים הנ"ל יתקבל:

$\ c_{1}=m_{1}\oplus k$

$\ c_{2}=m_{2}\oplus k$

אם מצותת המאזין לשידור מסוגל לקרוא את כל התשדורות, אזי הוא יכול פשוט לחבר את הטקסטים המוצפנים $\ c_{1}$ ו-$\ c_{2}$ שהתקבלו זה לזה באותה השיטה, באמצעות XOR. אפשר לראות כי:

$\ c_{1}\oplus c_{2}=m_{1}\oplus k\oplus m_{2}\oplus k=m_{1}\oplus m_{2}\oplus k\oplus k=m_{1}\oplus m_{2}$

הרי שבידי המצותת יש כעת מושג די טוב לגבי מקור הצופן כיוון ש-$\ m_{1}\oplus m_{2}$ מכיל כעת את מחרוזות הטקסט המקוריות מחוברות זו לזו ב-XOR ללא מפתח ההצפנה. הפעולה הנ"ל למעשה הסירה את מפתח ההצפנה מהצופן והערך שנותר בידי המצותת הוא בעל אותה התפלגות סטטיסטית כשל הטקסטים המקוריים. בניתוח סטטיסטי פשוט ניתן לחשוף את המסרים המקוריים בקלות רבה.

בעיית העברת המפתח

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

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

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

לקריאה נוספת

• הספר Handbook of Applied Cryptography, לשימוש פרטי בלבד.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0