ניתוח תדירויות
מתוך ויקיפדיה, האנציקלופדיה החופשית
במתמטיקה, בפיזיקה ובעיבוד אותות, ניתוח תדירות היא שיטה לפרק פונקציה,גל או אות למרכיביו התדריים כך שניתן להפיק את ספקטרום התדרים.
בקריפטוגרפיה, ניתוח תדירות הוא מעקב אחר התדירות של אותיות או קבוצות אותיות בטקסט מוצפן. השיטה משמשת כעזר בפענוח טקסטים המוצפנים בצפנים קלאסיים.
תוכן עניינים |
[עריכה] ניתוח תדירות עבור צפני החלפה פשוטים
בצופן החלפה פשוט, כל אות בטקסט המקור מוחלפת באות אחרת. כל אות מסוימת בטקסט המקור תמיד תומר לאותה אות בטקסט המוצפן. למשל, כל ה e יומרו ל X. טקסט מוצפן שמכיל הרבה X עשוי לרמז למנתח צפנים ש X מייצג e.
באמצעות ניתוח תדירות ראשית מחשבים את תדירות אותיות הטקסט המוצפן ואז מקשרים ניחושים של אותיות בטקסט המקור עמם. יותר אותיות X בטקסט המוצפן מרמזים שהאות X מתייחסת לאות e בטקסט המקור, אולם אין הדבר מובטח. הסיבה היא ש t וכן a הן גם כן אותיות נפוצות באנגלית כך שהאות X עשוייה להיות אחת מאותיות אלו גם כן. אין זה סביר שX תקושר עם z או q שהן פחות שכיחות. מכל האמור עולה כי מנתח צפנים עשוי להזדקק למספר צירופי מיפוים בין אותיות טקסט מוצפן לבין אותיות טקסט רגיל.
שימוש מורכב יותר בסטטיסטיקה עשוי להתרחש, כאשר מתחשבים בתדירות של זוגות אותיות וכן שלשות וכך הלאה. הדבר נעשה על מנת לספק יותר מידע למנתח הצפנים, למשל, האות Q והאות U כמעט תמיד מופיעות יחד כך ש Q ראשונה ו U שנייה. זאת למרות ש Q עצמה נדירה.
[עריכה] דוגמה
נניח שאיב יירטה את השדר המוצפן שלהלן. ידוע שהשדר מוצפן באמצעות צופן החלפה פשוט:
LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX
בדוגמה זו, אותיות לועזיות גדולות ישמשו לייצוג הטקסט המוצפן. אותיות קטנות ישמשו ליצוג הטקסט הרגיל (או אותיות שהם בגדר ניחוש לטקסט הרגיל). הסימון X~t ישמש כדי לבטא את הניחוש שהאות המוצפנת X מייצגת את האות הרגילה t.
איב יכולה להשתמש בניתוח תדירות כדי לפענח את ההודעה על פי הקווים הרעיוניים הבאים : ספירה של האותיות בכתב המוצפן מראה ש I היא האות השכיחה ביותר, ש XL הוא צירוף שני האותיות השכיח ביותר וכן ש XLI הוא צירוף שלושת האותיות השכיח ביותר. e היא האות השכיחה ביותר בשפה האנגלית, th צירוף שני האותיות השכיח ביותר וכן the צירוף שלושת האותיות השכיח ביותר בשפה. הדבר מחזק את האפשרות ש X~t, L~h וכן ש I~e. האות השנייה הכי נפוצה היא E; מאחר והאותיות התדירות ביותר בשפה הן e ו t אך הן כבר נמצאו, איב מציעה ש E~a. (שכן a היא האות השלישית הכי תדירה בשפה). לפי הנחות אלו מקבלים את ההודעה המפוענחת הבאה :
heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt
תוך שימוש בניחושים התחלתיים אלו, איב יכולה לאתר דפוסים שמתאימים לבחירותיה, כמו "that". יתר על כן, דפוסים אחרים מעלים אפשרויות ניחוש נוספות. "Rtate" עשוי להיות "state" ("מדינה" בתרגום מאנגלית). משמעות הדבר R~s. באמצעות ניחושים אלה, איב יכולה לאתר דפוסים שמאשרים את בחירותיה. למשל, "atthattMZe" עשוי להיות "atthattime" ("באותו הזמן" בתרגום מאנגלית). כך מקבלים M~i וכן Z~m. בנוסף, "heVe" עשוי להיות "here" ("כאן" בתרגום מאנגלית), ומתקבלת ההחלפה V~r. לאחר הזנת הניחושים האלה איב מקווה שיפתח לה צוהר לפענוח שארית ההודעה. היא מקבלת כעת את ההודעה המפוענחת הבאה :
hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit
ניחושים אלה מרמזים אודות החלפות נוספות ולבסוף מקבלים את טקסט המקור :
hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit
בדוגמה זו , ניחושיה של איב היו כולם נכונים. ברם, אין זה המצב תמיד. השינוי בסטטיסטיקה עובר טקסטים עשויה לגרור ניחושים התחלתיים שגויים. יתכן שיהיה צורך לפעול בשיטת ה backtracking כדי למצוא ניחושים שגויים או לנתח את הסטטיסטיקה הנתונה באופן מעמיק יותר.
קיימת אפשרות שטקסט המקור לא יקיים את הפילוג הצפוי של תדירות האותיות. הודעות קצרות יראו לפיכך יותר סטייה מהפילוג. קיימת אפשרות לייצר טקסטים מלאכותיים שעברו תהליך של השמטת אותיות מסוימות. צורת כתיבה שבה מיישמים זאת היא הליפוגרמה.
[עריכה] היסטוריה ושימוש
ההסבר הראשון שניתן לניתוח תדירות ניתן על ידי המתמטיקאי הערבי, בן המאה ה-9 , אבו יוסוף יעקוב אבן יצחק אל סבאח' אל-כינדי. ייתכן שלימוד מעמיק של הקוראן הוביל לראשונה לתפישה שלשפה הערבית יש תדירות אותיות אופינית. השימוש בניתוח תדירות היה כה נפוץ בתקופת הרנסאנס במדינות אירופה שמנתחי צופן פיתחו מספר שיטות להתגבר על כך. בין השיטות :
- שימוש ב"הומופונים"; מספר חלופות לאותיות הנפוצות ביותר בצפנים שנחשבים אחרת לצפני החלפה מונואלפבתיים.
- החלפה פוליאלפבתית כלומר שימוש במספר אלפבתים;
- החלפה פוליגרפית כלומר זוגות או שלשות של טקסט מקור מוחלפים כיחידה אחת. דוגמה לכך הוא צופן פלייפייר שהומצא על ידי צ'ארלס ויטסטון באמצע המאה ה-19.
החסרון של כל הנסיונות להביס את התקפות ניתוח התדירות היא הגדלת המורכבות של שיטות הקידוד והפענוח שמובילה לטעויות. הבריטים דחו את צופן פלייפייר משום שהיה מסובך מדי ללימוד עבור הנספחים .
מכונות הרוטורים של המחצית הראשונה של המאה ה-20 (למשל מכונת האניגמה) היו חסינות בפני התקפות ניתוח תדירות פשוטות. ברם, סוגים אחרים של התקפות סייעו בפענוח הודעות מוצפנות ממכונות אלו.
ניתוח תדירות דורש רק הבנה בסיסית בסטטיסטיקה של שפת טקסט המקור וכן מעט יכולת לפתור בעיות. אם הנתוח מבוצע ידנית דרושה סבלנות ויכולת לתחזק רשימות של אותיות. במהלך מלחמת העולם השנייה גייסו האמריקאים והבריטים מפענחי צפנים על ידי פרסום של תשבצים בעיתונים ועריכת תחרויות לגילוי הפותר המהיר ביותר. מספר מהצפנים ששימשו את מדינות הציר פוצחו באמצעות ניתוח תדירות (למשל, חלק מהצפנים הקונסולריים שהיו בשימוש היפנים). שיטות מכניות לספירת אותיות וניתוח סטטיסטי היו בשימוש לראשונה במלחמת העולם השנייה, כנראה על ידי מודיעין האותות של הצבא האמריקאי (ה SIS). כיום תוכנות מחשב יכולות לבצע ניתוח תדירות מלא בשניות. באמצעות מחשבים מודרניים, צפנים קלאסיים לא מספקים עוד כל הגנה על מידע חסוי.
[עריכה] ניתוח תדירות בספרות
ניתוח תדירות תואר בספרות על ידי אדגר אלן פו וארתור קונאן דויל.
[עריכה] ראו גם
- ETAOIN SHRDLU
- תדירות אותיות
[עריכה] מקורות
הערך מבוסס על תרגום ערך מקביל מהוויקיפדיה האנגלית שמקורותיו :
- Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN 0-486-20097-3
- Ibraham A. “Al-Kindi: The origins of cryptology: The Arab contributions”, Cryptologia, 16(2) (April 1992) pp. 97–126.
- Abraham Sinkov, "Elementary Cryptanalysis : A Mathematical Approach", The Mathematical Association of America, 1966. ISBN 0-88385-622-0.
