Раздел 5. Вопрос 1. (Зюляркина) Простейшие шифры. Шифры с симметричным и ассиметричным ключом.

Шифрование методами замены (подстановки). Этот вид шифрования подразумевает, что символы шифруемого текста заменяются другими символами, взятыми из одного (одно- или моноалфавитная подстановка) или нескольких (много- или полиалфавитная подстановка) алфавитов.

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

Таблица 6.2

Символы шифрования при простой замене

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

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

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

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

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

1) во всех (кроме первой) строках таблицы буквы располагаются в произвольном порядке;

2) в качестве ключа используются случайные последовательности чисел;

3) из таблицы Вижинера выбираются десять произвольных строк, которые кодируются натуральными числами от 0 до 10.

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

Вариант системы подстановок Вижинера при m = 2 называется системой Вернама. В ней ключ k = (k0, k1, ..., kk – 1) записывается на бумажной ленте, а каждая буква исходного текста переводится с использованием кода Бодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по модулю 2). Это считывающее устройство Вернама и оборудование для шифрования использовалось в свое время корпусом связи армии США.

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

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

Ri = Si + w mod(k – 1),

где Ri – символ зашифрованного текста; Si – символ исходного текста; w – целое число в диапазоне 0...(k – 1); k – число символов используемого алфавита.

Если w фиксировано, то формула описывает моноалфавитную подстановку; если w выбирается из последовательности w1, w2, ..., wn, то получается полиалфавитная подстановка с периодом n.

Если в полиалфавитной подстановке n > m (где m – число знаков шифруемого текста) и любая последовательность w1, w2, ..., wn используется только один раз, то такой шифр является теоретически нераскрываемым. Такой шифр получил название шифра Вермэна.

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

Самая простая перестановка – написать исходный текст задом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы

ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ

получится такой шифротекст:

ИЛЕТО ХЫМКА ККАТТ ЕДУБЬ ТСУП.

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

ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

Тогда шифрограмма, несмотря на столь незначительное изменение, будет выглядеть по-другому:

ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП.

Кажется, ничего сложного, но при расшифровке появятся серьезные неудобства.

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

Если матрицу А = (aij) использовать в качестве ключа, а вместо компонента вектора B = (bj) подставить символы текста, то компоненты вектора C = (cj) будут представлять собой символы зашифрованного текста.

Приведем пример, взяв в качестве ключа квадратную матрицу третьего порядка:

Заменим буквы алфавита цифрами, соответствующими их порядковому номеру в алфавите: А = 0, Б = 1, В = 2 и т.д. Тогда отрывку текста ВАТАЛА будет соответствовать последовательность чисел 2, 0, 19, 0, 12, 0. По принятому алгоритму шифрования выполним необходимые действия:

При этом зашифрованный текст будет иметь следующий вид: 85, 54, 25, 96, 60, 24.

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

Матрицей, обратной данной A, называется матрица А–1 получающаяся из присоединенной матрицы делением всех ее элементов на определитель данной матрицы. В свою очередь, присоединенной называется матрица, составленная из алгебраических дополнений Aij к элементам данной матрицы, которые вычисляются по следующей формуле:

Aij = (–1)I + j ∆ij,

где ∆ij – определитель матрицы, получаемой вычеркиванием i-й строки и j-го столбца исходной матрицы А.

Определителем матрицы называется алгебраическая сумма n! членов (для определителя n-го порядка), составленная следующим образом: членами служат всевозможные произведения n элементов матрицы, взятых по одному в каждой строке и в каждом столбце, причем член суммы берется со знаком “+”, если его индексы составляют четную подстановку, и со знаком “–” в противоположном случае. Для матрицы третьего порядка, например, определитель

∆ = a11a22a33 + a12a23a31 + a13a21a32 – a11а23а32 – a12a21a33 – a13a22a31.

Тогда процесс дешифровки текста будет выглядеть следующим образом:

Таким образом, получена последовательность чисел раскрытого текста: 3, 0, 19, 0, 12, 0, что соответствует исходному тексту. Этот метод шифрования является формальным, что позволяет легко реализовать его программными средствами.

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

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

Ri = (Si + G)mod(k – 1),

где Ri, Si, G – символы соответственно зашифрованного, исходного текста и гаммы.

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

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

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

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

Комбинированные методы шифрования с симметричными ключами. Эти методы являются достаточно эффективным средством повышения стойкости шифрования. Они заключаются в применении различных способов шифрования исходного текста одновременно или последовательно.

Как показали исследования, стойкость комбинированного шифрования Sk не ниже произведения стойкостей используемых способов Si, т.е.

Комбинировать можно любые методы шифрования и в любом количестве, однако на практике наибольшее распространение получили следующие комбинации: 1) подстановка + гаммирование; 2) перестановка + гаммирование; 3) гаммирование + гаммирование; 4) подстановка + перестановка. Типичным примером комбинированного шифра является национальный стандарт США криптографического закрытия данных (DES).

Асимметричное шифрование.

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

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

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

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

Криптографические системы с открытым ключом используют так называемые необратимые, или односторонние, функции, которые обладают следующим свойством: при заданном значении х относительно просто вычислить значение f(x), однако если М = f(x), то нет более простого пути для вычисления значения x.

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

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

1. Преобразование исходного текста должно быть необратимым и исключать его восстановление на основе открытого ключа.

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

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто для открытых систем и рекомендован МККТТ.

Все предлагаемые в настоящее время криптосистемы с открытым ключом основаны на одном из следующих типов необратимых преобразований:

разложение больших чисел на простые множители;

вычисление логарифма в конечном поле;

вычисление корней алгебраических уравнений.

Следует отметить, что алгоритмы криптосистемы СОК можно использовать в трех назначениях:

1) как самостоятельные средства защиты передаваемых и хранимых данных;

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

3) средства аутентификации пользователей (электронная подпись).

Шифрование методами замены (подстановки). Этот вид шифрования подразумевает, что символы шифруемого текста заменяются другими символами, взятыми из одного (одно- или моноалфавитная подстановка) или нескольких (много- или полиалфавитная подстановка) алфавитов.

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

Таблица 6.2

Символы шифрования при простой замене

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

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

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

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

Процесс шифрования осуществляется следующим образом: 1) под каждой буквой шифруемого текста записываются буквы ключа. Ключ при этом повторяется необходимое число раз; 2) каждая буква шифруемого текста заменяется по подматрице буквами, находящимися на пересечении линий, соединяющих буквы шифруемого текста в первой строке подматрицы и находящиеся под ними буквы ключа; 3) полученный текст может разбиваться на группы по несколько знаков. Пусть, например, требуется зашифровать сообщение: МАКСИМАЛЬНО ДОПУСТИМОЙ ЦЕНОЙ ЯВЛЯЕТСЯ ПЯТЬСОТ РУБ. ЗА ШТУКУ. В соответствии с первым правилом записываем под каждой буквой шифруемого текста буквы ключа. Получаем зашифрованный текст:

САЛЬЕРИСАЛЬ ЕРИСАЛЬЕРИ САЛЬЕ РИСАЛЬЕР ИСАЛЬЕР ИСА ЛЬ ЕРИСА.

Затем осуществляем непосредственное шифрование в соответствии со вторым правилом: берем первую букву шифруемого текста (M) и соответствующую ей букву ключа (C); по букве шифруемого текста (M) входим в рабочую матрицу шифрования и выбираем под ней букву, расположенную в строке, соответствующей букве ключа (C), – в нашем примере такой буквой является Э; выбранную таким образом букву помещаем в шифрованный текст. Эта процедура циклически повторяется до зашифрования всего текста.

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

Дешифровка текста производится в следующей последовательности: 1) над буквами зашифрованного текста последовательно надписываются буквы ключа, причем ключ повторяется необходимое число раз; 2) в строке подматрицы Вижинера, соответствующей букве ключа, отыскивается буква, соответствующая знаку зашифрованного текста. Находящаяся под ней буква первой строки подматрицы и будет буквой исходного текста; 3) полученный текст группируется в слова по смыслу.

На рис. 6.4 представлена схема дешифровки по таблице Вижинера с использованием ключа “Сальери”.

Схемы прямого и обратного преобразований легко реализуются по одному и тому же алгоритму.

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

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

1) во всех (кроме первой) строках таблицы буквы располагаются в произвольном порядке;

2) в качестве ключа используются случайные последовательности чисел;

3) из таблицы Вижинера выбираются десять произвольных строк, которые кодируются натуральными числами от 0 до 10.

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

Вариант системы подстановок Вижинера при m = 2 называется системой Вернама. В ней ключ k = (k0, k1, ..., kk – 1) записывается на бумажной ленте, а каждая буква исходного текста переводится с использованием кода Бодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по модулю 2). Это считывающее устройство Вернама и оборудование для шифрования использовалось в свое время корпусом связи армии США.

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

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

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

Ri = Si + w mod(k – 1),

где Ri – символ зашифрованного текста; Si – символ исходного текста; w – целое число в диапазоне 0...(k – 1); k – число символов используемого алфавита.

Если w фиксировано, то формула описывает моноалфавитную подстановку; если w выбирается из последовательности w1, w2, ..., wn, то получается полиалфавитная подстановка с периодом n.

Если в полиалфавитной подстановке n > m (где m – число знаков шифруемого текста) и любая последовательность w1, w2, ..., wn используется только один раз, то такой шифр является теоретически нераскрываемым. Такой шифр получил название шифра Вермэна.

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

Самая простая перестановка – написать исходный текст задом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы

ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ

получится такой шифротекст:

ИЛЕТО ХЫМКА ККАТТ ЕДУБЬ ТСУП.

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

ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

Тогда шифрограмма, несмотря на столь незначительное изменение, будет выглядеть по-другому:

ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП.

Кажется, ничего сложного, но при расшифровке появятся серьезные неудобства.

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

Таблица 6.3

Символы шифрования при усложненной замене по строкам

Таблица 6.4

Символы шифрования при усложненной замене по столбцам

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

ПКУМС ЫТХЬО БТУЕД ЛЕИТК ТЛАМК НКОАП.

Другой вариант этого шифра предусматривает предварительную процедуру записи исходной фразы в столбцы (табл. 6.4).

Затем строки разбивают на пятерки букв:

ПСЬУЕ ТКАМХ ТЛАВД УТБДТ АККЫО ЕИБГЕ.

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

Для примера возьмем решетку 6x6 (причем число строк может увеличиваться или уменьшаться в зависимости от длины исходного сообщения) и заполним ее по строкам (табл. 6.5).

Если шифровать по стрелкам (диагоналям) сверху вниз с левого верхнего угла, то в итоге получится такая шифрограмма:

П УУ СДК ТЕКХ ЬТАОА БТКТБМ АМЕВЛ ЫЛГК ИДИ ЕЗ Ж.

Для окончательного оформления шифротекст может быть разбит на группы по шесть символов:

ПУУСДК ТЕКХЬТ АОАБТК ТБМАМЕ ВЛЫЛГК ИДИЕЗЖ.

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

Возьмем, например, слово РАДИАТОР. Применяем следующий алгоритм кодировки букв. По алфавиту буква А получает номер 1, вторая буква А – 2, следующая по алфавиту буква Д – 3, потом И – 4, О – 5, первая буква Р – 6, вторая Р – 7 и буква Т- 8.

Заполним решетку (табл. 6.6).

Записываем столбики в соответствии с номерами букв ключа:

УТЫ ЬКТ СТХ ТАО УАЛ ПЕМО ДКИ БКЕ.

Затем последовательность опять разбиваем на пятерки:

УТЫЬК ТСТХТ АОУАЛ ПЕМОД КИБКЕ.

Таблица 6.7

Перестановка символов с пропусками

Развитием этого шифра является шифр перестановки колонок с пропусками (табл. 6.7), которые располагаются в решетке тоже в соответствии с ключом (в нашем случае через 6-1-3-4-2-8-5-7... символов).

Шифрограмма получается следующей:

УДК Ь СЕХЛ ТТОМ АЕП ПКИ УКЛР БТТО.

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

Если матрицу А = (aij) использовать в качестве ключа, а вместо компонента вектора B = (bj) подставить символы текста, то компоненты вектора C = (cj) будут представлять собой символы зашифрованного текста.

Приведем пример, взяв в качестве ключа квадратную матрицу третьего порядка:

Заменим буквы алфавита цифрами, соответствующими их порядковому номеру в алфавите: А = 0, Б = 1, В = 2 и т.д. Тогда отрывку текста ВАТАЛА будет соответствовать последовательность чисел 2, 0, 19, 0, 12, 0. По принятому алгоритму шифрования выполним необходимые действия:

При этом зашифрованный текст будет иметь следующий вид: 85, 54, 25, 96, 60, 24.

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

Матрицей, обратной данной A, называется матрица А–1 получающаяся из присоединенной матрицы делением всех ее элементов на определитель данной матрицы. В свою очередь, присоединенной называется матрица, составленная из алгебраических дополнений Aij к элементам данной матрицы, которые вычисляются по следующей формуле:

Aij = (–1)I + j ∆ij,

где ∆ij – определитель матрицы, получаемой вычеркиванием i-й строки и j-го столбца исходной матрицы А.

Определителем матрицы называется алгебраическая сумма n! членов (для определителя n-го порядка), составленная следующим образом: членами служат всевозможные произведения n элементов матрицы, взятых по одному в каждой строке и в каждом столбце, причем член суммы берется со знаком “+”, если его индексы составляют четную подстановку, и со знаком “–” в противоположном случае. Для матрицы третьего порядка, например, определитель

∆ = a11a22a33 + a12a23a31 + a13a21a32 – a11а23а32 – a12a21a33 – a13a22a31.

Тогда процесс дешифровки текста будет выглядеть следующим образом:

Таким образом, получена последовательность чисел раскрытого текста: 3, 0, 19, 0, 12, 0, что соответствует исходному тексту. Этот метод шифрования является формальным, что позволяет легко реализовать его программными средствами.

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

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

Ri = (Si + G)mod(k – 1),

где Ri, Si, G – символы соответственно зашифрованного, исходного текста и гаммы.

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

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

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

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

Комбинированные методы шифрования с симметричными ключами. Эти методы являются достаточно эффективным средством повышения стойкости шифрования. Они заключаются в применении различных способов шифрования исходного текста одновременно или последовательно.

Как показали исследования, стойкость комбинированного шифрования Sk не ниже произведения стойкостей используемых способов Si, т.е.

Комбинировать можно любые методы шифрования и в любом количестве, однако на практике наибольшее распространение получили следующие комбинации: 1) подстановка + гаммирование; 2) перестановка + гаммирование; 3) гаммирование + гаммирование; 4) подстановка + перестановка. Типичным примером комбинированного шифра является национальный стандарт США криптографического закрытия данных (DES).

Асимметричное шифрование.

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

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

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

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

Криптографические системы с открытым ключом используют так называемые необратимые, или односторонние, функции, которые обладают следующим свойством: при заданном значении х относительно просто вычислить значение f(x), однако если М = f(x), то нет более простого пути для вычисления значения x.

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

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

1. Преобразование исходного текста должно быть необратимым и исключать его восстановление на основе открытого ключа.

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

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто для открытых систем и рекомендован МККТТ.

Все предлагаемые в настоящее время криптосистемы с открытым ключом основаны на одном из следующих типов необратимых преобразований:

разложение больших чисел на простые множители;

вычисление логарифма в конечном поле;

вычисление корней алгебраических уравнений.

Следует отметить, что алгоритмы криптосистемы СОК можно использовать в трех назначениях:

1) как самостоятельные средства защиты передаваемых и хранимых данных;

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

3) средства аутентификации пользователей (электронная подпись).