Криптология и криптография

Моноалфавитные  подстановки можно описать выражением:

E_i =   (Mi + S_i)mod L, (1.1)

где E_i, Mj_ - числовые эквиваленты символов алфавита шифро-текста и алфавита открытого текста соответственно; S_i -коэффициент сдвига;  L - мощность алфавита.

Шифр  Цезаря

Простейшим  примером моноалфавитных подстановок  является шифр Цезаря. В этом шифре каждый символ открытого текста заменяется третьим после него символом в алфавите, замкнутом в кольцо, т. е. после пробела следует буква «А». Таким образом,  шифр Цезаря описывается так:

Ei = ( Mi + S)mod L, (1.2)

где S - коэффициент сдвига,  одинаковый для всех символов.

Цезарь  применял величину сдвига S = 3, но, конечно, можно использовать любое целое S:  1 < S <  (L - 1).

Зашифруем, например, текст «ШИФР_ЦЕЗАРЯ», применяя коэффициент сдвига S = 2:

Открытый  текст:   ШИФР    _ЦЕЗ    А    Р    Я Криптограмма: ЫКЦТ    Б    ШЗ    ЙВТ    А

Частотный анализ

Все естественные языки имеют характерное частотное распределение символов. Например, буква «О» встречается в русском языке чаще других, а буква «Ф» - самая редкая. Приведем вероятности встречаемости букв русского языка ( табл.1.3).

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

Таблица 1.3

 

Шифр  полиалфавитной подстановки

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

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

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

Ei =   (Mi + Ki _mod      mod L, (2.1)

где E_i, M_i - числовые эквиваленты символов криптограммы и открытого   текста   соответственно;   ^   -   числовой  эквивалент

буквы ключа; L - мощность алфавита открытого текста; U -длина ключа или период шифра.

Буквы ключа определяют величину смещения символов криптограммы относительно символов открытого текста.

Зашифруем, например, текст «полиалфавитная_подстановка» ключом «краб». Будем использовать алфавит, показанной в табл.1.2. Процесс  зашифрования приведен в табл.2.1.

Таблица 2.1

 

В результате получилась криптограмма:

«ЩЯЛиКЬФБМШТОКО_Р  ШФСУКЮОГФР».

Описанный в работе 1 шифр Цезаря является частным  случаем шифра Виженера с периодом,  равным единице.

где N - число символов в криптограмме; f[i] - общее число встречаемости i-й буквы алфавита в анализируемой криптограмме .

Существуют  таблицы, содержащие теоретически ожидаемые  значения ИС для разных длин ключа. Здесь представлена табл.2.2 для алфавита, состоящего из русских букв и пробела. Криптоаналитик, рассчитав ИС анализируемой им криптограммы, может определить ее период по такой таблице.

Однако  из-за погрешностей в оценке ИС его  использование становится неэффективным при длине ключа большей, чем десять символов.

Таблица 2.2

 

Зашифрование  «бегущим» ключем

Каждый  символ открытого текста складывается с символом ключа по модулю алфавита шифротекста. Ключом в данном случае является некоторая последовательность символов, называемая иногда «бегущим» ключом. Существует много способов порождения подобной ключевой последовательности. В данной работе в качестве «бегущего» ключа используются осмысленные тексты на русском языке, являющиеся предложениями из известных литературных произведений, крылатых фраз, песен, лозунгов и т. п. Алфавит шифротекста совпадает с алфавитом открытого текста.

Дешифрование  методом вероятных  слов

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

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

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

   Литература

   ·  Шнайер Б. Криптоанализ // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C — М.: Триумф, 2002. — С. 19—22. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.

   ·  Пилиди В. С. Криптография. Вводные главы — Ростов-на-Дону: ЮФУ, 2009. — 110 с.