Елена Ивановна Деза , Лидия Владимировна Котова - Введение в криптографию. Теоретико-числовые основы защиты информации

сравнения:

Tlgm: @it_boooks

Глава 3. Шифрующие матрицы

106

е) С -и =(!)'

В каждом из случаев, выбрав подходящий алфавит, расшифруйте со­
общение «ABCDEFG». Зашифруйте и расшифруйте придуманное вами
сообщение.
(§) Пользуясь 30-буквенным русским алфавитом (И и Й, Е и Ё, Ь и Ъ
отождествлены), дешифруйте биграмму f ( X ) , которая была получена
с помощью аффинного матричного преобразования
f ( X ) = А - Х + В (mod 30), если
a ) Л = ^ 2 4

В =

> f (x ) = «МА»;

b) Л = ^ * 3 ^ , Б = ^ 7 ^ , f ( X ) = «ПЫ»;

с> (Г1)’ (о)’/(х)=

«л и »;

^ А=( 5 §) ’В= (о) ’/(Х)=:
е>А= (і9 іо) ’В =(4 ) ’/(Х)=;
f ) A = ( 9 2 ),B=l

g) А = ^

),В=[

-

I , f ( X ) — «КО»;

0

) , / ( * ) = «ЗЫ».

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

Tlgm: @it_boooks

3.1. Алгебра матриц и аффинные матричные криптосистемы

107

Задачи

ПП Докажите, что для множества аффинных матричных преобразований
над одним и тем же алфавитом выполняются следующие утверждения:
a) композиция матричных сдвигов является матричным сдвигом;
b) композиция линейных матричных преобразований является ли­
нейным матричным преобразованием;
c) композиция аффинных матричных преобразований является аф­
финным матричным преобразованием.

(а ь\

Пусть А = I
I £ M2(Ztv) и А = ad — be — определитель этой
\с dj
матрицы. Докажите, что следующие утверждения эквивалентны:

a) (A , N )

= I;

b) Матрица А имеет обратную;
c) Если хотя бы один из элементов х, у £

отличен от нуля, то

d) Матрица А задает взаимно-однозначное отображение множества
ZN х
на себя.
[з] Найдите биграмму

открытого текста из сравнения:

Tlgm: @it_boooks

Глава 3. Шифрующие матрицы

108

(mod 25);

(mod 25).
[4] Числа Фибоначчи определяются правилами u\ = Ui — 1, un+\ = u n + un-\
при n > 1. Докажите, что в матричной форме это правило может быть
записано в виде

( ^П+І

\
Щ і-1 /

( 1 1\

\ 1 0 /,

Используя определение чисел Фибоначчи в матричной форме, до­
кажите, что ип четно тогда и только тогда, когда п делится на 3;
докажите, что ип делится на а тогда и только тогда, когда п делится
на Ь, если a = 2, Ъ — 3; a = 3, b — 4; a = 5, b = 5; a = 7, b = 8;
a = 8, 6 = 6; а = 11, Ь — 10.
[5| Постройте первые двадцать чисел Фибоначчи. Постройте матрицы
^п+І

.. ,

для п — 1, 2,..., 19, пользуясь уже известными значе-

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

Tlgm: @it_boooks

3.1. Алгебра матриц и аффинные матричные криптосистемы

109

(I 1 М 1. Какой способ удобнее? Можно ли использовать полученные
\1 О/
матрицы для построения аффинных матричных отображений? Можно

(

Ѣі+l Un

\I

при произволь-

un Un—
iJ
ном задании параметра п? Почему?
[б] Осуществите шифрование биграммы «ОХ», записанной в 33-буквенном
русском алфавите, с помощью аффинного матричного отображения
г/ ѵ \
( un+1 un \
да) —I
I А, где п — ваш номер в списке группы, a un —
\ Un Un—\ )
n-e число Фибоначчи.
0 Пусть N, М G N, и (ІѴ, М) = 1. Убедитесь в том, что любую матрицу
A G M 2(Zn) м о ж н о вложить в множество М 2(Ъм) простым приведе­
нием элементов по модулю М. Приведите примеры таких вложений.
\Й\ Пусть N = m n, где (т ,гі) — 1. Пусть Ат G М2(Zm) — матрица,
полученная путем приведения элементов матрицы Л по модулю т ,
и і „ G M2(Zn) — матрица, полученная путем приведения элементов
матрицы А по модулю п.
a) Докажите, что отображение, сопоставляющее матрице А пару
(Ат,А п), является взаимно-однозначным соответствием между
множеством M 2(ZN) и декартовым произведением M2(Zm)x M 2(Zn)
множеств M2(Zm) и M2(Zn). Приведите примеры.
b) Докажите, что это отображение задает взаимно-однозначное со­
ответствие между множеством М^{Ъ^) обратимых 2 x 2 матриц с
элементами из ZN и декартовым произведением М \(Zm) х М^С^п)
множества M |(Z m) обратимых 2 x 2 матриц с элементами из Zm
на множество М\ (Zn) обратимых 2 x 2 матриц с элементами из Zn.
Приведите примеры.
[9] Найдите число элементов множества M2(ZP), где р — простое число.
Подсчитайте число решений в Ъѵ уравнения ad —be — 0. Докажите,
что число --">