Традиционное шифрование информации

Цель работы: изучить методы традиционного шифрования информации.

Теоретические сведения.

1. Криптография: основные понятия.

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

Пожалуй, самым важным автоматизированным средством защиты сети и коммуникаций является шифрование.

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

С помощью рисунка 1 рассмотрим основные элементы схемы традиционного шифрования.

Источник создает сообщение  в форме открытого текста X=[X₁,X₂,…, X_M]. Элементами X_i  открытого текста X являются символы некоторого конечного алфавита. Для шифрования генерируется ключ в форме K=[K₁,K₂,…, K_J]. При наличии в качестве исходных данных сообщения X и ключа шифрования K с помощью алгоритма шифрования формируется шифрованный текст Y=[Y₁,Y₂,…, Y_N]. Это можно записать в виде формулы

 

Y=E_K(X).

Данная нотация означает, что Y получается путем применения алгоритма шифрования E к открытому тексту X при использовании ключа K.

Предполагаемый получатель сообщения, располагая ключом K, должен иметь возможность выполнить обратное преобразование

 

X=D_K(Y).

 

Противник, обладающий возможностью ознакомиться с Y, но не имеющий доступа ни к K, ни к X, может попытаться восстановить X или K или оба этих объекта. При этом подразумевается, что противник знает и алгоритм шифрования (E), и алгоритм дешифрования (D). Если противник заинтересован распознать только одно конкретное сообщение, ему следует сосредоточить свои усилия на восстановлении X путем построения вероятно соответствующего исходному открытого текста X¢. Однако чаще противник бывает заинтересован в получении возможности читать и все последующие сообщения. В этом случае его основные усилия должны быть сосредоточены на восстановлении K путем построения вероятно соответствующего исходному ключа K¢.

Процесс воссоздания значений X или K, или и того, и другого, называется криптоанализом. Человека, занимается криптоанализом, называют криптоаналитиком.

 

2. Классификация криптографических систем.

Классификация криптографических  систем в общем случае строится на основе следующих трех независимых характеристик.

1. Тип операций по преобразованию открытого текста в шифрованный. Все алгоритмы шифрования основываются на использовании двух операций: замены, означающей замещение каждого элемента открытого текста (бита, буквы, группы битов или группы букв) некоторым другим элементом, и перестановки, означающей изменение порядка следования элементов открытого текста. При этом главным требованием оказывается отсутствие потерь информации (т.е. обратимость всех операций). В большинстве реальных систем шифрования применяют не одну, а комбинацию нескольких операций замены и перестановки. Соответствующие шифры называют продукционными.
2. Число применяемых ключей. Если отправитель, и получатель использую один и тот же ключ, система называется симметричной, системой с одним ключом, системой с секретным ключом или схемой традиционного шифрования. Если отправитель и получатель используют разные ключи, система называется асимметричной, системой с двумя ключами или схемой шифрования с открытым ключом.
3. Метод обработки открытого текста. Блочное шифрование предполагает обработку открытого текста блоками, так что в результате обработки каждого блока получается блок шифрованного текста. Поточное шифрование подразумевает шифрование всех элементов открытого текста последовательно, одного за другим, в результате чего на каждом этапе получается по одному элементу шифрованного текста.
3. Классическая техника шифрования.

3.1. Применение подстановок.

 

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

Шифр Цезаря.

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

 

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

 

шифрование происходит следующим  образом:

 

Открытый текст:

К

Р

И

П

Т

О

Г

Р

А

Ф

И

Я

Шифрованный текст:

Н

У

Л

Т

Х

С

Ж

У

Г

Ч

Л

В

 

Определить преобразование можно, перечислив все варианты, как показано ниже.

 

Открытый текст:

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

Шифрованный текст:

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

А

Б

В

 

Если каждой букве назначить  числовой эквивалент (А = 1, Б = 2 и т.д.), то алгоритм шифрования можно выразить следующими формулами. Каждая буква  открытого текста P заменяется  буквой шифрованного текста C:

C = E(P) = (P+3) mod (26).

В общем случае сдвиг может быть любым, поэтому общий алгоритм Цезаря записывается формулой

C = E(P) = (P+k) mod (26),

где k принимает значения в диапазоне от 1 до 31 (для рассмотренного алфавита). Алгоритм дешифрования также прост:

P = D(C) = (C-k) mod (26).

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

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

1. Известны алгоритмы шифрования и дешифрования.
2. Необходимо перебрать всего 31 вариант.
3. Язык открытого текста известен и легко узнаваем.

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

Моноалфавитные  шифры.

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

Например, если в шифре Цезаря допустить использование любой из перестановок 31 символа алфавита, а не только сдвигом на k символов, то мы получим 31! Возможных ключей. Пример ключа такого шифра приведен ниже.

Открытый текст:

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

Шифрованный текст:

Й

Р

Ж

Ь

Ш

Л

Я

Е

В

Ъ

Ф

К

М

Б

С

Ч

Ю

А

Ц

И

Э

Щ

Ы

Н

У

П

Г

Х

Т

Д

О

З

 

Пример шифрования с использованием этого ключа:

 

Открытый текст:

К

Р

И

П

Т

О

Г

Р

А

Ф

И

Я

Шифрованный текст:

Ф

Ю

В

Ч

Ц

С

Ь

Ю

Й

Э

В

З

 

Создается впечатление, что 31! (что превышает 8´10³³) ключей не так то просто перебрать, и данный шифр обладает высокой степенью надежности. Однако для криптоаналитика существует и другая линия атаки. Если криптоаналитик имеет представление о природе открытого текста (например, о том, что это текст на английском языке), можно использовать известную информацию о характерных признаках, присущих текстам на соответствующем языке.

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

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

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