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

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

ОГЛАВЛЕНИЕ

Следующая >>

Множество значений ключа образует ключевое пространство K .
Далее рассматриваются традиционные (классические) методы шифрования, отличающиеся
симметричной функцией шифрования. К ним относятся шифры перестановки, шифры простой и
сложной замены, а также некоторые их модификации и комбинации. Следует отметить, что комбина-
ции шифров перестановок и шифров замены образуют все многообразие применяемых на практике
симметричных шифров.
Приводимые сведения о шифрах каждой группы даются по возможности в хронологическом
порядке, что позволяет постепенно вводить читателя в сферу криптографии. Как известно, довольно
трудно понять концептуальную схему науки, ее модели и методы исследования, если не иметь хотя
бы общего представления об истории развития этой науки.


2.2. Шифры перестановки
При шифровании перестановкой символы шифруемого текста переставляются по определен-
ному правилу в пределах блока этого текста. Шифры перестановки являются самыми простыми и,
вероятно, самыми древними шифрами.
Шифрующие таблицы
С начала эпохи Возрождения (конец XIV столетия) начала возрождаться и криптография. На-
ряду с традиционными применениями криптографии в политике, дипломатии и военном деле появ-
ляются и другие задачи – защита интеллектуальной собственности от преследований инквизиции или
заимствований злоумышленников. В разработанных шифрах перестановки того времени применяют-
ся шифрующие таблицы, которые в сущности задают правила перестановки букв в сообщении.
В качестве ключа в шифрующих таблицах используются:
• размер таблицы;
• слово или фраза, задающие перестановку;
• особенности структуры таблицы.
Одним из самых примитивных табличных шифров перестановки является простая переста-
новка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром ски-
тала. Например, сообщение
ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ
записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7
столбцов показан на рис. 2.1.
После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста
считывают содержимое таб-

Т Н П В Е Г Л
Е А Р А Д О Н
Р Т И Е Ь В О
М О Б Т М П Ч
И Р Ы С О О Ь

Рис. 2.1. Заполнение таблицы из 5 строк и 7 столбцов
лицы по строкам. Если шифртекст записывать группами по пять букв, получается такое шифрованное
сообщение:
ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ
Естественно, отправитель и получатель сообщения должны заранее условиться об общем
ключе в виде размера таблицы. Следует заметить, что объединение букв шифртекста в 5-буквенные
группы не входит в ключ шифра и осуществляется для удобства записи несмыслового текста. При
расшифровании действия выполняют в обратном порядке.
Несколько большей стойкостью к раскрытию обладает метод шифрования, называемый оди-
ночной перестановкой по ключу. Этот метод отличается от предыдущего тем, что столбцы таблицы
переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы.
Применим в качестве ключа, например, слово
ПЕЛИКАН,
а текст сообщения возьмем из предыдущего примера. На рис. 2.2 показаны две таблицы, заполнен-
ные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до
перестановки, а правая таблица – заполнению после перестановки.

Ключ
П Е Л И К А Н А Е И К Л Н П
7 2 5 3 4 1 6 1 2 3 4 5 6 7
Т Н П В Е Г Л Г Н В Е П Л Т
Е А Р А Д О Н О А А Д Р Н Е
Р Т И Е Ь В О В Т Е Ь И О Р
М О Б Т М П Ч П О Т М Б Ч М
И Р Ы С О О Ь О Р С О Ы Ь И

До перестановки После перестановки

Рис. 2.2. Таблицы, заполненные ключевым словом и текстом сообщения


В верхней строке левой таблицы записан ключ, а номера под буквами ключа определены в
соответствии с естественным порядком соответствующих букв ключа в алфавите. Если бы в ключе
встретились одинаковые буквы, они бы были понумерованы слева направо. В правой таблице столб-
цы переставлены в соответствии с упорядоченными номерами букв ключа.
При считывании содержимого правой таблицы по строкам и записи шифртекста группами по
пять букв получим шифрованное сообщение:
ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ
Для обеспечения дополнительной скрытности можно повторно зашифровать сообщение, ко-
торое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой. В
случае двойной перестановки столбцов и строк таблицы перестановки определяются отдельно для
столбцов и отдельно для строк. Сначала в таблицу записывается текст сообщения, а потом пооче-
редно переставляются столбцы, а затем строки. При расшифровании порядок перестановок должен
быть обратным.
Пример выполнения шифрования методом двойной перестановки показан на рис. 2.3. Если
считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следую-
щее:
ТЮАЕ ООГМ РЛИП ОЬСВ
Ключом к шифру двойной перестановки служит последовательность номеров столбцов и но-
меров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).

4 1 3 2 1 2 3 4 1 2 3 4
3 П Р И Л 3 Р Л И П 1 Т Ю А Е
1 Е Т А Ю 1 Т Ю А Е 2 О О Г М
4 В О С Ь 4 О Ь С В 3 Р Л И П
2 М О Г О 2 О О Г М 4 О Ь С В

Исходная таблица Перестановка столбцов Перестановка строк

Рис. 2.3. Пример выполнения шифрования методом двойной перестановки

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:
• для таблицы 3х3 36 вариантов;
• для таблицы 4х4 576 вариантов;
• для таблицы 5х5 14400 вариантов.
Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто
"взламывается" при любом размере таблицы шифрования.
Применение магических квадратов
В средние века для шифрования перестановкой применялись и магические квадраты.
Магическими квадратами называют квадратные таблицы с вписанными в их клетки последо-
вательными натуральными числами, начиная от 1, которые дают в сумме по каждому столбцу, каж-
дой строке и каждой диагонали одно и то же число.
Шифруемый текст вписывали в магические квадраты в соответствии с нумерацией их клеток.
Если затем выписать содержимое такой таблицы по строкам, то получится шифртекст, сформирован-
ный благодаря перестановке букв исходного сообщения. В те времена считалось, что созданные с
помощью магических квадратов шифртексты охраняет не только ключ, но и магичес-кая сила.
Пример магического квадрата и его заполнения сообщением
ПРИЛЕТАЮ ВОСЬМОГО
показан на рис. 2.4.

16 3 2 13 О И Р М

5 10 11 8 Е О С Ю

9 6 7 12 В Т А Ь

4 15 14 1 Л Г О П

Рис. 2.4. Пример магического квадрата 4х4 и его заполнения сообщением
ПРИЛЕТАЮ ВОСЬМОГО


Шифртекст, получаемый при считывании содержимого правой таблицы по строкам, имеет
вполне загадочный вид:
ОИРМ ЕОСЮ ВТАЬ ЛГОП
Число магических квадратов быстро возрастает с увеличением размера квадрата. Существу-
ет только один магический квадрат размером 3?3 (если не учитывать его повороты). Количество ма-
гических квадратов 4?4 составляет уже 880, а количество магических квадратов 5?5 – около 250000.
Магические квадраты средних и больших размеров могли служить хорошей базой для обес-
печения нужд шифрования того времени, поскольку практически нереально выполнить вручную пе-
ребор всех вариантов для такого шифра.


2.3. Шифры простой замены
При шифровании заменой (подстановкой) символы шифруемого текста заменяются символа-
ми того же или другого алфавита с заранее установленным правилом замены. В шифре простой за-
мены каждый символ исходного текста заменяется символами того же алфавита одинаково на всем
протяжении текста. Часто шифры простой замены называют шифрами одноалфавитной подстановки.
Система шифрования Цезаря
Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подста-
новки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который
использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).
При шифровании исходного текста каждая буква заменялась на другую букву того же алфави-
та по следующему правилу. Заменяющая буква определялась путем смещения по алфавиту от ис-
ходной буквы на К букв. При достижении конца алфавита выполнялся циклический переход к его
началу. Цезарь использовал шифр замены при смещении К = 3. Такой шифр замены можно задать
таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифртекста. Со-
вокупность возможных подстановок для К = 3 показана в табл. 2.3.
Например, послание Цезаря
VENI VIDI VICI
(в переводе на русский означает "Пришел, Увидел, Победил"), направленное его другу Аминтию по-
сле победы над понтийским царем Фарнаком, сыном Митридата, выглядело бы в зашифрованном
виде так:
YHQL YLGL YLFL
Таблица 2.3
Одноалфавитные подстановки (К = 3, m = 26)
A>D J>M S>V
B>E K>N T>W
C>F L>O U>X
D>G M>P V>Y
E>H N>Q W>Z
F>I O>R X>A
G>J P>S Y>B
H>K Q>T Z>C
I>L R>U

Выполним математический анализ шифра простой замены (подстановки) на основе понятий,
введенных в начале гл.2 [113].
Подстановка в алфавите Z m является взаимно однозначным отображением ? из Z m на
Zm :
? : t > ? (t),
которое заменяет букву t открытого текста на букву ? (t) шифртекста. Множество всех подстановок на
Z m называется симметричной группой Z m и обозначается S Y M ( Z m ).
Симметричная группа S Y M ( Z m ) обладает следующими свойствами:
1. Замкнутость. Произведение подстановок ?1?2 является подстановкой:
? ?1
? : Z m ?? > Z m ??> Z m ,
?2



? : t > ?1 (?2 (t)).
2. Ассоциативность. Оба способа заключения в скобки произведения подстановок ?1?2?3:
?1 (?2?3) = (?1?2) ?3
дают одинаковый результат.
3. Существование единичного элемента. Подстановка ?, определенная как
? (t) = t, 0 ? t < m,
является единственным единичным элементом группы S Y M ( Z m ) по умножению:
?? = ?? для всех ? ? S Y M ( Z m ).
4. Существование обратных элементов. Для каждой подстановки ? имеется взаимно одно-
значно определенная обратная подстановка, обозначаемая ?–1, которая удовлетворяет соотношению:
??–1 = ?.
Указанные свойства являются аксиомами группы.
Ключ К подстановки для алфавита Z m представляет собой последовательность элементов
симметричной группы из Z m :
К = (?0,?1, …, ?n–1, …), ?n ? S Y M ( Z m ), 0 ? n < ?.
Подстановка, определяемая ключом К, является криптографическим преобразованием ЕК,
которое шифрует n-грамму (x0, x1, x2, …, xn–1) открытого текста в n-грамму (y0, y1, y2, …, yn–1) шиф-
ртекста, где
yi = ?i (xi), 0 ? i < n,
для каждого n, n = 1, 2, 3, ... .
Криптографическое преобразование ЕК называется одноалфавитной подстановкой, если
значение ?i одинаково для каждого i, i = 0, 1, 2, ...; в противном случае преобразование ЕК называется
многоалфавитной подстановкой.
На рис.2.5 представлена схема реализации подстановки ЕК.
Источник Подстановка
…, xn–1, …, x1, x0 …, yn–1, …, y1, y0
открытого EK
текста Шифртекст

?0
?1
:
?n–1
:
Ключ K

Рис. 2.5. Схема подстановки EK


Отметим характерные особенности подстановки ЕК:
• открытый текст шифруется побуквенно (буква за буквой);
• i-я буква yi шифртекста является функцией только i-й компоненты ?i ключа K и i-й буквы xi от-
крытого текста;
• шифрование n-граммы (x0, x1, x2, …, xn–1) производится в соответствии с формулой
(y0, y1, y2, …, yn–1) = EK (x0, x1, x2, …, xn–1).
Система Цезаря представляет собой одноалфавитную подстановку, которая шифрует n-
грамму (x0, x1, x2, …, xn–1) открытого текста в n-грамму (y0, y1, y2, …, yn–1) шифртекста согласно сле-
дующему правилу:
yi = EK (xi), 0 ? i < n, (2.3)
EK : j > (j + К) (mod n), 0 ? K < m,
где j – числовой код буквы открытого текста; j + K – числовой код соответствующей буквы шифртек-
ста.
В отличие от шифра Цезаря, описанного в начале этого подраздела, система шифрования
Цезаря образует по существу семейство одноалфавитных подстановок для выбираемых значений
ключа К, причем 0 ? K < m.
Достоинством системы шифрования Цезаря является простота шифрования и расшифрова-
ния. К недостаткам системы Цезаря следует отнести следующие:
• подстановки, выполняемые в соответствии с системой Цезаря, не маскируют частот появления
различных букв исходного открытого текста;
• сохраняется алфавитный порядок в последовательности заменяющих букв; при изменении значе-
ния К изменяются только начальные позиции такой последовательности;
• число возможных ключей К мало;
• шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифртексте.
Криптоаналитическая атака против системы одноалфавитной замены начинается с подсчета
частот появления символов: определяется число появлений каждой буквы в шифртексте. Затем по-
лученное распределение частот букв в шифртексте сравнивается с распределением частот букв в
алфавите исходных сообщений, например в английском. Буква с наивысшей частотой появления в
шифртексте заменяется на букву с наивысшей частотой появления в английском языке и т.д. Вероят-
ность успешного вскрытия системы шифрования повышается с увеличением длины шифртекста.
Концепция, заложенная в систему шифрования Цезаря, оказалась весьма плодотворной, о
чем свидетельствуют ее многочисленные модификации. Несколько таких модификаций будут рас-
смотрены ниже.
Аффинная система подстановок Цезаря
В системе шифрования Цезаря использовались только аддитивные свойства множества це-
лых Z m . Однако символы множества Z m можно также умножать по модулю m. Применяя одновре-
менно операции сложения и умножения по модулю m над элементами множества Z m , можно полу-
чить систему подстановок, которую называют аффинной системой подстановок Цезаря.
Определим преобразование в такой системе:

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

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

ОГЛАВЛЕНИЕ

Следующая >>