Частотный анализ
.svg)
В криптоанализе ( частотный анализ также известный как подсчет букв ) — это исследование частоты букв или групп букв в зашифрованном тексте . Метод используется как средство взлома классических шифров .
Частотный анализ основан на том факте, что на любом участке письменного языка определенные буквы и комбинации букв встречаются с разной частотой. Более того, существует характерное распределение букв, примерно одинаковое почти для всех образцов этого языка. Например, учитывая раздел английского языка , И , Т , А и О являются наиболее распространенными, тогда как С , вопрос , Икс и Дж редки. Так же, ТД , ЯВЛЯЕТСЯ , НА , и АН являются наиболее распространенными парами букв (называемыми биграммами или диграфами ), и SS , ЭЭ , ТТ , и ФФ являются наиболее распространенными повторами. [1] Бессмысленная фраза « ETAOIN SHRDLU » представляет собой 12 наиболее часто встречающихся букв в типичном английском тексте.
В некоторых шифрах такие свойства открытого текста на естественном языке сохраняются в зашифрованном тексте, и эти шаблоны потенциально могут быть использованы при атаке только с использованием зашифрованного текста .
шифров замены Частотный анализ простой
В шифре простой замены каждая буква открытого текста заменяется другой, и любая конкретная буква открытого текста всегда будет преобразована в ту же букву зашифрованного текста. Например, если все вхождения буквы Это превратиться в букву Икс , зашифрованное сообщение, содержащее многочисленные экземпляры буквы Икс предложил бы криптоаналитику, что Икс представляет Это .
Основное использование частотного анализа состоит в том, чтобы сначала подсчитать частоту появления букв зашифрованного текста, а затем связать с ними угаданные буквы открытого текста. Более Икс в зашифрованном тексте, чем что-либо еще предполагает, что Икс соответствует Это в открытом тексте, но это не точно; т и а также очень распространены в английском языке, поэтому Икс может быть любой из них. вряд ли это будет открытый текст С или д , которые встречаются реже. Таким образом, криптоаналитику может потребоваться попробовать несколько комбинаций сопоставлений между буквами зашифрованного и открытого текста.
Можно придумать и более сложное использование статистики, например, рассмотрение подсчета пар букв ( биграмм ), троек ( триграмм ) и так далее. Это делается для того, чтобы предоставить криптоаналитику дополнительную информацию, например: вопрос и В в английском языке почти всегда встречаются вместе именно в таком порядке, хотя вопрос сам по себе редок.
Пример [ править ]
Предположим, Ева перехватила приведенную ниже криптограмму , и известно, что она зашифрована с использованием простого шифра замены:
LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX
В этом примере прописные буквы используются для обозначения зашифрованного текста, строчные буквы используются для обозначения открытого текста (или его догадок), а также Икс ~ т используется, чтобы выразить предположение о том, что буква зашифрованного текста Икс представляет собой букву открытого текста т .
Ева могла бы использовать частотный анализ, чтобы разгадать сообщение по следующим направлениям: подсчет букв в криптограмме показывает, что я это самая распространенная одиночная буква, [2] XL наиболее распространенный биграмм и XLI Это самая распространенная триграмма . Это самая распространенная буква в английском языке, й является наиболее распространенной биграммой, и тот — самая распространенная триграмма. Это убедительно свидетельствует о том, что Икс ~ т , л ~ час и я ~ Это . Вторая по распространенности буква в криптограмме — И ; поскольку первая и вторая по частоте буквы в английском языке, Это и т учтены, Ева догадывается, что И ~ а , третья по частоте буква. Предварительно сделав эти предположения, получается следующее частично расшифрованное сообщение.
heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMvaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRAWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ GSTVReaYVeatCVMUEMWarGMeWtMJMGCSSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV eZMtFSJtheKaGAaWHAPSWYSWeWeaVtheStheVtherRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSSRRFQMtha PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZenCTCMteVJSVhMRSCMWMSWVerceGtMWYMt
Используя эти первоначальные предположения, Ева может обнаружить закономерности, подтверждающие ее выбор, например: « что «. Более того, другие закономерности наводят на дальнейшие догадки». Рейтинг " возможно " состояние ", что означало бы р ~ с . Сходным образом " atthatMZe "можно предположить как" в это время ", уступив М ~ я и С ~ м . Более того, " поднимать " возможно " здесь ", давая V ~ р . Заполняя эти догадки, Ева получает:
здесьTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthetimeTWAWSQWtSWatTraPistsSJ GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr излучатьFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTciterJSrhisSCiWiSWresCeGtiWYit
В свою очередь, эти догадки наводят на мысль и еще о других (например, « ремарА " может быть " замечание ", подразумевая А ~ к ) и так далее, а остальные буквы относительно легко вывести и в конечном итоге получить открытый текст.
Тогда Леграндар поднялся с могилой и величественным воздухом и принес жука из стеклянной витрины. Там, где он был закрыт, был красивый скарабей, и в то время неизвестный натуралистам Конечно, большая награда, с научной точки зрения, кругом были черные пятна, рядом с одним доп. Задняя часть спины и близкая к другому, чешуя была чрезвычайно твердой и блестящей с Внешний вид полированного золота и вес насекомого были очень примечательными и захватывающими. вещи во внимание, я вряд ли мог бы винить Юпитера за его мнение, уважая его.
На этом этапе Еве было бы неплохо расставить пробелы и знаки препинания:
Тогда Легран встал с важным и величественным видом и принес мне жука. из стеклянного шкафа, в котором он был заключен. Это был красивый скарабей, и в тогдашнее время, неизвестное натуралистам — конечно, большая награда в научном отношении зрения. Около одного конца спины были два круглых черных пятна и еще длинный один рядом с другим. Чешуя была чрезвычайно твердой и блестящей, со всеми внешний вид полированного золота. Вес насекомого был весьма значительным, и принимая во внимание все обстоятельства, я вряд ли мог винить Юпитера за его мнение уважая это.
В этом примере из « Золотого жука » все догадки Евы оказались верными. Однако это не всегда так; различия в статистике для отдельных открытых текстов могут означать, что первоначальные предположения неверны. Возможно, потребуется отбросить неверные предположения или проанализировать имеющуюся статистику более глубоко, чем несколько упрощенные обоснования, приведенные в приведенном выше примере.
Вполне возможно, что открытый текст не демонстрирует ожидаемого распределения частот букв. Более короткие сообщения, скорее всего, будут более разнообразными. Также возможно создание искусственно искаженных текстов. Например, написаны целые романы, в которых буква отсутствует. Это вообще — форма литературы, известная как липограмма .
История и использование [ править ]
Первое известное зафиксированное объяснение частотного анализа (да и любого вида криптоанализа) было дано в 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 языка и портативный инструмент для создания распределений частот и слогов.
- Анализ частоты арабских букв
- Условные вероятности для символов в английском тексте
- Частота чешской буквы/биграммы/триграммы
| |||||||||||||||||||||||||
