צופן ויז'נר

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

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

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

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

צופן ויז'נר פשוט עם מחזוריות \ t, מעל אלפבית בעל \ s אותיות, ממפה מפתח בעל \ t ערכים \ k_1, k_2, ..., k_t על אותיות המסר \ m_1, m_2,m_3 ... בעזרת הפונקציה \ c_i = (m_i + k_i) \mbox{ mod } s לקבלת הטקסט המוצפן \ c_1, c_2, ..., c_t. כאשר אינדקס המפתחות \ i מצומצם מודולו \ t, כלומר המפתח מחזורי. לאחר שמשתמשים במפתח \ k_t חוזרים להשתמש במפתח \ k_1 וכן הלאה עד לגמר המסר.

לצורך המחשה, בצופן החלפה חד-אלפביתי, החלפת כל אות במילה "אמת" באות השלישית הבאה אחריה תתן: "דעג" (אותיות סופיות לא הובאו במנין), האות "ת" הוחלפה באות השלישית מההתחלה (ההזזה היא מחזורית) כשהמפתח הוא \ k = 3. בצופן החלפה רב-אלפביתי לעומת זאת, ההחלפה היא מרובה במובן שכל אות במסר מוחלפת לפי מפתח (היסט) אחר, האות הראשונה מוחלפת במרחק המוגדר על ידי המפתח \ k_1, האות השנייה לפי\ k_2... האות \ t במסר מוחלפת לפי \ k_t ואילו האות \ t+1 מוחלפת לפי \ k_1 וחוזר חלילה. בדוגמה לעיל בהינתן מפתח \ k_1=1,k_2=2,k_3=3 אזי צופן ויז'נר מחליף את האות "א" במילה "אמת" באות "ב" (הזזה של 1) האות "מ" באות "ס" (הזזה של 2 אותיות) ואילו "ת" תוחלף באות "ג" (הזזה של 3 אותיות) ומתקבל "בסג". כדי להקל על תהליך ההצפנה והפענוח, ניתן להכין טבלה של כל ההיסטים האפשריים (ראו ריבוע ויז'נר בתמונה).

ישנן גרסאות נוספות של צופן ויז'נר הבסיסי המתואר לעיל, בהן:

  • צופן ויז'נר מורכב - צופן זה משתמש בפונקציית מיפוי מורכבת יותר מהמתואר לעיל והיא: \ c_i = m_i + (k^1_i + k^2_i + ... + k^r_i) \mbox{ mod } s. כל אחד מהמפתחות \ k^j הוא בעל מחזוריות \ t_j שונה (הציון התחתי \ i מייצג את האות ה-\ i של המפתח \ k^j). צופן זה הוא בעצם יישום רציף של \ r צפני ויז'נר פשוטים. המחזוריות של צופן זה היא המכנה המשותף של \ t_1,...,t_r מחזורי צופן ויזנ'ר פשוטים.
  • צופן ביופורט (Beaufort) - דומה לצופן ויזנ'ר הפשוט אולם משתמש בפונקציית המיפוי \ c_i = k_i-m_i \mbox{ mod }s.
  • ויז'נר מעורב - הוא שילוב של צופן ויז'נר הפשוט עם פונקציית החלפה (תמורה) לא בהכרח פונקציית הזזה אלפביתית. השילוב יכול להתבצע בשני אופנים הראשון שילוב מאוחר: \ c_i=e(m_i)+k_i \mbox{ mod }s עם מיפוי הופכי לפענוח: \ m_i=e^{-1}(c_i-k_i)\mbox{ mod }s. הפונקציה \ e_i היא תמורה כלשהי. השני הוא שילוב מוקדם: \ c_i=e(m_i+k_i\mbox{ mod }s), כאשר המיפוי ההופכי הוא \ m_i=e^{-1}(c_i)-k_i\mbox{ mod }s.
  • ספר-צופן (Running key) - צופן ויזנ'ר נקרא ספר-צופן אם אורך המפתח \ k הנו באורך המסר. למשל מפתח ההצפנה יכול להיות קטע טקסט מתוך ספר כלשהו, ומכאן שמו. ספר צופן ניתן לחיזוק על ידי הצפנה חוזרת של המסר בעזרת מספר מפתחות שהם קטעי טקסט שונים. אם חוזרים על תהליך זה כארבע פעמים מטשטשים את יתירות השפה באופן כזה שהצופן המתקבל מתקרב באיכותו לפנקס חד פעמי.
  • מפתח עצמי (Auto-key) - צופן ויזנ'ר מסוג זה מיושם בעזרת מפתח ראשוני \ k שלאחר השימוש הראשוני בו, המסר עצמו משמש כמפתח הצפנה להצפנת יתר אותיות המסר בעזרת פונקציה: \ c_i = (m_i+m_{i-t})\mbox{ mod }s.

בטיחות[עריכת קוד מקור | עריכה]

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

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

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

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

  1. ^ Franksen, O. I. (1985) Mr. Babbage's Secret: The Tale of a Cipher—and APL. Prentice Hall

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