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

Вначале для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 1 найдем соответствующий участок и. с. 2. Имеем:

C₂-C₁

T₁
T₂	T₂₁	T₂₂	T₂₃	T₂₄	T₂₅	T₂₆	T₂₇

Поэтому для участка и. с. 2 получаем следующие 15 вариантов:

T₂₁

T₂₂

T₂₃

T₂₄

T₂₅

T₂₆

T₂₇

Теперь для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 2 найдем соответствующий участок и. с. 1. Имеем:

C₁-C₂

T₂
T₁	T₁₁	T₁₂	T₁₃	T₁₄	T₁₅	T₁₆	T₁₇

Поэтому для участка и. с. 1 получаем следующие 15 вариантов:

T₁₁

T₁₂

T₁₃

T₁₄

T₁₅

T₁₆

T₁₇

Заменим порядковые номера в найденных вариантах участков и. с. 1 и и. с. 2 на буквы русского алфавита. Получаем следующие таблицы:

участок

и.с.2

участок

и.с.1

Из таблиц видно, что осмысленными являются варианты:

и.с.1

и.с.2

Гг

Задача 1.Равносторонний треугольник ABC разбит на четыре части так, как показано на рисунке, где M и N - середины сторон AB и BC соответственно. Известно, что РК^MQ и NL^MQ. В каком отношении точки Р и Q делят сторону AC, если известно, что из этих частей можно составить квадрат?

Решение

3.6. Обозначения понятны из рис. .
1) MK₁P₁B центрально симметричен MKPA относительно M.
2) NL₁Q₁B центрально симметричен NLQC относительно N.
3) P₁K₂Q₁=PKQ (параллельный перенос).
4) LK₁K₂L₁ - квадрат.
5) MT^AC , NS^AC .
6) PMT=QNS (MT=NS, PM=QN, РT=РS=90^°).
7) Без ограничения общности AB=BC=CA=1.

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

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

Решение

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

порядковый номер места k

шифрованное сообщение S_k

вариант 0 для Г_k

вариант 1 для G_k

вариант 2 для G_k

вариант 3 для G_k

По задаче 3.4 последовательность, из которой выбран шифрующий отрезок, является периодической с периодом 20. Из таблицы вариантов значений цифр шифрующего отрезка видим, что 5-я его цифра может быть равна 5, 6, 7 или 8, а его 25-я цифра - 2, 3, 4 или 5. Отсюда получаем, что G₅ = G₂₅ = 5. На периоде последовательности, из которой выбран шифрующий отрезок, есть две цифры 5: C₅ и C₁₅. Поэтому рассмотрим два случая. Если G₅ = C₅, тоG₇=C₇=3. Это противоречит таблице вариантов значений цифр шифрующего отрезка, в которой G₇ может быть равна 4, 5, 6 или 7. Если же G₅ = C₁₅, то соответствующий шифрующий отрезок: 1636567490147656369016365674 хорошо согласуется с таблицей вариантов значений его цифр.

Задача 3. Дана последовательность чисел C₁, C₂, ..., C_n, ... в которой C_n есть последняя цифра числа nⁿ. Докажите, что эта последовательность периодическая и ее наименьший период равен 20.

Решение

Докажем, что 20 является периодом рассматриваемой последовательности. Заметим, что у двух натуральных чисел а и b совпадают цифры единиц тогда и только тогда, когда их разность делится на 10. Таким образом, мы достигнем цели, если докажем, что разность (n+20)ⁿ⁺²⁰-nⁿ делится на 10 для всех натуральных значений n. Исходя из того, что p^k-q^k делится на (p-q), получаем, что (n+20)ⁿ⁺²⁰-nⁿ⁺²⁰ делится на ((n+20)-20)=20. Кроме того, nⁿ⁺²⁰-nⁿ=nⁿ(n²⁰-1)=nⁿ((n⁴)⁵-1) делится на n(n⁴-1) для всех n > 1. Вместе с тем, n(n⁴-1)=n(n-1)(n+1)(n²+1)=n(n-1)((n+2)(n-2)+5)=(n-2)(n-1)n(n+1)(n+2)+5(n-1)n(n+1), где каждое из слагаемых делится на 2 (так как содержит произведение n(n+1)) и делится на 5 (поскольку первое слагаемое есть произведение пяти последовательных чисел, а второе содержит множитель 5). Следовательно, nⁿ⁺²⁰-nⁿ делится на 10. Число

(n+20)ⁿ⁺²⁰-nⁿ=((n+20)ⁿ⁺²⁰-nⁿ⁺²⁰)+(nⁿ⁺²⁰-nⁿ)

делится на 10, так как каждое из слагаемых делится на 10.

Проверим, что 20 является наименьшим периодом. Выписывая первые 20 значений последовательности C₁, C₂, ...

1 4 7 6 5 3 6 9 0 1 6 3 6 5 6 7 4 9 0

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

С	О	-	Г	Ж	Т	П	Н	Б	Л	Ж	О
Р	С	Т	К	Д	К	С	П	Х	Е	У	Б
-	Е	-	П	Ф	П	У	Б	-	Ю	О	Б
С	П	-	Е	О	К	Ж	У	У	Л	Ж	Л
С	М	Ц	Х	Б	Э	К	Г	О	Щ	П	Ы
У	Л	К	Л	-	И	К	Н	Т	Л	Ж	Г

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

Решение

Если символы одного отрезка занумеровать последовательно числами от 1 до 12, то после передачи его из А в Б символы расположатся в порядке (2,4,6,8,10,12,1,3,5,7,9,11), а после передачи этого отрезка (замена символов не меняет порядка) из Б в В - в порядке (4,8,12,3,7,11,2,6,10,1,5,9). Переставим символы перехваченных отрезков в соответствии с их номерами до передачи из пункта А. Получим отрезки вида:

Л	П	Г	С	Ж	Н	Ж	О	О	Б	Т	-
Е	С	К	Р	У	П	Д	С	Б	Х	К	Т
Ю	У	П	-	О	Б	Ф	Е	Б	-	П	-
Л	Ж	Е	С	Ж	У	О	П	Л	У	К	-
Щ	К	Х	С	П	Г	Б	М	Ы	О	Э	Ц
Л	К	Л	У	Ж	Н	-	Л	Г	Т	И	К

Поскольку в пунктах А и Б одинаковые буквы заменялись одинаковыми, а разные - разными, то найденные отрезки можно рассматривать как замену одинаковых символов исходного текста одинаковыми, а разных - разными. Сравнивая места одинаковых букв слова КРИПТОГРАФИЯ и места одинаковых символов в отрезках, находим, что слово КРИПТОГРАФИЯ зашифровано во втором отрезке. Это дает возможность найти исходное сообщение, используя гипотезы о частых буквах русского языка и смысле исходного сообщения.

Задача 5.Шифрпреобразование простой замены в алфавите A={a₁,a₂,......,a_n}, состоящем из n различных букв, заключается в замене каждой буквы шифруемого текста буквой того же алфавита, причем разные буквы заменяются разными. Ключом шифра простой замены называется таблица, в которой указано, какой буквой надо заменить каждую букву алфавита A. Если слово СРОЧНО зашифровать простой заменой с помощью ключа:

то получится слово ВЗДАБД. Зашифровав полученное слово с помощью того же ключа еще раз, получим слово ЮШЫЧЯЫ. Сколько всего различных слов можно получить, если указанный процесс шифрования продолжать неограниченно?

Решение

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

Так как буква С повторяется в каждом цикле шифрования, номер которого кратен 5, а буквы Р, О, Ч, Н - в каждом цикле, номера которых кратны 13, 7, 2 и 3 соответственно, то слово СРОЧНО появится впервые в цикле с номером, равным НОК(2,3,5,7,13)= 2·3·5·7·13 = 2730.
Задача 6.Установите, можно ли создать проводную телефонную сеть связи, состоящую из 993 абонентов, каждый из которых был бы связан ровно с 99 другими.

Решение

Если каждый из 993 абонентов связан с 99 абонентами, то для этого потребуется 993·99/2 линий связи, которое не может быть целым числом.

1994-1995 гг
Задача 1.Чтобы запомнить периодически меняющийся пароль в ЭВМ, математики придумали следующий способ. При известном числе a (например, номере месяца в году), пароль представляет собой первые шесть цифр наименьшего решения уравнения

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

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

Решение

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

ГЪЙ АЭЁ БПРК ЕЖЩЮ НМЬЧ СЫЛЗ ШДУ ЦХОТ ЯФВИ

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

Решение

Составим возможные варианты переданных букв:

ГЪЙ	АЭЁ	БПРК	ЕЖЩЮ	НМЬЧ	СЫЗЛ	ШДУ	ЦХОТ	ЯФВИ
БШЗ	АЫВ	АНОИ	ГЕЧЬ	ЛКЪХ	ПЩЕЙ	ЦВС	ФУМР	ЭТАЖ
ВЩИ	БЬЕ	БОПЙ	ДËШЭ	МЛЫЦ	РЪЖК	ЧГТ	ХФНС	ЮУБЗ
ГЪЙ	ВЭË	ВПРК	ЕЖЩЮ	НМЬЧ	СЬЗЛ	ШДУ	ЦХОТ	ЯФВИ
ДЫК	ЮЖ	ГРСЛ	Ë ЗЪЯ	ОНЭШ	ТЬИМ	ЩЕФ	ЧЦПУ	ХГЙ
ЕЬЛ	ЯЗ	СТМ	ЖИЫ	ПОЮЩ	УЭЙН	ЪЁХ	ШЧРФ	ЦДК

Выбирая вторую и последнюю группу букв (где есть короткие колонки букв), определяем слова, им соответствующие: ВЯЗ, ЭТАЖ. В исходных словах 33 буквы, поэтому буквы В, Я, З, Э, Т, А, Ж уже использованы и их можно вычеркнуть из всех колонок:

ГЪЙ	АЭЁ	БПРК	ЕЖЩЮ	НМЬЧ	СЫЗЛ	ШДУ	ЦХОТ	ЯФВИ
БШ		НОИ	ГЕЧЬ	ЛКЪХ	ПЩЕЙ	Ц С	ФУМР	ЭТАЖ
ЩИ		БОПЙ	ДËШ	МЛЫЦ	РЪ К	ЧГ	ХФНС
ГЪЙ	В	ПРК	Е Щ	НМЬЧ	СЬ Л	ШДУ	ЦХО
		ГРСЛ	Ë Ъ	ОН	ЬИМ	ЩЕФ	ЧЦПУ
ЕЬЛ	ЯЗ	С М	ИЫ	ПО	У ЙН	ЪËХ	ШЧРФ

Из нескольких вариантов, например, в третьей группе:

ГНОЙ ГНОМ ГРОМ

выбираем варианты так, чтобы каждая буква использовалась один раз. Продолжая таким образом, получим ответ.
Задача 3.Зашифрование фразы на латинском языке осуществлено в два этапа. На первом этапе каждая буква текста заменяется на следующую в алфавитном порядке (последняя 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.

Решение

Занумеруем буквы латинского алфавита последовательно числами от 1 до 24. Пусть x - некоторое число от 1 до 24, а f(x) - число, в которое переходит x на втором этапе. Тогда перестановочность этапов можно записать в следующем виде:

f(x+1) = f(x) + 1, т. е. f(x+1) - f(x) = 1.

Это означает, что соседние числа x и x+1 на втором этапе переходят в соседние же числа f(x) и f(x+1), т. е. второй этап - тоже сдвиг. Последовательное применение двух сдвигов - очевидно тоже сдвиг и остается рассмотреть 24 варианта различных сдвигов. Читаемый текст определяется однозначно. Осложнения, связанные с переходом Z в A, устраняются либо переходом к остаткам при делении на 24, либо выписыванием после буквы Z второй раз алфавита AB... Z.
Задача 4."Шифровальный диск" используется для зашифрования числовых сообщений. Он состоит из неподвижного диска и вращающегося на нем диска меньшего диаметра. На обоих дисках нанесены цифры от 0 до 9, которые расположены в вершинах правильных 10-угольников, вписанных в диски.

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