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

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

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

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

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

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

Мультипликативное обратное a^-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-грамм = (х₀, х₁, х₂,..., 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. Нетрудно убедиться, что

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

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

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

PA YM OR EM ON EY

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

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

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

Получаем

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

ТЕ ЕЕ PJ WQ DP GY

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

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

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

Не нашли, что искали? Воспользуйтесь поиском: