שיטת קסיסקי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
אין תמונה חופשית

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

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

שלבים לחישוב אורך המפתח (KEY) שבו השתמשו להצפנת המסר/הטקסט:

שלב א'[עריכת קוד מקור | עריכה]

מעבר על הצופן וחיפוש בו חזרות של מחורזות תווים. החזרות צריכות להיות מעל ל-3 תווים (בכל מחרוזות) כדי שיהיה פיענוח מוצלח בהכרח. רישום המרחק בין תחילת מחרוזת חוזרות בצופן (מספר התווים בין תחילת כל מחרוזת שחוזרת בצופן). המרחקים הללו הם מכפלות של אורך המפתח של הצופן. כיוון שאם מחרוזת חוזרת על עצמה, קרוב לוודאי שהמסר/טקסט המקור חזר על עצמו, ולא רק זה גם המפתח הצפין את החזרה באותה צורה (כל אות הוסטה באותה צורה), ומפה נובע שהמרחק בין שתי המחרוזות הוא מכפלה של המפתח, שאמור להתחיל בהצפנה השנייה היכן שהתחיל בהצפנה הראשונה. דוגמה: המילה החוזרת על עצמה ABC: ABCXSGDGSDGABC 01234567890123 המרחק בין שתי המילים החוזרות בטקסט הוא 10.

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

מציאת המחלק הגדול ביותר (GCD) בין כל המרחקים שמצאנו בשלב א'. כיוון שכל המרחקים הם מכפלה באותו מפתח, כאשר נמצא את המחלק הגדול ביותר נמצא את אורך המפתח.

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

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

נבנה טבלה עם K עמודות (K=אורך המפתח) - נכניס לכל עמודה את האות בצופן במקום המתאים שלה לפי אורך המפתח. למשל האות הראשונה בצופן תהיה בעמודה הראשונה, השנייה בעמודה השנייה עד לעמודה ה-K ואת האות ה-K+1 לעמודה ה-1 שוב. וכך הלאה עבור על אותיות הצופן. בסיום - כל עמודה הוצפנה בעזרת התמרה מונו-אלפביתית - ונפענח את ההצפנה של כל עמודה לפי אנליזה של תדירות האותיות בשפה. ההצפנה תהיה נכונה לגבי כל העמודות, כלומר אם האות e הוצפנה בעמודה 1 לפי אות s, היא תוצפן כך גם בשאר העמודות בטבלה.

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

על ידי פיענוח הצופן - ניתן למצוא את המפתח שבו השתמשו להצפנה. או ניתן גם לנחש את המפתח במהלך הפיענוח.

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

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

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

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

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

ההמשך כמו מקודם - פיענוח המפתח באותה צורה (חלוקה לעמודות)