Добавлен: 31.03.2023
Просмотров: 695
Скачиваний: 3
Итак, смещение K=3 или K=4 можно рассматривать как ключ шифра.
В таблице 2. показаны подстановки, соответствующие шифру Цезаря для латинского алфавита. Английская фраза (открытый текст) meet me after the toga party после шифрования примет следующий вид (шифрованный текст): PHHW PH DIWHU WKH WRJD SDUMB.
Послание Цезаря «VENI VIDI VICI» в переводе на русский язык означающее «Пришел. Увидел. Победил», направленное его другу Аминтию после победы над понтийским царем Фернаком, сыном Митридата, выглядело бы в зашифрованном виде так: YHQL YLGL YLFL.
Если каждой букве назначить числовой эквивалент (а = 1, b = 2 и т.д.), то алгоритм шифрования по Цезарю применительно к латинскому алфавиту можно выразить следующей формулой, которая показывает, каким образом каждая буква открытого текста p заменяется буквой шифрованного текста C:
С = Е(p) = (p + 3) mod(26).
Введем понятие обобщенного алгоритма (шифра) Цезаря, сдвиг K исходного алфавита в котором возможен на любую величину, но не больше, чем количество букв в применяемом алфавите минус 1. Для латинского алфавита обобщенный алгоритм Цезаря записывается формулой[5]:
С = Е(р) = (р + K) mod(26),
где K принимает значения в диапазоне от 1 до 25. Алгоритм расшифровывания также прост:
p = D(С) = (С – K)mod(26)
Достоинством системы шифрования Цезаря является простота шифрования и расшифровывания. К недостаткам системы Цезаря следует отнести:
— подстановки, выполняемые в соответствии с системой Цезаря, не маскируют частот появления различных букв исходного открытого текста;
- сохраняется алфавитный порядок в последовательности заменяющих букв; при изменении значения К изменяются только начальные позиции такой последовательности;
- число возможных ключей К мало;
- шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифротексте и даже на основе простого перебора вариантов.
Две практические задачи криптоанализа: доказательство слабой криптографической стойкости алгоритма Цезаря и шифров моноалфавитной подстановки.[5]
Если известно, что определенный текст был шифрован с помощью шифра Цезаря, то с помощью простого перебора всех вариантов раскрыть шифр очень просто – для этого достаточно проверить 25 возможных вариантов ключей. На рис. 2. показаны результаты применения этой стратегии к указанному выше первому сообщению. В данном случае открытый текст распознается в третьей строке.
Применение метода последовательного перебора всех возможных вариантов оправдано следующими тремя важными характеристиками данного шифра.
1. Известны алгоритмы шифрования и дешифрования.
2. Необходимо перебрать всего 25 вариантов.
3. Язык открытого текста известен и легко узнаваем.
В большинстве случаев, когда речь идет о защите сетей, можно предполагать, что алгоритм известен. Единственное, что делает криптоанализ на основе метода последовательного перебора практически бесполезным – это применение алгоритма, для которого требуется перебрать слишком много ключей. Например, алгоритм DES, использующий 56-битовые ключи, требует при последовательном переборе рассмотреть пространство из 256, или более чем 7х1016 ключей.[5]
Третья характеристика также важна. Если язык, на котором написан открытый текст, неизвестен, то расшифровыванный текст можно не распознать. Более того, исходный текст может состоять из сокращений или быть каким-либо образом сжат – это также затрудняет распознавание.
Рассмотрим теперь более простую возможность повысить криптостойкость шифров моноалфавитной подстановки. Если в латинском алфавите шифротекста допустить использование любой из перестановок 26 символов алфавита, то мы получим 26!, или более чем 4х1026 возможных ключей (ключ в данном случае – применяемый для записи шифротекста алфавит, полученный на основе перестановок символов обычного алфавита, а данный подход можно охарактеризовать как наивысший уровень развития идеи «шифра Цезаря»). Это на 10 порядков больше, чем размер пространства ключей DES, и это кажется достаточным для того, чтобы сделать невозможным успешное применение криптоанализа на основе метода последовательного перебора.[5]
1.3.2 Система шифрования Цезаря с ключевым словом
Особенностью этой системы является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки.
Выберем некоторое число 0 < К< 25 и слово или короткую фразу в качестве ключевого слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбрано слово DIPLOMAT в качестве ключевого слова и число К = 5 (в отличие от ключевого слова это число можно назвать ключевым параметром).[5]
Ключевое слово записывается под буквами алфавита, начиная с буквы, числовой код которой совпадает с выбранным числом К, так как это представлено в табл.3
Оставшиеся буквы алфавита подстановки записываются после ключевого слова в алфавитном порядке, так как это представлено в табл.4. Естественно, что при этом исключаются буквы, входящие в ключевое слово.
Теперь имеем подстановку для каждой буквы произвольного сообщения. Возьмем исходным следующее сообщение: SEND MORE MONEY. Тогда в соответствии с табл. 4 исходное сообщение зашифруется и будет выглядеть как HZBY TCGZ TCBZS.
Следует отметить, что требование о различии всех букв ключевого слова необязательно: буквы, повторяющиеся в ключевом слове, могут быть из него исключены. Несомненным достоинством системы Цезаря с ключевым словом является то, что количество возможных ключевых слов практически неисчерпаемо. Недостатком этой системы является возможность взлома шифротекста на основе анализа частот появления букв.[5]
1.3.3 Шифр омофонной замены
Выше был сделан вывод о том, что моноалфавитные шифры легко раскрываются, так как они наследуют частотность употребления букв оригинального алфавита. Контрмерой в данном случае может стать применение для одной буквы не одного, а нескольких заменителей (называемых омофонами). Число замен берется пропорциональным вероятности (относительной частоте) появления буквы в открытом тексте. Шифруя букву исходного сообщения, выбирают случайным образом одну из ее замен. Замены (омофоны) могут быть представлены трехразрядными числами от 000 до 999. Например, в английском алфавите букве Е присваиваются 123 случайных номера, буквам В и G – по 16 номеров, а буквам J и Z – по 1 номеру. [3]
Шифротекст представляет собой комбинацию указанных номеров. Выделяемые для каждой буквы номера можно рассматривать в качестве ключей.
Если омофоны (замены) присваиваются случайным образом различным появлениям одной и той же буквы, тогда каждый омофон появляется в шифротексте равновероятно. В этом случае подсчет частотности употребления букв в шифрованном тексте становится бессмысленным. Однако даже при употреблении омофонов по-прежнему будут наблюдаться характерные показатели частоты повторения комбинаций нескольких букв (например, биграмм), и в результате криптоанализ, хотя и усложнился, но, тем не менее, позволяет дешифровать исходный текст при применении шифра омофонной замены.[2]
В разделе 1.3.были рассмотрены и были приведены примеры шифров моноалфавитной (одноалфавитной) подстановки. Такие как, шифр Цезаря, система шифрования Цезаря с ключевым словом и шифр омофонной замены. Такие шифры являются самыми простыми, т.к. они наследуют частотность употребления букв оригинального алфавита.
1.4 Многобуквенные шифры
Данные методы шифрования заключается в замещении не отдельных символов открытого текста, а комбинаций нескольких символов.
1.4.1 Шифр Плейфейера
Одним из наиболее известных шифров, базирующихся на методе многобуквенного шифрования, является шифр Плейфейера, в котором биграммы открытого текста рассматриваются как самостоятельные единицы, преобразуемые в биграммы шифрованного текста.
Алгоритм Плейфейера применительно к английскому языку основан на использовании матрицы букв размерности 5x5, созданной на основе некоторого ключевого слова. В приведенной в табл. 5 матрице ключевым словом является monarchy (монархия). [3]
Матрица создается путем размещения букв, использованных в ключевом слове, слева направо с продолжением сверху вниз (повторяющиеся буквы отбрасываются). Затем оставшиеся буквы алфавита размещаются в естественном порядке в оставшихся строках и столбцах матрицы. Буквы I и J считаются одной и той же буквой.[1]
Открытый текст шифруется порциями по две буквы в соответствии со следующими правилами.
1. Если оказывается, что повторяющиеся буквы открытого текста образуют одну пару для шифрования, то между этими буквами вставляется специальная буква-заполнитель, например x. В частности, такое слово как balloon будет преобразовано к виду ba lx lo on. Буквы-заполнители можно использовать и в других случаях, например, в конце текста, в конце слова.[1]
2. Если буквы открытого текста, входящие в одну порцию для шифрования, попадают в одну и ту же строку матрицы, каждая из них заменяется буквой, следующей за ней в той же строке справа – с тем условием, что для замены последнего элемента строки матрицы служит первый элемент той же строки. Например, аг шифруется как RM.[1]
3. Если буквы открытого текста, входящие в одну порцию для шифрования, попадают в один и тот же столбец матрицы, каждая из них заменяется буквой, стоящей в том же столбце сразу под ней, с тем условием, что для замены самого нижнего элемента столбца матрицы берется самый верхний элемент того же столбца. Например, mu шифруется как СМ. [1]
4. Если не выполняется ни одно из приведенных выше условий, каждая буква из пары букв открытого текста заменяется буквой, находящейся на пересечении содержащей эту букву строки матрицы и столбца, в котором находится другая буква из пары букв открытого текста. Например, hs шифруется как BP, а ea – как IM (или JM, по желанию шифровальщика). [1]
Таким образом, слово balloon = ba lx lo on в зашифрованном с помощью алгоритма Плейфейера виде будет выглядеть следующим образом:
IBSUPMNA
При расшифровке:
1. Если буквы шифротекста, входящие в одну порцию для расшифровывания, попадают в одну и ту же строку матрицы, каждая из них заменяется буквой, стоящей перед ней слева – с тем условием, что для замены первого элемента строки матрицы служит последний элемент той же строки. [1]
2. Если буквы шифротекста, входящие в одну порцию для шифрования, попадают в один и тот же столбец матрицы, каждая из них заменяется буквой, стоящей в том же столбце непосредственно перед ней, с тем условием, что для замены самого верхнего элемента столбца матрицы берется самый нижний элемент того же столбца. [1]
3. Если не выполняется ни одно из приведенных выше условий расшифровывания, порядок расшифровывания полностью совпадает с порядком шифрования. [1]
В данном примере при расшифровке вначале «проявится» слово ba lx lo on, которое затем редактируется.
Шифр Плейфейера может быть использован и для текста на русском языке. Целесообразный размер матрицы в этом случае 5×6. Из алфавита удаляются буквы Ё (заменяется буквой Е) и буква Й (заменяется буквой И). Буквы Ъ и Ь считаются одной и той же буквой.
Шифр Плейфейера значительно надежнее простых моноалфавитных шифров. С одной стороны, латинских букв всего 26, а биграмм – 26 х 26 = 676, и уже поэтому идентифицировать биграммы сложнее, чем отдельные буквы. С другой стороны, относительная частота появления отдельных букв колеблется гораздо в более широком диапазоне, чем частота появления биграмм, поэтому анализ частотности употребления биграмм тоже оказывается сложнее анализа частотности употребления букв. По этим причинам очень долго считалось, что шифр Плейфейера взломать невозможно. Он служил стандартом шифрования в Британской армии во время Первой мировой войны и нередко применялся в армии США и союзных войсках даже в период Второй мировой войны. [1]
Несмотря на столь высокую репутацию в прошлом, шифр Плейфейера на самом деле вскрыть относительно легко, так как шифрованный с его помощью текст все равно сохраняет многие статистические характеристики открытого текста. Для взлома этого шифра криптоаналитику, как правило, достаточно иметь шифрованный текст, состоящий из нескольких сотен букв.
1.4.2 Шифр Хилла
Еще одним интересным многобуквенным шифром является шифр, разработанный математиком Лестером Хиллом (Lester Hill) в 1929 г. Являясь многобуквенным моноалфавитным шифром, он относится также к категории шифров, реализуемых с помощью аналитических преобразований. Лежащий в его основе алгоритм заменяет каждые m последовательных букв открытого текста m буквами шифрованного текста. Подстановка определяется m линейными уравнениями, для решения которых каждому символу исходного алфавита присваивается числовое значение (для латинского алфавита: а = 0, b = 1,..., z = 25). Например, при m = 3, получаем следующую систему уравнений[1]: