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

Алгебраический метод, обобщающий аффинную подстановку Цезаря

Е_a,b: Z_m ® Z_m,

E_a,b(t) = t® at + b(mod m)

для определения n-грамм, был сформулирован Лестером С. Хиллом.

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

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

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

Мультипликативное обратное a^-1 элемента a кольца может существовать не всегда. Например, если модуль m = 26, то значе­ния 2^-1(mod 26) и 13^-1(mod 26) не могут существовать.

Если модуль m является простым числом р, то существует обратная величина любого ненулевого элемента t из Z_p (при m = р), поскольку значения

t (mod m), 2t (mod m), 3t (mod m),....,(p-1) t (mod m)

различаются, если 1 £ t £ p -1.

Множество Z_p, где р – простое число, является примером алгебраической системы, называемой конечным полем. Ненулевые элементы Z_p образуют мультипликативную группу.

Множество всех n -грамм х = (х₀, х,, х₂,.... x_n-1) с компонентами из кольца Z_m образует векторное пространство Z_m,n над кольцом Z_m. Каждая n -грамма х называется вектором. В векторном про­странстве Z_mn для векторов х определены операции сложения и вычитания по модулю n, а также скалярное умножение вектора на элемент t кольца Z_m. Сложение и скалярное умножение являются операциями, удовлетворяющими коммутативному, ассоциативному и дистрибутивному законам. Вектор х является линейной комбинацией векторов

{х⁽ⁱ⁾: 0 <i < L}, если

х = t₀x⁽⁰⁾ + t₁x⁽¹⁾ +... + t_L-1.,x^(L-¹⁾(mod m).

Линейное преобразование Т является отображением:

T: Z_m,n ® Z_m,n,, T: x ® y, y=T(x),

которое удовлетворяет условию линейности

T = (t´x + s´y)-t´Т(х) + s´Т(у) (mod m) для всех s, t в Z_m и х, у в Z_{m п}.

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

 

 

причем.

Базисом для векторного пространства является набор векторов из {х⁽ⁱ⁾: 0 < i < L}, которые линейно независимы и порождают .Каждый базис для содержит n линейно независи­мых векторов Любой набор из n векторов, которые линейно независимы над является базисом.

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

Если векторы {х⁽ⁱ⁾ 0 < i < n} линейно независимы над , тогда их образы {Т(х⁽ⁱ⁾): 0 £ i < п} линейно независимы над только в том случае, если определитель матрицы , обозначаемый как det (Т), не делится на любое простое р, которое делит m. В этом случае преобразование называется обратимым (или невырожденным) линейным преобразованием, имеющим обратное преобразование , где l -единичная матрица. Кроме того, также является линейным преобразованием.

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

,

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

det(T) = 9 = 1(mod 2),

det(T) = 9 = 9{mod 13).

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

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

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

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

PA YM OR EM ON EY

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

.

Преобразование биграмм открытого текста в биграммы , шифртекста осуществляется в соответствии с уравнением

или

где и – вектор столбцов биграмм шифртекста и открытого текста соответственно.

Получаем

,

.

 

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

ТЕ ЕЕ PJ WQ DP GY

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

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