Frekans analizi - Frequency analysis

Diğer kullanımlar için bkz. Frekans analizi (belirsizliği giderme).
Tipik bir harf dağılımı ingilizce dili Metin. Zayıf şifreler dağıtımı yeterince maskelemez ve bu, bir kriptanalist tarafından mesajı okumak için kullanılabilir.

İçinde kriptanaliz, frekans analizi (Ayrıca şöyle bilinir harfleri saymak) çalışmasıdır harflerin sıklığı veya harf grupları bir şifreli metin. Yöntem kırılmaya yardımcı olarak kullanılır klasik şifreler.

Frekans analizi, yazılı dilin herhangi bir bölümünde, belirli harflerin ve harf kombinasyonlarının değişen frekanslarda ortaya çıktığı gerçeğine dayanır. Dahası, o dilin hemen hemen tüm örnekleri için kabaca aynı olan karakteristik bir harf dağılımı vardır. Örneğin, bir bölüm verildiğinde ingilizce dili, E, T, Bir ve Ö en yaygın olanı iken Z, Q, X ve J Nadir. Aynı şekilde, TH, ER, AÇIK, ve AN en yaygın harf çiftleridir ( Bigrams veya digraphs), ve SS, EE, TT, ve FF en yaygın tekrarlardır.[1] Saçma söz "ETAOIN SHRDLU ", tipik İngilizce metninde en sık kullanılan 12 harfi temsil eder.

Bazı şifrelerde, doğal dil düz metninin bu tür özellikleri şifreli metinde korunur ve bu kalıplar, bir yalnızca şifreli metin saldırısı.

Basit ikame şifreleri için frekans analizi

Basitçe ikame şifresi her harf düz metin başka bir harfle değiştirilir ve düz metindeki herhangi bir harf her zaman şifreli metinde aynı harfe dönüştürülür. Örneğin, mektubun tüm tekrarları e mektuba dönüşmek X, mektubun çok sayıda örneğini içeren bir şifreli metin mesajı X bir kriptanaliste şunu öneririm: X temsil eder e.

Frekans analizinin temel kullanımı, önce şifreli metin harflerinin sıklığını saymak ve ardından tahmin edilen düz metin harflerini onlarla ilişkilendirmektir. Daha Xs şifreli metindeki her şeyden çok X karşılık gelir e düz metinde, ancak bu kesin değil; t ve a İngilizcede de çok yaygındır, bu nedenle X bunlardan biri de olabilir. Düz metin olması olası değildir z veya q daha az yaygındır. Bu nedenle, kriptanalistin şifreli metin ve düz metin harfleri arasında birkaç eşleştirme kombinasyonunu denemesi gerekebilir.

Harf çiftlerinin sayısının dikkate alınması gibi istatistiklerin daha karmaşık kullanımı düşünülebilir (Bigrams), üçüzler (trigramlar), ve benzeri. Bu, örneğin kriptanaliste daha fazla bilgi sağlamak için yapılır. Q ve U İngilizcede neredeyse her zaman bu sırayla birlikte gerçekleşse de Q kendisi nadirdir.

Bir örnek

Varsayalım Havva araya girdi kriptogram aşağıdaki gibi basit bir ikame şifresi kullanılarak şifrelenmiş olduğu bilinmektedir: 

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIMWQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJGSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXVIZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLEPPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPPXLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

Bu örnekte, büyük harfler şifreli metni belirtmek için kullanılırken, küçük harfler düz metni belirtmek için kullanılır (veya bu tür tahminler) ve X~t şifreli metin mektubunun tahminini ifade etmek için kullanılır X düz metin mektubu temsil eder t.

Eve, aşağıdaki satırlarda mesajı çözmeye yardımcı olmak için frekans analizini kullanabilir: kriptograftaki harflerin sayısı ben en yaygın tek harftir[2] XL en yaygın Bigram, ve XLI en yaygın olanı trigram. e İngiliz dilinde en yaygın harftir, inci en yaygın bigramdır ve en yaygın trigramdır. Bu kesinlikle şunu gösteriyor: X~t, L~h ve ben~e. Kriptogramdaki en yaygın ikinci harf E; İngilizcede en sık görülen birinci ve ikinci harflerden beri, e ve t sayılır, Eve tahmin eder ki E~a, üçüncü en sık görülen harf. Bu varsayımlar geçici olarak yapılarak, aşağıdaki şifresi çözülmüş kısmi mesaj elde edilir.

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReMWQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJGSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtVeZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMthaPPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPPthMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

Eve, bu ilk tahminleri kullanarak, seçimlerini doğrulayan kalıpları belirleyebilir. Örneğin "o". Dahası, diğer kalıplar daha fazla tahmin önermektedir."Rtate" olabilir "durum"demek ki R~s. Benzer şekilde "atthattMZe"olarak tahmin edilebilir"o zaman", verimli M~ben ve Z~m. Dahası, "CENNET" olabilir "İşte"veren V~r. Bu tahminleri yerine getiren Eve şunları alır:

hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGaseiWQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJGSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtremitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQithaPPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPPthiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit

Buna karşılık, bu tahminler yine başkalarını önermektedir (örneğin, "remarA" olabilirdi "açıklama", ima ederek Bir~k) ve benzeri, ve harflerin geri kalanını çıkarmak nispeten basittir ve sonunda düz metni ortaya çıkarır.

hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscaseinwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsofcourseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextremityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywithalltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingallthingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit

Bu noktada, Havva'nın boşluk ve noktalama işareti eklemesi iyi bir fikir olabilir:

Bunun üzerine Legrand, büyük ve görkemli bir havayla ayağa kalktı ve içine kapatıldığı cam bir kasadan bana böceği getirdi. Bu güzel bir bokböcüydü ve o zamanlar doğa bilimcilerin bilmediği bir şeydi - elbette bilimsel bakış açısıyla büyük bir ödüldü. Sırtın bir ucunda ve diğerinin yanında iki yuvarlak siyah nokta vardı. Pullar son derece sert ve parlaktı, tüm parlak altın görünümleriyle. Böceğin ağırlığı çok dikkat çekiciydi ve her şeyi hesaba katarsak, Jüpiter'i ona ilişkin görüşlerinden dolayı suçlayamam.

Bu örnekte Altın böcek, Eve'in tahminleri doğruydu. Ancak bu her zaman böyle olmayacaktır; Tek tek düz metinler için istatistikteki varyasyon, ilk tahminlerin yanlış olduğu anlamına gelebilir. Gerekli olabilir geri dönüş yanlış tahminler veya mevcut istatistikleri yukarıdaki örnekte verilen biraz basitleştirilmiş gerekçelerden çok daha derinlemesine analiz etmek.

Açık metnin harf frekanslarının beklenen dağılımını göstermemesi de mümkündür. Daha kısa mesajların daha fazla varyasyon göstermesi muhtemeldir. Yapay olarak çarpık metinler oluşturmak da mümkündür. Örneğin, tüm romanlar yazılmıştır. "e"tamamen - bir edebiyat biçimi olarak bilinen lipogram.

Tarih ve kullanım

İlk sayfası Al-Kindi 9. yüzyıl Kriptografik Mesajların Deşifre Edilmesine İlişkin Makale
Arapça Harf Frekansı dağıtım.

Frekans analizinin (aslında, her türlü kriptanalizin) bilinen ilk kayıtlı açıklaması, 9. yüzyılda Al-Kindi, bir Arap çok yönlü, içinde Kriptografik Mesajların Deşifre Edilmesi Üzerine Bir Makale.[3] Yakın metinsel çalışma önerilmiştir. Kuran ilk önce gün ışığına çıkardı Arapça karakteristik bir harf frekansına sahiptir.[4] Kullanımı yayıldı ve benzer sistemler, Avrupa devletlerinde yaygın olarak kullanıldı. Rönesans. 1474'e kadar, Cicco Simonetta şifrelerin deşifre edilmesiyle ilgili bir kılavuz yazmıştı Latince ve İtalyan Metin.[5] Arapça Harf Frekansı ve tüm kitabın harf ve kelime frekansı analizinin ayrıntılı bir çalışması Kuran Intellaren Makaleleri tarafından sağlanmaktadır.[6]

Basit ikame şifrelemelerinde bu zayıflığı ortadan kaldırmak için kriptograflar tarafından birkaç şema icat edildi. Bunlar dahil:

  • Homofonik ikame: Kullanımı sesteş sözcükler - aksi takdirde monoalphabetic ikame şifrelerindeki en yaygın harflere birkaç alternatif. Örneğin, İngilizce için hem X hem de Y şifreli metni, düz metin E anlamına gelebilir.
  • Polifabetik ikame yani, çeşitli alfabelerin kullanımı - çeşitli, aşağı yukarı dolambaçlı yollarla (Leone Alberti bunu öneren ilk kişi gibi görünüyor); ve
  • Polygraphic ikame, düz metin harf çiftlerinin veya üçlülerinin tek harf yerine ikame birimleri olarak ele alındığı şemalar, örneğin, Playfair şifresi tarafından icat edildi Charles Wheatstone 19. yüzyılın ortalarında.

Frekans sayma saldırılarını yenmeye yönelik tüm bu girişimlerin bir dezavantajı, hem şifreleme hem de deşifre etme karmaşıklığını artırarak hatalara yol açmasıdır. Ünlü olarak, bir İngiliz Dışişleri Bakanı'nın Playfair şifresini reddettiği söyleniyor, çünkü okul çocukları Wheatstone ve Playfair'in gösterdiği gibi başarılı bir şekilde başa çıkabilseler bile, "ataşelerimiz asla öğrenemezdi!".

rotor makineleri 20. yüzyılın ilk yarısının (örneğin, Enigma makinesi ) basit frekans analizine karşı bağışıktı. Ancak, diğer analiz türleri ("saldırılar") bu makinelerin bazılarından gelen mesajları başarıyla çözdü.

İspanyolca harf frekansları.

Frekans analizi, düz metin dilinin istatistiklerinin yalnızca temel bir anlayışını ve bazı problem çözme becerilerini ve elle yapılırsa kapsamlı mektup defter tutma toleransı gerektirir. Sırasında Dünya Savaşı II (İkinci Dünya Savaşı), hem ingiliz ve Amerikalılar işe alınan kod kırıcılar yerleştirilerek bulmaca büyük gazetelerdeki bulmacalar ve bunları en hızlı kimin çözebileceği için yarışmalar. Tarafından kullanılan şifrelerin birkaçı Mihver güçleri frekans analizi kullanılarak kırılabilirdi, örneğin Japonlar tarafından kullanılan bazı konsolosluk şifreleri. Harf sayma ve istatistiksel analizin mekanik yöntemleri (genellikle IBM kart tipi makineler) ilk kez II.Dünya Savaşı'nda, muhtemelen ABD Ordusu tarafından kullanılmıştır. SIS. Bugün, harf sayma ve analizinin zor işi, yerini bilgisayar yazılım, bu tür bir analizi saniyeler içinde gerçekleştirebilir. Modern bilgi işlem gücüyle, klasik şifrelerin gizli veriler için gerçek bir koruma sağlama olasılığı düşüktür.

Kurguda frekans analizi

Kriptogramın bir parçası Dans Eden Adamlar

Frekans analizi kurguyla anlatılmıştır. Edgar Allan Poe 's "Altın böcek ", ve Sör Arthur Conan Doyle'un Sherlock Holmes masal "Dans Eden Adamların Serüveni "basit ikame şifrelerine saldırmak için frekans analizinin kullanımını tanımlayan hikaye örnekleridir. Poe hikayesindeki şifre birkaç aldatma önlemi ile kaplanmıştır, ancak bu, kriptografik olarak önemli olan her şeyden çok edebi bir cihazdır.

Ayrıca bakınız

daha fazla okuma

  • Helen Fouché Gaines, "Kriptanaliz", 1939, Dover. ISBN  0-486-20097-3
  • Abraham Sinkov, "Elementary Cryptanalysis: A Mathematical Approach", The Mathematical Association of America, 1966. ISBN  0-88385-622-0.

Referanslar

  1. ^ Singh, Simon. "Kara Oda: İpuçları ve Püf Noktaları". Alındı 26 Ekim 2010.
  2. ^ "Bill'in" A security site.com'daki yöntemin çalışılmış bir örneği"". Arşivlenen orijinal 2013-10-20 tarihinde. Alındı 2012-12-31.
  3. ^ İbrahim A. Al-Kadı "Kriptolojinin kökenleri: Arap katkıları", Kriptoloji, 16 (2) (Nisan 1992) s. 97–126.
  4. ^ "Bizim Zamanımızda: Kriptografi". BBC Radyo 4. Alındı 29 Nisan 2012.
  5. ^ Kahn, David L. (1996). Şifre kırıcılar: gizli yazmanın hikayesi. New York: Yazar. ISBN  0-684-83130-9.
  6. ^ Madi, Mohsen M. (2010). "Kuran Sureleri İstatistikleri". Intellaren Makaleleri. Alındı 16 Ocak 2011.

Dış bağlantılar