1). Допустим, что вы шифровальщик-любитель и хотите прочесть какой-либо текст на английском языке, чтобы определить частоту, с которой встречается каждый символ. Напишите программу, которая считывает текст и выдает на печать вычисленные частоты появления каждой из 26 букв английского алфавита и пробела. В английском языке наиболее распространены буквы ETOANIRSH, указанные здесь в порядке убывания частот их появления. Сравните полученные вами результаты с приведенной здесь последовательностью букв.
2). ЭВМ представляет собой идеальное устройство для кодирования и декодирования секретных сообщений. Напишите программу, выполняющую эти действия с использованием следующих алгоритмов:
Для того чтобы зашифровать букву П с использованием цифры 3, отсчитывается третья по порядку после П буква алфавита Т и подставляется вместо буквы П; шифрование буквы Р с помощью цифры 1 выполняется посредством отсчета одной буквы после Р и подстановки ее вместо Р. Для того чтобы дешифрировать (полученный набор символов, достаточно вести обсчет букв в обратном направлении. Очевидны преимущества этого метода по сравнению с цезаревской подстановкой: во-первых, для каждой буквы возможны 10 разных замен (0—9), а не одна и, во-вторых, труднее подобрать ключ для дешифрирования;
а) цезаревской подстановки, при которой буква А заменяется буквой С, буква В заменяется буквой D, буква С заменяется буквой Е и т.д.;
б) транспозиции по типу “частокола”, состоящей в том, что выбираются 1, 4, 7-й и т.д. символы и располагаются единой группой; за ними помещаются символы 2, 5, 8-й и т.д.; затем идут символы 3, 6, 9-й и т.д.;
в) метода Гронсфельда, основанного и а использовании некоторого цифрового ключа и модификации обычной цезаревской системы. Так, например, применяя в качестве ключа число 31206, можно получить шифрограмму слова ПРОГРАММИРОВАНИЕ следующим образом: Ключ 31206 31206 31206 3
Шифрируемый текст ПРОГР АММИР ОВАНИ Е
Шифр ТСРГЦ ГНОИЦ СГВНО 3
г) транслитерации при которой для перемешивания символов сообщения используются прямоугольные матрицы. Например, можно вписать алфавит в прямоугольник, расположив буквы следующим образом:
1 АДЗЛПУЧЫЯ
2 БЕИМРФШЬ
3 ВЁИНСХЩЭ
4 ГЖКОТЦЪЮ
3). Шифрирование осуществляется путем последовательной выборки элементов т строк матрицы в определенном порядке. Например, если выбираются элементы строк 2, 4, 3, 1, получается следующее зашифрованное сообщение:
БЕИМР ФШЬГЖ КОТЦЪ ЮВЕЙН СХЩЭА ДЗЛПУ ЧЫЯ
Ключом в данном случае являются размеры прямоугольника и порядок перестановки строк. Напишите программу для кодирования и декодирования сообщений этим методом.
Задачи с буквами и цифрами
Иначе говоря, криптографические задачи.
Расшифруйте примеры, подставив вместо букв цифры.
В этом примере одна буква равна двум, другая - пяти, а третья - семи.
ПЯТЬ
+ДВА
____
СЕМЬ
Вот интересная задачка для младшей школы. (Взято отсюда: Е.П.Бененсон, Л.С.Итина. "Математика. Тетрадь № 2 для 3го кл.").
Реши ребус: КОТ - К = КТО. Найди все решения.
Для взрослого человека не такая уж трудная задача. Но для ребенка... Есть большие сомнения...
Интересно, проверяли авторы пособия свои задачи на реальных, а не выдуманных третьеклассниках?
Другие задачки (не из этой книжки):
ДВЕСТИ
+
ТРИСТА
________
ПЯТЬСОТ
СИДИ
+
ЛЕЖИ
______
ИГРАЙ
СЕМЬЯ
Х
И
_______
ШКОЛА
ТРИ
+
ИТРИ
________
ШЕСТЬ
ДВА
+
ПЯТЬ
_________
СЕМЬ
donald
+
donald
gerald
______
robert
d=5, определить остальные цифры.
4). Избранные задачи олимпиад по криптографии
Институт криптографии, связи и информатики (ИКСИ) входит в состав Академии Федеральной службы контрразведки Российской Федерации. ИКСИ имеет в своем составе два факультета: информатики и специальной техники. Институт готовит высококвалифицированных специалистов в области защиты информации, криптографии, специальной связи, компьютерной безопасности.
Для школьников при ИКСИ действует вечерняя физико-математическая школа. С 1991 года институт проводит олимпиады по криптографии и математике, избранные задачи которых публикуются в данном приложении.
Задачки:
1. Ключом шифра, называемого «решетка», является трафарет, сделанный из квадратного листа клетчатой бумаги размером n×n (n — четно). Некоторые из клеток вырезаются с тем, чтобы в получившиеся отверстия на чистый лист бумаги того же размера можно было вписывать буквы текста, подлежащего зашифрованию. Одна из сторон трафарета является помеченной. Кроме того, трафарет должен обладать одним важным свойством: при наложении его на чистый лист бумаги четырьмя возможными способами (помеченной стороной вверх, вправо, вниз, влево) его вырезы полностью покрывают всю площадь квадрата, причем каждая клетка оказывается под вырезом ровно один раз.
Буквы сообщения, имеющего длину n2, последовательно вписываются в вырезы трафарета при каждом из четырех его указанных положений. После снятия трафарета на листе бумаги оказывается зашифрованное сообщение.
Найдите число различных ключей для произвольного четного числа n.
2. В адрес олимпиады пришла шифртелеграмма
ЦДОЗИФКДЦЮ.
Прочитайте зашифрованное сообщение, если известно, что использовался шифр, по которому к двузначному порядковому номеру буквы в алфавите (от 01 до 33) прибавлялось значение многочлена
f(x) = x6 + 3x5 + x4 + x3 + 4x2 + 4x + 5,
вычисленное либо при x = x1, либо при x = x2 (в случайном порядке), где x1,x2 — корни трехчлена x2 + 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. Подберите пароль, состоящий более, чем из трех букв.
4. Коммерсант для передачи цифровой информации с целью контроля передачи разбивает строчку передаваемых цифр на пятерки и после каждых двух пятерок приписывает две последние цифры от суммы чисел, изображенных этими пятерками. Затем процесс шифрования осуществляется путем прибавления к шифруемым цифрам членов арифметической прогрессии с последующей заменой сумм цифр остатками от деления на 10. Прочитайте зашифрованное сообщение:
4 2 3 4 6 1 4 0 5 3 1 3.
5. Рассмотрим модель шифра для цифрового текста, в котором каждая цифра заменяется остатком от деления значения многочлена
f(x) = b(x3 + 7x7 + 3x + a)
на число 10, где a,b — фиксированные натуральные числа. Выяснить, при каких значениях a и b возможно однозначное расшифрование.
6. Фирма предложила на рынок кодовый замок. При установке владелец замка сопоставляет каждой из 26 латинских букв, расположенных на клавиатуре, произвольное натуральное число (известное лишь обладателю замка). После выбора произвольной комбинации попарно различных букв, происходит суммирование числовых значений набранных букв и замок открывается, если сумма делится на 26. Докажите, что для любых числовых значений букв существует комбинация, открывающая замок.
7. Рассматривается шифр, в котором буквы русского 30-буквенного алфавита Ω занумерованы по следующей таблице:
А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Для зашифрования сообщения τ = t1t2...tn выбирается некоторая последовательность κ = γ1γ2...γn (ключ), состоящая из букв алфавита Ω. Зашифрование состоит в позначном сложении соответствующих букв из τ и κ с последующей заменой суммы буквой алфавита Ω, номер которой равен остатку от деления этой суммы на число 30.
Известно, что два сообщения τ1 и τ2 зашифрованы с помощью одного ключа (κ) и что каждое из них содержит слово «корабли». Восстановить τ1 и τ2 по текстам данных криптограмм:
σ1=ЮПТЦАРГШАЛЖЖЕВЦЩЫРВУУ
σ2=ЮПЯТБНЩМСДТЛЖГПСГХСЦЦ
8. Перехвачена «шифровка»: РБЬНПТСИТСРРЕЗОХ
Относительно шифра известно следующее:
— используется шифр предыдущей задачи;
— в качестве ключа используется произвольная последовательность, составленная из букв: А,Б,В.
Прочтите зашифрованное сообщение.
9. Шифр простой замены в алфавите A = {a1, a2,..., an}, состоящем из n различных букв, заключается в замене каждой буквы шифруемого текста буквой того же алфавита, причем разные буквы заменяются разными. Ключом шифра простой замены называется таблица, в которой указано, какой буквой надо заменить каждую букву алфавита A. Если слово СРОЧНО зашифровать простой заменой с помощью ключа:
АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЭЮЯ
ЧЯЮЭЫЫЦШЦХФУБДТЗВРПМЛКАИОЖЕСГН,
то получится слово ВЗДАБД. Зашифровав полученное слово с помощью того же ключа еще раз, получим новое слово ЮШЫЧЯЫ. Сколько всего различных слов можно получить, если указанный процесс шифрования продолжить неограниченно?
10. Сообщение, зашифрованное в пункте А шифром простой замены в алфавите из букв русского языка и знака пробела (_) между словами, передается в пункт Б отрезками по 12 символов. При передаче очередного отрезка сначала передаются все его знаки, стоящие на четных местах в порядке возрастания их номеров, начиная со второго, а затем — все знаки, стоящие на нечетных местах, также в порядке возрастания их номеров, начиная с первого. В пункте Б полученное шифрованное сообщение дополнительно шифруется с помощью некоторого другого шифра простой замены в том же алфавите, а затем таким же образом, как и из пункта А, передается в пункт В. По перехваченным в пункте В отрезкам:
СО_ГЖТПНБЛЖО
РСТКДКСПХЕУБ
_Е_ПФПУБ_ЮОБ
СП_ЕОКЖУУЛЖЛ
СМЦХБЭКГОЩПЫ
УЛКЛ_ИКНТЛЖГ,
восстановите исходное сообщение зная, что в одном из передаваемых отрезков зашифровано слово КРИПТОГРАФИЯ.
11. Дана последовательность C1, C2, C3, ..., Cn, ..., в которой Cn есть последняя цифра числа nn. Доказать, что эта последовательность периодическая и ее период равен 20.
12. Знаки алфавита, состоящего из букв русского языка и символа пробела между словами (_), заменим парами цифр согласно таблице:
А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я _
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Для зашифрования сообщения длины m, записанного в этом алфавите, сначала преобразуем буквенный текст в цифровой T = t1, t2, ..., t2m,а затем, выбрав отрезок K = Cn+1, Cn+2, ..., Cn+2m последовательности из задачи 11, осуществим последовательное поразрядное сложение цифр текста T с цифрами отрезка K, причем в качестве очередного знака шифрованного текста берется цифра единиц соответствующей суммы (младший разряд).
Прочитайте зашифрованное сообщение:
2 3 3 9 8 6 7 2 1 6 4 5 8 1 6 0 6 7 0 6 1 7 3 1 5 5 8 8.
5). Хотелось бы прокомментировать некоторые задачи:
Задача 1. Многие участники дали правильный ответ — 2011015 = 2005*1003, однако только два человека доказало это. Остальные же просто привели некоторые примеры таблиц и нашли нужную сумму только для таблиц определенного вида! Основной проблемой в данном случае было доказать, что на диагонали стоят все числа от 1 до 2005. Для некоторых участников хочу отметить, что эти числа не обязательно стоят в прямом лексикографическом порядке, т.е. 1, 2, 3, 4,…, 2005!
Задача 2. Здесь можно лишь отметить то, что некоторые участники получили половину максимального балла только потому, что не довели свою правильную мысль до конца, не договорив, буквально, всего одного предложения!
Задача 3. Основной ошибкой, которую допускали в этой задаче было предположение, что весь открытый текст был зашифрован простой заменой! Иногда также считали, что исходным текстом было только слово «КРИПТОГРАФИЯ»!
Задача 5. Некоторые участники неправильно поняли смысл задачи или же теоремы, о которой говорилось перед началом олимпиады! Поэтому и указали в качестве ответа число 1, что, разумеется, неверно — ведь нельзя же, используя монеты достоинством в 7 и 10 бут, составить сумму, скажем, в 3 бута — для этого придется взять «отрицательное количество» монет по 10 бут, что в принципе невозможно. А в условиях задачи запрещено давать «сдачу»!
Задача 6. При решении этой задачи участникам пришлось попотеть — ведь подставлять корни первого трехчлена (которые были числами иррациональными) в многочлен шестой степени не такая уж и простая задача. В то же время данная задача решается тривиально — ведь достаточно заметить, что нет никакой разницы, в каком порядке подставлять корни — значением многочлена всегда будет число 3.
Задача 7. Тут были две основные ошибки: некоторые считали, что при шифровании очередной буквы открытого текста диски возвращались в первоначальное положение; другие же подумали, что раз первый диск вращается против часовой стрелки, то буквы алфавита отсчитываются в обратном порядке (Я, Ю, Э…)
6). Задачи
Задача 1
Квадратная таблица размером 2005 × 2005 заполнена натуральными числами от 1 до 2005 так, что в каждой строке присутствуют все числа от 1 до 2005.
Найдите сумму чисел, стоящих на диагонали, которая соединяет левый верхний и правый нижний углы таблицы, если известно, что заполнение таблицы симметрично относительно этой диагонали.
Задача 2
Зашифрование сообщения состоит в замене букв исходного текста на пары цифр в соответствии с некоторой (известной только отправителю и получателю) таблицей, в которой разным буквам алфавита соответствуют разные пары цифр.
Криптоаналитику дали задание восстановить зашифрованный текст. В каком случае ему будет легче выполнить задание:
если известно, что первое слово второй строки — «термометр»
или что первое слово третьей строки — «ремонт»?
Обоснуйте свой ответ.
(Предполагается, что таблица зашифрования криптоаналитику неизвестна).
Задача 3
Для зашифрования текста использовался вращающийся диск, центр которого находится на оси, закрепленной на неподвижном основании. Диск разделен на 33 равных сектора, в которые в неизвестном порядке вписаны все буквы русского алфавита (по одной в каждый сектор). На основании, по одной напротив каждого сектора, выписаны буквы в алфавитном порядке по часовой стрелке. Каждое положение диска, получающееся из исходного поворотом на угол, кратный величине сектора, задает соответствие между буквами на диске и на основании. При зашифровании очередной буквы текста, ее заменяли соответствующей ей буквой при текущем положении диска, после чего диск поворачивался на один сектор по часовой стрелке.
Докажите, что если в результате зашифрования получился текст
РЖВЦЦФШУФЁУМЙУЩЦЯЦЛМВЧЬБЯВЭЪХПЬМЕДБЙЧМПЬИМЕЕРЧСЩГШТЩЭ
, то в исходном тексте не было слова «КРИПТОГРАФИЯ».
Задача 4
Сообщение, зашифрованное в пункте А шифром простой замены в алфавите из букв русского языка и знака пробела (-) между словами, передается в пункт Б отрезками по 12 символов. При передаче очередного отрезка сначала передаются символы, стоящие на четных местах в порядке возрастания их номеров, начиная со второго, а затем — символы, стоящие на нечетных местах (также в порядке возрастания их номеров), начиная с первого. В пункте B полученное шифрованное сообщение дополнительно шифруется с помощью некоторого другого шифра простой замены в том же алфавите, а затем таким же образом, как и из пункта А, передается в пункт В. По перехваченным в пункте В отрезкам:
С О - Г Ж Т П Н Б Л Ж О
Р С Т К Д К С П Х Е У Б
- Е - П Ф П У Б - Ю О Б
С П - Е О К Ж У У Л Ж Л
С М Ц Х Б Э К Г О Щ П Ы
У Л К Л - И К Н Т Л Ж Г
восстановите исходное сообщение, зная, что в одном из переданных отрезков зашифровано слово «КРИПТОГРАФИЯ».
Задача 5
а) Для передачи информации от резидента Гарриваса в Нагонии только что внедренному разведчику был установлен следующий порядок: все сообщения резидента определены заранее и пронумерованы числами 1, 2, 3, ... Разведчик, обладающий феноменальной памятью, полностью запомнил соответствие между сообщениями и их номерами. Теперь для того, чтобы передать информацию разведчику, достаточно было сообщить ему лишь соответствующее число. Для передачи числа в условленном месте оставлялась равная этому числу денежная сумма.
На момент разработки операции в Нагонии имели хождение денежные купюры достоинством 1, 3, 7 и 10 бут (бут - денежная единица Нагонии). Однако в результате денежной реформы купюры достоинством 1 и 3 бут были изъяты из обращения.
Выясните, начиная с какого номера можно передать разведчику любое сообщение, пользуясь только оставшимися в обращении купюрами.
б) Пусть имеются в наличии купюры достоинством a и b бут, где НОД(a, b) = 1.
Начиная с какого номера можно передавать разведчику любое сообщение, пользуясь только купюрами названного достоинства?
Задача 6
Вам пришло зашифрованное сообщение:
ЫЛЧУЩЗКГУВ
Найдите исходное сообщение, если известно, что шифрпреобразование заключалось в следующем:
Пусть x1, x2 — корни трехчлена x2 + 3x + 1. К порядковому номеру каждой буквы в стандартном русском алфавите (33 буквы) прибавлялось значение многочлена f(x) = x6 + 3x5 + x4 + x3 + 4x2 + 4x + 4, вычисленное либо при x = x1, либо при x = x2 (в неизвестном нам порядке), а затем полученное число заменялось соответствующей ему буквой.
Задача 7
На каждой из трех осей установлено по одной вращающейся шестеренке и неподвижной стрелке. Шестеренки соединены последовательно. На первой шестеренке 33 зубца, на второй — 10, на третьей — 7. На каждом зубце первой шестеренки по часовой стрелке написано по одной букве русского языка в алфавитном порядке:
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
На зубцах второй и третьей шестеренки в порядке возрастания по часовой стрелке написаны цифры от 0 до 9 и от 0 до 6 соответственно. Когда стрелка первой оси указывает на букву, стрелки двух других осей указывают на цифры. Буквы сообщения шифруются последовательно. Зашифрование производится вращением первой шестеренки против часовой стрелки до первого попадания шифруемой буквы под стрелку. В этот момент последовательно выписываются цифры, на которые указывают вторая и третья стрелки. В начале шифрования стрелка 1-го колеса указывала на букву А, а стрелки 2-го и 3-го колес — на цифру 0.
а) зашифруйте слово «ОЛИМПИАДА»
б) расшифруйте сообщение 0381717491847501.
Задача 8
а) Установите, возможно ли создать такую проводную телефонную сеть связи, состоящую из 2005 абонентов, каждый из которых был бы связан ровно с 997 другими?
б) Пусть в этой сети N абонентов, каждый из которых должен быть связан ровно с K другими. Найти все возможные наборы (N, K) и описать способ построения таких сетей.
Задача 9
Текст
ЦЗЩИОНФЛЦЩРИОПЖЩЭЩХЖНФЛТЪЙ
ЗНЛУФ_АЩЛЗПИАЗНЭПЬОИВЛОПАЛ
АПАЛТЪЙЗЛЖФЛЦЗВХФОЛХПИОЩОН
ЛЪИЦЩУДЁЩЭПЖЪВЛЗПЁУЪХЖНШЛИ
ЪЮЭЩУЩЭЛЭЛЩОАЗНОЩЮЛОФАИОФ
получен из исходного текста шифром простой замены. А текст
ЯАЧЕЕТВТВРАКНОО_ЛТКЛЛОРСТА
РИФШЫ_ПС_ЫЗХО_ЫКЫК_ОВОТЕНЕ
ЛСЯДЫП_ЧРВПСАК_ЕЗ_СГРМАОТН
СВ_ЕПР_Н_КТСЫОРААИТОООТИК_
ТРИ_НО_ТЧЧЬЫШВЮ_ФАИ_МЕИСЯ
получен из исходного простым перестановочным шифром.
Олимпиада ФСБ по криптографии и шифрованию.
Для зашифрования текста использовался вращающийся диск, центр которого находится на оси, закрепленной на неподвижном основании. Диск разделен на 32 равных сектора, в которые в неизвестном порядке вписаны все буквы русского алфавита (по одной в каждый сектор; буквы Е и Ё не различаются). На основании, по одной напротив каждого сектора, выписаны буквы в алфавитном порядке по часовой стрелке. Каждое положение диска, получающееся из исходного поворотом на угол, кратный величине сектора, задает соответствие между буквами на основании и на диске. При зашифровании очередной буквы текста ее заменяли соответствующей ей буквой при текущем положении диска, после чего диск поворачивался на один сектор по часовой стрелке. Укажите, какой из фрагментов полученного шифртекста
Ж Ж С Ч Ф С Е Н Ы Ы В Я Я О В Ч Э Э Ц Ь Ч Ю Ц Г О Ч П Ю П Ы Ь М З С Х Б З
может соответствовать слову ПРОЖЕКТОР в исходном тексте:
Ж С Ч Ф С Е Н Ы Ы
В Я Я О В Ч Э Э Ц
Ч Ю Ц Г О Ч П Ю П
Ы Ы В Я Я О В Ч Э
Э Э Ц Ь Ч Ю Ц Г О
7). Для тех кому понравилось решать крептографические задачи вам прелогается ещё 4 серии задач.))) Первая серия задач
1.1. Докажите, что если p и q - простые числа, большие 3, то p2-q2 делится на 24.
1.2. Выписывая буквы по ходу шахматного коня, прочтите текст.
л е а ш е
з е а ш д
п е и м и
р ь с а н
ж ч о т у
1.3. Следующая криптограмма получена заменой каждой буквы открытого текста некоторой взаимно однозначно сопоставляемой ей цифрой. Проведите дешифровку и объясните свое решение.
1-2-3 4-5-4 2-1 6-6 2-7-8-4-1 2-6 9-2-3-6-4.
1.4. Имея в виду, что каждая буква заменяет некоторую определенную цифру, восстановите исходное арифметическое равенство:
О:Н = .(УЗНАЕТ)
1.5. Через Zm обозначается множество всех остатков от деления натуральных чисел на фиксированное натуральное число m. В Zm определяются операции сложения и умножения по модулю m: два числа складываются (умножаются) и берется остаток от деления суммы(произведения) на m. Например, в Z5 имеем: 2+4=1, 2*4=3 и т.п.
В Z5 решите уравнения x2 - x + 3 = 0 и x2 + 3x + 1 = 0.
Вторая серия задач
2.1. Дан словарь, то есть набор слов некоторого языка. Анаграммой данного слова называется всякое слово, полученное из него перестановкой букв. Укажите способ нахождения всех анаграмм в заданном словаре.
2.2. Дано натуральное число n, n<100000, и целые числа a1,...,an, -109 <= ai <= 109. Напишите программу, определяющую, можно ли из этих чисел составить арифметическую прогрессию, и если да, то укажите ее первый член и разность.
2.3. Найдите число X и цифру Y такие, что [3*(230+X)]2=492Y04.
2.4. В некоторых системах шифрования в качестве секретных ключей используются панграммы - слова, в которых нет одинаковых букв. Найдите панграммы с числом букв 5, 6, 7, 8, ... Как далеко вы продвинулись? Придумайте как можно более длинную фразу-панграмму.
2.5. Тридцати двум буквам русского алфавита А, Б, В, ..., Э, Ю, Я приписаны соответственно числа 1, 2, 3, ..., 30, 31, 0 (буквы Е и Ё отождествляются). Выбрано некоторое нечетное число k (секретный ключ). Шифрование текста осуществляется побуквенно следующим образом:
1) число a, соответствующее данной букве, умножается на k,
2) вычисляется остаток r от деления a*k на 32,
3) выписывается буква, соответствующая числу r.
Расшифруйте криптограмму:
МН ЩЩКФД ГШМОМЫД ЦЫДЩЩ.
Третья серия задач
3.1. Докажите, что если сумма трех целых чисел делится на 6, то и сумма их кубов делится на 6.
3.2. Палиндромы. Найдите число строк длины n над русским алфавитом (32 буквы), не изменяющихся при чтении в обратном порядке
3.3. Шифр Цезаря. Криптограмма ЩНТШНЬ получена из открытого текста циклическим сдвигом букв русского алфавита (А...ДЕЖ...ЩЬ...Я) на k знаков вправо. Найдите ключ k, восстановите исходное сообщение, а затем зашифруйте его циклическим сдвигом на k знаков влево.
3.4. При шифровании открытый текст разбивается на блоки одинаковой длины и в каждом блоке осуществляется перестановка букв по одной и той же схеме. Восстановите исходное сообщение по криптограмме.
ПЬОКМРХТЮЕШИРООМОПЙОККНЩИТОИРПФАРГА
3.5. Первоначально строка s состоит из данного сообщения, строка t - пустая. Шифрование сообщения происходит следующим образом:
1. если в строке s не осталось букв, шифрование закончено - криптограмма записана в строке t;
2. к строке t справа последовательно приписываются буквы из строки s, стоящие на нечетных местах;
3. из строки s вычеркиваются все буквы, стоящие на нечетных местах;
4. процесс повторяется, начиная с шага 1.
Например, для строки s=КРИПТОГРАФИЯ криптограммой будет t=КИТГАИРОФПЯР. Расшифруйте текст ПИЫАТАТАОЗОТИРВЗРЕМБВДЕРП. Какой символ строки s=s1s2...s1024 будет занимать в криптограмме t позицию 1000? Каким методом вы действовали?
Четвертая серия задач
4.1. Дано натуральное число k. Найти наименьшее натуральное число n, имеющее в точности k различных делителей. Можно считать, что k<=60.
4.2. Даны n целых чисел a1,a2,...,an и натуральное число m>1. Составьте программу, которая распределит числа a1,a2,...,an так, чтобы сначала шли (по возрастанию абсолютной величины) все числа, дающие при делении на m остаток 0, затем 1, 2,...,m-1.
4.3. Каждой букве ai руского алфавита (см. 2.5, 3.3) ставится в соответствие натуральное число f(ai). Сообщение m=m1m2... шифруется следующим образом: буква m1 циклически сдвигается в нем вправо на f(m1) позиций, затем m2 на f(m2) позиций и т.д. Расшифруйте криптограмму ДИМАИЛПАО.
4.4. Под буквами шифруемого текста последовательно подписываются буквы, составляющие начальный фрагмент некоторого литературного произведения (ключ). Шифрование осуществляется побуквенно сложением по модулю 32 (см. 1.5) номера данной буквы открытого текста (см 2.5) с номером стоящей под ней буквы ключа и последующим выписыванием буквы, соответствующей полученной сумме. Известно, что сообщение СМЕНИТЕШИФР было зашифровано как ЪНРЫДАЛККЭБ. Определите ключевое стихотворение.
4.5. Открытое сообщение разбивается на блоки по k букв в каждом (при необходимости к нему приписывается нужное число букв). Секретным ключом является вектор (a1,a2,...,ak) с натуральными компонентами. При шифровании i-я буква каждого блока заменяется буквой, стоящей в алфавите на ai позиции правее ее (сдвиг циклический). Зная, что k=3, расшифруйте криптограмму
ВМВЪСМЫУДЪСМОЧДЪЫДЪСМСБЖЪСД
