IV Олимпиада по криптографии и математике
список всех олимпиад по криптографии и математике
Задача 4.1.
Ключом шифра, называемого «решеткой», является прямоугольный трафарет размера 6× 10 клеток. В трафарете вырезаны 15 клеток так, что при наложении его на прямоугольный лист бумаги размера 6 × 10 клеток четырьмя возможными способами его вырезы полностью покрывают всю площадь листа.
Буквы сообщения (без пропусков) последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений. Прочтите исходный текст, если после зашифрования на листе бумаги оказался следующий текст (на русском языке):
Задача 4.2.
Криптограмма
12 2 24 5 3 21 6 29 28 2 20 18 20 21 5 10 27 17 2 11 2 16 -
19 2 27 5 8 29 12 31 22 2 16, 19 2 19 5 17 29 8 29 6 29 16:
8 2 19 19 29 10 19 29 14 19 29 29 19 10 2 24 2 11 2 16
10 14 18 21 17 2 20 2 28 29 16 21 29 28 6 29 16.
получена заменой букв на числа (от 1 до 32) так, что разным буквам соответствуют разные числа. Отдельные слова разделены несколькими пробелами, буквы - одним пробелом, знаки препинания сохранены. Буквы «е» и «ё» не различаются. Прочтите четверостишие В. Высоцкого.
Задача 4.3.
«Шифровальный диск» используется для зашифрования числовых сообщений. Он состоит из неподвижного диска и соосно вращающегося на нем диска меньшего диаметра. На обоих дисках нанесены цифры от 0 до 9, которые расположены в вершинах правильных 10-угольников, вписанных в диски.
Цифра X на неподвижном диске зашифровывается в цифру Y подвижного диска, лежащую на том же радиусе, что и X.
Для построения вписанного 10-угольника без транспортира надо уметь строить угол в 36◦. Попытайтесь вычислить с точностью до 0,1 значение какой-либо тригонометрической функции такого угла без таблиц и калькулятора.
Задача 4.4.
Зашифрование фразы на латинском языке осуществлено в два этапа. На первом этапе каждая буква текста заменяется на следующую в алфавитном порядке (последняя Z заменяется на первую A). На втором этапе применяется шифр простой замены с неизвестным ключом. Его применение заключается в замене каждой буквы шифруемого текста буквой того же алфавита, при этом разные буквы заменяются разными буквами. Ключом такого шифра является таблица, в которой указано, какой буквой надо заменить каждую букву алфавита.
По данному шифртексту
OSZJX FXRE YOQJSZ RAYFJ
восстановите открытое сообщение, если известно, что для использованного (неизвестного) ключа результат шифрования не зависит от порядка выполнения указанных этапов для любого открытого сообщения. Пробелы в тексте разделяют слова.
Латинский алфавит состоит из следующих 24 букв:
A B C D E F G H I J L M N O P Q R S T U V X Y Z.
Задача 4.5.
Для проверки телетайпа, печатающего буквами русского алфавита
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
передан набор из 9 слов, содержащий все 33 буквы алфавита. В результате неисправности телетайпа на приемном конце получены слова
ГЪЙ АЭЕ БПРК ЕЖЩЮ НМЬЧ СЫЛЗ ШДУ ЦХОТ ЯФВИ
Восстановите исходный текст, если известно, что характер неисправности таков, что каждая буква заменяется буквой, отстоящей от нее в указанном алфавите не дальше, чем на две буквы. Например, буква Б может перейти в одну из букв {А, Б, В, Г}.
Задача 4.6.
Исходное сообщение из букв русского алфавита преобразуется в числовое сообщение заменой каждой его буквы числом по следующей таблице:
A | Б | В | Г | Д | Е | Ж | З | И | К |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
Л | М | Н | О | П | Р | С | Т | У | Ф |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
X | Ц | Ч | Ш | Щ | Ь | Ы | Э | Ю | Я |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
Для зашифрования полученного числового сообщения используется шифрующий отрезок последовательности подходящей длины, начинающийся с
.
При зашифровании каждое число числового сообщения складывается с соответствующим числом шифрующего отрезка. Затем вычисляется остаток от деления полученной суммы на 30, который по данной таблице заменяется буквой. Восстановите сообщение КЕНЗЭРЕ, если шифрующий отрезок взят из последовательности, у которой и
для любого натурального
.
Задача 4.7
Чтобы запомнить периодически меняющийся пароль в ЭВМ, математики придумали следующий способ. При известном числе a (например, номере месяца в году), пароль представляет собой первые шесть цифр наименьшего решения уравнения . (Число меньшей значности дополняется справа необходимым числом нулей.)
Решите такое уравнение при произвольном .