Главная | Обратная связь

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

Задачи про графы

Гг

Задача 1.Рассмотрим преобразование цифрового текста, в котором каждая цифра заменяется остатком от деления значения многочлена F(х)=b(x³+7x²+3x+a) на число 10, где a, b - фиксированные натуральные числа.

Выясните, при каких значениях a, b указанное преобразованиеможет быть шифрпреобразованием (т. е. допускает однозначное расшифрование).

Решение

Обозначим через f(x) - остаток от деления значения многочлена F(x) на 10. Для однозначного расшифрования необходимо и достаточно, чтобы разным значениям x соответствовали разные значения f(x). Поэтому f(0), f(1), ..., f(9) принимают все значения от 0 до 9. Найдем эти значения:

f(0) = r10(b(a+0))	f(1) = r10(b(a+1))
f(2) = r10(b(a+2))	f(3) = r10(b(a+9))
f(4) = r10(b(a+8))	f(5) = r10(b(a+5))
f(6) = r10(b(a+6))	f(7) = r10(b(a+7))
f(8) = r10(b(a+4))	f(9) = r10(b(a+3)),

где r₁₀(y) - остаток от деления числа y на 10.

Отсюда, пользуясь свойствами остатков, замечаем, что b должно быть нечетным (иначе f(x) будут только четные числа) и b не должно делиться на 5 (иначе f(x) будут только 0 и 5). Непосредственной проверкой можно убедиться, что при любом a и при всех b, удовлетворяющим приведенным условиям, гарантируется однозначность расшифрования.

Задача 2.Одна фирма предложила устройство для автоматической проверки пароля. Паролем может быть любой непустой упорядоченный набор букв в алфавите {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.

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

P= м п н п о cb c... c k раз acb c... c k раз   k - нечетное; b c... c k раз ab c... c kраз   k - четное.

ФН × Ы = ФАФ + × - ЕЕ + Е = НЗ = = = ИША + МР = ИМН

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

Решение

Из последней строчки легко заметить, что Ш=0. Тогда из первого столбца находим, что И=1. Затем из последнего столбца находим Ф=2. Итак,

2Н × Ы = 2А2 + × - ЕЕ + Е = НЗ = = = 10А + МР = 1МН

Из средней строки ясно, что Н > Е. Из первого столбца находим Е=7. Из средней строки можно вычислить значения Н и З: Н=8 и З=4. Получим

× Ы = 2А2 + × - + = = = = 10А + МР = 1М8

Далее, последовательно вычисляем значения: А=5,Ы=9, М=6, Р=3.

Задача 4.Сколько существует упорядоченных пар натуральных чисел 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.

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

Решение

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

Задача 6.Суммой двух букв назовем букву, порядковый номер которой в алфавите имеет тот же остаток от деления на число букв в алфавите, что и сумма порядковых номеров исходных двух букв. Суммой двух буквенных последовательностей одинаковой длины назовем буквенную последовательность той же длины, полученную сложением букв исходных последовательностей, стоящих на одинаковых местах.

а) Докажите, что существует последовательность из 33 различных букв русского алфавита, сумма которой с последовательностью букв, представляющей собой сам этот алфавит, не содержит одинаковых букв.

б) Докажите, что сумма любой последовательности из 26 различных букв английского алфавита с последовательностью букв, представляющей собой сам этот алфавит, содержит не менее двух одинаковых букв.

 

Решение

Занумеруем горизонтали и вертикали квадрата натуральными числами от 1 до 13 сверху вниз и слева направо соответственно. Тогда каждая клетка квадрата однозначно определяется парой чисел (i;j), где i - номер горизонтали, а j - номер вертикали, в которых находится клетка.

Расстояние между центром клетки (a;b) и центром клетки (c;d) равно Ц{(a-c)²+(b-d)²}. Заметим, что |a-c| О {0,1,...,12} и |b-d| О {0,1,...,12}. Обозначим x=|a-c|, y=|b-d|, z=Ц{x²+y²}. Тогда z - число натуральное, если x² = (z+y)(z-y). Отсюда получаем, что

1=(z+y)(z-y) Ы м п н п о z=1 y=0

22=(z+y)(z-y) Ы м п н п о z=2 y=0

32=(z+y)(z-y) Ы м п н п о z=3 y=0 или м п н п о z=5 y=4 ; и т. д.

Гг

Задача 1.Буквы русского алфавита занумерованы в соответствии с таблицей:

А

Б

В

Г

Д

Е

Ж

З

И

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ь

Ы

Э

Ю

Я

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

Прочтите шифрованное сообщение: РБЬНТСИТСРРЕЗОХ, если известно, что шифрующая последовательность не содержала никаких букв, кроме А, Б и В.

Решение

Каждую букву шифрованного сообщения расшифруем в трех вариантах, предполагая последовательно, что соответствующая буква шифрующей последовательности есть буква А, Б или буква В:

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

Р

Б

Ь

Н

П

Т

С

И

Т

С

Р

Р

Е

З

О

Х

вариант А

П

А

Щ

М

О

С

Р

З

С

Р

П

П

Д

Ж

Н

Ф

вариант Б

О

Я

Ш

Л

Н

Р

П

Ж

Р

П

О

О

Г

Е

М

У

вариант В

Н

Ю

Ч

К

М

П

О

Е

П

О

Н

Н

В

Д

Л

Т

Замечание. Из полученной таблицы можно было найти такое исходное сообщение как НАШ МОРОЗ ПОПОВ ЕМУ которое представляется не менее осмысленным, чем приведенное выше. А если предположить одно искажение в шифрованном сообщении (скажем, в качестве 11-й буквы была бы принята не буква Р, а буква П), то, наряду с правильным вариантом, можно получить и такой: НАШ МОРОЗ ПОМОГ ЕМУ Число всех различных вариантов исходных сообщений без ограничений на осмысленность равно 3¹⁶ или 43046721, т. е. более 40 миллионов!

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

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

Решение

Обозначим через S(n) остаток от деления на 26 суммы чисел, которые соответствуют первым n буквам алфавита (n=1,2,...,26) 0 Ј S(n) Ј 25.

Если среди чисел S(1), S(2), ..., S(26) есть нуль: S(t)=0, то искомой ключевой комбинацией является цепочка первых t букв алфавита.

Если среди чисел S(1), S(2), ..., S(26) нет нуля, то обязательно найдутся два одинаковых числа: S(k)=S(m) (считаем, что k < m). Тогда искомой ключевой комбинацией является участок алфавита, начинающийся с (k+1)-й и заканчивающийся m-й буквой.

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

Найдите исходное цифровое сообщение по шифрованному сообщению:

4 2 3 4 6 1 4 0 5 3 1 3

Решение

Согласно условию, исходное сообщение состоит из двух пятерок цифр: A₁A₂A₃A₄A₅ и B₁B₂B₃B₄B₅. Пусть C₁C₂ - последние две цифры суммы чисел, изображенных этими пятерками. Через aЕb обозначим последнюю цифру суммы чисел a и b. Пусть D обозначает цифру переноса (цифру десятков) суммы (A₅ ⊕ B₅). По условию имеем, что A₅ЕB₅=C₂ и (A₄ЕB₄)ЕD=C₁.

Пусть G₁ - первый член, а X - разность арифметической прогрессии, которую коммерсант использовал при шифровании. Тогда из условия получаем:

A1 ЕG1 = 4	(1)
A2 Е(G1+X) = 2	(2)
A3 Е(G1+2X) = 3	(3)
A4 Е(G1+3X) = 4	(4)
A5 Е(G1+4X) = 6	(5)
B1 Е(G1+5X) = 1	(6)
B2 Е(G1+6X) = 4	(7)
B3 Е(G1+7X) = 0	(8)
B4 Е(G1+8X) = 5	(9)
B5 Е(G1+9X) = 3	(10)
B5 Е(G1+9X) = 3	(10)
((A4 ЕB4) ЕD) Е(G1+10X) = 1	(11)
(A5 ЕB5) Е(G1+11X) = 3	(12)

Обозначим символом A є B равенство остатков от деления на 10 чисел A и B. Тогда записи AЕB=C и (A+B) є C имеют одинаковый смысл. Если A є B и C єD, то A+B є C+D, A-B є C-D. Всегда A є A, так как остаток от деления единствен.

Из соотношений (4), (5), (9) и (10) находим соответственно:

A4 є 4-(G1+3X)	(13)
A5 є 6-(G1+4X),	(14)
B4 є 5-(G1+8X)	(15)
B5 є 3-(G1+9X)	(16)

Подставляя эти значения в равенства (11) и (12), получим следующие равенства: 9+D-G-X є 1 и 9-G-2X є 3. Отсюда следует, что

X є (-2-D)	(17)
G1 є 2D	(18)

Подставив X из (17) и G₁ из (18) в (1), (2),(3), (13, (14), (6), (7), (8), (15), (16), найдем выражения для цифр исходного сообщения:

A1 є 4-2D, A2 є 4-D, A3 є 7, A4 є D, A5 є 4+2D)
B1 є 1+3D, B2 є 6+4D, B3 є 4+5D, B4 є 1+6D
B5 є 1+7D

Задача 4. В древнем шифре, известном под названием "Сцитала", использовалась полоска папируса, которая наматывалась на круглый стержень виток к витку без просветов и нахлестов. Далее, при горизонтальном положении стержня, на папирус построчно записывался текст сообщения. После этого полоска папируса с записанным на ней текстом посылалась адресату, имеющему точно такой же стержень, что позволяло ему прочитать сообщение.
В наш адрес поступило сообщение, зашифрованное с помощью шифра "Сцитала". Однако ее автор, заботясь о том, чтобы строчки были ровные, во время письма проводил горизонтальные линии, которые остались на полоске в виде черточек между буквами. Угол наклона этих черточек к краю ленты равен a, ширина полоски равна d, а ширина каждой строки равна h. Укажите, как, пользуясь имеющимися данными, прочитать текст.

Решение

Рассмотрим один виток ленты на развертке цилиндра (разрез по горизонтальной линии). По условию высота CE, опущенная на сторону AD, равна d. Угол DAC равен (90-a)^°. Отсюда AC равно d/cosa. Так как высота строки равна h, то всего на одном витке n=d/(h·cosa) букв.

Задача 5.При зашифровании текста на русском языке (в текстах строчные и заглавные буквы не различались, а пробелы и знаки препинания опускались) каждую букву заменяли парой цифр. При этом разные буквы текста заменялись разными парами, а одинаковые - одинаковыми. Найдите все возможные места расположения слова ПОДЪЕЗД в исходном тексте по шифрованному тексту:

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

Решение

Если две буквы с порядковыми номерами Т₁ и Т₂ зашифрованы в буквы с порядковыми номерами С₁ и С₂ с помощью одной и той же буквы, то остатки от деления чисел (С₁-Т₁) и (С₂ -Т₂) на 30 равны между собой и совпадают с порядковым номером шифрующей буквы (порядковым номером буквы Я удобно считать число 0). Тогда, с учетом соглашения о порядковом номере буквы Я, справедливо, что Т₁ равен остатку от деления числа (Т₂+(С₁-С₂)) на 30, а, вместе с тем, Т₂ равен остатку от деления числа (Т₁+(С₂-С₁)) на 30. Если каждое из выражений в скобках заменить соответствующим остатком от деления на 30, то упомянутая связь не нарушится.

Представим в виде набора порядковых номеров известные шифрованные сообщения (обозначим их соответственно ш. с. 1 и ш. с. 2) и слово КОРАБЛИ:

слово	К	О	Р	А	Б	Л	И
Т

 

ш.с.1

Ю

П

Т

Ц

А

Р

Г

Ш

А

Л

Ж

Ж

Е

В

Ц

Щ

Ы

Р

В

У

У

С1

 

ш.с.2

Ю

П

Я

Т

Б

Н

Щ

М

С

Д

Т

Л

Ж

Г

П

С

Г

Х

С

Ц

Ц

С2

Возможны 15 вариантов (номер варианта обозначим буквой k) расположения слова КОРАБЛИ в каждом из двух исходных сообщений (и. с. 1, и. с. 2).