Измененный алфавит для осуществления подстановки

 

0

5

10

15

20

25

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

T

U

V

W

X

Y

Z

V

W

X

Y

Z

D

I

Р

L

О

M

А

Т

В

С

Е

F

G

H

J

K

N

0

R

S

U

 

Теперь имеем подстановку для каждой буквы произвольного сообщения. Возьмем исходным следующее сообщение: SEND MORE MONEY. Тогда в соответствии с табл. 2.8 исходное сообщение зашифруется и будет выглядеть как HZBY TCGZ TCBZS.

Следует отметить, что требование о различии всех букв ключевого слова необязательно: буквы, повторяющиеся в ключевом слове, могут быть из него исключены. Несомненным достоинством системы Цезаря с ключевым словом является то, что количество возможных ключевых слов практически неисчерпаемо. Недостатком этой системы является возможность взлома шифротекста на основе анализа частот появления букв.

 

Шифр омофонной замены. Выше был сделан вывод о том, что моноалфавитные шифры легко раскрываются, так как они наследуют частотность употребления букв оригинального алфавита. Контрмерой в данном случае может стать применение для одной буквы не одного, а нескольких заменителей (называемых омофонами). Число замен берется пропорциональным вероятности (относительной частоте) появления буквы в открытом тексте (см., например, рис. 2.20). Шифруя букву исходного сообщения, выбирают случайным образом одну из ее замен. Замены (омофоны) могут быть представлены трехразрядными числами от 000 до 999. Например, в английском алфавите букве Е присваиваются 123 случайных номера, буквам В и G – по 16 номеров, а буквам J и Z – по 1 номеру.

Шифротекст представляет собой комбинацию указанных номеров. Выделяемые для каждой буквы номера можно рассматривать в качестве ключей.

Если омофоны (замены) присваиваются случайным образом различным появлениям одной и той же буквы, тогда каждый омофон появляется в шифротексте равновероятно. В этом случае подсчет частотности употребления букв в шифрованном тексте становится бессмысленным. Однако даже при употреблении омофонов по-прежнему будут наблюдаться характерные показатели частоты повторения комбинаций нескольких букв (например, биграмм), и в результате криптоанализ, хотя и усложнился, но, тем не менее, позволяет дешифровать исходный текст при применении шифра омофонной замены.

 

Многобуквенные шифры. Данные методы шифрования заключается в замещении не отдельных символов открытого текста, а комбинаций нескольких символов.

Шифр Плейфейера. Одним из наиболее известных шифров, базирующихся на методе многобуквенного шифрования, является шифр Плейфейера, в котором биграммы открытого текста рассматриваются как самостоятельные единицы, преобразуемые в биграммы шифрованного текста.

Алгоритм Плейфейера применительно к английскому языку основан на использовании матрицы букв размерности 5x5, созданной на основе некоторого ключевого слова. В приведенной в табл. 2.9 матрице ключевым словом является monarchy (монархия).

 

Таблица 2.9

 

Пример матрицы для шифра Плейфейера

Матрица создается путем размещения букв, использованных в ключевом слове, слева направо с продолжением сверху вниз (повторяющиеся буквы отбрасываются). Затем оставшиеся буквы алфавита [3] размещаются в естественном порядке в оставшихся строках и столбцах матрицы. Буквы I и J считаются одной и той же буквой.

Открытый текст шифруется порциями по две буквы в соответствии со следующими правилами.

1. Если оказывается, что повторяющиеся буквы открытого текста образуют одну пару для шифрования, то между этими буквами вставляется специальная буква-заполнитель, например x. В частности, такое слово как balloon будет преобразовано к виду ba lx lo on. Буквы-заполнители можно использовать и в других случаях, например, в конце текста, в конце слова.

2. Если буквы открытого текста, входящие в одну порцию для шифрования, попадают в одну и ту же строку матрицы, каждая из них заменяется буквой, следующей за ней в той же строке справа – с тем условием, что для замены последнего элемента строки матрицы служит первый элемент той же строки. Например, аг шифруется как RM.

3. Если буквы открытого текста, входящие в одну порцию для шифрования, попадают в один и тот же столбец матрицы, каждая из них заменяется буквой, стоящей в том же столбце сразу под ней, с тем условием, что для замены самого нижнего элемента столбца матрицы берется самый верхний элемент того же столбца. Например, mu шифруется как СМ.

4. Если не выполняется ни одно из приведенных выше условий, каждая буква из пары букв открытого текста заменяется буквой, находящейся на пересечении содержащей эту букву строки матрицы и столбца, в котором находится другая буква из пары букв открытого текста. Например, hs шифруется как BP, а ea – как IM (или JM, по желанию шифровальщика).

Таким образом, слово balloon = ba lx lo on в зашифрованном с помощью алгоритма Плейфейера виде будет выглядеть следующим образом:

 

IBSUPMNA

 

При расшифровке:

1. Если буквы шифротекста, входящие в одну порцию для расшифровывания, попадают в одну и ту же строку матрицы, каждая из них заменяется буквой, стоящей перед ней слева – с тем условием, что для замены первого элемента строки матрицы служит последний элемент той же строки.

2. Если буквы шифротекста, входящие в одну порцию для шифрования, попадают в один и тот же столбец матрицы, каждая из них заменяется буквой, стоящей в том же столбце непосредственно перед ней, с тем условием, что для замены самого верхнего элемента столбца матрицы берется самый нижний элемент того же столбца.

3. Если не выполняется ни одно из приведенных выше условий расшифровывания, порядок расшифровывания полностью совпадает с порядком шифрования.

В данном примере при расшифровке вначале «проявится» слово ba lx lo on, которое затем редактируется.

Шифр Плейфейера может быть использован и для текста на русском языке. Целесообразный размер матрицы в этом случае 5 × 6. Из алфавита удаляются буквы Ё (заменяется буквой Е) и буква Й (заменяется буквой И). Буквы Ъ и Ь считаются одной и той же буквой.

Шифр Плейфейера значительно надежнее простых моноалфавитных шифров. С одной стороны, латинских букв всего 26, а биграмм – 26 х 26 = 676, и уже поэтому идентифицировать биграммы сложнее, чем отдельные буквы. С другой стороны, относительная частота появления отдельных букв колеблется гораздо в более широком диапазоне, чем частота появления биграмм, поэтому анализ частотности употребления биграмм тоже оказывается сложнее анализа частотности употребления букв. По этим причинам очень долго считалось, что шифр Плейфейера взломать невозможно. Он служил стандартом шифрования в Британской армии во время Первой мировой войны и нередко применялся в армии США и союзных войсках даже в период Второй мировой войны.

Несмотря на столь высокую репутацию в прошлом, шифр Плейфейера на самом деле вскрыть относительно легко, так как шифрованный с его помощью текст все равно сохраняет многие статистические характеристики открытого текста. Для взлома этого шифра криптоаналитику, как правило, достаточно иметь шифрованный текст, состоящий из нескольких сотен букв.

Шифр Хилла. Еще одним интересным многобуквенным шифром является шифр, разработанный математиком Лестером Хиллом (Lester Hill) в 1929 г. Являясь многобуквенным моноалфавитным шифром, он относится также к категории шифров, реализуемых с помощью аналитических преобразований. Лежащий в его основе алгоритм заменяет каждые m последовательных букв открытого текста m буквами шифрованного текста. Подстановка определяется m линейными уравнениями, для решения которых каждому символу исходного алфавита присваивается числовое значение (для латинского алфавита: а = 0, b = 1,..., z = 25). Например, при m = 3, получаем следующую систему уравнений:

Эту систему уравнений можно записать в виде произведения вектора и матрицы в следующем виде:

или                                                 С=К*Р;

где С и Р – векторы длины 3, представляющие соответственно шифрованный и открытый текст, а К – это матрица размерности 3x3, представляющая ключ шифрования. Операции выполняются по модулю 26 (бинарная операция взятия остатка от деления на 26).

Рассмотрим, например, как будет шифрован текст “рауmоrеmоnеу” при использовании ключа

Первые три буквы открытого текста представлены вектором (15 0 24). Таким образом, К(15 0 24) = (375 819 486) mоd 26 = (11 13 18) = LNS. Правила умножения вектора на матрицу раскрыты в представленной выше системе уравнений. Продолжая вычисления и используя тот же ключ, получим для данного примера шифрованный текст вида LNSHDLEWMTRW.

Для расшифровки нужно воспользоваться матрицей, обратной К. Обратной по отношению к матрице К называется такая матрица К^-1, для которой выполняется равенство КК^-1 = К^-1К = I, где I – это единичная матрица (матрица, состоящая из нулей всюду, за исключением главной диагонали, проходящей с левого верхнего угла в правый нижний, на которой предполагаются единицы – см. ниже). Обратная матрица существует не для всякой матрицы, однако, когда обратная матрица имеется, для нее обязательно выполняется приведенное выше равенство. В нашем примере обратной матрицей является матрица

Это проверяется следующими вычислениями:

Легко увидеть, что в результате применения матрицы К^-1 к шифрованному тексту получается открытый текст. Чтобы пояснить, как получена обратная матрица, нам придется предпринять небольшой экскурс в линейную алгебру – необходимые подробности любознательный студент может найти в любом подходящем учебнике.

Для получения обратной матрицы необходимо вычислить определитель заданной матрицы. Определителем квадратной матрицы (т×т) называют сумму таких всевозможных произведений элементов матрицы, что в произведении каждый столбец и каждая строка представлены ровно одним элементом, причем некоторые из этих произведений умножаются на -1. В частности, для матрицы 2 × 2 вида определитель вычисляется по формуле k₁₁k₂₂ – k₁₂k₂₁. Для матрицы 3 × 3 значение определителя подсчитывается по формуле k₁₁k₂₂k₃₃ + k₂₁k₃₂k₁₃ + k₃₁k₁₂k₂₃ - k₃₁k₂₂k₁₃ - k₂₁k₁₂k₃₃ - k₁₁k₃₂k₂₃. Если квадратная матрица А имеет отличный от нуля определитель, то обратная матрица вычисляется как [А^-1]_ij= (-1)^i+j(D_ij) / det(A), где (D_ij) – определитель матрицы, получаемой путем удаления i-й строки и j-го столбца из матрицы А, а det(А) – определитель самой матрицы А. В нашем случае все эти вычисления проводятся по модулю 26. Нетрудно видеть, что по указанной формуле определяется каждый элемент обратной матрицы.

В общем виде систему Хилла можно записать в следующей форме:

Как и в случае шифра Плейфейера, преимущество шифра Хилла состоит в том, что он полностью маскирует частоту вхождения отдельных букв. Кроме того, для шифра Хилла чем больше размер матрицы в шифре, тем больше в шифрованном тексте скрывается информации о различиях в значениях частоты появления других комбинаций символов. Так, шифр Хилла с матрицей 3 × 3 скрывает частоту появления не только отдельных букв, но и двухбуквенных комбинаций.

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