Введение в криптографию. Теоретико-числовые основы защиты информации [Елена Ивановна Деза] (pdf) читать постранично, страница - 20

алфавит и шифрующее отображе-

(

ние f ( X ) = А • X с матрицей А — I

\3

1

2\}, была получена биграмма «ББ»
4/

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

(I ЛI .

Таким образом, для нахождения числового эквивалента соответ­

ствующей биграммы открытого текста необходимо решить сравнение

соем :)—
Поскольку А = 1 -4 —2 -3 — 4 —6 — —2 и (—2, 33) = 1, то данное
сравнение разрешимо и имеет ровно одно решение — биграмму по моду­
лю 33. Найдем его двумя способами.
Первый способ. В матричной форме сравнение имеет вид
Y = А - X (mod 33).

Перейдем к сравнению X = А ~1 • Y (mod 33) и найдем

Tlgm: @it_boooks

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

101

Прежде всего найдем А 1. Поскольку А • А 1 = 1 (mod 33), то есть
-2 • А -1 = 1 (mod 33), то А -1 = 16. Тогда
А~1 = 16 •

Отсюда следует, что

\ —15 1 6 /

\ 1 /

Ѵ -15+16

Таким образом, числовой эквивалент биграммы открытого текста X /з2 \

= I
I , а сама биграмма имеет вид «ЯБ».
V 1/
Второй способ. Запишем наше преобразование в виде системы срав­
нений:
х + 2у = 1 (mod 33)

(

Зх + 4у = 1 (mod 33).

Домножим левую и правую части первого сравнения на 2 и вычтем
из второго сравнения первое. Получим х = —1 (mod 33), откуда сле­
дует, что у = 1 (mod 33). Поскольку х = —1 = 32 (mod 33), то получаем
/32\

окончательный ответ X = \

I , дающий, как и в предыдущем случае,

биграмму «ЯБ».
2.
Если при шифровании по той или иной причине была использована
«плохая» шифрующая матрица А , ситуация может осложниться. Рассмот­
рим, например, задачу дешифрования биграммы «АД», полученной при
использовании 33-буквенного русского алфавита и шифрующего.отобрас матрицей А = I( 1 5 \1.
V2 1}
Попробуем, как и ранее, найти биграмму из сравнения

жения f ( X) =

Tlgm: @it_boooks

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

102

Поскольку А = 1 -1 —2 - 5 = 1 — 10 = - 9 , и (-9 , 33) ^ 1, то для
( 1 5\
матрицы I
I обратной матрицы не существует, и решить сравнение
\2 1 )
первым способом не представляется возможным.
Что даст второй способ? Запишем сравнение в виде системы сравнений:

{

х + 5у = 1 (mod 33),
2х + у = 5 (mod 33).

Проведя несложные преобразования, получим сравнение - 9 у = 3 (mod 33).
Поскольку (—9,33) = 3, то данное сравнение имеет три решения:
у = 7,18, 29 (mod 33). Находя соответствующие х = 1 —5?/(mod 33), по­
лучим следующие возможности:
у = 7, 18, 29 (mod 33),
х = 32, 10, 21 (mod 33).
( 32 \

Это дает нам три вектора

V 7/

( 10 \

1,

\ 18/

/2 1
1,

\29,

J , и, следовательно, три

возможных варианта «ЯЖ», «ЙС», «ФЬ» расшифровки имеющегося в на­
шем распоряжении шифротекста.
3. Если же при использовании 33-буквенного русского алфавита и то-

5\

го же шифрующего отображения f ( X) = А • X с матрицей А = (I 1 1
\2 1 /
бьша получена биграмма «БД», то попытка ее дешифровки будет выгля­
деть следующим образом.
Как и ранее, попытка найти биграмму из сравнения

С

1 ) ■С

Н

У

(mod зз>

заставит нас убедиться в том, что обратной матрицы не существует и ре­
шить задачу первым способом не представляется возможным. При реше­
нии задачи вторым способом, записав сравнение в виде системы срав­
нений
х + 5у = 1 (mod 33),

{

2х + у = 4 (mod 33),

Tlgm: @it_boooks

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

103

получим, после несложных преобразований, сравнение —9у = 2 (mod 33).
Поскольку (—9, 33) = 3, и 3 | 2 , то данное сравнение решений не имеет,
и дешифровать имеющуюся в нашем распоряжении биграмму не пред­
ставляется возможным. Видимо, в ходе шифрования произошел какойто сбой.
□
Чтобы с помощью аффинных матричных преобразований дешифро­
вать некоторое шифрованное сообщение, его следует разбить на биграммы
и построить последовательность Zi Z2Z i . .. Zm, состоящую из m числовых

( * Л1, . . . ,

( z™\
Zm = I
I биграмм шифротекста. Эту

t j

\ t mJ

последовательность можно рассматривать как 2 х ш матрицу Z , состоящую
из m векторов-столбцов, которые представляют биграммы шифротекста.
Таким образом, для дешифровки сообщения достаточно умножить
2 x 2 матрицу А~1 на 2 х m матрицу Z и, получив при этом 2 х ш матрицу
X = А~1 • Z, состоящую из числовых эквивалентов биграмм-векторов
открытого текста, перейти с ее помощью к исходному сообщению.
[Пример 3.1.6] Дешифруем сообщение «БЯЕБФХ», полученное при ис­

пользовании 33-буквенного русского алфавита и шифрующего преобра/2

3\

зования Z — А Х с матрицей А — I
). Для этого представим шиф\4 8 /
рованное сообщение «БЯЕБФХ» в виде последовательности трех векторов
/ 1\

I

(ъ \
I, I

(

/21 \

I, I

і 5 2і\

1. Составим из них 2 x 3 матрицу Z = I

\32/ V1/ V22/

)

V32122/

и осуществим нужное преобразование:

770 34

570
(mod 33).

,576 177 1046/

V 15 12 23 /

Рассматривая вектора-столбцы I/ 11 \I , I/ М 1 ,1I 9 \I полученной мат\ 15 /

\n j

\23)

рицы как числовые эквиваленты биграмм открытого текста, без труда
получим