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

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

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

если неизвестно, каким из указанных способов получена каждая из них. Также известно, что последовательность ШВМВРЖЭЭСВХБКЗНДЭЬ получена из названия произведения и фамилии автора той же заменой букв, которая использовалась при преобразовании исходного фрагмента.

Решение

Подсчитаем число появлений каждой из букв в шифртекстах. Первый текст: Б, Г,П, Р, Ы, Ю - 1 раз; А, Д, З, М, Т, Ч - 2 раза; Л - 3 раза; Н, С - 4 раза; Е, И - 6 раз; В - 7 раз; О - 12 раз. Второй текст: Г, И, К, С, Т, Ч - 1 раз; А, Б, Е, У, Х, Я - 2 раза; М - 3 раза; Ш, Ь - 4 раза; Ж, Э - 6 раз; Р - 7 раз; В - 12 раз. Если текст получен перестановкой букв, то частоты встречаемости букв в нем должны быть характерны для текстов на русском языке. Во втором тексте отсутствует букваО, одна из самых частых букв. Поэтому можем сделать вывод, что первый текст получен перестановкой, а второй - заменой букв в исходном тексте.

При использовании шифра замены число вхождений буквы в исходный текст совпадает с числом вхождений заменяющей ее буквы в шифрованный текст. Поэтому заключаем, что буква О заменялась на В, В - на Р, Л - на М. Кроме того, буквы Е и И заменялись на Ж и Э либо на Э и Ж, Н и С - на Ш и Ь либо на Ь и Ш.

Первая буква второго текста - Р; ей должна соответствовать буква В первого текста. Поэтому длина участков, на которые разбивался исходный текст при шифровании перестановкой не менее пяти. Тогда в первый участок первого текста войдет буква О, которой должна соответствовать буква В во втором тексте, поэтому длина участков не менее 6. Предположив, что длина участков равна 6 получаем что внутри участка буквы переставлялись по схеме 1234546-546213, что приводит к осмысленному варианту восстановления исходного текста: В БЕЗМОЛВИИ САДОВ ВЕСНОЙ ВО МГЛЕ НОЧЕЙ ПОЕТ НАД РОЗОЮ ВОСТОЧНЫЙ СОЛОВЕЙ.

В названии произведения и фамилии автора стали известными почти все буквы:СОЛОВЕЙИРОЗАП???ИН. Знаками вопроса обозначены буквы, которые не встретились в исходном тексте. По смыслу легко догадаться, что автор -ПУШКИН.

Задача 4.Известно, что число вхождений некоторого символа в текст составляет от 10,5 % до 11 % длины текста. Найдите минимально возможную длину текста.

Решение

Пусть длина текста равна L. Пусть символ встречается в тексте x раз. Задачу можно переформулировать так: найти наименьшее натуральное число L, для которого существует такое натуральное число x, что

10,5

x L

При решении задачи некоторые участники руководствовались, вообще говоря, ошибочным утверждением, что чем меньше x, тем меньше соответствующее L. Однако при малых x это действительно так. При x=1 не существует удовлетворяющего неравенству натурального L. При x=2 находим L=19. Из неравенства L і 100x/11 заключаем, что L > 19 при x і 3.

Гг

Задача 1.Для зашифрования сообщения используют последовательность неотрицательных целых чисел x₁, x₂,…, удовлетворяющую соотношению x_k₊₃=x_k+x_k₊₂, k=1,2,… Две строки известного стихотворения, последние 5 букв которых совпадают, зашифровали следующим образом. Первую букву заменили числом согласно таблице

и сложили с x₁, вторую заменили и сложили с x₂ и т.д. Затем все суммы заменили остатками от деления на 31, а остатки заменили буквами согласно таблице. Получили текст

СЕЗНПБКЬЛЧЕЮЩЦТНИЭЛЬЩБШЬЕЮ
ЛУАЕЧЖЪЭШЭЛЪШЩХЧШДЮВЫЮИД.

Восстановите три буквы, соответствующие в таблице числам x₁,x₂,x₃, и прочитайте двустишие.

Решение

Обозначим a = x₁, b = x₂, c = x₃. Так как эти числа соответствуют буквам в таблице, они принимают значения от 0 до 30. Из соотношения

x_k₊₃ = x_k + x_k₊₂

последовательно получим

x₁ = a ,

x₂ = b ,

x₃ = c,

x₄ = a + c,

x₅ = a + b + c,

x₆ = a + b+ 2c,

x₇ = 2a + b+ 3c,

x₈ = 3a + 2b+ 4c,

x₉ = 4a + 3b+ 6c,

x₁₀= 6a + 4b+ 9c,

и т.д.

При дальнейшем построении этой последовательности используем следующие правила.

1. Для построения следующей строки последнюю строку складываем с предпредпоследней.

2. Легко заметить, что столбцы чисел отличаются сдвигом по вертикали, поэтому сначала можно определить только коэффициенты при c.

3. Так как нас интересуют только остатки от деления на 31, то, например, 41c = 31c + 10c можно заменить на 10c.

Продолжая аналогично, получим

x₁₁ = 13,

x₁₂ = 19,

x₁₃ = 28,

x₁₄ = 10,

x₁₅ = 29,

x₁₆ = 26,

x₁₇ = 5,

x₁₈ = 3,

x₁₉ = 29,

x₂₀= 3,

x₂₁ = 6,

x₂₂ = 6a + 3b+ 4c,

x₂₃ = 7a + 4b+ 13c,

x₂₅ = 13a + 7b+ 17c,

x₂₆= 17a + 13b+ 24c,

x₂₆= 6a + 4b+ 9c,

Используя сдвиги столбцов, получили значения x₂₂, x₂₃, x₂₄, x₂₅, x₂₆. Продолжая аналогично, получим последние пять значений x₄₆, x₄₇, x₄₈, x₄₉,x₅₀:

x₂₇ = 6,

x₂₈ = 23,

x₂₉ = 16,

x₃₀ = 22,

x₃₁ = 14,

x₃₂ = 30,

x₃₃ = 21,

x₃₄ = 4,

x₃₅ = 3,

x₃₆= 24,

x₃₇ = 28,

x₃₈ = 0,

x₃₉ = 24,

x₄₀= 21,

x₄₁ = 21,

x₄₂ = 14,

x₄₃ = 4,

x₄₄= 25,

x₄₅ = 8,

x₄₆ = 8a + 25b+ 12c,

x₄₇ = 12a + 8b+ 6c,

x₄₈ = 6a + 12b+ 14c,

x₄₉= 14a + 6b+ 26c,

x₅₀= 26a + 14b+ 1c.

Итак, получено выражение чисел x₂₂, x₂₃, x₂₄, x₂₅, x₂₆ и чисел x₄₆, x₄₇, x₄₈,x₄₉, x₅₀ через a, b, c. Обозначим через О_i, Ш_i числа, соответствующие i-м буквам стихотворения и полученного шифрованного текста. Тогда числа О₂₂+x₂₂ и Ш₂₂ имеют одинаковые остатки от деления на 31. То же самое и с числами О₄₆+x₄₆ и Ш₄₆.

А так как числа О₂₂ и О₄₆ одинаковые, рассмотрев разности соответствующих частей, получим, что

x₄₆ - x₂₂ и Ш₄₆ - Ш₂₂ (*)

дают одинаковые остатки от деления на 31.

Последним пяти буквам первой строки шифрованного текста соответствуют следующие числа Ш_i:

Б, Ш, Ь, Е, Ю — 1, 23, 27, 5, 29,

а последним буквам второй строки — следующие:

В, Ы, Ю, И, Д — 2, 26, 29, 8, 4.

Подставляя эти значения в (*) и выражая x_i через a, b, c, получаем систему

	2a − 9b + 8c = 1,
8a + 2b − c = 3,
−a + 8b + c = 2,
a − b + 9c = 3,
9a + b + 8c = 6,

где равенство означает равенство остатков от деления на 31. При этом использовали правило 3. Например, в первом уравнении +22b заменили на −9b. Осталось решить полученную систему. Складывая второе и третье, четвертое и пятое, третье и четвертое уравнения, получим

	7a + 10b = 5,	(**)
10a + 17c = 9,
7b + 10c = 5.

Выразим b и c через a и подставим в первое уравнение:

b = (5 − 7a)/10, c = (9 − 10a)/17,

2a − 9((5 − 7a)/10) + 8((9 − 10a)/17) = 1,

340a − 9·17(5 − 7a) + 80(9 − 10a) = 170,

611a = 215,

22a = 29.

Последнее уравнение можно решить методом подбора и обнаружить, что 22 ·14 и 29 дают одинаковые остатки от деления на 31. Итак,

a=14.

Из системы (**) находим, что 10b = 0 и 10с = 5, откуда

b=0,
c=16.

Зная a, b, c, можно последовательно найти все x_i и из соотношения O_i=Ш_i-x_iполучить стихотворение:

ВЕЧОРТЫПОМНИШЬВЬЮГАЗЛИЛАСЬ
НАМУТНОМНЕБЕМГЛАНОСИЛАСЬ

Задача 2. Какое наименьшее количество натуральных чисел надо взять, чтобы любое число от 1 до 300 можно было представить в виде суммы подходящего набора различных указанных натуральных чисел.
Решение

При решении этой задачи участники широко использовали двоичное представление чисел. Например, 105=1101001. Известно, что в двоичном представлении степеней двойки присутствует лишь одна единица: 2⁰=1, 2¹=10, 2²=100, ..., 2⁸=100000000. Видим, что в двоичной записи числа 105 единицы стоят в 1-й, 4-й, 6-й и 7-й позициях (считаем слева направо). Значит, 105=2⁰+2³+2⁵+2⁶. Поскольку двоичное число 111111111 (девять единиц) равно 511 > 300, заключаем, что девяти чисел 1, 2, 4, 8, 16, 32, 64, 128, 256 вполне достаточно для представления любого натурального числа от 1 до 300 (и даже до 511).

Отметим, что использование двоичной системы записи не является ключевым при решении этой задачи. Например, участниками были предложены следующие девять чисел: 1, 2, 3, 7, 14, 28, 56, 112, 224.

Лишь в очень немногих работах присутствовало доказательство того, что искомый набор не может содержать менее девяти чисел. Действительно, пусть у нас есть восемь чисел и любое число от 1 до 300 представимо в виде суммы разных чисел из этого набора. Используя наш набор, мы можем закодироватьлюбое число от 1 до 300: пусть, например, число a равно сумме первого и третьего чисел нашего набора, тогда будем писать a=(1,0,1,0,0,0,0,0). Итак, число а получило свой код - строку из восьми символов, каждый символ или 0, или 1. Но нам надо закодировать триста чисел, а строк длины 8, как нетрудно видеть, всего 256. Значит, восьми чисел недостаточно.

Здача 3.Формулировка некоторого геометрического утверждения была вписана в клетки таблицы 10×10 построчно слева направо, начиная с верхней левой клетки. Знак переноса на следующую строку не ставился, но между соседними словами одной строки помещалась пустая клетка. Криптоша решил переставлять буквы в отдельных столбцах, сдвигая их все на одну позицию вверх и перенося самую верхнюю букву вниз (при этом пустую клетку он также считал буквой). Иногда он менял местами сразу все строки, симметричные относительно средней линии, а именно 1-ю с 10-й, 2-ю с 9-й - и т.д., после чего снова брался за передвижение букв в столбцах. В результате таблица приняла представленный на рисунке вид. Прочитайте исходное геометрическое утверждение.

а	л	п	н	в	и		в	т	р
е	о	с	н	л	я		о	л	т
п		я	л	ы	е	о	ы	т	у
е	о	а	о	щ	д	р	р	а	е
н	р	у	и		о	н	с	т	в
п	к	и	м	е	ь		р
е	в	о	ю	т	х	х	н	а	с
д	с	е	х	и	и	е	о	я
о	к	ь	т	ы	п	ь	п	е	н
с	ж	с	с	е	л		о	о	о

Решение

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

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

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

Решение

Цифры пароля будем подбирать последовательно. Свяжемся с банком и наберем цифру 0. Если связь не оборвалась, то первая цифра пароля - 0. Если связь прервана, то первая цифра отлична от 0 и, связываясь заново с банком, пробуем набрать 1, и т.д. Не позднее чем через девять звонков мы будем точно знать, какая цифра стоит на первом месте в пароле, и сможем перейти к подбору второй цифры и т.д.

Общее количество звонков, которое понадобится для выяснения пароля, не более 7·9=63. Еще один звонок может понадобиться для получения доступа после полного выяснения пароля.

Заметим, что если бы решение о доступе или отказе принималось только после ввода всего пароля, то система защиты была бы гораздо надежнее - последовательный подбор был бы невозможен и потенциально пришлось бы перебирать все 10⁷ вариантов пароля.

Задача 5.Шифр Bifid, имеющий простое правило зашифрования, использует в качестве ключа квадратную таблицу, в которую в некотором порядке записаны буквы английского алфавита (буквы I и J отождествлены). Результатом зашифрования фразы SIXTY EIGHT MILES на приведенном ключе является «фраза» RYXXT OFTXT LKSWS. Зашифруйте на том же ключе фразу ENTER OTHER LEVEL.

C	O	D	E	A
B	F	G	H	I
K	L	M	N	P
Q	R	S	T	U
V	W	X	Y	Z

Решение

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


C	O	D	E	A
B	F	G	H	I
K	L	M	N	P
Q	R	S	T	U
V	W	X	Y	Z

Правило зашифрования шифра Bifid состоит в следующем. Строки и столбцы квадратной таблицы пронумеруем числами от 1 до 5, как показано на рисунке. Теперь каждая буква алфавита имеет свой номер, состоящий из пары чисел , где i - номер строки, а j - номер столбца. Например, буква S имеет номер . Выпишем буквы открытого текста в строку, разделяя пробелом каждую пятерку букв, а под ней - номера соответствующих букв. Фраза, взятая из условия задачи, запишется в виде

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

E	I	G	H	T


O	F	T	X	T

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

Зашифруем на том же ключе фразу ENTER OTHER LEVEL, заполнив следующую таблицу:

Задача 6.Пользователи сети связи для обеспечения секретности сообщений выбирают (независимо друг от друга) пары преобразований (E,D), одно из которых, E (открытый ключ), публикуют в справочнике, а второе, D (личный ключ), держат в секрете. Известно, что значения E(m) иD(n) легко вычислить для любых сообщений m и n, причем из равенства E(m)=n следует, что D(n)=m. В то же время нахождение m по E(m) является сложной задачей, которую невозможно решить (любыми средствами) за реальное время, если неизвестно D. Если пользователь A хочет послать пользователю B сообщение m, он берет из справочника открытый ключ E_B пользователя B, вычисляет n=E_B(m) и посылает n к B. Получив n, Bвычисляет D_B(n)=m. Злоумышленник, перехвативший n, не сможет вычислить m. Это гарантирует секретность информации.

Ватсон предложил Холмсу способ передачи секретных сообщений с уведомлением о получении: A передает B сообщение (A,E_B(m)); B, получив сообщение, вычисляет m и направляет A уведомление (B,E_A(m)). Холмс возразил Ватсону, что этот способ не обеспечивает секретности информации от любого пользователя, который может перехватывать сообщения и как угодно их изменять. Дополнительно потребовав, чтобы для каждого преобразования E было сложно подобрать пару (m,n), для которой E(m)=E(n), Холмс предложил Ватсону свой способ: A передает B сообщение E_B(A,m); B, получив сообщение, находит m и направляет A уведомление E_A(B,m). Объясните, почему способ Холмса лучше способа Ватсона.

Решение

Недостаток способа Ватсона состоит в том, что, перехватив сообщение (A,E_B(m)), злоумышленник C может заменить его на (C,E_B (m)), получив которое, Bвоспринимает его как первый шаг протокола передачи с уведомлением от C. Вычислив m, B затем уведомляет C о получении, посылая ему сообщение (B,E_C(m)). Из него C извлекает искомое m и от имени B уведомляет A о получении, посылая ему сообщение (B,E_A(m)).

Способ Холмса не позволяет злоумышленнику получить секретное сообщениеm. В самом деле, получить его C может либо из перехваченных сообщенийE_B(A,m), E_B(B,m), либо из направленного к нему сообщения E_C(B,m). По E_B(A,m) и E_B(B,m) злоумышленнику невозможно найти m, поскольку для этого ему нужно решить сложную задачу обращения E_A или E_B. Исключая возможность сговора между B и C, считаем, что B « добровольно» не пошлет к C сообщение E_C(B,m). Значит, такое сообщение попадет к C от B лишь в качестве уведомления о получении им сообщения E_B(C,m). Такое сообщение к B может попасть лишь отC, который заменяет E_B(A,m) на сообщение E_B(C,m). По условию этого C также сделать не в состоянии.

Гг

Задача 1.Имеется клетчатая бумага неограниченных размеров со стороной клетки, равной 1. Шаблоном размера k называется всякая плоская фигура, составленная путем соединения концами друг с другом k параллельных или перпендикулярных отрезков длины 1. Если существует отрезок длины 0,5, полностью размещаемый на шаблоне, то точки шаблона, общие с точками между концами этого отрезка, называются внутренними.

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒