С 5 по 11 декабря 2022 года проходил I тур XXI олимпиады школьников и студентов по криптографии SarCrypt. Олимпиада проводится с 2002 года сотрудниками кафедры теоретических основ компьютерной безопасности и криптографии и лаборатории компьютерной безопасности Саратовского национального исследовательского государственного университета имени Н.Г.Чернышевского. Последние годы олимпиада проводится в два этапа: d первую полную неделю декабря проходит отборочный тур, а в последнее воскресенье января проходит итоговый тур. В этом году в олимпиаде приняли участие более 300 школьников и студентов из России, Республики Казахстан, Туркменистана, Республики Молдова и Республики Беларусь: 84 участника 6-8 классов, 162 участника 9-11 классов, 58 студентов. Все победители приглашаются на II тур, который пройдёт в очно-дистанционном режиме 29 января 2023 года. Далее проведём краткий разбор задач I тура.
Задания были разделены на три категории – 6-8 классы (6 задач с номерами от 1 до 6), 9-11 классы (8 задач с номерами от 1 до 8) и студенты (все 10 задач).
Задача № 1. Котограмм
«О киса...» – подумал бедный Котилио,
Но не поддался чувству уныния!
Детские тайны он помнил, и вот,
Снова в дорогу отправился кот.
В словах персонажей сокрытый секрет
Заглавными буквами впишите в ответ.
Пробелы в ответе не принимаем.
Ну что, к решению приступаем?
Решение
В первой задаче требуется найти скрытое сообщение в переписке. Легко заметить ошибки в первом сообщениях от Кисы:
Тушистик, хачу я поведать секрет.
Волнуют беня толька горы монет.Кодами терпела твою я старанья,
Но не окажу вновь тебе понинамьэ.
Неверные буквы перечеркнуты. Если мы исправим эти ошибки и подставим правильные буквы, то получим текст составленный из правильных букв: ПомоГимне
Далее тот же принцип используется и в ответе Котилио. Продолжая, получим скрытое сообщение.
Ответ
ПОМОГИМНЕВЫГДЕУКОТЕЯБЕССМЕРТНОГО
Задача № 2
Иван Васильевич очень уважаемый человек. В свои шесть лет он, как выдающийся криптограф, разработал новый шифр «Непростая замена». Он основан на многократном применении шифра «Простая замена».
Иван Васильевич решил спрятать до дня рожденья мамы её любимое лакомство в коробочку и запер на электронный замок с паролевым замком, а то такие подарки постоянно куда-то пропадают до момента дарения. Для этого в течение 10 дней он зашифровывал пароль, чтобы никто не смог вскрыть шкатулку без его ведома. Целых 9987 раз пришлось выполнять шифр простой замены. Результат Иван Васильевич предусмотрительно записал на зелёном листочке. Ключ для шифра простой замены был зарисован на бумаге и хранился у сердца.
Вот настал день «икс». Через час маме нужно дарить подарок. Иван Васильевич забыл пароль. Чтобы расшифровать пароль, нужно снова потратить 10 дней.
Но это не беда. Иван Васильевич меняет профессию, теперь он – ведущий криптоаналитик с десятилетним стажем. Теперь ему по силу взломать этот шифр за 5 минут. А вам?
В ответе запишите заглавными буквами без пробелов, какой пароль использовал Иван Васильевич для того, чтобы закрыть шкатулку.
Решение
Возьмём первую букву зашифрованного сообщения: У. Она находится в цикле У->Л->Я->П->Ь->У. Очевидно, что если 5 раз применить шифр к любой из этих букв, то получим ту же самую букву. Поэтому вместо 9987 раз мы можем взять остаток от деления 9987 на 5 и получим тот же результат: 2. То есть после двух применений шифра была получена буква У, значит, она была получена из буквы П: двигаемся два раза назад по стрелкам от буквы У.
Следующая буква Ю находится в цикле длины 2. Значит, результат 9987 шифрований будет такой же, как одного: буква Ю получена из буквы Р.
Продолжаем с остальными буквами и получаем ответ.
Ответ
ПРИЯТНОПОЗНАКОМИТЬСЯЦАРЬ
Задача № 3. Очень простой шифр без буквы Ё
На примере победитель – ОПАЖГЙСЖКЭ установите правило, по которому при шифровании производится замена букв открытого текста, и прочтите сообщение
ЧЙУ СЬУ НУЯ КМЬ ИАЖ ЬЙЕ КАР ПНВ ШОЗ ЛНГ
Запишите ответ заглавными буквами без пробелов.
Решение
Из примера видим, что буква П перешла в О (предыдущую), а О - в П (следующую), Б - в А (опять предыдущая), Е - в Ж (опять следующая) и т.д. Находим правило: буквы открытого текста, стоящие в нем на нечетных местах, заменяются предыдущими в алфавите буквами, а буквы, стоящие на четных местах, - следующими по алфавиту.
Ответ
ШИФРЭТОТАЙНЫЙЯЗЫКДЛЯСООБЩНИКОВ
Задача № 4
Зная, что ключом шифра является стихотворение Лермонтова «Из Гёте», прочтите сообщение
ВНСЕЕПЗЫ НЛАИМТЕД НОИРТОЫГ ЕАМНАЕТД ЕРМОАЖТА
ИТКЛИИБС ЫТЛЫИПКО РДИОПЖТД ОИГНРЕАМ ФНАОМГИО
Запишите ответ заглавными буквами без пробелов.
Решение
Вспомним или найдём в Интернете (можно использовать любые средства) указанное в условии стихотворение:
Горные вершины
Спят во тьме ночной;
Тихие долины
Полны свежей мглой;
Не пылит дорога,
Не дрожат листы...
Подожди немного,
Отдохнёшь и ты.
Перебирая варианты, можно заметить, что на чётных местах стоят буквы ключевого стихотворения, начиная с «не пылит дорога». На нечётных местах стоит сообщение: ВСЕ ЗНАМЕНИТЫЕ МАТЕМАТИКИ БЫЛИ КРИПТОГРАФАМИ
Ответ
ВСЕЗНАМЕНИТЫЕМАТЕМАТИКИБЫЛИКРИПТОГРАФАМИ
Задача № 5
Прочитайте цитату:
П18о11д10т06м10м16н01с10п18о19т10т06н01м15а26е19ч01с20ь06
В ответе запишите фамилию автора заглавными буквами.
Решение
Заметим, что текст состоит из последовательности букв и-двузначных чисел: П 18 о 11 д 10 т 06...
Попробуем вместо числа поставить букву алфавита с соответствующим номером: Пройдите мимо нас и простите нам наше счастье
С помощью Интернета определяем, что это «Идиот» Достоевского.
Ответ
ДОСТОЕВСКИЙ
Задача № 6
Мария отправила Владиславу сообщение
ЭФУ ЮБВ ПГЯ ЖЮЮ ВЮЬ ЛЫЮ АЮЬ ГЖШ ВЛШ
ЮПЮ ШОЭ ПУЮ ЭРЩ ВШШ ЬЯА ШЫЮ ЧФЮ ШФ
В процессе передачи оно повредилось, найдите количество ошибок. В ответе запишите только число.
Решение
Воспользуемся онлайн-калькулятором шифра Цезаря: https://planetcalc.ru/1434/
Удобно, что он показывает результаты для всех возможных сдвигов. В строке ROT17 видим частично читаемый текст:
НЕД ОСТ АУП ЧОО ТОМ ЬЛО РОМ УЧИ ТЬИ ОАО ИЯН АДО НБЙ ТИИ МПР ИЛО ЗЕО ИЕ
Находим ошибки:
НЕДОСТАУПЧООТОМЬЛОРОМУЧИТЬИОАОИЯНАДОНБЙТИИМПРИЛОЗЕОИЕ
Исправляем и подсчитываем количество ошибок:
НЕДОСТАТОЧНОТОЛЬКОПОЛУЧИТЬЗНАНИЯНАДОНАЙТИИМПРИЛОЖЕНИЕ
Ответ
13
Задача № 7
В городе Базеле рядом с домом Леонарда Эйлера была найдена загадочная записка
Попробуйте восстановить пропуски. Ответ запишите единым числом.
Решение
Подсказкой в задаче является упоминание имени выдающегося математика Леонарда Эйлера. Один из самых известных математических объектов, связанный с Эйлером и криптографией - функция Эйлера, значение которой для натурального числа n равно количеству натуральных чисел, меньших либо равных n и взаимно простых с ним. Функция Эйлера используется в алгоритме шифрования RSA, а все её значения при n > 2 являются чётными. В Википедии приведена таблица первых 99 значений функции Эйлера:
Попробуем поискать начальный фрагмент записки: 16, 24, 24, 16. Последовательных таких значений нет, но, начиная с 48 встречаются 16, 24, 24, 16, 32 с шагом 4. Тогда пропущенные значения: 32, 24, 40.
Ответ
322440
Задача № 8
Задание № 1. Перед вами записка, оставленная обмотанной бинтами женщиной с рыжими волосами. Текст в записке – это набор больших букв русского алфавита в кодировке UTF-8. На записке указаны байты:
1D 02 1C F6 19 EE 11 F0 23 EC 1F F1 14 ED25 E4
24 F8 20 E3 23 F0 27 DF 22 F3 1D F6 1C EF 19 F3
11 FA 23 E7 1F EB 14 EA 25 EA 24 EA 20 E3 23 FF
Известно, что использовался шифр Вижинера на байтах, а в качестве ключа использовалось слово из 13 букв, представленное в кодировке ASCII. В ответе укажите, какой ключ использовался при шифровании.
Решение
Посмотрим, что из себя представляет текст, состоящий из больших букв русского алфавита в кодировке UTF-8:
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ
Сохраним в текстовом файле в кодировке UTF-8, а потом посмотрим коды получившегося текста. Мы для этого воспользуемся программой Far Manager: Shift+F4 для создания нового файла, далее Shift+F8 для выбора кодировки UTF-8. Вставляем алфавит, сохраняем файл, открываем на просмотр F3 и переходим в режим Код:
Видим, что каждая буква кодируется двумя байтами, причём первый байт всегда D0 в шестнадцатеричной системе или 208 в десятичной системе. Это позволяет нам сразу определить ключ без непосредственной дешифровки.
Действительно, D0 при шифровании переходит в 1D, определяем разницу: 77 (буква M в таблице ASCII) - это первая буква ключа. Продолжаем с нечётными байтами. Следующий D0 перейдёт в 1C, разница 76 (буква L) - это третья буква ключа. Продолжая, найдем сначала буквы ключа на нечётных местах, а потом на чётных. Можно определить и открытый текст, хотя это не требуется: ЭТОНЕПРИЯТНАЯСЛУЧАЙНОСТЬ
Ответ
MULTIPASSWORD
Задача № 9
Дано множество точек (x, y). Сложение точек P = (xp, yp) и Q = (xq, yq) происходит по следующему правилу:
Также mP = P + … + P (сложение m раз), где m – целое число
Если координата y точки P = (x, y) не равна 0, то –P = (x,–y).
Если координата y точки P = (x, y) равна 0, то –P = (x, y).
Найдите точку –4P, где P = (2,1), a = 9 и все вычисления проводятся в кольце вычетов по модулю 11. В ответе запишите координаты точки P через пробел.
Решение
В задаче требуется аккуратно проделать указанные в условии задачи действия. Можно составить для этого программу, можно выполнить непосредственно. Правила описывают сложение на эллиптических кривых. Сначала можно вычислить 2P = P + P, потом 4P = 2P + 2P, потом -4P.
Ответ
6 6
Задача № 10
AES – симметричный алгоритм блочного шифрования, принятый в качестве стандарта шифрования правительством США по результатам конкурса AES в 2001 году. Найдите произведения байт, используя алгоритм в данном стандарте шифрования, и в ответ запишите наибольший из результатов – последовательность бит без скобок, пробелов и иных знаков препинания.
(0, 1, 1, 1, 1, 1, 1, 0)(0, 1, 0, 1, 0, 1, 0, 1);
(0, 0, 1, 0, 1, 0, 1, 0)(1, 1, 0, 1, 0, 1, 0, 1);
(1, 1, 1, 0, 0, 1, 1, 1)(0, 0, 0, 0, 1, 0, 1, 1);
(0, 0, 1, 0, 1, 1, 1, 0)(0, 1, 1, 0, 1, 1, 0, 0);
(1, 1, 1, 1, 1, 1, 1, 1)(0, 0, 0, 1, 1, 0, 0, 0).
Решение
Описание алгоритма AES легко найти в Интернете, например, в Википедии по ссылке. Не забываем, что для всех действий используется неприводимый полином x^8+x^4+x^3+x+1.
Перемножаем многочлены в кольце Z2: (x^6+x^5+x^4+x^3+x^2+x)(x^6+x^4+x^2+1) = x^12+x^11+x^8+x^7+x^6+x^5+x^2+x
Разделим полученное произведение на x^8+x^4+x^3+x+1
(x12+x11+x8+x7+x6+x5+x2+x) = (x4+x3)(x8+x4+x3+x+1) + (x7+x3+x2+x)
Результат: 1 0 0 0 1 1 1 0 (в соответствии с коэффициентами остатка от деления многочленов). Остальные аналогично.
Выбираем наибольший из 10001110, 10100110, 01001011, 00010001, 11010000.
Ответ
11010000