ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Криптосистема Хилла
Алгебраический метод, обобщающий аффинную подстановку Цезаря
для определения 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-грамм = (х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-грамму открытого текста на биграммы, причем
PA YM OR EM ON EY
Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом из таблицы:
Преобразование биграмм xj открытого текста в биграммы, уi шифртекста осуществляется в соответствии с уравнением
где хj и уi – вектор - столбцы биграмм шифртекста и открытого текста соответственно. Получаем
Заменяя в биграммах шифртекста числа на соответствующие буквы согласно табл. 2.2, получаем 12-грамму шифртекста
ТЕ ЕЕ PJ WQ DP GY
Для расшифрования биграмм уi шифртекста и восстановления биграмм открытого текста необходимо выполнить обратное преобразование -1 согласно уравнению
В рассмотренном примере матрицы преобразования имели размер 2x2 и шифровались биграммы (пары) букв. Хотя буква Е может быть зашифрована по-разному в различных парах исходного сообщения, одна и та же пара, например ЕМ, будет шифроваться всегда одинаково на протяжении всего исходного текста. Система Хилла является одноалфавитной в широком смысле слова.
Не нашли, что искали? Воспользуйтесь поиском:
|