קרוב ל-300 שנה נדרשו כדי לפענח את צופן ההחלפה המוגן במפתח, שנחשב "בלתי ניתן לפיצוח". סודות ההצפנה: כתבה רביעית בסדרה

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

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

תקופה ארוכה כונה צופן ויז'נר "le chiffre indéchiffrable" בצרפתית, כלומר "הצופן הבלתי ניתן לפיצוח". בשנת 1863 פרסם לבסוף פרידריך קסיסקי (Kasiski), שהיה קצין בצבא הפרוסי, שיטה שמקלה מאוד על פיצוחו וקרויה כיום על שמו. הקרדיט האמיתי על ההישג מגיע דווקא למתמטיקאי והממציא הבריטי צ'רלס בבג' (Babbage), שנודע בראש ובראשונה בזכות מכונות החישוב המכניות שבנה, ששימשו בסיס כעבור עשרות שנים לפיתוח המחשב המודרני. בבג' פיצח את הצופן כמעט בדרך אגב, בעקבות אתגר שהציב לפניו רופא שיניים חובב צפנים. אולם ממשלת בריטניה הטילה איפול על השיטה, כדי שלא תיפול לידי אויבי הממלכה במלחמת קרים, וקסיסקי נהנה מן ההפקר.

צ'רלס בבג' | איור: roseed abbas, Shutterstock
הראשון לפצח את צופן ויזנר היה המתמטיקאי והממציא הבריטי, אולם קסיסקי הפרוסי זכה בקרדיט. צ'רלס בבג' | איור: roseed abbas, Shutterstock 

שיטת הפיצוח

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

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

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

דוגמה

נשתמש בריבוע ויז'נר

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

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

כעת נצפין את הפתגם המקורי: "לא דובים ולא יער" באמצעות אותה מילת מפתח:

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

תנ נקלאא קתנ רזח

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

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

חומר למחשבה

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

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

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

אתגר לחובבי ההסתברות

אחת ההנחות של קסיסקי היא שהסבירות לכך ששתי מילים שונות יוצפנו כאותו צירוף אותיות היא קלושה. 

*התשובה נמצאת בתגובות

2 תגובות

  • דניאל

    סדרת כתבות נחמדה ממש! תמשיכו

    סדרת כתבות נחמדה ממש! תמשיכו בבקשה עד שנגיע לאניגמה (-:

  • מומחה מצוות מכון דוידסוןמאיה קאהן

    פתרון האתגר

    תשובה: נסמן את האותיות בטקסט כ-ø ,ß. ואת אותיות המפתח כ-Ω, ‏∆. הכלל הוא: ø+∆ = ß+Ω. אם אחד מהסכומים עובר את 22 (מספר האותיות באלפבית העברי) נחסיר ממנו 22.

    לדוגמה: האותיות בטקסט הן א' וש' ואותיות המפתח הן ג' וה'. במקרה הראשון א+ג=1+3=4 ובמקרה השני ש+ה=21+5=26, נחסיר 22 ונקבל 4. נקבל שהאות המוצפנת תהיה ד' בשני המקרים.