Криптосистема Хилла
Алгебраический метод, обобщающий аффинную систему подстановок Цезаря, определения n-грамм, был сформулирован Лестером С.Хиллом:
|
|
|
Множество целых
,
для которого определены операции
сложения, вычитания и умножения по
модулю
,
является примером кольца. Кольцо
представляет
собой алгебраическую систему, в которой
определены операции сложения, вычитания
и умножения пар элементов. Эта
алгебраическая система обладает рядом
свойств:
элементы кольца образуют коммутативную группу относительно операции сложения; кроме того, существуют единичный и обратный элементы относительно операции сложения;
умножение и сложение удовлетворяют ассоциативному и дистрибутивному законам.
Мультипликативное обратное
элемента
кольца
может существовать не всегда. Например,
если модуль
,
то значения:
и
-
не могут существовать.Если модуль
является
простым числом
,
то существует обратная величина любого
ненулевого элемента
из
,
поскольку значения:
различаются,
если {
}.
Множество
,
где
-
простое число, является примером
алгебраической системы, называемой
конечным полем. Ненулевые элементы
образуют
мультипликативную группу.Множество
всех n-грамм
с
компонентами из кольца
,
образует векторное пространство
над
кольцом
.
Каждая n-грамма
называется
вектором. В векторном пространстве
для
векторов
определены
операции сложения и вычитания по модулю
,
а также скалярное умножение вектора на
элемент
кольца
.
Сложение и скалярное умножение являются
операциями, удовлетворяющими
коммутативному, ассоциативному и
дистрибутивному законам. Вектор
является
линейной комбинацией векторов: {
},
если
.
Линейное преобразование
является
отображением:
;
;
,
которое удовлетворяет условию линейности
для
всех
в
и
в
.
Линейное преобразование
может
быть представлено матрицей размером
вида:
причем
или
,
.
Базисом для векторного пространства является набор векторов из { }, которые линейно независимы и порождают , Каждый базис для содержит n линейно независимых векторов. Любой набор из п векторов, которые линейно независимы над . является базисом.
Пусть является линейным преобразованием, описываемым матрицей (3.7), причем: .
Если векторы {
}
линейно независимы над
,
тогда их образы {
}
линейно независимы над
только
в том случае, если определитель матрицы
,
обозначаемый как
,
не делится на любое простое
,
которое делит
.
В этом случае поеобоазование
называется
обратимым (или невырожденным) линейным
преобразованием, имеющим обратное
преобразование
:
.
|
|
(3.5) |
где
-
единичная матрица. Кроме того,
также
является линейным преобразованием.
Например, когда и матрица преобразования:
то определитель этой матрицы:
;
.
Поэтому существует обратное преобразование . Нетрудно убедиться, что:
удовлетворяет соотношению:
.
Пусть
является
линейным преобразованием на
c
матрицей
.
Используем это преобразование
для
определения биграммной подстановки &
английском алфавите {
},
Сначала разобьем n-грамму открытого
текста на бкграммы, причем берем n
кратным 2. Например, 12-грамма:
делится на шесть биграмм:
.
Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом из таблицы:
Преобразование биграмм
,
открытого текста в биграммы
,
шифртекста осуществляется в соответствии
с уравнением:
или
,
где
и
-
вектор-столбцы биграмм шифртекста и
открытого текста соответственно.
Получаем:
;
;
;
;
;
;
Заменяя в биграммах шифртекста числа на соответствующие буквы согласно табл. 3.2, получаем 12-грамму шифртекста:
Для расшифрования биграмм
шифртекста
и воссгаиовления биграмм
,
открытого текста необходимо выполнить
обратное преобразование
согласно
уравнению:
.
В рассмотренном примере матрицы
преобразования имели размер
и
шифровались биграммы (пары) букв. Хотя
буква Е может быть зашифрована поразному
в различных парах исходного сообщения,
одна и та же пара, например ЕМ, будет
шифроваться всегда одинаково на
протяжении «сего исходного текста.
Система Хилла является одноалфавигной в широком смысле слова.