Шифрующие таблицы Трисемуса
В 1508 г. аббат из Германии Иоганн Трисемус издал печатную работу но криптологии под названием "Полиграфия". В этой книге он впервые систематически описал применение 'шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку. Поскольку ключевое слово или фразу легко хранить в памяти, то такой подход упрощал процессы шифрования и расшифрования.
Поясним этот метод
шифрования на примере. Для русского
алфавита шифрующая таблица может иметь
размер
.
Выберем в качестве ключа слово: БАНДЕРОЛЬ.
Шифрующая таблица с таким ключом показана на рис. 1.2:
Рис. 1.2. Шифруюшая таблица с ключевым словом БАНДЕРОЛЬ.
Б |
А |
Н |
Д |
Е |
Р |
О |
Л |
Ь |
В |
Г |
Ж |
З |
И |
Й |
К |
М |
П |
С |
Т |
У |
Ф |
Х |
Ц |
Ч |
Ш |
Щ |
Ы |
Ъ |
Э |
Ю |
Я |
Как и в случае полибианского квадрата, при шифровании находят в этой таблице очередную букву открытого текста и записывают в шифртекст букву, расположенную ниже ее в том же столбце. Если буква текста оказывается в нижней строке таблицы, тогда для шифртекста берут самую верхнюю букву из того же столбца. Такие табличные шифры называются монограммными, так как шифрование выполняется по одной букве. Трисемус первым заметил, что шифрующие таблицы позволяют шифровать сразу по две буквы. Такие шифры называются биграммными.
Криптосистема Хилла
Алгебраический метод, обобщающий аффинную систему подстановок Цезаря, определения n-грамм, был сформулирован Лестером С.Хиллом:
|
|
|
Множество целых
,
для которого определены операции
сложения, вычитания и умножения по
модулю
,
является примером кольца. Кольцо
представляет
собой алгебраическую систему, в которой
определены операции сложения, вычитания
и умножения пар элементов. Эта
алгебраическая система обладает рядом
свойств:
элементы кольца образуют коммутативную группу относительно операции сложения; кроме того, существуют единичный и обратный элементы относительно операции сложения;
умножение и сложение удовлетворяют ассоциативному и дистрибутивному законам.
Мультипликативное
обратное
элемента
кольца
может существовать не всегда. Например,
если модуль
,
то значения:
и
-
не могут существовать.Если модуль
является
простым числом
,
то существует обратная величина любого
ненулевого элемента
из
,
поскольку значения:
различаются,
если {
}.
Множество
,
где
-
простое число, является примером
алгебраической системы, называемой
конечным полем. Ненулевые элементы
образуют
мультипликативную группу.Множество
всех n-грамм
с
компонентами из кольца
,
образует векторное пространство
над
кольцом
.
Каждая n-грамма
называется
вектором. В векторном пространстве
для
векторов
определены
операции сложения и вычитания по модулю
,
а также скалярное умножение вектора на
элемент
кольца
.
Сложение и скалярное умножение являются
операциями, удовлетворяющими
коммутативному, ассоциативному и
дистрибутивному законам. Вектор
является
линейной комбинацией векторов: {
},
если
.
Линейное
преобразование
является
отображением:
;
;
,
которое удовлетворяет условию линейности
для
всех
в
и
в
.
Линейное
преобразование
может
быть представлено матрицей размером
вида:
причем
или
,
.
Базисом для векторного пространства является набор векторов из { }, которые линейно независимы и порождают , Каждый базис для содержит n линейно независимых векторов. Любой набор из п векторов, которые линейно независимы над . является базисом.
Пусть является линейным преобразованием, описываемым матрицей (3.7), причем: .
Если векторы {
}
линейно независимы над
,
тогда их образы {
}
линейно независимы над
только
в том случае, если определитель матрицы
,
обозначаемый как
,
не делится на любое простое
,
которое делит
.
В этом случае поеобоазование
называется
обратимым (или невырожденным) линейным
преобразованием, имеющим обратное
преобразование
:
.
|
|
(1.3) |
где
-
единичная матрица. Кроме того,
также
является линейным преобразованием.
Например, когда
и
матрица преобразования:
то
определитель этой матрицы:
;
.
Поэтому существует обратное преобразование . Нетрудно убедиться, что:
удовлетворяет
соотношению:
.
Пусть
является
линейным преобразованием на
c
матрицей
.
Используем это
преобразование
для
определения биграммной подстановки &
английском алфавите {
},
Сначала разобьем n-грамму открытого
текста на бкграммы, причем берем n
кратным 2. Например, 12-грамма:
делится на шесть биграмм:
.
Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом из таблицы:
Преобразование
биграмм
,
открытого текста в биграммы
,
шифртекста осуществляется в соответствии
с уравнением:
или
,
где
и
-
вектор-столбцы биграмм шифртекста и
открытого текста соответственно.
Получаем:
;
;
;
;
;
;
Заменяя в биграммах шифртекста числа на соответствующие буквы согласно табл. 3.2, получаем 12-грамму шифртекста:
Для расшифрования
биграмм
шифртекста
и воссгаиовления биграмм
,
открытого текста необходимо выполнить
обратное преобразование
согласно
уравнению:
.
В рассмотренном
примере матрицы преобразования имели
размер
и
шифровались биграммы (пары) букв. Хотя
буква Е может быть зашифрована поразному
в различных парах исходного сообщения,
одна и та же пара, например ЕМ, будет
шифроваться всегда одинаково на
протяжении «сего исходного текста.
Система Хилла является одноалфавигной в широком смысле слова.
Основная литература: [1, 5, 6]
Дополнительная литература: [2-4]
Контрольные вопросы:
1. В чем особенность шифрования шифром простой замены.
2. Чем отличаются распределения символов открытого и зашифрованного текстов.
3. Чем отличаются распределения пар символов открытого и зашифрованного текстов.
4. Чем отличаются распределения троек символов открытого и зашифрованного текстов.
Лабораторная работа № 4. Исследование шифра Вернама.
Цель работы – сравнительный анализ статистических характеристик открытого и зашифрованного текстов по методу «Исследование шифра Вернама».