Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для использования в других целях, см. Частотный анализ (значения) .
Типичное распределение букв в тексте на английском языке . Слабые шифры недостаточно маскируют распространение, и это может быть использовано криптоаналитиком для чтения сообщения.

В криптоанализе , частотный анализ (также известный как подсчет буквы ) является изучением частоты букв или групп букв в шифротексте . Метод используется для взлома классических шифров .

Частотный анализ основан на том факте, что на любом участке письменного языка определенные буквы и комбинации букв встречаются с разной частотой. Более того, существует характерное распределение букв, которое примерно одинаково почти для всех образцов этого языка. Например, учитывая раздел английского языка ,E, Т, А и О являются наиболее распространенными, а Z, Q, Икс и Jредки. Так же,TH, ER, НА, и ANявляются наиболее распространенными парами букв (называемыми биграммами или орграфами ), иSS, EE, TT, и FFявляются наиболее распространенными повторами. [1] Бессмысленная фраза « ETAOIN SHRDLU » представляет собой 12 наиболее часто встречающихся букв в типичном тексте на английском языке.

В некоторых шифрах такие свойства открытого текста естественного языка сохраняются в зашифрованном тексте, и эти шаблоны потенциально могут быть использованы при атаке только зашифрованного текста .

Частотный анализ для простых подстановочных шифров [ править ]

В простом шифре подстановки каждая буква открытого текста заменяется другой, и любая конкретная буква в открытом тексте всегда будет преобразована в ту же букву в зашифрованном тексте. Например, если все вхождения буквые превратиться в письмо Икс, зашифрованное сообщение, содержащее многочисленные экземпляры буквы Икс предложил криптоаналитику, что Икс представляет е.

Основное использование частотного анализа состоит в том, чтобы сначала подсчитать частоту появления букв зашифрованного текста, а затем связать с ними предполагаемые буквы открытого текста. БолееИксs в зашифрованном тексте, чем что-либо еще предполагает, что Икс соответствует е в открытом тексте, но это не точно; т и а также очень распространены в английском языке, поэтому Иксможет быть и одним из них. Вряд ли это будет открытый текстz или же qкоторые встречаются реже. Таким образом, криптоаналитику может потребоваться попробовать несколько комбинаций сопоставлений между зашифрованным текстом и буквами открытого текста.

Можно представить себе более сложное использование статистики, например, учет количества пар букв ( биграмм ), троек ( триграмм ) и так далее. Это сделано, чтобы предоставить криптоаналитику больше информации, например,Q и U почти всегда встречаются вместе в таком порядке на английском языке, хотя Q сам по себе редко.

Пример [ править ]

Предположим, что Ева перехватила криптограмму ниже, и известно, что она зашифрована с помощью простого шифра подстановки следующим образом: 

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIMWQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJGSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXVIZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLEPPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPPXLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

В этом примере прописные буквы используются для обозначения зашифрованного текста, строчные буквы используются для обозначения открытого текста (или предположений), и Икс~т используется для выражения предположения, что буква зашифрованного текста Икс представляет собой текстовую букву т.

Ева могла бы использовать частотный анализ, чтобы помочь решить сообщение в следующих строках: подсчет букв в криптограмме показывает, что ясамая распространенная буква, [2] XLнаиболее распространенная биграмма , иXLIэто наиболее распространенная триграмма .е это самая распространенная буква в английском языке, th является наиболее распространенной биграммой, и вэто наиболее распространенная триграмма. Это убедительно свидетельствует о том, чтоИкс~т, L~час и я~е. Вторая по частоте буква в криптограмме -E; так как первая и вторая по частоте буквы в английском языке,е и т учтены, Ева предполагает, что E~а, третье по частоте письмо. Ориентировочно, исходя из этих предположений, получается следующее частично расшифрованное сообщение.

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReMWQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJGSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtVeZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMthaPPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPPthMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

Используя эти первоначальные предположения, Ева может обнаружить закономерности, подтверждающие ее выбор, например "который". Более того, другие закономерности предполагают дальнейшие предположения".Rtate" возможно "государственный", что означало бы р~s. По аналогии "atthattMZe"можно было догадаться как"в это время", уступая M~я и Z~м. Более того, "он" возможно "здесь", давая V~р. Выполняя эти предположения, Ева получает:

здесьTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGaseiWQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJGSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtremitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQithaPPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPPthiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit

В свою очередь, эти догадки предполагают и другие (например, "remarA" может быть "замечание", подразумевая А~k) и так далее, и относительно просто вывести остальные буквы, в конечном итоге давая открытый текст.

В связи с этим, бабушка, могила и государство, принесла жука из стеклаnкоторая была закрыта, это была прекрасная карабея, а в то время не было натуралистовкурспризнанаучная точка зренияоткладываемыйчерные пятна рядом с одним другимулыбка на спине и на носу рядом с другой весы были чрезмерно жесткие и блестящиеВесь вид полированного золота вес насекомого был очень примечательным и принимал всевещи, на которые стоит обратить внимание, вряд ли можно винить, юпитер за свое мнение уважать его

На этом этапе Еве было бы неплохо вставить пробелы и знаки препинания:

Тут Легран поднялся с серьезным и величественным видом и принес мне жука.из стеклянного ящика, в который он был заключен. Это был красивый скарабей, ив то время, неизвестное натуралистам - конечно, большая награда в научном отношениизрения. На одном конце спины было два круглых черных пятна иодин рядом с другим. Чешуйки были чрезвычайно твердыми и блестящими, со всемивнешний вид полированного золота. Вес насекомого был очень значительным, и,принимая во внимание все обстоятельства, я вряд ли мог винить Юпитера за его мнениеуважая это.

В этом примере из «Золотого жука » предположения Евы оказались верными. Однако так будет не всегда; различия в статистике для отдельных открытых текстов могут означать, что первоначальные предположения неверны. Может возникнуть необходимость вернуться к неверным догадкам или проанализировать имеющуюся статистику гораздо глубже, чем несколько упрощенные обоснования, приведенные в приведенном выше примере.

Также возможно, что открытый текст не показывает ожидаемого распределения частот букв. Более короткие сообщения, вероятно, будут более разнообразными. Также возможно создание искусственно искаженных текстов. Например, были написаны целые романы без буквы "е«вообще - форма литературы, известная как липограмма .

История и использование [ править ]

Первая страница рукописи Аль-Кинди 9 века о расшифровке криптографических сообщений
Распределение частот арабских букв .

Первый известное записано объяснение частотного анализа (впрочем, любого рода криптоанализ) было дано в 9 - м века Аль-Кинди , в арабских эрудит , в рукописном на Дешифрирование криптографических сообщений . [3] Было высказано предположение, что тщательное изучение текста Корана впервые выявило, что арабский язык имеет характерную частоту букв. [4] Его использование распространилось, и аналогичные системы широко использовались в европейских государствах ко времени Возрождения . К 1474 году Чикко Симонетта написал руководство по расшифровке шифров на латинском и итальянском языках.текст. [5]

Криптографы изобрели несколько схем, чтобы преодолеть эту слабость в простом шифровании с заменой. К ним относятся:

  • Гомофоническая замена : использование омофонов - несколько альтернатив наиболее распространенным буквам в других моноалфавитных шифрах замещения. Например, для английского языка зашифрованный текст X и Y может означать открытый текст E.
  • Полиалфавитная замена , то есть использование нескольких алфавитов, выбранных различными, более или менее хитрыми способами ( Леоне Альберти, кажется, был первым, кто предложил это); и
  • Полиграфическая подстановка , схемы, в которых пары или тройки букв открытого текста рассматриваются как единицы для подстановки, а не отдельные буквы, например, шифр Playfair, изобретенный Чарльзом Уитстоном в середине 19 века.

Недостатком всех этих попыток обойти атаки подсчета частоты является то, что они усложняют как шифрование, так и дешифрование, что приводит к ошибкам. Известно, что министр иностранных дел Великобритании отверг шифр Playfair, потому что, даже если школьники могут успешно справляться, как показали Уитстон и Playfair, «наши атташе никогда не смогут его выучить!».

На роторных машинах первой половины 20 - го века (например, машина Энигмы ) были по существу невосприимчивы к простому частотному анализу. Однако другие виды анализа («атаки») успешно декодировали сообщения от некоторых из этих машин.

Частота букв на испанском языке.

Частотный анализ требует только базового понимания статистики языка открытого текста и некоторых навыков решения проблем, а также, если выполняется вручную, терпимости к обширному учету писем. Во время Второй мировой войны (Второй мировой войны) и британцы, и американцы нанимали взломщиков кодов, размещая кроссворды в крупных газетах и ​​устраивая конкурсы на то, кто быстрее их решит. Некоторые из шифров, используемых державами Оси, можно было взломать с помощью частотного анализа, например, некоторые из консульских шифров, используемых японцами. Механические методы подсчета писем и статистического анализа (обычно IBMмашины карточного типа) были впервые использованы во время Второй мировой войны, возможно, SIS армии США . Сегодня тяжелая работа по подсчету и анализу букв заменена компьютерным программным обеспечением , которое может выполнить такой анализ за секунды. При современных вычислительных мощностях классические шифры вряд ли смогут обеспечить реальную защиту конфиденциальных данных.

Частотный анализ в художественной литературе [ править ]

Часть криптограммы в The Dancing Men

Частотный анализ описан в художественной литературе. « Золотой жук » Эдгара Аллана По и сказка сэра Артура Конан Дойля о Шерлоке Холмсе « Приключение танцующих людей » - это примеры историй, в которых описывается использование частотного анализа для атаки на простые подстановочные шифры. Шифр в рассказе По инкрустирован несколькими средствами обмана, но это скорее литературный прием, чем что-либо значимое с криптографической точки зрения.

См. Также [ править ]

  • ЭТАЙН ШРДЛУ
  • Частоты букв
  • Частота арабских букв
  • Индекс совпадения
  • Темы в криптографии
  • Закон Ципфа
  • «Пустота» , роман Жоржа Перека . Оригинальный французский текст написан без буквы e , как и английский перевод. Испанская версия не содержит A .
  • Гэдсби (роман) , роман Эрнеста Винсента Райта . Роман написан в виде липограммы , в которой нет слов, содержащих букву Е.

Дальнейшее чтение [ править ]

  • Хелен Фуше Гейнс, «Криптоанализ», 1939, Дувр. ISBN  0-486-20097-3
  • Абрахам Синьков , «Элементарный криптоанализ: математический подход», Математическая ассоциация Америки, 1966. ISBN 0-88385-622-0 . 

Ссылки [ править ]

  1. ^ Сингх, Саймон . «Черная палата: подсказки и подсказки» . Проверено 26 октября 2010 года .
  2. ^ "Работающий пример метода из билла " A security site.com " " . Архивировано из оригинала на 2013-10-20 . Проверено 31 декабря 2012 .
  3. ↑ Ибрагим А. Аль-Кади «Истоки криптологии: вклад арабов», Cryptologia , 16 (2) (апрель 1992 г.), стр. 97–126.
  4. ^ «В наше время: криптография» . Радио BBC 4 . Проверено 29 апреля 2012 года .
  5. ^ Кан, Дэвид Л. (1996). Взломщики кодов: история секретного письма . Нью-Йорк: Скрибнер. ISBN 0-684-83130-9.

Внешние ссылки [ править ]

  • Бесплатные инструменты для анализа текстов: Frequency Analysis Tool (с исходным кодом)
  • Инструменты для анализа арабского текста
  • Статистические распределения букв арабского текста
  • Статистические распределения английского текста
  • Статистические распределения чешского текста
  • Частоты символов и слогов 33 языков и портативный инструмент для создания частотного и слогового распределения
  • Английский частотный анализ на основе потока данных в реальном времени сообщений с форума.
  • Расшифровка текста
  • Частота писем на немецком языке