Главная > Разное > Введение в криптографию
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5. Условия задач олимпиад по математике и криптографии

Ниже приводятся задачи семи олимпиад по криптографии и математике. Нумерация задач двойная: первая цифра — номер олимпиады, вторая — номер задачи в олимпиаде. Для решения задач не требуется специальных знаний. Все необходимые определения даны в условиях. Задачи рассчитаны на учащихся 9, 10 и 11 классов.

1.1. Ключом шифра, называемого «поворотная решетка», является трафарет, изготовленный из квадратного листа клетчатой бумаги размера четно). Некоторые из клеток вырезаются. Одна из

сторон трафарета помечена. При наложении этого трафарета на чистый лист бумаги четырьмя возможными способами (помеченной стороной вверх, вправо, вниз, влево) его вырезы полностью покрывают всю площадь квадрата, причем каждая клетка оказывается под вырезом ровно один раз.

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

Найдите число различных ключей для произвольного четного числа

1.2. В адрес олимпиады пришло зашифрованное сообщение:

Найдите исходное сообщение, если известно, что шифрпреобразование заключалось в следующем. Пусть корни трехчлена К порядковому номеру каждой буквы в стандартном русском алфавите (33 буквы) прибавлялось значение многочлена вычисленное либо при либо при (в неизвестном нам порядке), а затем полученное число заменялось соответствующей ему буквой.

1.3. Для передачи информации от резидента Гарриваса в Нагонии только что внедренному разведчику был установлен следующий порядок.

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

Для передачи числа в условленном месте оставлялась равная этому числу денежная сумма.

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

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

1.4. Сколько существует упорядоченных пар натуральных чисел а и 6, для которых известны их наибольший общий делитель и их наименьшее общее кратное Сформулируйте ответ и в общем

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

1.5. Дана криптограмма:

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

1.6. Одна фирма предложила устройство для автоматической проверки пароля. Паролем может быть любой непустой упорядоченный набор букв в алфавите Будем обозначать такие наборы большими латинскими буквами. Устройство перерабатывает введенный в него набор в набор Отображение держится в секрете, однако про него известно, что оно определено не для каждого набора букв и обладает следующими свойствами. Для любого набора букв

3) набор получается из набора выписыванием букв в обратном порядке.

Устройство признает предъявленный пароль верным, если Например, трехбуквенный набор является верным паролем, так как Подберите верный пароль, состоящий более чем из трех букв.

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

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

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

Найдите исходное цифровое сообщение по шифрованному сообщению:

2.3. Рассмотрим преобразование цифрового текста, в котором каждая цифра заменяется остатком от деления значения многочлена на число 10, где фиксированные натуральные числа.

Выясните, при каких значениях указанное преобразование может быть шифрпреобразованием (то есть допускает однозначное расшифрование).

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

Докажите, что для любых числовых значений букв существует комбинация, открывающая замок.

2.5. Сообщение, записанное в алфавите

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

Восстановите два исходных сообщения, каждое из которых содержит слово КОРАБЛИ, если результат их зашифрования при помощи одной и той же шифрующей последовательности известен:

2.6. Буквы русского алфавита занумерованы в соответствии с таблицей:

(см. скан)

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

Прочтите шифрованное сообщение: если известно, что шифрующая последовательность не содержала никаких букв, кроме

3.1. Установите, можно ли создать проводную телефонную сеть связи, состоящую из 993 абонентов, каждый из которых был бы связан ровно с 99 другими.

3.2. Шифрпреобразование простой замены в алфавите состоящем из различных букв, заключается в замене каждой буквы шифруемого текста буквой того же алфавита, причем разные буквы заменяются разными. Ключом шифра простой замены называется таблица, в которой указано, какой буквой надо заменить каждую букву алфавита А. Если слово СРОЧНО зашифровать простой заменой с помощью ключа:

(см. скан)

то получится слово Зашифровав полученное слово с помощью того же ключа еще раз, получим слово Сколько всего различных слов можно получить, если указанный процесс шифрования продолжать неограниченно?

3.3. Сообщение, зашифрованное в пункте А шифром простой замены в алфавите из букв русского языка и знака пробела между словами, передается в пункт отрезками по 12 символов. При передаче очередного отрезка сначала передаются символы, стоящие на четных местах в порядке возрастания их номеров, начиная со второго, а затем — символы, стоящие на нечетных местах (также в порядке возрастания их номеров), начиная с первого. В пункте В полученное шифрованное сообщение дополнительно шифруется с помощью некоторого другого шифра простой замены в том же алфавите, а затем таким же образом, как и из пункта А, передается в пункт В. По перехваченным в пункте В отрезкам:

(см. скан)

восстановите исходное сообщение, зная, что в одном из переданных отрезков зашифровано слово КРИПТОГРАФИЯ.

3.4. Дана последовательность чисел в которой есть последняя цифра числа пп. Докажите, что эта последовательность периодическая и ее наименьший период равен 20.

3.5. Исходное сообщение, состоящее из букв русского алфавита и знака пробела между словами, преобразуется в цифровое сообщение заменой каждого его символа парой цифр согласно следующей таблице:

(см. скан)

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

3.6. Равносторонний треугольник разбит на четыре части так, как показано на рисунке, где середины сторон и соответственно. Известно, что В каком отношении точки делят сторону если известно, что из этих частей можно составить квадрат?

Рис. 6.

4.1. Ключом шифра, называемого «решеткой», является прямоугольный трафарет размера клеток. В трафарете вырезаны 15 клеток

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

Буквы сообщения (без пропусков) последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений. Прочтите исходный текст, если после зашифрования на листе бумаги оказался следующий текст (на русском языке):

(см. скан)

4.2. Криптограмма

получена заменой букв на числа (от 1 до 32) так, что разным буквам соответствуют разные числа. Отдельные слова разделены несколькими пробелами, буквы — одним пробелом, знаки препинания сохранены. Буквы не различаются. Прочтите четверостишие В. Высоцкого.

4.3. «Шифровальный диск» используется для зашифрования числовых сообщений. Он состоит из неподвижного диска и соосно вращающегося на нем диска меньшего диаметра. На обоих дисках нанесены цифры от 0 до 9, которые расположены в вершинах правильных -угольников, вписанных в диски.

Цифра X на неподвижном диске зашифровывается в цифру подвижного диска, лежащую на том же радиусе, что и

Для построения вписанного -угольника без транспортира надо уметь строить угол в 36°. Попытайтесь вычислить с точностью до 0,1 значение какой-либо тригонометрической функции такого угла без таблиц и калькулятора.

4.4. Зашифрование фразы на латинском языке осуществлено в два этапа. На первом этапе каждая буква текста заменяется на следующую в алфавитном порядке (последняя заменяется на первую А). На втором этапе применяется шифр простой замены с неизвестным ключом. Его применение заключается в замене каждой буквы шифруемого текста буквой того же алфавита, при этом разные буквы заменяются

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

восстановите открытое сообщение, если известно, что для использованного (неизвестного) ключа результат шифрования не зависит от порядка выполнения указанных этапов для любого открытого сообщения. Пробелы в тексте разделяют слова.

Латинский алфавит состоит из следующих 24 букв:

4.5. Для проверки телетайпа, печатающего буквами русского алфавита

передан набор из 9 слов, содержащий все 33 буквы алфавита. В результате неисправности телетайпа на приемном конце получены слова

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

4.6. Исходное сообщение из букв русского алфавита преобразуется в числовое сообщение заменой каждой его буквы числом по следующей таблице:

(см. скан)

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

При зашифровании каждое число числового сообщения складывается с соответствующим числом шифрующего отрезка. Затем вычисляется остаток от деления полученной суммы на 30, который по данной таблице заменяется буквой. Восстановите сообщение если шифрующий отрезок взят из последовательности, у которой для любого натурального k.

4.7. Чтобы запомнить периодически меняющийся пароль в математики придумали следующий способ. При известном числе а (например, номере месяца в году), пароль представляет собой первые шесть цифр наименьшего решения уравнения

(Число меньшей значности дополняется справа необходимым числом нулей.)

Решите такое уравнение при произвольном

5.1. Комбинация трех натуральных чисел, лежащих в диапазоне от 10 до 20 включительно, является отпирающей для кодового замка, если выполнено соотношение Найдите все отпирающие комбинации для замка с

5.2. Сообщение было построчно записано в таблицу, имеющую 20 столбцов. При этол в каждую клетку таблицы записывалось по одной букве сообщения, пробелы между словами были опущены, а знаки препинания заменены на условные комбинации: точка — запятая — Затем столбцы таблицы были некоторым образом переставлены, в результате чего был получен текст:

(см. скан)

Прочтите исходное сообщение.

5.3. Из точки О внутри треугольника на его стороны опущены перпендикуляры Докажите, что

5.4. Зашифрование сообщения состоит в замене букв исходного текста на пары цифр в соответствии с некоторой (известной только отправителю и получателю) таблицей, в которой разным буквам алфавита соответствуют разные пары цифр. Криптографу дали задание восстановить зашифрованный текст. В каком случае ему будет легче выполнить задание: если известно, что первое слово второй строки — «термометр» или что первое слово третьей строки — «ремонт»? Обоснуйте свой ответ. (Предполагается, что таблица зашифрования криптографу неизвестна).

5.5. Решите уравнение:

5.6. При передаче сообщений используется некоторый шифр. Пусть известно, что каждому из трех шифрованных текстов

соответствовало исходное сообщение МОСКВА. Попробуйте расшифровать три текста

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

6.1. В системе связи, состоящей из 1997 абонентов, каждый абонент связан ровно с N другими. Определите все возможные значения

6.2. Квадратная таблица размером заполнена натуральными числами от 1 до 1997 так, что в каждой строке присутствуют все числа от 1 до 1997. Найдите сумму чисел, стоящих на диагонали, которая соединяет левый верхний и правый нижний углы таблицы, если заполнение таблицы симметрично относительно этой диагонали.

6.3. Текст

получен из исходного сообщения перестановкой его букв. Текст

получен из того же исходного сообщения заменой каждой буквы на другую букву так, что разные буквы заменены разными, а одинаковые — одинаковыми. Восстановите исходное сообщение.

6.4. На каждой из трех осей установлено по одной вращающейся шестеренке и неподвижной стрелке. Шестеренки соединены последовательно. На первой шестеренке 33 зубца, на второй — 10, на третьей — 7. На каждом зубце первой шестеренки по часовой стрелке написано по одной букве русского языка в алфавитном порядке:

На зубцах второй и третьей шестеренки в порядке возрастания по часовой стрелке написаны цифры от 0 до 9 и от 0 до 6 соответственно. Когда стрелка первой оси указывает на букву, стрелки двух других осей указывают на цифры.

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

третья стрелки. В начале шифрования стрелка колеса указывала на букву А, а стрелки колес — на цифру 0.

а) зашифруйте слово

б) расшифруйте сообщение 24809283911211.

6.5. Цифры от 1 до 9 расположены на окружности в некотором неизвестном порядке. При зашифровании цифрового сообщения каждая отличная от 0 цифра заменяется на соседнюю с ней цифру на окружности по часовой стрелке, а при расшифровании — на соседнюю с ней цифру на окружности против часовой стрелки. Цифра 0 остается без изменения в обоих случаях.

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

6.6. Докажите, что для каждого простого числар последовательность является периодической с периодом 2, если равно остатку от деления числа на 24 при всех

6.7. Найдите все значения параметра а, при которых уравнение

имеет ровно 1997 различных решений.

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

7.2. В компьютерной сети используются пароли, состоящие из цифр. Чтобы избежать хищения паролей, их хранят на диске в зашифрованном виде. При необходимости использования происходит однозначное расшифрование соответствующего пароля. Зашифрование пароля происходит посимвольно одним и тем же преобразованием. Первая цифра остается без изменения, а результат зашифрования каждой следующей цифры зависит только от нее и от предыдущей цифры.

Известен список зашифрованных паролей:

имеющиеся в зашифрованном виде в этом списке. Можно ли определить какие-либо другие пароли? Если да, то восстановите их.

7.3. В результате перестановки букв сообщения получена криптограмма:

БТИПЧЬЛОЯЧЫЬТОТПУНТНОНЗЛЖАЧОЬОТУНИУХНИППОЛОЬЧОЕЛОЛС

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

7.4. Знаменитый математик Леонард Эйлер в 1759 г. нашел замкнутый маршрут обхода всех клеток шахматной доски ходом коня ровно по одному разу. Прочтите текст, вписанный в клетки шахматной доски по такому маршруту (см. рис. 7). Начало текста в

Рис. 7.

7.5. При докажите неравенство:

7.6. Для рисования на большой прямоугольной доске используется мел с квадратным сечением со стороной 1 см. При движении мела стороны сечения всегда параллельны краям доски. Как начертить выпуклый многоугольник площадью с наименьшей площадью границы (площадь границы не входит в площадь многоугольника)?

7.7. Цифры разбиты на несколько непересекающихся групп. Из цифр каждой группы составляются всевозможные числа, для записи каждого из которых все цифры группы используются ровно один раз (учитываются и записи, начинающиеся с нуля). Все полученные числа расположили в порядке возрастания и к-ому числу поставили в соответствие букву алфавита

Оказалось, что каждой букве соответствует число и каждому числу соответствует некоторая буква. Шифрование сообщения осуществляется заменой каждой буквы соответствующим ей числом. Если ненулевое число начинается с нуля, то при шифровании этот нуль не выписывается. Восстановите сообщение 873146507381 и укажите таблицу замены букв числами.

<< Предыдущий параграф Следующий параграф >>
Оглавление