![](/user_photo/2706_HbeT2.jpg)
Криптосистема Хилла
.docКриптосистема Хилла
Алгебраический метод, обобщающий аффинную подстановку Цезаря
для определения n-грамм, был сформулирован Лестером С. Хиллом [79].
Множество
целых
,
для которого определены операции
сложения, вычитания и умножения по
модулю m, является примером кольца.
Кольцо R представляет собой алгебраическую
систему, в которой определены операции
сложения, вычитания и умножения пар
элементов. Эта алгебраическая система
обладает рядом свойств:
• элементы кольца R образуют коммутативную группу относительно операции сложения; кроме того, существуют единичный и обратный элементы относительно операции сложения;
• умножение и сложение удовлетворяют ассоциативному и дистрибутивному законам.
Мультипликативное обратное -1 элемента а кольца может существовать не всегда. Например, если модуль m = 26, то значения 2-1(mod 26) и 13-1(mod 26) не могут существовать.
Если
модуль m является простым числом р, то
существует обратная
величина любого ненулевого элемента t
из
(при
m = р), поскольку значения
t (mod m), 2t (mod m), 3t (mod m),..., (p -1) t (mod m)
различаются, если 1 t p -1.
Множество
,
где р - простое число, является примером
алгебраической системы, называемой
конечным полем. Ненулевые элементы
образуют
мультипликативную группу.
Множество
всех n-грамм
=
(х0,
х1,
х2,...,
x n-1)
с компонентами из кольца
образует
векторное пространство
над
кольцом
.
Каждая n-грамма х называется вектором.
В векторном пространстве
для
векторов х определены операции сложения
и вычитания по модулю n,
а также скалярное умножение вектора на
элемент t кольца
.
Сложение и скалярное умножение
являются
операциями, удовлетворяющими
коммутативному, ассоциативному и
дистрибутивному законам. Вектор
является
линейной комбинацией векторов
(2.5)
Линейное
преобразование
является
отображением:
(2.6)
которое удовлетворяет условию линейности
для
всех s, t в
Линейное
преобразование Т может быть представлено
матрицей размером nхn вида
(2.7)
причем
или
Базисом
для векторного пространства
является
набор векторов из
которые линейно независимы и порождают
.
Каждый базис для
содержит
n линейно независимых векторов. Любой
набор из n векторов, которые линейно
независимы над
является
базисом.
Пусть
является
линейным преобразованием, описываемым
матрицей (2.7), причем
:
Если
векторы
линейно
независимы над
,
тогда их образы линейно
независимы
над
только
в том случае, если определитель матрицы
,
обозначаемый как det (
),
не делится на любое простое р, которое
делит m.
В этом случае преобразование
называется
обратимым (или невырожденным) линейным
преобразованием, имеющим обратное
преобразование
-1:
-1
:
,
-1
=
-1T
=
(2.8)
где
-единичная
матрица. Кроме того,
-1
также
является линейным преобразованием.
Например, когда m = 26 и матрица преобразования
то определитель этой матрицы
det()
= 9 = 1(mod 2),
det()
= 9 = 9 (mod 13)
Поэтому
существует обратное преобразование
-1.
Нетрудно убедиться,
что
удовлетворяет соотношению
Пусть
является
линейным преобразованием на Z26.2
c
матрицей
Используем
это преобразование
для
определения биграммной подстановки в
английском алфавите {ABCDEFGH..XYZ}. Сначала
разобьем n-грамму открытого текста на
биграммы, причем
выберем n кратным 2.
Например, 12-грамма PAYMOREMONEY делится на
шесть биграмм:
PA YM OR EM ON EY
Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом из таблицы:
Преобразование биграмм xj открытого текста в биграммы, уi шифртекста осуществляется в соответствии с уравнением
где хj и уi – вектор - столбцы биграмм шифртекста и открытого текста соответственно.
Получаем
Заменяя в биграммах шифртекста числа на соответствующие буквы согласно табл. 2.2, получаем 12-грамму шифртекста
ТЕ ЕЕ PJ WQ DP GY
Для
расшифрования биграмм уi шифртекста и
восстановления биграмм
открытого
текста необходимо выполнить обратное
преобразование
-1
согласно
уравнению
В рассмотренном примере матрицы преобразования имели размер 2x2 и шифровались биграммы (пары) букв. Хотя буква Е может быть зашифрована по-разному в различных парах исходного сообщения, одна и та же пара, например ЕМ, будет шифроваться всегда одинаково на протяжении всего исходного текста.
Система Хилла является одноалфавитной в широком смысле слова.