 |
|
C r y p t o g r a p h i c a l g o r i t h m 7 страница
Найдите все шаблоны, которыми можно покрыть все линии клетчатой бумаги (шаблоны можно поворачивать и переворачивать). При покрытии разрешается использовать шаблоны одного вида, причем никакие два шаблона не могут иметь общих внутренних точек.
а) k=2;
б) k=3.
Решение
Сначала выясним, какие вообще могут быть шаблоны. Очевидно, что при k = 2 имеется 2 вида шаблонов:
При k=3 имеется 5 видов шаблонов:
Оказывается, все линии клетчатой бумаги можно покрыть любым из перечисленных выше шаблонов, кроме шаблона вида
Докажем последнее. Пусть требуемое покрытие существует. Рассмотрим одно наложение такого шаблона на клетчатую бумагу. Из условия задачи и расположения первого шаблона следует, что пунктирные линии должны быть покрыты двумя другими шаблонами, но тогда волнистые линии без наложения внутренних точек шаблонов покрыть нельзя. Решение для остальных шаблонов показано ниже:
Задача 2.Для зашифрования текста v1v2...vk на русском языке каждую его букву vi заменили числомti согласно таблице
|
К каждому числу ti последовательности t1,t2,…,tk прибавили число ai последовательностиa1,a2,…,ak, заданной соотношениями a1=1, an+1=3an+4 при n > 0. Затем остаток от деления каждой суммы ti+ai на 33 вновь заменили буквой по той же таблице. При переписывании зашифрованного текста несколько букв были пропущены. В результате получилось вот что:
Р Ч Ж Ь Э Т С Ъ Й Л Ж Ъ Я О Ш К С
Найдите исходный текст.
Решение
Заменяя каждый член последовательности a1=1, an+1=3an+4 остатком от его деления на 33, получим периодическую последовательность. Вот несколько первых членов этой последовательности:
1, 7, 25, 13, 10, 1, 7, 25, 13, 10, 1, 7, 25, 13,...
Так как каждый член этой последовательности остатков однозначно находится из предыдущего, заключаем, что ее период равен пяти.
Будем вычитать из чисел, соответствующих буквам зашифрованного текста, числа этой периодической последовательности, а результаты заменять буквами согласно данной в условии задачи таблице:
| Р | Ч | Ж | Ь | Э | Т | С | Ъ | Й | Л | ... |
| ... | ||||||||||
| ... | ||||||||||
| ... | ||||||||||
| П | Р | О | П | У | С | К | В | Э | В | ... |
После слова ПРОПУСК идет нечитаемый текст. Значит, или непосредственно после этого слова, или после буквы В пропущены буквы. (Перебор различных вариантов тривиален и поэтому здесь не приводится.) Сдвигая нашу периодическую последовательность относительно зашифрованного текста, находим такой вариант:
| Р | Ч | Ж | Ь | Э | Т | С | Ъ | Й | А | Ж | Ъ | Я | О | Ш | К | С | |
| П | Р | О | П | У | С | К | Н | А | К | А | В | Т | Е | Ч | Д | Щ |
Естественно предположить, что на месте пропущенного знака в исходном тексте находилась буква З. Действуя далее аналогично, восстанавливаем весь текст.
Задача 3.Разложите на простые множители 222+39·210+81.
Решение
Обозначим 210=x. Тогда исходное число имеет вид 4x2+39x+81. Корни этого трехчлена равны −3 и −27/4. Значит, 4x2+39x+81 = 4(x+3)(x+27/4). Далее, (210+3)(212+27)=1027·4123=13 ·79·7·19·31.
Задача 4.На фирме работают P служащих. В гараже фирмы имеется B автомобилей. Каждый служащий имеет ключи от t автомобилей, причем ключи от разных автомобилей разные. (Будем говорить, что каждый служащий «владеет» i автомобилями.) Каждой машиной «владеют» ровно s служащих. При этом наборы ключей любых двух служащих содержат не более одного одинакового ключа. Известно также, что если служащий x не «владеет» автомобилем L, то из всех владельцев автомобиля L только у одного есть в наборе такой же ключ, как у служащего x.
Выразите числа P, B, а также общее количество ключей, имеющихся у служащих, через s иt. Числа s и t целые, большие 1.
Решение
Сопоставим каждому служащему «точку», а каждому автомобилю - «линию». Если p - служащий, владеющий автомобилем L, то будем говорить, что точкаp инцидентна линии L, а линия L инцидентна точке p. При этом пару (L,р) назовем «флагом». Условия задачи можно сформулировать в следующем виде:
1. для каждой точки p имеется ровно t флагов вида
(L1,p), (L2,p), ј, (Lt,p);
2. для каждой линии L имеется ровно s флагов вида
(L,p1), (L,p2), ј, (L,ps);
3. если точка x не инцидентна линии L, то имеются ровно одна такая линия M и одна такая точка y, что (L, y), (М,x) и (M,y) - флаги.
Изобразим условия 1-3 графически:
1. («пучок линий с центром в точке p»)
2. (точки «располагаются на линии L»)
3. («треугольники» (с точкой z) исключаются)
Вычисляя число F флагов двумя способами, получаем, согласно условиям 2 и 3, равенство F = P·t = B·s. Из условия 3 следует, что все точки располагаются на линиях пучков, центрами которых служат точки любой линии, например L. Отсюда (с учетом условий 1 и 2) следует, что число точек, не лежащих на линии L, равно t·(s-1)·5. Добавляя к этому число точек линии L, получаем общее число точек:
P = t·(s−1)·s+s = s·(t·(s−1)+1).
Теперь находим число линий:
|
Наконец, число флагов равно
F = t·s(t·(s−1)+1).
Задача 5.Кодовая комбинация сейфа устанавливается на внутренней стороне дверцы с помощью трех дисков. Каждый из них может быть установлен в одно из 20 положений, пронумерованных числами от 0 до 19, поворотом по часовой стрелке. В начальный момент диски установлены в положение (0, 0, 0). За положение с номером 19 диск не поворачивается. При повороте каждого диска на одно положение раздается щелчок. Сравните число возможных кодовых комбинаций, при установке которых раздается 33, 32, 25 щелчков.
Решение
Пусть MN - число различных комбинаций, при установке которых раздается N(N Ј 57) щелчков.
Заметим, что из соображений симметрии MN = M57−N. Для обоснования этого равенства достаточно установить взаимно однозначное соответствие между комбинациями, получаемыми за N и за 57−N поворотов. Это можно, например, сделать так: сопоставим комбинации (n1,n2,n3), где n1+n2+n3=N, комбинацию (19−n1,19−n2,19−n3), получаемую за 19−n1+19−n2+19−n3=57−(n1+n2+n3)=57−>N щелчков. Отсюда заключаем, что число комбинаций, при установке которых раздается 32 и 25 щелчков, одинаково (M32=M25).
Из предыдущего рассуждения также следует, что М24=М33. Поэтому для завершения решения достаточно сравнить числа М24 и M25.
Комбинацию будем называть насыщенной, если один из дисков установлен в положение 19; остальные комбинации считаем ненасыщенными. Кроме того, будем отдельно рассматривать комбинации, в которых один из дисков установлен в положение 0.
Все комбинации, устанавливаемые за 24 щелчка, разделим на четыре группы: насыщенные и содержащие нуль, насыщенные без нуля, ненасыщенные с нулем, ненасыщенные без нуля. Легко подсчитать, что в первую группу входит 6 комбинаций (всевозможные перестановки чисел 19, 5 и 0), во вторую - 3·4=12 (три варианта места для числа 19; для каждого из них по четыре варианта значения первой незаполненной позиции, после чего оставшееся число находится однозначно), а в третью - 3·13 = 39 (три варианта выбора места для 0; для каждого из них возможно 13 вариантов выбора значения первой незаполненной позиции числами от 6 до 18). Число комбинаций в четвертой группе находить не будем, а просто обозначим его через X.
Мысленно выпишем все комбинации, получаемые за 24 щелчка, в один столбец, а получаемые за 25 щелчков - в другой. Если какая-либо комбинация первого столбца с помощью еще одного щелчка может быть преобразована в комбинацию второго столбца, то соединим их стрелкой. Проведем все такие стрелки. Из каждой комбинации первой группы выходит ровно две стрелки. Шесть из них ведут к комбинациям, содержащим 0, а шесть - к не содержащим 0. Каждую комбинацию второй группы также можно продолжить двумя способами, и все получаемые стрелки (их 24) ведут к комбинациям, не содержащим 0. Каждая комбинация третьей группы продолжается тремя способами, всего при этом получится 39·2 стрелок к комбинациям с нулем и 39 - к комбинациям без нуля. Комбинации последней группы можно продолжить также тремя способами. При этом получится 3X стрелок, все ведут к комбинациям, не содержащим 0.
Всего получим 6+39·2 = 84 стрелки, ведущие к комбинациям с нулем, и 6+24+39+3X - без нуля.
С другой стороны, к каждой комбинации, получаемой за 25 щелчков и не содержащей 0, ведет ровно три стрелки, а к комбинациям, содержащим 0, - ровно по две. Таким образом, число различных комбинаций, получаемых за 25 щелчков, составит 42+23+X=65+X, что на 8 больше, чем 6+12+39+X=57+X - число различных комбинаций, получаемых за 24 щелчка.
Задача 6.Числа, расположенные в клетках таблицы, указывают, сколько соседних по горизонтали, вертикали и диагонали клеток (включая ту, в которой находится само число) должны быть окрашены. Восстановите картинку, которой соответствуют эти числа.
Ответ
Гг
Задача 1.Для всех p ∈ (0;1) найдите минимальное значение выражения (x1 + x2) ·p + x3 ·(1−p) при условии, что
1) 0 < x1 < 1; 0 < x2 < 1; 0 < x3 < 1,
2) x1+x2+x3=1,
3) x1 ≤ x2; x3 ≤ x2; x2·(1−p) ≤ x1 ·p.
Решение
Предварим решение этой задачи небольшим отступлением о кодах аутентификации, поясняющим происхождение ее формулировки.
При передаче информации по незащищенному (общедоступному) каналу связи возникает задача защиты от активных атак со стороны злоумышленника. Под активными атаками понимают попытки фальсификации (имитации) и модификации (подмены) сообщения.
Цель активных атак - дезинформация получателя. Не вдаваясь в детали, сообщим, что сегодня имеется техническая возможность проведения подобных атак.
Для противодействия активным атакам используются так называемые коды аутентификации (кратко - A-коды). Они дают возможность получателю сообщения проверить его подлинность (или аутентичность). Проверка использует некий секрет, известный лишь отправителю и получателю сообщения, точно так же, как при обеспечении секретности используется секретный ключ шифрования. В общем виде код аутентификации представляет собой совокупность (S,E,M) трех конечных множеств, где S - множество состояний источника, E - множество правил кодирования, M - множество сообщений. Каждый элемент e &isn; E представляет собой отображение e:S® M. Правила кодирования « кодируют» состояния источникаs &isn; S в сообщения m &isn; M. Таким образом, сообщения передают информацию о наблюдаемом отправителем состоянии источника. Таковыми могут быть, например, результаты подбрасывания монеты при проведении жребия по телефону или обычные текстовые сообщения. Отображение e &isn;E должно быть « обратимым», чтобы по данным m и e можно было однозначно восстановить s. Формально это требование записывается с помощью отображения fecolonM® S И{0}, где 0 - число нуль (не принадлежащее S) и
Так вот, в определении A-кода требуется, чтобы выполнялось равенствоfe(e(s))=s для любых s &isn; S и e О E. Как стороны A и B используют A-код для аутентификации передаваемой информации? Прежде всего, они сообща выбирают (втайне от злоумышленника) правило кодирования e &isn; E. ПустьA желает передать состояние источника s &isn; S. Тогда он вычисляет m =e(s) и посылает m к получателю B по каналу связи. Получив m, B использует то же правило кодирования e для вычисления fe (m). Если fe(m) № 0, то mпринимается как аутентичное, в противном случае - нет. На практике используются лишь такие A-коды, для которых вычисление fe (m) производится так же просто, как и e(s). При анализе надежности защиты от активных атак с помощью A-кодов предполагается, что злоумышленник знает об A-коде все, кроме секретного правила кодирования (ключа). Он (злоумышленник) проводит атаки на основе анализа свойств A-кода. При этом его действия являются наиболее целесообразными с точки зрения достижения успеха атаки. Приведем пример. Рассмотрим A-код, для которогоS = {H,T} (сокращение от head - герб, tail - решка), E = {e1 ,e2 ,e3 }, M = {m1,m2, m3 }. Действие правил кодирования запишем в виде таблицы (матрицы кодирования): В этой таблице указано, например, что состояние источника Hкодируется с помощью правила e1 в сообщение m1, итд Пусть состояние источника выбирается случайно (как при подбрасывании монеты). При этом одно из двух состояний появляется чаще другого (как при использовании несимметричной монеты). Пусть p - « доля» состояния H. Тогда (1 -p) - « доля» состояния T. Например, если при бросании монеты она в среднем в двух случаях из трех выпадает гербом, то p = 2/3. С целью уменьшения шансов на успех злоумышленника A и B выбирают правило кодирования случайно. Пусть при этом p(ei) = xi - « доля» ei, i = ѕ1,3. Числа xi лежат в интервале (0,1), и их сумма равна 1. Пусть P(E) = (x1, x2, x3). Эта тройка чисел называется стратегией защиты. Эта стратегия выбирается стороной защиты с таким расчетом, чтобы минимизировать « шансы» злоумышленника на успех. Не вдаваясь в детали, укажем, что для данного A-кода при выбранной стратегии P(E) эти шансы злоумышленника характеризуются величиной
|
Сторона защиты выбирает оптимальную стратегию P(0)(E) так, чтобы минимизировать L(ѕx). Таким образом, возникает задача вычисления minѕx О DL(ѕx), где
|
Этот минимум можно вычислить, разбивая область D на подмножества Dj, j =ѕ1,8, в которых раскрывается каждый максимум в выражении L(ѕx). Например, в случае, когда L(ѕx) имеет вид L(ѕx) = p(x1 + x2 ) + (1 - p)x3. Как раз эта задача была предложена на олимпиаде. Решается она, например, следующим образом. Заметим, прежде всего, что из условий следует неравенство p і 1/2. В самом деле,
|
откуда p і 1 - p или 2p і 1. Выразив x3 из условия x1 + x2 + x3 = 1, получим следующее выражение:
|
Легко видеть, что минимальное значение это выражение принимает при максимально большом значении x3. Остается найти достижимую верхнюю границу для значения x3. Из цепочки неравенств x3 Ј x2 Ј [(p)/(1 - p)]x1получаем
|
откуда следует, что x3 Ј [(p)/(p + 1)]. Ясно, что равенство x3 = [(p)/(p + 1)] достигается лишь в случае, когда в указанной цепочке неравенств выполняются равенства, те если x3 = x2 = [(p)/(1 - p)]x1. Мы нашли максимальное значение x3. Отсюда получаем, что
|
Задача 2. Центральный замок автомобиля открывается и закрывается с помощью брелка. При получении сигнала брелка замок открывается (если был закрыт) или закрывается (если был открыт). В брелке и замке имеются счетчики (назовем их СБ и СЗ), на которых изначально было выставлено одно и то же число. Пусть N - текущее значение СБ. При нажатии на кнопку брелка СБ меняет значение на N+1, старое же значение N в зашифрованном виде передается замку. Микрокомпьютер замка расшифровывает полученный сигнал и находит число, переданное брелком. Если это число равно или превосходит значение СЗ, то замок срабатывает, а значение СЗ становится N+1. Если это число оказывается меньше или при расшифровании обнаруживается ошибка, то замок остается в прежнем состоянии. Злоумышленник способен а) запоминать сигналы брелка, б) поставив помеху, искажать сигналы брелка (при этом сам злоумышленник получает сигнал без искажений), в) посылать замку ранее запомненные сигналы. Как злоумышленнику открыть замок? Алгоритмы шифрования и расшифрования ему неизвестны.
Решение
Приведенный в задаче протокол работы брелка и замка был изобретен в ЮАР и практически без изменения использовался во многих известных противоугонных системах. Вызывает лишь удивление, что достаточно продолжительное время очевидная уязвимость этого протокола не была замечена (примечательно, что заметили и воспользовались ошибкой разработчиков непрофессионалы в области защиты информации).
Перейдем собственно к решению, пояснив предварительно одно из условий задачи. Пусть СБ=k и СЗ=m, где k не меньше m. Отметим, что в данной ситуации при нажатии на кнопку брелка и срабатывании замка счетчик замка принимает значение не m+1 (как ошибочно считали некоторые участники олимпиады), а k+1. Это сделано для того, чтобы один и тот же сигнал брелка не мог быть использован дважды. Запишем теперь по пунктам действия злоумышленника.
1. Пусть сейчас замок открыт. Владелец хочет запереть машину и уйти. Пусть СБ=k и СЗ=m, где k не меньше m. Владелец нажимает кнопку брелка. Злоумышленник запоминает посланный сигнал k и ставит помеху. В результате СБ=k+1 и по-прежнему СЗ=m, т.е. замок не закрылся.
2. Заметив, что машина не заперта, владелец повторно нажимает кнопку брелка. Злоумышленник снова запоминает сигнал k+1 брелка и опять ставит помеху. Значит, СБ=k+2, а замок так и остается открытым, т.е. СЗ=m.
3. Выполнив действия пункта 2, злоумышленник немедленно посылает замку ранее запомненный сигнал k. Замок закрывается, и при этом СЗ=k+1. Владелец уходит, полагая, что машину запер он сам.
4. Злоумышленник посылает замку ранее запомненный сигнал k+1, и замок открывается.
К сожалению, многие участники решали задачу исходя из слишком упрощенной модели реальной ситуации, отводя владельцу роль эдакого простачка, который, запирая машину, то ли не может, то ли забывает проверить, сработал замок или нет: предлагалось выбрать момент, когда владелец попробует запереть автомобиль, поставить помеху, не дав тем самым замку сработать, а затем подождать, пока владелец уйдет.
Задача 3.При зашифровании текста на русском языке (в текстах строчные и заглавные буквы не различались, а пробелы и знаки препинания опускались) каждую букву заменяли парой цифр. При этом разные буквы текста заменялись разными парами, а одинаковые - одинаковыми. Найдите все возможные места расположения слова ПОДЪЕЗД в исходном тексте по шифрованному тексту:
92 97 36 72 97 92 70 73 97 90 97 72 38 39 74 76
97 34 79 78 97 70 76 74 72 74 73 74 76 70 70 97
76 74 96 74 37 39 75 97 70 39 74 79 39 37 71 74
98 35 94 90 98 97 94 96 74 98 74 76 97
Решение
Если две буквы с порядковыми номерами Т1 и Т2 зашифрованы в буквы с порядковыми номерами С1 и С2 с помощью одной и той же буквы, то остатки от деления чисел (С1-Т1) и (С2 -Т2) на 30 равны между собой и совпадают с порядковым номером шифрующей буквы (порядковым номером буквы Я удобно считать число 0). Тогда, с учетом соглашения о порядковом номере буквы Я, справедливо, что Т1 равен остатку от деления числа (Т2+(С1-С2)) на 30, а, вместе с тем, Т2 равен остатку от деления числа (Т1+(С2-С1)) на 30. Если каждое из выражений в скобках заменить соответствующим остатком от деления на 30, то упомянутая связь не нарушится.
Представим в виде набора порядковых номеров известные шифрованные сообщения (обозначим их соответственно ш. с. 1 и ш. с. 2) и слово КОРАБЛИ:
| слово | К | О | Р | А | Б | Л | И |
| Т |
| ш.с.1 | Ю | П | Т | Ц | А | Р | Г | Ш | А | Л | Ж | Ж | Е | В | Ц | Щ | Ы | Р | В | У | У |
| С1 |