Криптосистема Хилла

Алгебраический метод, обобщающий аффинную систему подстановок Цезаря, определения n-грамм, был сформулирован Лестером С.Хиллом:

Множество целых , для которого определены операции сложения, вычитания и умножения по модулю , является примером кольца. Кольцо представляет собой алгебраическую систему, в которой определены операции сложения, вычитания и умножения пар элементов. Эта алгебраическая система обладает рядом свойств:

· элементы кольца образуют коммутативную группу относительно операции сложения; кроме того, существуют единичный и обратный элементы относительно операции сложения;

· умножение и сложение удовлетворяют ассоциативному и дистрибутивному законам.

Мультипликативное обратное элемента кольца может существовать не всегда. Например, если модуль , то значения: и - не могут существовать.Если модуль является простым числом , то существует обратная величина любого ненулевого элемента из , поскольку значения: различаются, если { }.

Множество , где - простое число, является примером алгебраической системы, называемой конечным полем. Ненулевые элементы образуют мультипликативную группу.Множество всех n-грамм с компонентами из кольца , образует векторное пространство над кольцом . Каждая n-грамма называется вектором. В векторном пространстве для векторов определены операции сложения и вычитания по модулю , а также скалярное умножение вектора на элемент кольца . Сложение и скалярное умножение являются операциями, удовлетворяющими коммутативному, ассоциативному и дистрибутивному законам. Вектор является линейной комбинацией векторов: { }, если .

Линейное преобразование является отображением: ; ; , которое удовлетворяет условию линейности для всех в и в .

Линейное преобразование может быть представлено матрицей размером вида:

причем или , .

Базисом для векторного пространства является набор векторов из { }, которые линейно независимы и порождают , Каждый базис для содержит n линейно независимых векторов. Любой набор из п векторов, которые линейно независимы над . является базисом.

Пусть является линейным преобразованием, описываемым матрицей (3.7), причем: .

Если векторы { } линейно независимы над , тогда их образы { } линейно независимы над только в том случае, если определитель матрицы , обозначаемый как , не делится на любое простое , которое делит . В этом случае поеобоазование называется обратимым (или невырожденным) линейным преобразованием, имеющим обратное преобразование : .

(3.5)

где - единичная матрица. Кроме того, также является линейным преобразованием.

Например, когда и матрица преобразования:

то определитель этой матрицы: ;

.

Поэтому существует обратное преобразование . Нетрудно убедиться, что:

удовлетворяет соотношению: .

Пусть является линейным преобразованием на c матрицей

.

Используем это преобразование для определения биграммной подстановки & английском алфавите { }, Сначала разобьем n-грамму открытого текста на бкграммы, причем берем n кратным 2. Например, 12-грамма:

делится на шесть биграмм:

.

Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом из таблицы:

Преобразование биграмм , открытого текста в биграммы , шифртекста осуществляется в соответствии с уравнением: или , где и - вектор-столбцы биграмм шифртекста и открытого текста соответственно. Получаем:

;

;

;

;

;

;

Заменяя в биграммах шифртекста числа на соответствующие буквы согласно табл. 3.2, получаем 12-грамму шифртекста:

Для расшифрования биграмм шифртекста и воссгаиовления биграмм , открытого текста необходимо выполнить обратное преобразование согласно уравнению: .

В рассмотренном примере матрицы преобразования имели размер и шифровались биграммы (пары) букв. Хотя буква Е может быть зашифрована поразному в различных парах исходного сообщения, одна и та же пара, например ЕМ, будет шифроваться всегда одинаково на протяжении «сего исходного текста.

Система Хилла является одноалфавигной в широком смысле слова.