Лингвистический криптоанализ

Вот и пришло время рассказать о криптоанализе. Криптоанализ - наука о методах получения исходного значения зашифрованной информации, не имея доступа к секретной информации (ключу), необходимой для этого (по Wikipedia). Если криптография - шифрование, то криптоанализ - взлом шифра.

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

Рассматривать я буду криптоанализ, который относится к той эпохе, когда шифры были уделом лингвистов, а не математиков. Хотя, и до вторых мы тоже со временем дойдём. =)

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

Лингвистический криптоанализ строится на отличном знании языка, на котором составлено зашифрованное сообщение. К примеру, методами ЛК являются: поиск в тексте слов из одной буквы, парных сочетаний и прочих явных и неявных признаков, позволяющих сделать суждения об истинном значении того или иного символа. Естественно, большую часть времени криптоаналитику приходится предполагать эти соответствия, постепенно отсеивая варианты, так что в лингвистичекой криптоаналитике большое значение имеет интуиция… и удача. =)

Пример (без него никуда =)):

BQWQJGQQJ LYJCMQC VQXMB EXGQM, X GLRJD HPPYMMQC GLXG ERWQC RJ FQHFEQ’B ZQZHMRQB KHM DQJQMXGRHJB, YJGRE ERKQIXVB PLXJDQC GHH ZYPL KHM GLQZ GH ZXAQ BQJBQ HK RG.

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

Обратите внимание на символ B. Он находится в начале 2 слов и в конце 5 слов (1 раз даже за апострофом!) при всём при том, что в середине слова он находится лишь в одном случае. Можно предположить, что это буква s - самое частое окончание (преимущественно из-за формы множественного числа) в английском языке.

Так же следует обратить внимание на сдвоенные символы. Всего 7 букв (в 99% случаев) в английском языке могут образовывать пары сами с собой: ll, ee, oo, tt, ss, ff и oo. в нашем тексте парными являются символы QQ, PP, MM, учтём это.

Обратите внимание на два набора символов: GHH и GH. С наибольшей долей вероятности это слова too и to, надеюсь, Вы и сами уже догадались об этом. Таким образом, у нас обозначились две буквы, в которых мы уверены на все сто процентов: t и o. Подставим предполагаемое в шифр и посмотрим, что вышло:

sQWQJtQQJ LYJCMQC VQiMs EitQM, i tLRJD oPPYMMQC tLit ERWQC RJ FQoFEQ’s ZQZoMRQs KoM DQJQMitRoJs, YJtRE ERKQIiVs PLiJDQC too ZYPL KoM tLQZ to ZiAQ sQJsQ oK Rt.

Обратите внимание на последнее шифрослово: Rt. В английском языке всего два слова, оканчивающиеся на t: it и at. i мы уже предположили, а вот a ещё нет, поэтому попробуем подставить вместо символа R букву a:

sQWQJtQQJ LYJCMQC VQiMs EitQM, i tLaJD oPPYMMQC tLit EaWQC aJ FQoFEQ’s ZQZoMaQs KoM DQJQMitaoJs, YJtaE EaKQIiVs PLiJDQC too ZYPL KoM tLQZ to ZiAQ sQJsQ oK at.

В английском языке крайне маловероятна (если не невозможна) ситуация, когда at стоит в конце предложения после неглагола, oK же глаголом, по всей видимости, не является. А вот если мы поменяем местами i и a, то получим:

sQWQJtQQJ LYJCMQC VQaMs EatQM, a tLiJD oPPYMMQC tLat EiWQC iJ FQoFEQ’s ZQZoMiQs KoM DQJQMatioJs, YJtiE EiKQIaVs PLaJDQC too ZYPL KoM tLQZ to ZaAQ sQJsQ oK it.

Здесь явно всё на своих местах, так что ещё две буквы поддались нам: a и i, что уже немало. =) После небольших размышлений в Q можно признать e, так как ситуация, когда 2 и 3 с конца буквы являются парными, присуща числительным (-teen), а здесь сам Бог велел: seventeen. Продолжая цепочку таких вот размышлений, можно придти к следующим явным заменам: L - h, K - f, M - r… Всё, шифр поддался!

seventeen LYnCreC Vears Eater, a tLinD oPPYrreC tLat EiveC in FeoFEe’s ZeZories for Denerations, YntiE EifeIaVs PLanDeC too ZYPL for tLeZ to ZaAe sense of it.

Подчищаем наши пробелы в таблице соответствий символов и читаем полный текст:

a c d e f g h i k l m n o p r s t u v w
X P C Q K D L R A E Z J H F M B G Y W I

Seventeen hundred years later, a thing occurred that lived in people’s memories for generations, until lifeways changed too much for them to make sense of it.

Магия! =) На самом деле, текст был подобран достаточного объёма, содержит почти весь английский алфавит и легко поддаётся криптоанализу. Бывают ситуации и посложнее, к примеру: NERJC ZXJ IHYEC NQ DEXC GH BQQ.

Теперь о дёгте: в качестве противоборства ЛК и частотному анализу (читайте следующий пост) было придумано усовершенствование: одноалфавитный шифр с омофонами. Это принцип, по которому одной букве может соответствовать несколько шифросимволов (а подробнее, что это такое, также читайте в следующих постах. =)). Криптоанализ от этого не потерял своей силы, но расшифровывать стало заметно труднее. Также одним препятствием из многих является опускание пробелов в шифротексте. Но, опять же, задача лишь усложняется, не становясь при этом неразрешимой. =)

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

YR TH GFBI SH, GTH JTFRG LR YE HLJTGW-GFE RZTFFEHC FU Y CHSYCQYVBW ULEH SFIHB. THC VHYS, FC KLIGT, LR GKHEGW-GTCHH UHHG, YEI THC BHEJGT Y BLGGBH FPHC ELEHGW UHHG. Y BHYI QHHB FU UYVXBFXR VXG XEQEFKE KHLJTG SYQHR THC PHCW RGYVBH, KTLBH RTH ZYCCLHR YE LSSHERH ROCHYI FU ZYEPYR. UCFS GTH IHZQ GF GTH GCXZQ FU GTH SYLEGFOSYRG LR RFSHGTLEJ FPHC Y TXEICHI UHHG, KTLBH GTH UFCHSYRG KLGT LGR GFOSYRG LR HLJTG FC GHE UHHG RTFCGHC.

Комментариев: 10

  1. Павел Воронин пишет:

    Что Вы этим хотели сказать, уважаемый Соколов?

  2. SHAman пишет:

    Да. Примерно этим мы и занимались на защите информации:) Только у нас было еще проще. Текст был довольно объемный (где-то экран), а еще было известно, что это - отрывок из русской классической литературы. Правда, был текст именно русский. Что усложняло дело. Но объем текста все перебивал.

  3. Павел Воронин пишет:

    =) Описание технологии нужно было с чего-то начать. =) Дальше частотный криптоанализ и… И ещё немного истории. Дальше можно заняться и более современными вещами.

  4. Павел Воронин пишет:

    Да. Я излагаю, как взломать закодированный одноалфавитным шифром текст.

  5. Павел Воронин пишет:

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

    Лучше познаете истоки, лучше поймёте будущее. У кого-то из великих эта фраза была очень красиво сформулирована, но я запамятовал…

  6. Екатерина пишет:

    Блин, я теперь на уроках только и делаю. что расшифровываю ваши примеры!!!!Спасибо, что пишете!!! Большой вам респект!

  7. Павел Воронин пишет:

    =) Спасибо, Екатерина, Вам за то, что читаете и оставляете такие тёплые отзывы. =)

  8. SHAman пишет:

    Екатерина, на уроках нужно уроками заниматься:) По себе знаю. Тоже думал, что это все ботва и не нужно. Сейчас жалею.

  9. Екатерина пишет:

    SHAman, моя совесть тоже это знает)))осталось наладить с ней контакт))…ну а если серьезно, то уроки и правда вещь важная..)

  10. Max Folder пишет:

    А есле вы будити песать на олбанской языке и шыфроват уже этот текст, то знатаков лингвистического криптоанализа ждот приятны суприз;-)