Добавлен: 31.03.2023
Просмотров: 700
Скачиваний: 3
Эту систему уравнений можно записать в виде произведения вектора и матрицы в следующем виде:
или С=К*Р;
где С и Р – векторы длины 3, представляющие соответственно шифрованный и открытый текст, а К – это матрица размерности 3x3, представляющая ключ шифрования. Операции выполняются по модулю 26 (бинарная операция взятия остатка от деления на 26). [1]
Рассмотрим, например, как будет шифрован текст “рау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 – это единичная матрица (матрица, состоящая из нулей всюду, за исключением главной диагонали, проходящей с левого верхнего угла в правый нижний, на которой предполагаются единицы – см. ниже) [3].Обратная матрица существует не для всякой матрицы, однако, когда обратная матрица имеется, для нее обязательно выполняется приведенное выше равенство. В нашем примере обратной матрицей является матрица
Это проверяется следующими вычислениями:
Легко увидеть, что в результате применения матрицы К-1 к шифрованному тексту получается открытый текст.
Для получения обратной матрицы необходимо вычислить определитель заданной матрицы. Определителем квадратной матрицы (т×т) называют сумму таких всевозможных произведений элементов матрицы, что в произведении каждый столбец и каждая строка представлены ровно одним элементом, причем некоторые из этих произведений умножаются на -1. В частности, для матрицы 2×2 вида 
определитель вычисляется по формуле k11k22 – k12k21. Для матрицы 3×3 значение определителя подсчитывается по формуле k11k22k33 + k21k32k13 + k31k12k23 - k31k22k13 - k21k12k33 - k11k32k23. Если квадратная матрица А имеет отличный от нуля определитель, то обратная матрица вычисляется как [А-1]ij= (-1)i+j(Dij)/det(A), где (Dij) – определитель матрицы, получаемой путем удаления i-й строки и j-го столбца из матрицы А, а det(А) – определитель самой матрицы А. В нашем случае все эти вычисления проводятся по модулю 26. Нетрудно видеть, что по указанной формуле определяется каждый элемент обратной матрицы. [1]
В общем виде систему Хилла можно записать в следующей форме:
Как и в случае шифра Плейфейера, преимущество шифра Хилла состоит в том, что он полностью маскирует частоту вхождения отдельных букв. Кроме того, для шифра Хилла чем больше размер матрицы в шифре, тем больше в шифрованном тексте скрывается информации о различиях в значениях частоты появления других комбинаций символов. Так, шифр Хилла с матрицей 3×3 скрывает частоту появления не только отдельных букв, но и двухбуквенных комбинаций. [1]
Хотя шифр Хилла устойчив к попыткам криптоанализа в тех случаях, когда известен только шифрованный текст, этот шифр легко раскрыть при наличии известного открытого текста (или хотя бы его части), который может быть получен криптоаналитиком на основе агентурных действий. В этом случае достаточно просто определить матрицу-ключ и использовать ее для расшифровки сообщений до тех пор, пока ключ не будет изменен. Следовательно, для каждого нового сообщения необходимо использовать новый ключ и, желательно, другой размер шифруемой последовательности букв, обозначенный выше как число m. Сложность заключается в синхронизации этого процесса отправителем и получателем сообщения. [1]
В разделе 1.4 рассмотрены более сложные шифры, по сравнению с моноалфавитными шифрами – многобуквенные. Их отличие заключается в том, что заменяются не отдельные символы, а целые комбинации отдельных символов. На примерах были разобраны шифр Плейфейера и шифр Хилла. Эти шифры могут полностью замаскировать частоту вхождения отдельных букв и они достаточно устойчивы к попыткам криптоанализа.
1.5. Шифры полиалфавитной подстановки
Слабая криптостойкость моноалфавитных подстановок преодолевается с применением подстановок многоалфавитных (полиалфавитных). Многоалфавитное шифрование (многоалфавитная замена) заключается в том, что для шифрования последовательных символов исходного текста используются одноалфавитные методы с различными ключами или, иными словами, – свои специальные алфавиты.
Например, первый символ заменяется по методу Цезаря со смещением 18, второй – со смещением 12 и т.д. до конца ключа, задающего переход к новому смещению. Затем процедура продолжается периодически. Более общей является ситуация, когда используется не шифр Цезаря, а последовательность произвольных подстановок, соответствующих одноалфавитным методам.
1.5.1 Шифр Виженера
Самым широко известным и одновременно самым простым алгоритмом такого рода является шифр Виженера (Vigenere). Этот шифр базируется на наборе правил моноалфавитной подстановки, представленных для латинского алфавита из 26 букв шифрами Цезаря со сдвигом от 0 до 25. Каждый из таких шифров можно обозначить ключевой буквой, являющейся буквой шифрованного текста, соответствующей букве a открытого текста. Например, шифр Цезаря, для которого смещение равно 3, обозначается ключевой буквой d. Для полного алфавита русского языка могут использоваться 32 шифра Цезаря со сдвигом от 0 до 32.[5]
Для облегчения понимания и применения этой схемы была предложена матрица, названная “табло Виженера” (рис. 3 и 4). Все 26 (для русского алфавита – 33, а в данном случае – 32) шифров располагаются по горизонтали, и каждому из шифров соответствует своя ключевая буква, представленная в крайнем столбце слева. Алфавит, соответствующий буквам открытого текста, находится в первой сверху строке таблицы. Процесс шифрования прост – необходимо по букве Х, задаваемой ключом, и букве открытого текста У найти букву шифрованного текста, которая находится на пересечении строки Х и столбца У. В данном случае такой буквой является буква V.[2]
Чтобы зашифровать сообщение, нужен ключ, имеющий ту же длину, что и само сообщение. Обычно ключ представляет собой повторяющееся нужное число раз ключевое слово, чтобы получить строку подходящей длины. Например, если ключевым словом является deceptive /обманчивый/, сообщение «we are discovered save yourself» /мы раскрыты, спасайте себя/ шифруется следующим образом.
Расшифровать текст также просто – буква ключа определяет строку, буква шифрованного текста, находящаяся в этой строке, определяет столбец, и в этом столбце в первой строке таблицы будет находиться соответствующая буква открытого текста.[6]
Рассмотрим еще один пример получения шифротекста с помощью таблицы Виженера. Пусть выбрано ключевое слово АМБРОЗИЯ. Необходимо зашифровать сообщение на русском языке ПРИЛЕТАЮ СЕДЬМОГО.
Выпишем исходное сообщение в строку и запишем под ним ключевое слово с повторением. В третью строку будем выписывать буквы шифротекста, определяемые из таблицы Виженера.
Преимущество этого шифра заключается в том, что для представления одной и той же буквы открытого текста в шифрованном тексте имеется много различных вариантов – по одному на каждую из неповторяющихся букв ключевого слова. [2] Таким образом, скрывается информация, характеризующая частотность употребления букв. Но и с помощью данного метода все же не удается полностью скрыть влияние структуры открытого текста на структуру шифрованного.
Можно отметить два предложения по усовершенствованию шифра Виженера. Инженером компании AT&T Гилбертом Вернамом (Gilbert Vernam) в 1918 г. было предложено выбирать ключевое слово, по длине равное длине открытого текста, но отличающегося от открытого текста по статистическим показателям (то есть в общем случае речь шла о фрагменте некоторого текста). Кроме того, система Вернама оперирует не буквами, а двоичными числами. Кратко ее можно выразить формулой[6]:
где рi – i-я двоичная цифра открытого текста; ki – i-я двоичная цифра ключа; Ci – i-я двоичная цифра шифрованного текста; ⓧ – операция XOR (исключающее “ИЛИ”).
Таким образом, шифрованный текст генерируется путем побитового выполнения операции XOR для открытого текста и ключа. Благодаря свойствам этой операции для расшифровки достаточно выполнить подобную операцию:
Сутью этой технологии является способ выбора ключа. Г.Вернам предложил использовать закольцованную ленту, что означает циклическое повторение ключевого слова, так что его система на самом деле предполагала работу хоть и с очень длинным, но все же повторяющимся ключом. Несмотря на то, что такая схема в силу очень большой длины ключа значительно усложняет задачу криптоанализа, схему, тем не менее, можно взломать, имея в распоряжении достаточно длинный фрагмент шифрованного текста, известные или вероятно известные фрагменты открытого текста либо и то, и другое сразу.[2]
Офицер армейского корпуса связи Джозеф Моборн (Joseph Mauborgne) предложил такие улучшения схемы шифрования Вернама, которые сделали эту схему исключительно надежной. Моборн предложил отказаться от повторений, а случайным образом генерировать ключ, по длине равный длине сообщения. Такая схема, получившая название ленты однократного использования (или схемы с одноразовым блокнотом), взлому не поддается. В результате ее применения на выходе получается случайная последовательность, не имеющая статистической взаимосвязи с открытом текстом. Поскольку в этом случае шифрованный текст не дает никакой информации об открытом тексте, нет способа и взломать код.[6]
Сложность практического применения этого метода заключается в том, что и отправитель, и получатель должны располагать одним и тем же случайным ключом и иметь возможность защитить его от посторонних. Поэтому, несмотря на все преимущества шифра Вернама-Моборна перед другими шифрами, на практике к нему прибегают редко.[2]
1.5.2 Шифр “двойной квадрат” Уитстона
В 1854 г. англичанин Чарльз Уитстон разработал новый метод шифрования биграммами, который называют “двойным квадратом”. Свое название этот шифр получил по аналогии с полибианским квадратом, изобретенным в древнем мире. Шифр Уитстона открыл новый этап в истории развития криптографии. В отличие от полибианского шифр «двойной квадрат» использует сразу две таблицы, размещенные по одной горизонтали, а шифрование идет биграммами, как в шифре Плейфейера. Эти не столь сложные модификации привели к появлению на свет качественно новой криптографической системы ручного шифрования. Шифр «двойной квадрат» оказался очень надежным и удобным и применялся Германией даже в годы Второй мировой войны.[2]
Поясним процедуру шифрования этим шифром на примере. Пусть имеются две таблицы со случайно расположенными в них буквами русского алфавита (рис. 5). Перед шифрованием исходное сообщение разбивают на биграммы. Каждая биграмма шифруется отдельно. Первую букву биграммы находят в левой таблице, а вторую букву – в правой таблице. Затем мысленно строят прямоугольник так, чтобы буквы биграммы лежали в его противоположных вершинах. Другие две вершины этого прямоугольника дают буквы биграммы шифротекста. Первый символ шифрованной пары должен лежать в одной строке с первым символом исходной.
Предположим, что шифруется биграмма исходного текста ИЛ. Буква И находится в столбце 1 и строке 2 левой таблицы. Буква Л находится в столбце 5 и строке 4 правой таблицы. Это означает, что прямоугольник образован строками 2 и 4, а также столбцами 1 левой таблицы и 5 правой таблицы. Следовательно, в биграмму шифротекста входят буква О, расположенная в столбце 5 и строке 2 правой таблицы, и буква В, расположенная в столбце 1 и строке 4 левой таблицы, т.е. получаем биграмму шифротекста ОВ.[2]
Если обе буквы биграммы сообщения лежат в одной строке, то и буквы шифротекста берут из этой же строки. Пусть первый символ имеет позицию (s, c) в левой таблице. Тогда он заменяется тем символом правой таблицы, какой там стоит на позиции (s, c). Пусть второй символ имеет позицию (s2, c2) в правой таблице. Тогда он заменяется тем символом левой таблицы, какой там стоит на позиции (s2, c2).[6]
Поэтому биграмма сообщения ТО превращается в биграмму шифротекста ЖБ. Аналогичным образом шифруются все биграммы сообщения:
Шифрование методом «двойного квадрата» дает весьма устойчивый к вскрытию и простой в применении шифр. Взламывание шифротекста «двойного квадрата» требует больших усилий, при этом длина сообщения должна быть не менее тридцати строк.