Текст книги "Шифрованный мир. Азы криптографии и задачи по криптоанализу"

Практика по шифру Виженера

Для определения периода ключа используется метод Касиски – в шифровке ищутся повторяющиеся группы символов и из расстояния между ними делается вывод о длине периода ключа (кодовой фразы). Например, в следующей шифровке самая частая триграмма «4ХБ» встречается три раза (причём в двух случаях из трёх перед этим идёт G либо дальше идёт Щ):

!CZ. ЩQKF8D KWRP. TЩUZABII04-КIQOAW4O!Щ FOOЩ. (?CYY8Ъ8ABFBLYЩZЛIS!:MEWCTXЩO4?В! CWKXU5ZЩP7C9IYZX3?ZUNQЁKPYPЯЩV (БH-PWH::ЩKЪJMHЗГ:?АA! CZ.4XЮЩ8Щ-U! JTAUIU? F+NCFIOUБ! EVV4OY92FHQ9!ZАQ! P5JVTFQD9LCRMIS! SGIQЁY. B9ЭBMИ. X-ZG4XБЫ2N4PSVЕ) RQВG4XБЩKЪ88ARKWHГTZKTMVD7MYЩ?) +DДPSCАAKBEFGR Л-LEMN8EXC2VCSK.WSQXЁ5C5ZMRN40FЗГИ3ГTZKTMEKЪ6ЭL. Ж.C БSIOALGPCЭ6X):VOVX96AJQIHZDCВ(L:ZPЩW!4UBDЭJ.KЖL).EG5,GQPKGMRK: LVP6ЩVPEQJ9L8:Z-3,K,4XБЩTЪ6G8ДKЖL).T6

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

!CZ. ЩQKF8D KWRP.

TЩUZABII04-КIQOA

W4O!Щ FOOЩ. (?CYY

8Ъ8ABFBLYЩZЛIS!

:MEWCTXЩO4?В! CWK

XU5ZЩP7C9IYZX3?Z

UNQЁKPYPЯЩV (БH-P

WH::ЩKЪJMHЗГ:?АA

!CZ.4XЮЩ8Щ-U! JTA

UIU? F+NCFIOUБ! EV

V4OY92FHQ9!ZАQ! P

5JVTFQD9LCRMIS! S

GIQЁY. B9ЭBMИ. X-Z

G4XБЫ2N4PSVЕ) RQВ

G4XБЩKЪ88ARKWHГT

ZKTMVD7MYЩ?) +DДP

SCАAKBEFGR Л-LEM

N8EXC2VCSK.WSQXЁ

5C5ZMRN40FЗГИ3ГT

ZKTMEKЪ6ЭL. Ж.C Б

SIOALGPCЭ6X):VOV

X96AJQIHZDCВ (L:Z

PЩW!4UBDЭJ. KЖL).

EG5,GQPKGMRK: LVP

6ЩVPEQJ9L8:Z-3,K

,4XБЩTЪ6G8ДKЖL).

T6

Каждый столбец зашифрован простым шифром Цезаря.

Для противодействия такому способу криптоанализа можно в случайные места шифровки добавить символ (ы) не из этого алфавита, при условии что санкционированный получатель будет об этом знать, а у несанкционированного нет tabula recta. Тогда найти период ключа будет гораздо сложнее. Так что, если у Вас не получается найти период ключа – попробуйте избавиться от какого-то символа (ов).

Задача: дешифровать сообщение, имея более-менее подходящую tabula recta (встроена в приложение), но не имея ключа.

Решение:

Итак, после некоторых манипуляций с шифровкой:

– Открываем приложение CryptoApp, заходим в «Полиалфавитные шифры замены», жмём «Определить период ключа», получаем те же 16, «Дешифровать на русском», получаем результат чуть получше (как минимум, расставлены пробелы), и предполагаемый ключ (31% символов клера абсолютно верно определились).

– Предположим, что первое слово из четырёх букв, заканчивающееся на «Р» «М (БР» – это «ШИФР». Таким образом, с помощью корректировки (сдвигает tabula recta) побуквенно подбираем вместо предполагаемых «МБФЖ» первых 5 букв ключа – «Б БЖ». Возвращаем корректировку на 0 и заменяем первые 5 символов ключа.

– 13 строка начинается с «ВОЛЯЮ», так как мы уверены в первых 5 буквах ищем слово, содержащее «воляю» на http://xworder.com/ru/Xword.aspx?q=%d0%b2%d0%be%d0%bb%d1%8f%d1%8e&m=c. В обоих случаях перед этим идёт «ОЗ», а дальше идёт «Щ» (*озволяющ*) (окончание не учитываем из-за множества словоформ каждого слова). Таким образом, мы узнаём 6-ой, 15-ый и 16-ый символы ключа: « (» и «КЖ».

– На 19—20 строках замечаем слово «ШИФРОВКИ», слева должен быть пробел или знак препинания. Предположим, что там пробел и, аналогично, подбираем 14-ую букву ключа «А»

– На 12 строке находим «ПРИЛОИХНИQ». Предполагаем, что это словоформа «ПРИЛОЖЕНИ*». Находим 7-ой и 8-ой символы ключа:»!.»

– На четвёртой снизу строке находим «СМОТПИТQ». Предполагаем, что это слово «СМОТРИТЕ». Находим 11-ый символы ключа: «И» (7-ой уже найден, но не совпадает здесь потому, что, как оговаривалось в условии, имеющаяся tabula recta не идеальна)

– На 1—2 строках видим « ДНБРО ПОЖАЛН! Б:Ъ», очевидно, что это « ДОБРО ПОЖАЛОВАТЬ». Подбираем 9-ый и 10-ый символ ключа «V.»

– Используя корректировку, восстанавливаем весь ключ: при значении корректировки = 69 получаем предполагаемый ключ «КАКРАЗГБ: БТЪШЙФР». Восстанавливаем ключ «КАКРАЗГАДАТЬШИФР» для более чем 62-символьного алфавита (в шифровке были замечены и русские, и латинские буквы и мн. др.). Не меняя корректировку, вводим восстановленный ключ.

– Восстановить текст, следуя логике. Ответ в конце книги.

Задача №2 (сложная): Имея восстановленный клер (открытый текст) из прошлой задачи полностью восстановить используемый алфавит и его порядок (а соответственно и tabula recta)

Начало решения:

Первый символ шифровки»!», ключа «К», клера «Ш», то есть (№^{Ш рус} + №^К рус) mod N = №!, где №^а рус – позиция (начинается с нуля) русского символа а в алфавите, N> 62 – мощность алфавита (количество символов), X mod Y – операция вычисления остатка от деления X на Y (сравнение по модулю можно часто встретить в криптографии как в различных протоколах с симметричным ключом, так и в системах с открытым ключом. Так, например, модульная арифметика обеспечивает конечные поля, над которыми затем строятся эллиптические кривые, используемые в эллиптической криптографии).

Четвертый символ: (2*№^{Р рус}) mod N = №.

5-ый символ: (№^пробел + №^А рус) mod N = №^{Щ рус}; №^пробел + №^А рус = №^{Щ рус} + с₅N, где с₅ – целое, т.к. любой № <N, то с₅ = 0 или 1. Далее аналогично.

7-ой: (№^{Н рус} + №^{Г рус}) mod N = №^К анг

11-ый: (№^{Н рус} + №^{Т рус}) mod N = №^пробел

12-ый: (№^пробел + №^{Ь рус}) mod N = №^К анг

17: (№^пробел + №^{Ш рус}) mod N = №^W анг

21: (№^А рус + №^А анг) mod N = №^А рус, т.к. №^А анг <N, то №^А анг = 0

29: (№^О рус + №^К рус) mod N = №^Т анг

33: (№^С рус + №^К рус) mod N = №^W анг

42: (№^{Т рус} + №^О рус) mod N = №^Щ рус

50: (№. + №^А рус) mod N = №^Ъ рус

53: (№^{З рус} + №^А рус) mod N = №^В анг

55: (№^{Г рус} + №^{Е рус}) mod N = №^В анг

70: (№^{З рус} + №^С рус) mod N = №^Т рус

71: (№^{Г рус} + №^{Ь рус}) mod N = №^Х анг

93: (№^{Е рус} + №^{Ш рус}) mod N = №^Х анг

107: (№^И рус + №^{Т рус}) mod N = №^V анг

119: (№^пробел + №^{Г рус}) mod N = №^Ъ рус

160: (№^К рус + №^{Р рус}) mod N = №^V анг

204: (№^{Ш рус} + №^{Ь рус}) mod N = №^И рус

Объединим 53 и 55: (№^{З рус} + №^А рус) mod N = (№^{Г рус} + №^{Е рус}) mod N, следовательно

№^{З рус} + №^А рус – №^{Г рус} – №^{Е рус} = с₅₃₅₅N, где с₅₃₅₅ – целое, и т.к. любой № <N, то -2 <с <2

Из остальных уравнений сделаем связный граф:

Это поможет нам сделать из пяти переменных меньше. Попробуем заменить эти переменные через эти уравнения:

№^{З рус} – №! – №^пробел – №^{Е рус} = (с₁₁₉+с₅₃₅₅-с₅₀) N, где с₅₀ и с₁₁₉ равны 0 или 1, т.к. любой № <N, аналогично далее.

Мы получили опять уравнение с 4 неизвестными №, но другими. Е рус и пробел связаны через 17 и 93. Заменяем:

№^{З рус} +2*№^{Ш рус} – №! – №^W – №^{Х анг} = (с₁₇+с₁₁₉+с₅₃₅₅-с₅₀) N

Подсказка: символы А-Я идут по порядку, как и A-Z, и 0—9

Шифр Гронсфельда

Шифр Гронсфельда – это вариант шифра Вижинера, где используется не строковый ключ, а цифровой. То есть, вместо возможных 26 символов в каждой букве ключа для английского алфавита здесь используется только 10 цифр. Таким образом, достаточно просто использовать как ключ любое число (возможно очень большое), а также ускоряется как шифрование и расшифрование, так и дешифрование. Шифр был создан графом Гронсвельдом (руководителем первой дешифровальной службы Германии) в XVII веке.

Шифр Бофора

Шифр Бофора/Бофорта/Бьюфорта идентичен шифру Виженера, за исключением того, что tabula recta записывается не слева направо и сверху вниз, а справа налево и сверху вниз, хотя наименование столбцов всё также слева направо:

За счёт этого операция гаммирования символа клера и ключа перестаёт быть коммутативной. То есть, например, для стандартной таблицы Бофора, размещённой чуть выше H+K=7, но K+H=D. Зато если H+K=7, то H+7=K. Можно сказать, что + меняется на —

Применялся в механической роторной шифровальной машине

M-209 для тактических задач в войнах середины 20 века.

Практика по шифру Бофора

8JCV5J, YCJDUQBYHICEBC1K38OC76W4HYDYCJDUQBYHO5Q6-

3W0DHAQ83OL5EH06UCCE.BE0D6YHAEQL3E962ATQ6C2E17A3Q

IQ2DYDAC26.BATQPX4WST-ORWYJW80OC8J54JT49C5K

3QQ44WROW57ACISYIOC0N, OYC1Q5QSQIW-EPCMET4HAQ

Q449DQE-Q.PY [пробел] EQDQ6A.8JCII66C

.49CIA74NQBWSELY4OCJKBJDUQQ-8PU3W4J654ODQPX4NUSW

57ACC6S7E-4W80OCIHY6D5BUCCKT8BY49EQNUD6,49CJDUQIFW

[пробел] PQ6—3W1KPC8J5EW,0O4QL3E962PYEJDQK

– 4WSELAQ80IPC070KPC [пробел] 0C3K.B63IXC3Q38J

WQS0HHTQSQHWY8YCCK34W576-Q. KUYGU [пробел] C2K1

8A4QKVQPX4W,T,G-W84NUQL3E962ATQ7AQ9Y5BUHA

–JWSEI10JY4OD

Для упрощения дешифровки можете воспользоваться приложением CryptoApp, раздел «Полиалфавитные шифры замены»

Шифр Плейфера

или квадрат Плейфера – ручная симметричная техника шифрования, в которой впервые использована замена биграмм. Изобретена в 1854 году английским физиком Чарльзом Уитстоном, но названа именем лорда Лайона Плейфера, который внёс большой вклад в продвижение использования данной системы шифрования в государственной службе, так как он хоть и недостаточно криптостойкий, но прост и не требует специальных средств. Шифр предусматривает шифрование парами символов (биграммами). Таким образом, шифр Плейфера более устойчив к взлому по сравнению с шифром простой замены, так как усложняется его частотный анализ.

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

Шифр Плейфера – Википедия

Шифр Плейфера использует таблицу (например, 8х4 для русского алфавита), в которую вписывается ключевое слово (за исключением повторяющихся букв). Допустим, что мы выбрали ключом шифра слово «РЕСПУБЛИКА», записываем в таблицу и дописываем по алфавиту оставшиеся буквы (за исключением Й).

Можно использовать таблицы другого размера (например, 4х8, 6х5 или 5х6, опуская ещё и Ё) или договориться записывать ключевое слово не слева направо, а сверху вниз, по диагонали, по спирали и т. д. Далее, допустим, нам необходимо зашифровать «ПРИБЫЛЬ УПАЛА, НЕОБХОДИМЫ ПОСТАВКИ ЙОДА». Для начала, убираем пробелы, запятые, Й заменяем на И, так как их нет в нашей таблице и делим оставшиеся символы по два: «ПР ИБ ЫЛ ЬУ ПА ЛА НЕ ОБ ХО ДИ МЫ ПО СТ АВ КИ ИО ДА» (пробелами просто отмечены разделения для наглядности, а если бы в биграмме оказались одинаковые символы, то между ними надо было бы вставить какой-нибудь другой символ по договорённости, например Х, а если бы в конце осталась лишь одна буква, то надо было бы добавить к ней какой-то ещё символ, например, тоже Х и при расшифровке может получиться ПХРИБЫЛЬХ, это нормально). Найдём первую биграмму в таблице, получается такой прямоугольник:

Прямоугольник получился с высотой в 1 символ, поэтому в шифровку мы пишем символы справа от шифруемых – УЕ. Далее ИБ, та же ситуация, но справа от И ничего нет, поэтому берём вместо этого самый левый символ в строке, получается РЛ. Если бы прямоугольник был шириной в 1 символ, мы бы брали символы снизу. Далее ЫЛ

В шифровку пишем символы в других углах, но на той же строке – ЮП. Таким образом, получается шифровка «УЕРЛЮПЪСЕГЕЖАЩХСЦТЗУТШСТВГЗРСЧЁВ». Для расшифровки необходимо применять те же правила, но наоборот – вместо справа используем слева, снизу – сверху, удаляя Х, если он не несёт смысловой нагрузки. Несмотря на кажущуюся сложность алгоритма – сначала министерство иностранных дел Великобритании отклонило его из-за сложности восприятия, после небольшой практики оказывается, что он не сложнее в использовании шифра Цезаря, зато имеет на порядок большую криптостойкость, что, однако, с появлением компьютеров делает и её непригодной для хранения секретов свыше десятка секунд, если кто-то предположит что это Плейфер, то и ключевое слово в современном мире уже и не нужно. Также можно создать аналог шифра Плейфера не в 2-мерном пространстве, а в многомерном, например, работать не с биграммами, а с пентаграммами, для чего потребуется использовать большие алфавиты, например, вместо прямоугольника использовать пентеракт со стороной 3 символа с алфавитом 243 символа (русский и английский в обоих регистрах, знаки препинания, цифры, спецсимволы), что повысит время на простой перебор с 15 секунд на обычном компьютере до нескольких лет. Однако, при очень большом количестве перехваченных символов или сообщений с одинаковым ключом поможет обычный частотный анализ. Так что, у этого шифра есть перспектива, а поэтому потренируйтесь.

Практика по шифру Плейфера

Попробуйте расшифровать это с помощью той же таблицы: «ФВНЩВМНТАЦТСЕРФДНКОЫВОЧСУЕВГРИВККНАЩЬПОЬЕЗУЦВГПЧ

ШПВКНРПШНГЛИЛЧРПСТВЬСЁУРПЬГВЧЕШЗЖЛНИОЬВТПИЬОЗЕЬ

ВНГКЬЧБИЬПРОКЦСЬОЛЗСИГНСИЩОМВВЗГЪРЕВКРПСТСЮВЧГВО

ЫЕКАЧЯПГВЕРНЩФОГЕЕРНРСККВЗСПРНТПОСЧФГГНЬТЫГЕКЖСА

ЩЗИФТДЁВАЕРГЫЬВФТРЗЬВОЫСТГЬПРОПЩИЭАНЩСТИШВФЁМ» (Для удобства после расшифровки каждой биграммы, проверяйте нет ли таких далее, чтобы несколько раз не расшифровывать одно и то же). А чтобы подогреть Ваш интерес, скажу, что ответа в конце книги на эту задачу не будет. Узнать что же там смогут не только лишь все.

Алгоритм Диффи – Хеллмана

Алгоритм используется для выработки секретного ключа по открытому каналу связи, если злоумышленники могут читать, но никак не смогут подменять сообщения на свои – например, с некоторыми оговорками, при передаче короткими радиоволнами между мощными радиостанциями…

Аспидистра был британским средневолновым радиопередатчиком, он начинал передачу, первоначально ретранслируя трансляцию немецкой сети, полученную от активной станции. Это заставляло немецких слушателей поверить в то, что это оригинальная станция. Затем операторы вставляли в трансляцию деморализующий ложный контент и пропаганду в поддержку союзников. А когда немецкие радиолокационные станции транслировали движение потоков бомбардировщиков на пути к целям во время битвы за Берлин.

Немецкоязычные операторы Аспидистры выдавали себя за немецких операторов наземного управления, отправляя фальшивые инструкции ночным истребителям.

Аспидистра (передатчик) – Aspidistra (transmitter) – ВикибриФ

…иначе, если надёжного канала связи нет – уже необходимо применять дополнительные методы аутентификации, использовать квантовый аналог алгоритма или же получится то, что описывается в главе «Уязвимости при использовании криптографии».

Абоненты вместе выбирают два числа g (простое) и p (простое> 10³⁰⁰, причём (p-1) /2 – тоже простое) – эти числа не являются секретными, кто угодно может их перехватить или узнать (самое главное – не подменить), это не влияет на успех. Затем абоненты генерируют свои случайные числа (> 10¹⁰⁰, не обязательно простое) и не передают их никак никому:

 
Абонент 1
Сгенерировал a
Вычисляет A = остаток от деления (g в степени а) на p
Передаёт А
Получил B
Вычисляет секретный ключ = остаток от деления (B в степени а) на p
 

Абонент 2

Сгенерировал b

Вычисляет B = остаток от деления (g в степени b) на p

Передаёт B

Получил А

Вычисляет секретный ключ = остаток от деления (A в степени b) на p

У сторон получились одинаковые секретные ключи, которые ни разу не передавались по открытому каналу связи и которые невозможно за разумное время вычислить на основе полученных открытых данных.

Практика по алгоритму Диффи – Хеллмана

Для примера, используем маленькие числа:

Итак, Вы с собеседником выбрали g = 5 (простое), и p = 23 (простое). Вы загадали a = 6, и не сообщаете его собеседнику. Вы вычислили А и сообщили его собеседнику. Собеседник сообщил Вам B = 19. Вычислите общий секретный ключ. Ответ, как всегда, в конце книги.

Уязвимости при использовании криптографии

Атака «человек посередине»

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

Так, алгоритм Диффи – Хеллмана рассыпается при таких условиях:

Представим, что мы – сеть злоумышленников, которая подключилась к обоим собеседникам. Мы подслушали, например, что были выбраны числа g = 7 и p = 31. Первый собеседник отправляет А = 10. Мы не знаем a, которое он загадал. Однако, это нам и не нужно – просто меняем А на любое число меньше p, например, 8 – второй собеседник вместо А = 10 получает А = 8. Он загадывает b и отправляет B = 25. Аналогично, меняем B на 20. Получаем два секретных ключа – для связи с первым собеседником = 20⁷ mod 31 = 18, и 8⁷ mod 31 = 2 для связи со вторым. Причём обе стороны будут убеждены, что выработали одинаковый, никому не известный, ключ и будут шифровать сообщения специальными ключами, которые знают злоумышленники. Далее мы можем просто читать их сообщения, можем отправлять им свои сообщения от имени другого собеседника, можем удалять неугодные нам сообщения или менять их на что-то другое – например, на исполняемый файл с вирусом и надписью «Открой, это наш новый *что-то там*». Так, даже шифрованное общение может подвергнуть риску всю информацию в системе, а не только ту, что Вы отправляете. Единственное, о чём нельзя забывать, что при таком канале связи – злоумышленник сам не может быть уверен, что общается с взламываемыми без посредников. Вдруг, и его так же взломали, и читают и подменяемые сообщения, и оригинальные, и меняют менянное на то, что угодно им?

Для решения этой проблемы придумали сертификаты открытых ключей – чтобы каждый раз не отправлять собеседнику числа А и B, они заранее для каждого абонента записаны в каком-то центре: доверенный сервер с дополнительной аутентификацией или в Вашей базе данных. Тогда их подменить не получится, а если ещё этой БД нет у злоумышленника – вообще красота – у каждой пары абонентов будет уникальный секретный ключ, которым не нужно даже обмениваться! Но это была бы не криптография, если бы всё было так просто —

в 2011 году нарушение безопасности голландского центра сертификации DigiNotar привело к мошеннической выдаче сертификатов. Впоследствии мошеннические сертификаты в свою очередь были использованы для совершения атак «человек посередине»

Атака посредника – Википедия

Также, схема подключения по SSL в таком канале связи рассыпается:

Перехватываем весь шифрованный трафик между клиентов и сервером. Меняем шифрованную страницу на нешифрованный редирект к шифрованной странице своего сервера. Поскольку, у обычных пользователей до сих пор разрешены оба режима работы (и шифрованный и нешифрованный), хотя Гугл и его браузер Хром активно с 2015 года борется с HTTP контентом – понижение в результатах поиска, пометка небезопасно, блокирование контента, содержащего сразу оба режима, всё же данный редирект будет для пользователя не заметен – страница шифрованная, выдана по ссылке с оригинального сервера, да, наименование сертификата будет другое, но кто его вообще смотрит? Смело вводим пароль, платёжную информацию и удивляемся, почему у друзей от Вашего имени просят деньги и куда исчезли Ваши. Профит!

Таким же образом, можно перенаправить общение с других защищённых протоколов на незащищённые или менее защищённые, например, с SSH V2 на SSH V1, который имеет достаточно много уже известных уязвимостей. Поэтому отключайте все старые и незащищённые версии протоколов, которые на многих ПО до сих пор поддерживаются для обратной совместимости.

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

Чтобы выявить такие атаки, серьёзные стороны обычно проверяют расхождения во времени ответа.

Предположим, что они обычно затрачивают определённое количество времени для выполнения конкретной транзакции. Однако, если одна транзакция занимает аномальный период времени для достижения другой стороны, это может свидетельствовать о вмешательстве третьей стороны, вносящей дополнительную задержку в транзакцию.

Атака посредника – Википедия

Так, например, чем больше заблокированных сервисов и технических средств противодействия угрозам в стране и у Вашего провайдера, в частности, тем неизбежно будет больше пинг, особенно если их количество резко увеличивается – больше, чем в 2 раза за 10 лет.

А теперь подошла очередь шифра, который невозможно взломать: