C r y p t o g r a p h i c a l g o r i t h m 3 страница

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

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

Решение

Отсутствует.
Задача 5.Криптограмма

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) так, что разным буквам соответствуют разные числа. Отдельные слова разделены несколькими пробелами, буквы - одним пробелом, знаки препинания сохранены. Буквы "е" и "ё" не различаются. Прочтите четверостишие В. Высоцкого.

Решение

Один из вариантов решения состоит из следующих этапов.

1. 19=н из второй строки ("19,2 19,5").

2. 29=о из третьей строки ("29,н,10") и 10=а или 10=и.

3. 14=щ из "но,14,но".

4. 8=д, 2=е, 10=и из "денно и нощно".

Получили текст:

12 е 24 5 3 21 6 о 28 е 20 18 20 21 5 и 27 17 е 11 е 16 - н е 27 5 д о 12 31 22 е 16, н е н 5 17 о д о 6 о 16: д е н н о и н о щ н о о н и е 24 е 11 е 16 и щ 18 21 17 е 20 е 28 о 16 21 о 28 6 о 16.

5. 5=а и 27=з из второй строки.

6. 17=в 6=п 16=й - последнее слово второй строки - водопой.

Получили текст:

12 е 24 а 3 21 п о 28 е 20 18 20 21 а и з в е 11 е й - н е з а д о 12 31 22 е й, н е н а в о д о п о й: д е н н о и н о щ н о о н и е 24 е 11 е й и щ 18 21 в е 20 е 28 о й 21 о 28 п о й.

7. 21=т 18=у 28=л 20=с из последней строки "ищут веселой толпой".

8. 11=р из "з в е 11 е й" первой строки.

Итак,

12 е 24 а 3 т п о л е с у с т а и з в е р е й - н е з а д о 12 31 22 е й, н е н а в о д о п о й: д е н н о и н о щ н о о н и е 24 е р е й и щ у т в е с е л о й т о л п о й.

9. 24=г из "егерей".

10. 12=б 3=ю из "бегают".

11. 31=ы 22=ч из "добычей".

Задача 6.Ключом шифра, называемого "решеткой", является прямоугольный трафарет размера 6×10 клеток. В трафарете вырезаны 15 клеток так, что при наложении его на прямоугольный лист бумаги размера 6×10 клеток четырьмя возможными способами его вырезы полностью покрывают всю площадь листа.

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

Р	П	Т	Е	Ш	А	В	Е	С	Л
О	Я	Т	А	Л	-	Ь	З	Т	-
-	У	К	Т	-	Я	А	Ь	-	С
Н	П	-	Ь	Е	У	-	Ш	Л	С
Т	И	Ь	З	Ы	Я	Е	М	-	О
-	Е	Ф	-	-	Р	О	-	С	М

Решение

Исходный текст состоит из 48 букв, следовательно, при зашифровании было использовано три положения решетки полностью и еще три буквы вписаны в четвертом положении. Значит, незаполненные 12 клеток совпадают с вырезами решетки в четвертом положении. Так как текст вписывается последовательно, то неизвестные нам три выреза могут располагаться только в первой строке таблицы и первых пяти клетках второй строки (до первого известного выреза). Считаем, что трафарет лежит в четвертом положении. Учитывая, что в одну клетку листа нельзя вписать две буквы, получаем, что вырезы могут быть только в отмеченных знаком "?" местах трафарета ("*" - места известных вырезов):

	?							?
		?	?		*				*
*				*				*
		*				*
								*
*		*	*				*

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

Гг

Задача 1.Решите уравнение:

Ответ

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

Решение

Во втором случае известны пары цифр, которыми шифруются буквы "р", "е", "м", "о", "н", "т", а в первом - пары цифр для тех же букв, за исключением буквы "н".

Задача 3.Из точки О внутри треугольника ABC на его стороны AB , BC , AC опущены перпендикуляры OP, OQ , OR . Докажите, что OA+OB+OC >= 2(OP+OQ+OR).

Решение.
Отсутвует

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

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

Решение

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

Рис 1

К	Е	Т	Р	И	Я
Л	Е	У	О	Д	О
И	Н	Д	Х	И	Е
Е	Ы	Е	З	Н	Ч
Е	Щ	В	Н	Я	С
-	-	-	-	-	-

Естественно предположить, что сообщение оканчивалось точкой. Поэтому на третьем с конца месте в первой группе должен быть столбец, оканчивающийся на Т, на втором - на Ч, на последнем - на К. Получаем два варианта (рис.2), из которых первый является явно "нечитаемым".

Рис 2

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

Задача 5. Комбинация (x,y,z) трех натуральных чисел, лежащих в диапазоне от 10 до 20 включительно, является отпирающей для кодового замка, если выполнено соотношение F(x,y,z)=99. Найдите все отпирающие комбинации для замка с

F(x,y,z)=3x²-y²-7z.

Решение

Найдите допустимые варианты для остатков от деления неизвестных x и y на 7. Таких вариантов будет восемь. Учитывая принадлежность неизвестных к заданному диапазону, найдите допустимые варианты для (x,y) (19 вариантов). Для каждой пары (x,y) найдите z.
1996-1997 гг

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

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

Решение

При a ≤ 0 рассматриваемое уравнение равносильно |x-a|-1995a=1996, которое имеет не более двух решений.

При a ≥ 0 из графика функции в левой части уравнения видно, что если 1996 ∈ (0, a), число решений будет четным, поэтому не может быть равно 1997. Если 1996 ∈ (a, + ∞), то уравнение имеет ровно 2 решения. Если же a=1996, то уравнение имеет ровно 1997 решений.

Задача 2. Докажите, что для каждого простого числа р последовательность a₁, a₂, a₃,... является периодической с периодом 2,

если a_n равно остатку от деления числа pⁿ⁺² на 24 при всех n ≥ 1.

Решение

Последовательность остатков от деления чисел a₁, a₂, ... на 24 - периодическая с периодом 2, так как для любого натурального n справедливо:

Кроме того, p³-p=(p-1)p(p+1) кратно 24, то есть остатки у a_n+2 и a_nравны.

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

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

Решение

Рассмотрим некоторую расстановку ненулевых цифр на окружности. Упорядоченную пару (a,b) соседних цифр на этой окружности назовем 1-соседней, если b является соседней с a по часовой стрелке. Пару (a,c) назовем 2-соседней, если существует цифра b, для которой пары (a,b) и (b,c) являются 1-соседними.

Каждой расстановке ненулевых цифр на окружности однозначно соответствует цепочка 1-соседних пар вида: (1,a₁), (a₁,a₂), (a₂,a₃), ..., (a₇,a₈), (a₈,1), которой, в свою очередь, однозначно соответствует цепочка 2-соседних пар вида:

(1,a₂), (a₂,a₄), (a₄,a₆),(a₆,a₈),(a₈,a₁)(a₁,a₃)(a₃,a₅)(a₅,a₇)(a₇,1),

(*)

где a₂,a₃,...,a₈ ∈ {2,...,9} и a_i ≠ a_j при i ≠ j.

Если из цепочки (*) удалить любую пару, то по оставшимся парам она восстанавливается однозначно.

Если из цепочки (*) удалить две соседние пары, то она также восстанавливается однозначно.

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

(a,b)(b,c)(c,d) и (a,c)(c,b)(b,d),		(a,b,c,d - различные цифры),

(a,b)_(c,d)(d,e) и (a,d)(d,b)_(c,e),		(a,b,c,d,e - различные цифры),

(a,b)_(c,d)_(e,f) и (a,d)(e,b)_(c,f),		(a,b,c,d,e,f - различные цифры)

Таким образом, при наличии двух указанных в условии задачи цифровых текстов нам будут известны некоторые 2-соседние пары, в которых первая цифра берется из первой криптограммы, а вторая - из второй. Поэтому с учетом вышесказанного получаем условие однозначного восстановления порядка расстановки цифр на данной окружности.

Задача 4.На каждой из трех осей установлено по одной вращающейся шестеренке и неподвижной стрелке. Шестеренки соединены последовательно. На первой шестеренке 33 зубца, на второй - 10, на третьей - 7. На каждом зубце первой шестеренки по часовой стрелке написано по одной букве русского языка в алфавитном порядке:А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

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

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

а) зашифруйте слово О Л И М П И А Д А;

б) расшифруйте сообщение 2 4 8 0 9 2 8 3 9 1 1 2 1 1.

Решение

а) Определим моменты остановок после начала шифрования. Для этого каждой букве русского алфавита припишем ее порядковый номер: А - 0, Б - 1, и т. д. Тогда буквам из шифруемого слова будут соответствовать номера: О - 15, Л - 12, И - 9, М - 13, П -16, А - 0, Д - 4. Моменты остановок будем указывать числом одношаговых (на один зубец) поворотов I колеса до соответствующей остановки.

остановки
Буква I колеса	О	Л	И	М	П	И	А	Д	А
Число одношаговых поворотов от начала до остановки
Цифра II колеса
Цифра III колеса

Искомый шифртекст: 515355128523864354

б) Пусть t_k - количество одношаговых поворотов I колеса от начала до остановки с номером k, k=1,2,...,

a_k - цифра, на которую указывает стрелка II колеса в момент остановки с номером k,

b_k - цифра III колеса, на которую указывает стрелка III колеса в момент остановки с номером k.

Тогда, учитывая, что начальное положение стрелок соответствует букве А на первом колесе и 0 на II и III колесах, справедливы равенства

t_k=10m_k-a_k, k=1,2,... t_k=7n_k+b_k, k=1,2,...

для подходящих неотрицательных целых чисел m_k и n_k.

Заметим, что 1=7·3-10·2. Отсюда справедливы равенства

a_k=7·(3a_k)-10·(2a_k), k=1,2,... b_k=7·(3b_k)-10·(2b_k), k=1,2,...

Подставляя эти значения в равенства предыдущие, получим

t_k=10(m_k+2a_k)-7(3a_k), k=1,2,... t_k=7(n_k+3b_k)-10(2b_k), k=1,2,...

Следовательно,

10(m_k+2a_k)-7(3a_k) = 7(n_k+3b_k)-10(2b_k), k=1,2,...

Правая и левая части делятся на 70, то есть имеют вид 70s_k для подходящего неотрицательного целого s_k. Поэтому

m_k=7s_k-2(a_k+b_k), k=1,2,... n_k=10s_k-3(a_k+b_k), k=1,2,...

Подставляя m_k, получим

t_k=70s_k-21a_k-20b_k, k=1,2,... .

Учитывая условие 0 < t₁ < t₂ < ... < t₇ и то, что остановка колеспроисходит в момент первого появления шифруемой буквы под стрелкой I колеса, имеем

k
a_k
b_k
-(21a_k+20b_k)	-122	-168	-229	-228	-209	-61	-41
t_k
Буквы	C	И	С	Т	Е	М	А

Задача 5.Текст

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

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

Решение

Пусть некоторая буква a при зашифровании первым способом заменялась на букву b. Тогда количество повторов буквы b в первой криптограмме будет равно числу повторов буквы a во второй криптограмме.

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

Решение

Покажем, что на диагонали присутствуют все числа от 1 до 1997. Пусть число a ∈ {1,...,1997} не стоит на диагонали. Тогда, в силу симметрии таблицы, число a встречается четное количество раз. С другой стороны, так как число a по одному разу встречается в каждой строке, всего в таблице чисел a нечетное количество (1997). Получили противоречие.

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒