Криптосистема Гены и Чебурашки - 2

Крокодил Гена и Чебурашка могут связываться по двум каналам: радиоканалу и оптическому каналу. Используя эти каналы, они хотят договориться о кодовой комбинации сейфа, составленной из 20 букв К, З, С или Ч. Для этого Гена по оптическому каналу передаёт случайную комбинацию из 20 вспышек, причём каждая вспышка может быть красного (К), синего (С) или зелёного (З) цвета. Для каждой вспышки Чебурашка наугад выбирает светофильтр. Если его цвет совпадает с переданным цветом, то срабатывает датчик, а если не совпадает, то цвет вспышки остаётся для Чебурашки неизвестным. После замера всех вспышек Чебурашка по радиоканалу сообщает, какие светофильтры он выбрал. В результате Гена узнаёт номера вспышек, цвет которых Чебурашка определил. Гена устанавливает комбинацию на сейфе так: если цвет очередной вспышки Чебурашке определить удалось, то выбирается буква, соответствующая цвету вспышки (К, З либо С), если нет – выбирается Ч.

Шапокляк прослушивает радиоканал и «встроилась» в оптический канал. На пути передаваемых вспышек она выставляла свои светофильтры: ККЗЗЗСКСКСЗЗСКСКСКЗКи одновременно передавала вспышки соответствующих цветов Чебурашке. Срабатывание датчика у неё произошло на 6, 10, 11, 14, 17 и 19 вспышках. Чебурашка, не зная о вмешательстве, сообщил по радиоканалу свои цвета: СКЗККККЗЗККССККЗСЗСК. С учётом собранной Шапокляк информации, определите число кодовых комбинаций, которые гарантированно не откроют сейф.

Решение

Сравним посимвольно последовательности цветов, приведённые в условии и сформируем таблицу:

Светофильтры Чебурашки

Светофильтры Шапокляк

Ответ:4²⁰ - 2⁹

Пароль на мобильном телефоне

На клавиатуре мобильного телефона каждой кнопке сопоставлено по нескольку букв: кнопке 2 соответствуют буквыABC, 3 – DEF, 4 – GHI, 5 – JKL, 6 – MNO, 7 – PQRS, 8 – TUV, 9 – WXYZ.Выбор нужной буквы определяется числом нажатий на кнопку. Например, нажав на кнопку 4 один раз, получим буквуG, а два нажатия на кнопку 4 дадут или букву H(если нажимать быстро) или две буквыG (если нажимать с паузой). Известно, что при наборе пароля из 10 букв были нажаты последовательно кнопки 777255899999. Определите число возможных вариантов паролей.

Решение

Обозначим через х число букв, получившихся при наборе цифры 7 (их может быть от 1 до 3), у – число букв при наборе цифры 5 (1 или 2) и z – число букв при наборе цифры 9 (от 2 до 5). Перечислим возможные варианты представления числа 10 в виде суммы x+1+y+1+z:

1) 3+1+2+1+3; 2) 3+1+1+1+4; 3) 2+1+2+1+4; 4) 2+1+1+1+5; 5) 1+1+2+1+5.

Для варианта 1 получить три буквы, нажимая 7, можно только одним способом; получить две буквы, нажимая 5, можно опять-таки только одним способом; а вот получить три буквы с помощью пяти девяток можно 6 способами. В итоге, для варианта 1 имеем 1·1·6 вариантов паролей, аналогично для варианта 2 будет 1·1·4 вариантов паролей и т.д. Всего получаем 6+4+2·4+2+1=21 вариант.

Ответ:21

Совпадение при замене

Сообщение, составленное из нулей и единиц, шифруется двумя способами. При первом способе каждый нуль заменяется на последовательность из k₁ нулей и следующих за ними k₂ единиц, а каждая единица заменяется на последовательность из k₃ нулей. При втором способе шифрования каждая единица заменяется на последовательность из k₄ единиц и следующих за ними k₅ нулей, а каждый нуль заменяется на последовательность из k₆ нулей. При каких натуральных значениях k_i, i=1,2,...,6, найдется хотя бы одно сообщение, которое будет одинаково зашифровано обоими способами? Укажите общий вид таких сообщений.

Решение

Последовательность из k нулей или k единиц обозначим соответственно через 0^k или 1^k. Тогда шифрование каждого знака сообщения состоит в замене

ì ï í ï î

® 0^k₁1^k₂

® 0^k₃

для I способа,

ì ï í ï î

® 1^k₄0^k₅

® 0^k₆

для II способа.

(1)

В зашифрованном сообщении все серии из единиц имеют длину k₂ для первого способа и длину k₄ для второго способа, поэтому, для совпадения результатов зашифрования необходимо, чтобы

k₂=k₄.

(2)

Теперь легко получить, что в сообщении должно быть одинаковое число нулей и единиц.

Пусть n - число нулей в сообщении. Тогда число нулей в зашифрованном I способом сообщении равно nk₁ + nk₃, а II способом - nk₅ + nk₆. Таким образом,

nk₁ + nk₃ = nk₅ + nk₆.

(3)

Из видно, что сообщение должно начинаться с нуля и оканчиваться единицей. Пусть перед первой единицей сообщения расположено a нулей. Тогда первые а +1 знаков сообщения представляются при шифровании в виде:

при а=1

ì ï í ï î

0^k₁1^k₂0^k₃ для I способа,

0^k₆1^k₄0^k₅ для II способа,

при а > 1

ì ï í ï î

0^k₁1^k₂0^k₁1^k₂...0^k₁1^k₂0^k₃ для I способа,

0^ak₆1^k₄0^k₅ для II способа.

При a=1 получаем необходимость равенства k₁=k₆, а значит, с учетом - равенства k₃=k₅.

При а > 1 получаем условия:

k₁=ak₆ , а - натуральное,

k₁=k₅+bk₆, b - натуральное или нуль.

Подставляя k₁=k₅+bk₆ в , получаем равенство k₃=(1-b)k₆, которое при натуральных k₃, k₆ и b ³ 0 возможно лишь в случае b = 0. Следовательно, k₃=k₆, а значит, с учетом k₁=k₅.

Таким образом, при а > 1 необходимы условия k₂=k₄, k₅=k₁=ak₆=ak₃, где a - натуральное. Из следует, что сообщение должно иметь вид 0...01...1, где число нулей и число единиц равно a.

Ответ:При k₂=k₄, k₁=k₆, k₃=k₅ сообщения вида 0101...01 шифруются одинаково.

При k₂=k₄, k₅=k₁=ak₆=ak₃, где a - натуральное, сообщения вида (0...01...1) ... (0...01...1) (группы из a нулей и a единиц) шифруются одинаково.

Примечание. Первый ответ не является частным случаем второго при a = 1.

Подбор пароля

Одна фирма предложила устройство для автоматической проверки пароля. Паролем может быть любой непустой упорядоченный набор букв в алфавите {a,b,c}. Будем обозначать такие наборы большими латинскими буквами. Устройство перерабатывает введенный в него набор P в набор Q=j(P). Отображение j держится в секрете, однако про него известно, что оно определено не для каждого набора букв и обладает следующими свойствами. Для любого набора букв P

1) j(aP)=P;

2) j(bP) = j(P)aj(P);

3) набор j(cP) получается из набора j(P) выписыванием букв в обратном порядке.

Устройство признает предъявленный пароль верным, если j(P)=P. Например, трехбуквенный набор bab является верным паролем, так как j(bab) = j(ab)aj(ab)=bab. Подберите верный пароль, состоящий более чем из трех букв.

Решение

Обозначим [j(P)] - набор j(P) , выписанный в обратном порядке.

j(cbcacbc)=[j(bcacbc)] = [j(cacbc)aj(cacbc)] = [[j(acbc)]a[j(acbc)]] = [[cbc]a[cbc]]=[cbcacbc]=cbcacbc.

В общем случае можно показать, что множество искомых наборов состоит из слов вида:

ì ï í ï î

c... c k раз

acb

c... c k раз

k - нечетное;

c... c k раз

c... c kраз

k - четное.

Ответ:например, cbcacbc.

НОД и НОК

Сколько существует упорядоченных пар натуральных чисел a и b, для которых известны их наибольший общий делитель d=6 и их наименьшее общее кратное m=6930. Сформулируйте ответ и в общем случае, используя канонические разложения d и m на простые множители.

Решение

Разложим числа m и d на простые множители: d=6=2·3; m=6930=2·3·3·5·7·11. Обозначим буквой t число m/d, равное произведению 3·5·7·11 . Найдем все его делители q вида: q=3^x5^y7^z11^u, где числа x, y, z и u принимают только значения 0 и 1. Тогда, как нетрудно видеть, числа q и t/q окажутся взаимно простыми. Полагая а=dq и b=dt/q, получим все искомые пары (a,b). В самом деле, в указанных выше условиях наибольший общий делитель такой пары равен d, а ее наименьшее общее кратное равно dqt/q=dt=dm/d=m. Таким образом, искомое число упорядоченных пар совпадает с числом всех делителей q вида: 3^x5^y7^z11^u, которое равно числу всех упорядоченных наборов длины 4 и состоящих только из 0 и 1. Число всех таких наборов равно 2⁴=16, так как для каждого места в наборах существует ровно 2 варианта его значений независимо от значений на других местах. В общем случае число m/d представляется в виде m/d=pⁱr^j... s^h, где p, r, ..., s - различные простые числа, а i, j, ..., h - натуральные числа. Число всех делителей вида: q=p^xr^y... s^z, где числа x, y, ..., z принимают только по два значения (0 и соответствующий натуральный показатель степени в представлении числа m/d), равно 2^k, где k - число всех простых делителей числа m/d. Если число различных простых множителей в каноническом разложении числа m/d равно k, то число различных упорядоченных пар (a,b) равно 2^k.

Ответ:16 пар (пары (a,b) и (b,a) разные). В общем случае число упорядоченных пар равно 2^k, где k - число всех простых делителей m/d.

Поворотная решетка

Ключом шифра, называемого "поворотная решетка", является трафарет, изготовленный из квадратного листа клетчатой бумаги размера n×n (n - четно). Некоторые из клеток вырезаются. Одна из сторон трафарета помечена. При наложении этого трафарета на чистый лист бумаги четырьмя возможными способами (помеченной стороной вверх, вправо, вниз, влево) его вырезы полностью покрывают всю площадь квадрата, причем каждая клетка оказывается под вырезом ровно один раз. Буквы сообщения, имеющего длину n², последовательно вписываются в вырезы трафарета, сначала наложенного на чистый лист бумаги помеченной стороной вверх. После заполнения всех вырезов трафарета буквами сообщения трафарет располагается в следующем положении и т. д. После снятия трафарета на листе бумаги оказывается зашифрованное сообщение. Найдите число различных ключей для произвольного четного числа n.

Решение

Все клетки квадрата размера n×n разобьем на непересекающиеся группы по четыре клетки в каждой. Отнесем клетки к одной и той же группе, если при каждом повороте квадрата до его самосовмещения они перемещаются на места клеток этой же группы. На рисунке показано такое разбиение на группы всех клеток квадрата 6×6, причем клетки одной группы помечены одной и той же цифрой. Всего таких групп будет n²/4 (целое, так как n - четное число). При наложении трафарета на квадрат ровно одна клетка из каждой группы окажется под его вырезами. Каждому трафарету поставим в соответствие упорядоченный набор всех клеток из таких групп, оказавшихся под вырезами трафарета при наложении его на квадрат помеченной стороной вверх. Такое соответствие является взаимнооднозначным, поскольку каждому ключу будет однозначно соответствовать упорядоченный набор из n²/4 клеток (по одной из каждой группы), вырезанных в трафарете, и наоборот. Всего таких наборов 4^n2/4. В самом деле, существует ровно четыре различных варианта выбора клетки из каждой группы независимо от выбранных клеток из других таких групп.

Ответ:Число различных ключей шифра "поворотная решетка" при четных значениях n равно 4^n2/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 флагов вида

(L₁,p), (L₂,p), ј, (L_t,p);

2. для каждой линии L имеется ровно s флагов вида

(L,p₁), (L,p₂), ј, (L,p_s);

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).

Теперь находим число линий:

B =

p·t s

= t·(t·(s-1)+1).

Наконец, число флагов равно

F = t·s(t·(s−1)+1).

Ответ:P=t·(s−1)·s+s=s·(t·(s−1)+1);B=t·(t·(s−1)+1); F=t·s(t·(s−1)+1).

Сейфовый замок (щелчки)

Кодовая комбинация сейфа устанавливается на внутренней стороне дверцы с помощью трех дисков. Каждый из них может быть установлен в одно из 20 положений, пронумерованных числами от 0 до 19, поворотом по часовой стрелке. В начальный момент диски установлены в положение (0, 0, 0). За положение с номером 19 диск не поворачивается. При повороте каждого диска на одно положение раздается щелчок. Сравните число возможных кодовых комбинаций, при установке которых раздается 33, 32, 25 щелчков.

Решение

Пусть MN - число различных комбинаций, при установке которых раздается N (NЈ 57) щелчков.

Заметим, что из соображений симметрии M_N = M_57−N. Для обоснования этого равенства достаточно установить взаимно однозначное соответствие между комбинациями, получаемыми за N и за 57−N поворотов. Это можно, например, сделать так: сопоставим комбинации (n₁,n₂,n₃), где n₁+n₂+n₃=N, комбинацию (19−n₁,19−n₂,19−n₃), получаемую за 19−n₁+19−n₂+19−n₃=57−(n₁+n₂+n₃)=57−>N щелчков. Отсюда заключаем, что число комбинаций, при установке которых раздается 32 и 25 щелчков, одинаково (M₃₂=M₂₅).

Из предыдущего рассуждения также следует, что М₂₄=М₃₃. Поэтому для завершения решения достаточно сравнить числа М₂₄ и M₂₅.

Комбинацию будем называть насыщенной, если один из дисков установлен в положение 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 щелчка.

Ответ:Количества комбинаций, получаемых за 25 и 32 щелчка, совпадают, комбинаций для 33 щелчков меньше.

Телебанк

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

Решение

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

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

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

Где ключей больше?

Два криптографа выясняют, чей шифр содержит больше ключей. Первый говорит, что ключ его шифра состоит из 50 упорядоченных символов, каждый из которых принимает 7 значений. Второй говорит, что ключ его шифра состоит всего из 43 упорядоченных символов, зато каждый из них принимает 10 значений. Чей шифр содержит больше ключей?

Решение

У первого криптографа каждый из 50 символов ключа выбирается из 7 возможных значений. Значит, всего 7·7·...·7 = 7⁵⁰ различных вариантов выбора ключа шифра. Аналогично у второго криптографа всего 10⁴³ различных вариантов выбора ключа. Задача сводится к сравнению чисел 7⁵⁰ и 10⁴³. Это можно сделать несколькими способами:

а) 2²⁵ = 2¹⁰·2¹⁰·2⁵> 10³·10³·32 > 10⁷, следовательно,