<< Предыдущая

стр. 6
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Ea,b : Z m > Z m ,
E a,b : t > E a,b (t) ,
E a,b (t) = at + b (mod m), (2.4)
где a, b – целые числа, 0 ? a, b < m, НОД ( a, m ) = 1.
В данном преобразовании буква, соответствующая числу t, заменяeтся на букву, соответст-
вующую числовому значению ( at + b ) по модулю m.
Следует заметить, что преобразование E a,b (t) является взаимно однозначным отображением
на множестве Z m только в том случае, если наибольший общий делитель чисел a и m, обозначае-
мый как НОД (a, m), равен единице, т.e. a и m должны быть взаимно простыми числами.
Например, пусть m = 26, a = 3, b = 5. Тогда, очевидно, НОД (3,26) = 1, и мы получаем сле-
дующее соответствие между числовыми кодами букв:
t 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3t+5 5 8 11 14 17 20 23 0 3 6 9 12 15 18 21 24 1 4 7 10 13 16 19 22 25 2

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

ABCDEFGH I J K LMNOPQRSTUVWX Y Z
F I LORUXADGJ MPSVYBEHKNQTWZ C

Исходное сообщение HOPE преобразуется
в шифртекст AVYR
Достоинством аффинной системы является удобное управление ключами – ключи шифрова-
ния и расшифрования представляются в компактной форме в виде пары чисел (a, b). Недостатки
аффинной системы аналогичны недостаткам системы шифрования Цезаря.
Аффинная система использовалась на практике несколько веков назад, а сегодня ее приме-
нение ограничивается большей частью иллюстрациями основных криптологических положений.
Система Цезаря с ключевым словом
Система шифрования Цезаря с ключевым словом является одноалфавитной системой под-
становки. Особенностью этой системы является использование ключевого слова для смещения и из-
менения порядка символов в алфавите подстановки [79].
Выберем некоторое число k, 0 ? k < 25 , и слово или короткую фразу в качестве ключевого
слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбраны слово DIP-
LOMAT в качестве ключевого слова и число k = 5.
Ключевое слово записывается под буквами алфавита, начиная с буквы, числовой код ко-
торой совпадает с выбранным числом k:
012345 10 15 20 25
ABCDEFGH I J K L MNO P QR S T U VWX Y Z
D I P L OMA T
Оставшиеся буквы алфавита подстановки записываются после ключевого слова в алфавит-
ном порядке:
5
ABCDEFGH I J K L MNO P QR S T U VWX Y Z
VWX Y Z D I P L O M A T B C E F G H J K N Q R S U
Теперь мы имеем подстановку для каждой буквы произвольного сообщения.
Исходное сообщение SEND MORE MONEY
шифруется как HZBY TCGZ TCBZS
Следует отметить, что требование о различии всех букв ключевого слова не обязательно.
Можно просто записать ключевое слово (или фразу) без повторения одинаковых букв. Например,
ключевая фраза
КАК ДЫМ ОТЕЧЕСТВА НАМ СЛАДОК И ПРИЯТЕН
и число k = 3 порождают следующую таблицу подстановок:
0 3
А Б ВГДЕЖЗ ИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ
Ъ Э Ю К А Д Ы М О Т Е Ч С В Н Л И П РЯ Б Г Ж З Й У Ф Х ЦШ Щ Ь
Несомненным достоинством системы Цезаря с ключевым словом является то, что количество
возможных ключевых слов практически неисчерпаемо. Недостатком этой системы является возмож-
ность взлома шифртекста на основе анализа частот появления букв.
Шифрующие таблицы Трисемуса
В 1508 г. аббат из Германии Иоганн Трисемус написал печатную работу по криптологии под
названием "Полиграфия". В этой книге он впервые систематически описал применение шифрующих
таблиц, заполненных алфавитом в случайном порядке [32]. Для получения такого шифра замены
обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу
сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. За-
тем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку. Поскольку ключе-
вое слово или фразу легко хранить в памяти, то такой подход упрощал процессы шифрования и рас-
шифрования.
Поясним этот метод шифрования на примере. Для русского алфавита шифрующая таблица
может иметь размер 4?8. Выберем в качестве ключа слово БАНДЕРОЛЬ. Шифрующая таблица с та-
ким ключом показана на рис. 2.6.

Б А Н Д Е Р О Л
Ь В Г Ж З И Й К
М П С Т У Ф Х Ц
Ч Ш Щ Ы Ъ Э Ю Я

Рис. 2.6. Шифрующая таблица с ключевым словом БАНДЕРОЛЬ


Как и в случае полибианского квадрата, при шифровании находят в этой таблице очередную
букву открытого текста и записывают в шифртекст букву, расположенную ниже ее в том же столбце.
Если буква текста оказывается в нижней строке таблицы, тогда для шифртекста берут самую верх-
нюю букву из того же столбца.
Например, при шифровании с помощью этой таблицы сообщения
ВЫЛЕТАЕМПЯТОГО
получаем шифртекст
ПДКЗЫВЗЧШЛЫЙСЙ
Такие табличные шифры называются монограммными, так как шифрование выполняется по
одной букве. Трисемус первым заметил, что шифрующие таблицы позволяют шифровать сразу по
две буквы. Такие шифры называются биграммными.
Биграммный шифр Плейфейра
Шифр Плейфейра, изобретенный в 1854 г., является наиболее известным биграммным шиф-
ром замены. Он применялся Великобританией во время первой мировой войны. Основой шифра
Плейфейра является шифрующая таблица со случайно расположенными буквами алфавита исход-
ных сообщений.
Для удобства запоминания шифрующей таблицы отправителем и получателем сообщений
можно использовать ключевое слово (или фразу) при заполнении начальных строк таблицы. В целом
структура шифрующей таблицы системы Плейфейра полностью аналогична структуре шифрующей
таблицы Трисемуса. Поэтому для пояснения процедур шифрования и расшифрования в системе
Плейфейра воспользуемся шифрующей таблицей Трисемуса из предыдущего раздела (см. рис 2.6).
Процедура шифрования включает следующие шаги.
1. Открытый текст исходного сообщения разбивается на пары букв (биграммы). Текст должен иметь
четное количество букв и в нем не должно быть биграмм, содержащих две одинаковые буквы. Ес-
ли эти требования не выполнены, то текст модифицируется даже из-за незначительных орфогра-
фических ошибок.
2. Последовательность биграмм открытого текста преобразуется с помощью шифрующей таблицы в
последовательность биграмм шифртекста по следующим правилам:
2а.Если обе буквы биграммы открытого текста не попадают на одну строку или столбец (как, на-
пример, буквы А и Й в табл. на рис.2.6), тогда находят буквы в углах прямоугольника, опреде-
ляемого данной парой букв. (В нашем примере это – буквы АЙОВ. Пара букв АЙ отображается
в пару ОВ. Последовательность букв в биграмме шифртекста должна быть зеркально располо-
женной по отношению к последовательности букв в биграмме открытого текста.)
2б.Если обе буквы биграммы открытого текста принадлежат одному столбцу таблицы, то буквами
шифртекста считаются буквы, которые лежат под ними. (Например, биграмма НС дает биграм-
му шифртекста ГЩ.) Если при этом буква открытого текста находится в нижней строке, то для
шифртекста берется соответствующая буква из верхней строки того же столбца. (Например,
биграмма ВШ дает биграмму шифртекста ПА.)
2в.Если обе буквы биграммы открытого текста принадлежат одной строке таблицы, то буквами
шифртекста считаются буквы, которые лежат справа от них. (Например, биграмма НО дает би-
грамму шифртекста ДЛ.) Если при этом буква открытого текста находится в крайнем правом
столбце, то для шифра берут соответствующую букву из левого столбца в той же строке. (На-
пример, биграмма ФЦ дает биграмму шифртекста ХМ.)
Зашифруем текст
ВСЕ ТАЙНОЕ СТАНЕТ ЯВНЫМ
Разбиение этого текста на биграммы дает
ВС ЕТ АЙ НО ЕС ТА НЕ ТЯ ВН ЫМ
Данная последовательность биграмм открытого текста преобразуется с помощью шифрующей таб-
лицы (см. рис. 2.6) в следующую последовательность биграмм шифртекста
ГП ДУ ОВ ДЛ НУ ПД ДР ЦЫ ГА ЧТ
При расшифровании применяется обратный порядок действий.
Следует отметить, что шифрование биграммами резко повышает стойкость шифров к вскры-
тию. Хотя книга И.Трисемуса "Полиграфия" была относительно доступной, описанные в ней идеи по-
лучили признание лишь спустя три столетия. По всей вероятности, это было обусловлено плохой ос-
ведомленностью криптографов о работах богослова и библиофила Трисемуса в области криптогра-
фии [32].
Криптосистема Хилла
Алгебраический метод, обобщающий аффинную подстановку Цезаря
E a,b : Z m > Z m ,
Ea,b (t) = t > at + b (mod m)
для определения n-грамм, был сформулирован Лестером С.Хиллом [79].
Множество целых Z m , для которого определены операции сложения, вычитания и умноже-
ния по модулю m, является примером кольца. Кольцо R представляет собой алгебраическую систе-
му, в которой определены операции сложения, вычитания и умножения пар элементов. Эта алгеб-
раическая система обладает рядом свойств:
• элементы кольца R образуют коммутативную группу относительно операции сложения; кроме того,
существуют единичный и обратный элементы относительно операции сложения;
• умножение и сложение удовлетворяют ассоциативному и дистрибутивному законам.
Мультипликативное обратное ?–1 элемента ? кольца может существовать не всегда. На-
пример, если модуль m = 26, то значения 2–1 (mod 26) и 13–1 (mod 26) не могут существовать.
Если модуль m является простым числом p, то существует обратная величина любого нену-
левого элемента t из Z p (при m = p), поскольку значения
t (mod m), 2t (mod m), 3t (mod m), ..., (p – 1) t (mod m)
различаются, если 1 ? t ? p – 1.
Множество Z p , где p – простое число, является примером алгебраической системы, назы-
ваемой конечным полем. Ненулевые элементы Z p образуют мультипликативную группу.
Множество всех n-грамм x = (x0, x1, x2, …, xn–1) с компонентами из кольца Z m образует век-
торное пространство Z m,n над кольцом Z m . Каждая n-грамма x называется вектором. В векторном
пространстве Z m,n для векторов x определены операции сложения и вычитания по модулю n, а
также скалярное умножение вектора на элемент t кольца Z m . Сложение и скалярное умножение
являются операциями, удовлетворяющими коммутативному, ассоциативному и дистрибутивному за-
конам. Вектор x является линейной комбинацией векторов
{ x (i) : 0 ? i < L}, если
x = t 0 x (0) + t1x (1) + ... + t L?1x (L?1) (mod m). (2.5)
Линейное преобразование T является отображением:
T : Z m,n > Z m,n ,
T : x > y , y = T (x) , (2.6)
которое удовлетворяет условию линейности
T = (t ? x + s ? y) = t ? T (x) + s ? T (y) (mod m)
для всех s, t в Z m и x, y в Z m,n .
Линейное преобразование T может быть представлено матрицей размером n?n вида

? 0,0 ? 0,1 ? 0,j ? 0,n-1
… …
? 1,0 ? 1,1 ? 1,j ? 1,n-1
… …











(2.7)
T= ? i,0 ? i,1 ? i,j ? j,n-1
… …











? n-1,0 ? n-1,1 ? n-1,j … ? n-1,n-1


причем
yi = ? i,0 ? x0 + ? i,1 ? x1 + … + ? ij ? x j + … + ? i,n–1 ? xn–1 (mod m)
или
n ?1

? ? ij ? xj (mod m), 0 ? i ? n – 1.
yi =
j=0

Базисом для векторного пространства Z m,n является набор векторов из { x (i) : 0 ? i < L}, кото-
рые линейно независимы и порождают Z m,n . Каждый базис для Z m,n содержит n линейно незави-
симых векторов. Любой набор из n векторов, которые линейно независимы над Z m,n , является ба-
зисом.
Пусть T является линейным преобразованием, описываемым матрицей (2.7), причем
T : Z m,n > Z m,n .

Если векторы { x (i) : 0 ? i < n} линейно независимы над Z m,n , тогда их образы { T (x (i) ) : 0 ? i < n}
линейно независимы над Z m,n только в том случае, если определитель матрицы T , обозначаемый
как det ( T ), не делится на любое простое p , которое делит m. В этом случае преобразование T на-
зывается обратимым (или невырожденным) линейным преобразованием, имеющим обратное преоб-
разование T ?1 :
T ?1 : Z m,n > Z m,n ,
T T ?1 = T ?1 T = ? , (2.8)
где ? – единичная матрица. Кроме того, T ?1 также является линейным преобразованием.
Например, когда m=26 и матрица преобразования
?3 3?
T=? ,
2 5?
? ?
то определитель этой матрицы
det ( T ) = 9 = 1 (mod 2),
det ( T ) = 9 = 9 (mod 13).

Поэтому существует обратное преобразование T ?1 . Нетрудно убедиться, что
удовлетворяет соотношению
?15 17?
?1
T =? ?
?20 9 ?
?1 0?
?1
?1
=T T= I =?
TT ?.
0 1?
?
Пусть T является линейным преобразованием на Z26,2 с матрицей
?3 3?
T=? .
2 5?
? ?
Используем это преобразование T для определения би-граммной подстановки в английском
алфавите {ABCDEFGH..XYZ}.
Сначала разобьем n-грамму открытого текста на биграммы, причем выберем n кратным 2. Например,
12-грамма PAYMOREMONEY делится на шесть биграмм:
PA YM OR EM ON EY
Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом
из таблицы:
РА > 15 0; YM > 24 12; OR > 14 17;
< < <
EM > 4 12; ON > 14 13; EY > 4 24;
< < <

Преобразование биграмм x j открытого текста в биграммы y i шифртекста осуществляется в
соответствии с уравнением
y j = T ? x j (mod 26)
или

<< Предыдущая

стр. 6
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>