Частотный анализ

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

Частотный анализ основан на том факте, что на любом участке письменного языка определенные буквы и комбинации букв встречаются с разной частотой. Более того, существует характерное распределение букв, примерно одинаковое почти для всех образцов этого языка. Например, учитывая раздел английского языка , И , Т , А и ТО являются наиболее распространенными, тогда как С , вопрос , Х и Дж редки. Так же, ТД , ЯВЛЯЕТСЯ , НА , и АН являются наиболее распространенными парами букв (называемыми биграммами или диграфами ), и SS , ЭЭ , ТТ , и ФФ являются наиболее распространенными повторами. ^[1] Бессмысленная фраза « ETAOIN SHRDLU » представляет собой 12 наиболее часто встречающихся букв в типичном английском тексте.

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

Частотный анализ шифров простой замены

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

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

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

Пример

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

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ
GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

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

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

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ
GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP
thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

Используя эти первоначальные предположения, Ева может обнаружить закономерности, подтверждающие ее выбор, например: « что «. Более того, другие закономерности наводят на дальнейшие догадки». Рейтинг "может быть" состояние ", что означало бы Р ~ с . Сходным образом " atthatMZe "можно предположить как" в это время ", уступив М ~ я и С ~ м . Более того, " поднимать "может быть" здесь ", давая V ~ р . Заполняя эти догадки, Ева получает:

hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ
GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr
emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit

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

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.

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

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

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

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

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

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

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

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

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

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

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

Часть криптограммы в «Танцующих человечках».

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

См. также

Индекс совпадения
Темы криптографии
Закон Ципфа
Пустота — роман Жоржа Перека . Оригинальный французский текст написан без буквы е , как и английский перевод. Испанская версия не содержит файла .
Гэдсби (роман) — роман Эрнеста Винсента Райта . Роман написан в виде липограммы , в которую не входят слова, содержащие букву Е.

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

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

Ссылки

^ Сингх, Саймон . «Черная палата: полезные советы» . Проверено 26 октября 2010 г.
^ «Работающий пример метода из статьи Билла «A Security site.com » . Архивировано из оригинала 20 октября 2013 г. Проверено 31 декабря 2012 г.
^ Ибрагим А. Аль-Кади «Истоки криптологии: вклад арабов», Cryptologia , 16 (2) (апрель 1992 г.), стр. 97–126.
^ «В наше время: Криптография» . Радио Би-би-си 4 . Проверено 29 апреля 2012 г.
^ Кан, Дэвид Л. (1996). Взломщики кодов: история тайного письма . Нью-Йорк: Скрибнер. ISBN 0-684-83130-9 .
^ Кру, Луи; Деворс, Шифр (январь 2002 г.). «Коммерческая загадка: начало машинной криптографии» . Криптология . 26 (1): 1–16. дои : 10.1080/0161-110291890731 . ISSN 0161-1194 . S2CID 41446859 .

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

Онлайн-инструмент частотного анализа
Частоты символов и слогов 41 языка и портативный инструмент для создания распределений частот и слогов.
Анализ частоты арабских букв
Условные вероятности для символов в английском тексте
Частота чешской буквы/биграммы/триграммы

[1] Сингх, Саймон . «Черная палата: полезные советы» . Проверено 26 октября 2010 г.

[2] «Работающий пример метода из статьи Билла «A Security site.com » . Архивировано из оригинала 20 октября 2013 г. Проверено 31 декабря 2012 г.

[3] Ибрагим А. Аль-Кади «Истоки криптологии: вклад арабов», Cryptologia , 16 (2) (апрель 1992 г.), стр. 97–126.

[4] «В наше время: Криптография» . Радио Би-би-си 4 . Проверено 29 апреля 2012 г.

[isbn0-684-83130-9-5] Кан, Дэвид Л. (1996). Взломщики кодов: история тайного письма . Нью-Йорк: Скрибнер. ISBN 0-684-83130-9 .

[6] Кру, Луи; Деворс, Шифр (январь 2002 г.). «Коммерческая загадка: начало машинной криптографии» . Криптология . 26 (1): 1–16. дои : 10.1080/0161-110291890731 . ISSN 0161-1194 . S2CID 41446859 .

[1]

[2]

[3]

[4]

[5]

[6]