Шифрование с использованием алгебры матриц.docx

Шифрование с использованием алгебры матриц

(частный случай перестановок).

Считается, что этим методом можно получить надёжное закрытие информации. Например, применим правило умножения матрицы на вектор.

é 11

12        a13 ù

éb1 ù

é  11        1

a12 × b2 + a13 × b3 ù

éc1 ù

ê                 a ú × êb ú

= ê+×a

× b + a

× b ú º êc ú

ê  21            22            23 ú

ê 2 ú

ê  21        1

22         2            23        3 ú

ê 2 ú

ê           31         32        a33 úû

êëb3 úû

ëê           31      1

a32 × b2 + a33 × b3 úû

êëc3 úû

Здесь матрицу

aij

будем  брать  за  основу  (ключ)  шифрования. Матрицу   bi        —

как   символы  исходного  текста.  Матрицу  столбец   ci

текста.

— как символы шифрованного

Пример. Представляем ключ матрицы, например, 3-го порядка

é14   8

ê

ê

êë

3ù

ú

ú

1úû

Знаки алфавита кодируем числами по порядку.

A B C D E F G H I J K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Текст “Data management system” зашифруем как:

é14     8    3ù  é 3 ù D    é14 3

8 × 0 + 3×19ù    é99ù

ê            2ú × ê 0 ú A = ê

5 × 0 + 2 ×19 ú = ê62ú

ê              ú  ê   ú        ê                          ú    ê    ú

ê            1úû  êë19úû T     êë          2 × 0 +1×19 úû    êë28úû

é14   8    3ù  é 0 ù A     é96ù

ê            2ú × ê12ú M = ê60ú

и т.д.

ê              ú  ê   ú         ê    ú

ê            1úû  êë 0 úû  A     êë24úû

Получим шифрованный текст: 99, 62, 28, 96, 60, 24, и т.д.

Дешифрование производится по тому же правилу умножения, но в качестве ключа

берём обратную матрицу

-1

ij

и умножаем её на вектор столбец из соответствующего

количества чисел шифрограммы. Числа вектора результата дадут эквиваленты знаков исходного текста.

-1

ij

Pij ,

D

ij 1()              ×

ij , где

Pij

—  называется присоединённая матрица

Dij

—     определитель матрицы присоединённой получаем из определителя D

вычёркиванием i-строки и j-столбца

D  — определитель матрицы-ключа.  D  - n-го порядка есть алгебраическая сумма

n!  членов  из  всевозможных  произведений  n   -  элементов  матрицы,  взятых  по  одному в

каждой строке и в каждом столбце, со знаком (+), если его индексы составляют чётную подстановку, и со знаком (-) в противоположном случае.

Для третьего порядка:

= 11 a22 a33 + a12 a23 a31 + a13 a21 a32 - a11 a22 a32 - a12 a21 a33 - a13 a22 a31

Получаем обратную матрицу:

é        -

ê

ê

ê                              -

1 ù

ú

ú

6 úû

Теперь расшифрование:

é        -        1  ù   é99ù    é*199          2 * 62   1* 28  ù    é 3 ù D

ê                    4ú × ê62ú = ê *299           5 * 62 - 4 * 28ú = ê 0 ú A

ê                      ú  ê    ú    ê                                     ú    ê    ú

ê        -        6  úû   êë28úû    êë*199          4 * 62    6 * 28  úû    êë19úû T

é        -        1 ù  é96ù    é 0 ù A

ê                    4ú × ê60ú = ê12ú M

и т.д.

ê                      ú  ê    ú    ê   ú

ê        -        6  úû   êë24úû    êë 0 úû  A

Т.к. процедуры шифрования и дешифрования строго формализованы, то они сравнительно легко программируются. Недостаток — много арифметических действий для матрицы выше 3-го порядка.

Достоинство — фактически длина ключа (здесь 9 чисел) длиннее групп (здесь 3 числа) циклического шифрования/дешифрования символов текста, что, по-видимому, и увеличивает стойкость шифра.