Частотный анализ - Frequency analysis

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

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

Частотный анализ основан на том факте, что на любом участке письменного языка определенные буквы и комбинации букв встречаются с разной частотой. Более того, существует характерное распределение букв, которое примерно одинаково почти для всех образцов этого языка. Например, учитывая раздел английского языка , E , Т , А и О являются наиболее распространенными, а Z , Q , Икс и J редки. Точно так же TH , ER , НА , и AN являются наиболее распространенными парами букв (называемыми биграммами или орграфами ), и СС , EE , TT , и FF являются наиболее распространенными повторами. Бессмысленная фраза « ЭТАЙН ШРДЛУ » представляет собой 12 наиболее часто встречающихся букв в типичном тексте на английском языке.

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

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

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

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

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

Пример

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

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ
GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

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

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

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ
GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP
thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

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

hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ
GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr
emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit

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

hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei
nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof
courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr
emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha
lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall
thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit

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

Hereupon Legrand arose, with a grave and stately air, and brought me the beetle
from a glass case in which it was enclosed. It was a beautiful scarabaeus, and, at
that time, unknown to naturalists—of course a great prize in a scientific point
of view. There were two round black spots near one extremity of the back, and a
long one near the other. The scales were exceedingly hard and glossy, with all the
appearance of burnished gold. The weight of the insect was very remarkable, and,
taking all things into consideration, I could hardly blame Jupiter for his opinion
respecting it.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

дальнейшее чтение

  • Хелен Фуше Гейнс, «Криптоанализ», 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 .

внешние ссылки