В адрес олимпиады пришло зашифрованное сообщение фвмежтивфю

Обновлено: 05.07.2024

Избранные задачи олимпиад по криптографии

Институт криптографии, связи и информатики (ИКСИ) входит в состав Академии Федеральной службы контрразведки Российской Федерации. ИКСИ имеет в своем составе два факультета: информатики и специальной техники. Институт готовит высококвалифицированных специалистов в области защиты информации, криптографии, специальной связи, компьютерной безопасности.

Для школьников при ИКСИ действует вечерняя физико-математическая школа. С 1991 года институт проводит олимпиады по криптографии и математике, избранные задачи которых публикуются в данном приложении.

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

2. В адрес олимпиады пришла шифртелеграмма

f(x) = x 6 + 3x 5 + x 4 + x 3 + 4x 2 + 4x + 5,

вычисленное либо при x = x₁, либо при x = x₂ (в случайном порядке), где x₁,x₂ — корни трехчлена x 2 + 3x + 1, а затем полученное число заменялось соответствующей ему буквой.

3. Одна фирма предложила устройство для автоматической проверки пароля. Паролем может быть любой непустой упорядоченный набор букв в алфавите a, b, c>. Будем обозначать такие наборы большими латинскими буквами. Устройство перерабатывает введенный в него набор P в набор Q = φ(P). Отображение φ держится в секрете, однако про него известно, что оно определено не для каждого набора букв P и обладает следующими свойствами. Для любого набора букв P

1) φ(aP) = P;

2) φ(bP) = φ(P)aφ(P);

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

Устройство признает предъявленный пароль верным, если φ(P) = P. Например, трехбуквенный набор bab является паролем, так как φ(bab) = φ(ab)aφ(ab) = bab. Подберите пароль, состоящий более, чем из трех букв.

5. Рассмотрим модель шифра для цифрового текста, в котором каждая цифра заменяется остатком от деления значения многочлена

f(x) = b(x 3 + 7x 7 + 3x + a)

на число 10, где a,b — фиксированные натуральные числа. Выяснить, при каких значениях a и b возможно однозначное расшифрование.

6. Фирма предложила на рынок кодовый замок. При установке владелец замка сопоставляет каждой из 26 латинских букв, расположенных на клавиатуре, произвольное натуральное число (известное лишь обладателю замка). После выбора произвольной комбинации попарно различных букв, происходит суммирование числовых значений набранных букв и замок открывается, если сумма делится на 26. Докажите, что для любых числовых значений букв существует комбинация, открывающая замок.

7. Рассматривается шифр, в котором буквы русского 30-буквенного алфавита Ω занумерованы по следующей таблице:

Относительно шифра известно следующее:

— используется шифр предыдущей задачи;

— в качестве ключа используется произвольная последовательность, составленная из букв: А,Б,В.

9. Шифр простой замены в алфавите A = a₁, a₂. a_n>, состоящем из n различных букв, заключается в замене каждой буквы шифруемого текста буквой того же алфавита, причем разные буквы заменяются разными. Ключом шифра простой замены называется таблица, в которой указано, какой буквой надо заменить каждую букву алфавита A. Если слово

то получится слово

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

11. Дана последовательность C₁, C₂, C₃, . C_n, . в которой C_n есть последняя цифра числа n n . Доказать, что эта последовательность периодическая и ее период равен 20.

12. Знаки алфавита, состоящего из букв русского языка и символа пробела между словами (_), заменим парами цифр согласно таблице:

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

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

Ф В М Е Ж Т И В Ф Ю

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Описание презентации по отдельным слайдам:

XVI олимпиада
по математике
и криптографии
3 декабря 2006 г.

Задача № 1
Каждая буква фрагмента известного стихотворения Ф.И. Тютчева заменена некоторой буквой так, что разным буквам соответствуют разные буквы, а одинаковым - одинаковые. Пробелы и знаки препинания сохранены. Восстановите этот фрагмент стихотворения:
Гьюь Фюббшн эй яюэовл,
Пфзшэюь юришь эй шчьйфшвл:
Г эйщ юбюрйээпо бвпвл 
С Фюббшн ьюцэю вюылъю сйфшвл.

Гьюь Фюббшн эй яюэовл,
Пфзшэюь юришь эй шчьйфшвл:
Г эйщ юбюрйээпо бвпвл 
С Фюббшн ьюцэю вюылъю сйфшвл.

Задача № 1 (ответ)

Умом Россию не понять,
Аршином общим не измерить:
У ней особенная стать –
В Россию можно только верить.

Задача № 2
Криптоша изобрел устройство, которое позволяет вычислить среднее арифметическое любых 9 чисел или любых 223 чисел.

Задача №2 (продолжение)
Как правильно использовать это устройство, чтобы найти среднее арифметическое любых 2006 чисел.

При необходимости можно дополни-тельно провести одно деление и одно умножение.

Задача № 2 (решение)
Добавим к числам еще одно, равное нулю. Тогда

Задача № 2 (решение)

Задача № 2 (ответ)

Задача № 3
Пара вида аij blm заменяется:

при i ≠ l парой bim alj ;

при i = l парой blj aim .

d s z q u p h s b q i j d b m h p s j u i n.
Определите, какой именно?

Задача № 3 (решение)
Способ зашифрования текста обладает свойством:
Если пара ab заменяется на пару cd,
то пара dc перейдет в пару ba.

Задача № 3 (решение)
ОТКРЫТЫЙ ТЕКСТ
сr yp to gr ap hi ca lg or it hm

рa bd gl iu rc av th ot ue ad sp
ПЕРВЫЙ ШИФРТЕКСТ

противоречащих свойству пар нет

Задача №3 (решение)
ОТКРЫТЫЙ ТЕКСТ
сr yp to gr ap hi ca lg or it hm

ds zq up hs bq ij db mh ps ju in
ВТОРОЙ ШИФРТЕКСТ

есть противоречащие свойству пары

Задача № 4
Пусть a1, a2, a3, … и b1, b2, b3, … последовательности периодов 16 и 2006 соответственно. Найдите период последовательности
a1, b1, a2, b2, a3, b3, …
Периодом x1, x2,… называется наимень-шее натуральное число T, что для всех натуральных n верно равенство
xn+T = xn

Задача № 4 (решение)
Разобьём последовательность на пары
(х1,х2), (х3,х4), …
(a1,b1), (a2,b2), …
Период этой последовательности пар равен c=НОК(16,2006)=16048.

Задача № 4 (решение)
При всех натуральных n верно равенство
xn=xn+2с

Задача № 4 (решение)
При всех натуральных n верно равенство
xn=xn+2с
Покажем, что 2с – наименьшее число с таким условием.

Задача № 4 (решение)
При всех натуральных n верно равенство
xn=xn+2с
Покажем, что 2с – наименьшее число с таким условием.
Пусть период последовательности равен t. Тогда число 2c должно делиться на число t.

Задача № 4 (решение)
Случай 1. Пусть t нечетно.

Задача № 4 (решение)
Случай 2. Пусть t четно, t =2k.
Тогда для всех m выполнено
x2m-1+t = x2m-1
x2m+t = x2m
Отсюда
am+k=am
bm+k=bm

Задача № 4 (решение)
Таким образом, k делится на НОК периодов исходных последователь-ностей.

Отсюда t = 2НОК(16, 2006) = 32096.

Задача № 5
Бильярдные шары плотно уложены в правильный треугольник с основа-нием из 2006 шаров. На каждом шаре написано число. Сумма трех чисел на шарах при вершинах исход-ного треугольника, а также любых треугольников со сторонами, парал-лельными исходному треугольнику, равна 0. Какие числа могут быть написаны на шарах?

Задача № 5 (решение)

Задача № 6
Заполните неокрашенные клетки таблицы числами от 1 до 9. При этом, сумма цифр в каждой горизонтальной неокрашенной цепочке должна совпадать с числом, указанным слева от цепочки, а в каждой вертикальной неокрашенной цепочке - с числом, указанным сверху от цепочки.
В каждой цепочке ни одна цифра не должна повторяться.

Задача № 6 (решение)

Единственно возможное заполнение таблицы

Задача № 6 (решение)

Мероприятия для школьников в 2007 году
Окружной тур олимпиады по математике
28 января (воскресенье)

Окружной тур олимпиады по физике
3 февраля (суббота)

Региональная олимпиада по математике
25 февраля (воскресенье)

Мероприятия для школьников в 2007 году

Победителям этих олимпиад предоставляются льготы при поступлении в ИКСИ и ряд других вузов.

Мероприятия для школьников в 2007 году

Собеседования
(для школьников 10 класса)

март, май
по предварительной записи

Мероприятия для школьников в 2007 году

Письменные работы по математике и физике
октябрь

Мероприятия для школьников в 2007 году
XVII Олимпиада по математике и криптографии

в конце ноября или начале декабря

подготовка к ЕГЭ/ОГЭ и ВПР
по всем предметам 1-11 классов

Курс повышения квалификации

Охрана труда

Курс профессиональной переподготовки

Охрана труда

Курс профессиональной переподготовки

Библиотечно-библиографические и информационные знания в педагогическом процессе

ЗП до 91 000 руб.
Гибкий график
Удаленная работа

Дистанционные курсы для педагогов

Свидетельство и скидка на обучение каждому участнику

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

5 605 635 материалов в базе

Самые массовые международные дистанционные

Школьные Инфоконкурсы 2022

Свидетельство и скидка на обучение каждому участнику

Другие материалы

Вам будут интересны эти курсы:

Оставьте свой комментарий

18.01.2020 144
PPTX 107 кбайт
1 скачивание
Оцените материал:

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

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Автор материала

40%

Подготовка к ЕГЭ/ОГЭ и ВПР
Для учеников 1-11 классов

Московский институт профессиональной
переподготовки и повышения
квалификации педагогов

Дистанционные курсы
для педагогов

663 курса от 690 рублей

Выбрать курс со скидкой

Выдаём документы
установленного образца!

Учителя о ЕГЭ: секреты успешной подготовки

Время чтения: 11 минут

Ленобласть распределит в школы прибывающих из Донбасса детей

Время чтения: 1 минута

В Россию приехали 10 тысяч детей из Луганской и Донецкой Народных республик

Время чтения: 2 минуты

Курские власти перевели на дистант школьников в районах на границе с Украиной

Время чтения: 1 минута

Время чтения: 2 минуты

Школы граничащих с Украиной районов Крыма досрочно уйдут на каникулы

Время чтения: 0 минут

Минпросвещения России подготовит учителей для обучения детей из Донбасса

Время чтения: 1 минута

Подарочные сертификаты

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

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

Читайте также: