#криптография #дискретная_математика #криптоаналитика
Как расшифровать текст, зашифрованный с использованием многоалфавитного шифра простой
замены? Вкратце о том что это за шифр: ключ состоит из n алфавитов, каждая i-ая буква
открытого текста заменяется по (i-1)%keyLenght + 1 алфавиту. Шифр по сути представляет
из себя обобщенный шифр Виженера.
Длину ключа я определил. А вот как теперь подобрать ключ я не знаю.
Ответы
Ответ 1
Я пока не нашел полного решения, но нащупал некое направление, по которому можно пробовать идти. И так, с начала определяем длину ключа например по методу, предложенному автором вопроса (@Asem) в комментариях, т.е. методом индекса совпадений После этого определяем частоты букв в каждом словаре шифрования отдельно. Для предложенного примера шифротекста я получил следующую картину: 0: t=>14.268, h=>9.348, d=>8.364, u=>8.364, l=>8.364, s=>7.38, j=>6.396, a=>4.92, z=>4.428, x=>3.936, e=>3.444, r=>2.952, k=>2.952, w=>2.46, y=>2.46, m=>2.46, c=>2.46, n=>1.968, p=>1.476, f=>0.492, i=>0.492, b=>0.492, o=>0.492, 1: s=>13.776, a=>8.364, n=>8.364, j=>7.38, g=>7.38, t=>7.38, y=>6.888, h=>6.396, p=>4.92, k=>4.428, v=>4.428, e=>3.444, q=>3.444, i=>2.952, c=>2.46, w=>1.968, f=>1.476, m=>1.476, l=>0.984, z=>0.984, o=>0.984, 2: t=>12.3, n=>10.332, c=>9.84, w=>9.348, q=>7.872, k=>6.396, y=>5.904, a=>4.428, h=>4.428, v=>4.428, s=>4.428, f=>3.936, r=>2.952, l=>2.952, x=>2.46, g=>1.968, m=>1.968, j=>1.476, b=>0.984, d=>0.492, i=>0.492, p=>0.492, 3: t=>9.84, m=>9.348, g=>8.856, p=>8.364, q=>8.364, i=>7.872, r=>6.396, k=>6.396, x=>4.428, s=>4.428, f=>3.444, z=>3.444, j=>2.952, n=>2.952, w=>2.46, e=>2.46, c=>2.46, d=>1.968, l=>1.476, u=>0.984, v=>0.492, o=>0.492, Далее нам надо как то сопоставить эти частоты с частотами английского текста. К сожалению к реальных текстах небольшого размера частоты могут сильно отличаться. Я посчитал минимальные и максимальные частоты на большом наборе блоков текста по 814 байт (размер шифротекста) и получил следующую картину: Минимум Максимум Минимум 4 Максимум 4 A: 4.545 11.916 A: 0.982 16.216 B: 0.368 4.176 B: 0.491 5.405 C: 0.614 5.651 C: 0.491 8.353 D: 1.474 7.739 D: 0.491 11.302 E: 6.756 16.461 E: 5.405 21.621 F: 0.368 4.545 F: 0.491 6.879 G: 0.491 4.668 G: 0.491 5.896 H: 1.719 10.319 H: 0.491 13.267 I: 3.316 9.828 I: 1.474 13.759 J: 0.122 1.228 J: 0.491 1.965 K: 0.122 3.439 K: 0.491 4.422 L: 1.105 7.739 L: 0.491 9.828 M: 0.737 5.159 M: 0.491 8.353 N: 3.808 10.81 N: 1.965 12.285 O: 4.299 12.407 O: 2.457 15.724 P: 0.122 5.282 P: 0.491 5.405 Q: 0.122 1.474 Q: 0.491 1.474 R: 2.702 8.845 R: 1.474 12.776 S: 3.194 10.073 S: 0.982 12.285 T: 4.299 13.022 T: 0.982 16.216 U: 0.737 6.019 U: 0.491 8.845 V: 0.122 3.316 V: 0.491 3.931 W: 0.491 5.282 W: 0.491 7.371 X: 0.122 1.105 X: 0.491 2.457 Y: 0.245 6.388 Y: 0.491 7.371 Z: 0.122 1.597 Z: 0.491 1.965 В колонках "Минимум/Максимум 4" я посчитал частоты, если брать каждую 4ю букву блока. К сожалению они имеют еще большие отклонения от реальности и в некоторых случаях возможно придется ориентироваться на них. Далее подстановкой самых частых по нашему разумению букв замечаем места в шифротексте, где близко расположено несколько букв с повторами. А так же повторяющиеся комбинации символов. Для выбранного участка готовим регулярное выражение, которое учитывает во первых повтор букв, во вторых на месте букв перечисляем класс символов из всех букв, которые могли бы подойти по частоте. Например буква t из третьего (последнего, при нумерации с 0) словаря, с частотой 9.84 может быть представлена [ETAONIHS]. Таким образом для участка шифротекста tzzstmtgtmt (первая буква в позиции 2го словаря) у меня получилась следующая регулярка (в ней нарочно оставлены маленькие буквы шифротекста, что бы можно было быстро увидеть правильность выбора участка). Большими буквами обозначаем ожидаемые символы в открытом тексте, так потом удобнее для замены. (?[tETAO]) [zONIHSRDLUWCMGFYPBK] (? [zTAONIHSRDLUWCMGFYPBK]) (? [sET]) \g{t2} (? [mETAONIHS]) (? [tE]) [gTAONIHSRDL] \g{t2} \g{m3} \g{t0} Имена групп захвата и соответствующие ссылки идут по букве шифротекста и номеру словаря. К сожалению регулярка упрощенная и не контролирует, что одна буква алфавита в пределах одного словаря, соответствует строго одной букве словаря. Этот контроль я реализовывал позже в скрипте. Прогоняем полученную регулярку по реальному тексту большого объема (я использовал 2Mb склеенных в один текст только из букв английских рассказов) и находим попадающие под нее места: TBUTTHENTHE THATTHEOTHE TIMETHENTHE TOGETHERTHE TSATTHEOTHE TWHETHERTHE Собственно когда я писал эту регулярку я как раз хотел понять, на сколько жизнеспособна моя идея расшифровки tmt как THE. Просто эта комбинация с одной стороны часто встречалась, с другой, в данном месте два раза THE стоят слишком близко и мне было интересно на сколько это реально. Далее по шифротексту есть еще одно место с нагромождением тех же букв, его я проверял скрипте по другой регулярке с подстановкой букв найденных первой. В итоге для второй точки нашлись предположения только для случая если в первом случае была комбинация TWHETHERTHE. Если бы набор текстов был больше, возможно нашлось бы что то еще. Вот результат подстановок реальных примеров из текстов. Видно, что начинают вырисовываться другие участки текста. Аналитик с очень хорошим знанием английского языка (к которым я явно не отношусь), вполне мог бы их заполнить. На самом деле я боле менее уверен только в тех THE и еще в нескольких буквах, остальное может варироваться и надо проверять каждый вариант просматривая поведение новых букв в нескольких точках шафротекста.
Комментариев нет:
Отправить комментарий