Простейшие методы шифрования с закрытым ключом
Эти методы основаны на том, что символы исходного текста, обычно разделенные на блоки и записанные в одном алфавите, заменяются одним или несколькими символами другого алфавита в соответствии с принятым правилом преобразования.
Шифр простой (или одноалфавитной) замены, простой подстановочный шифр, моноалфавитный шифр - группа методов шифрования, которые сводятся к созданию по определённому алгоритму таблицы шифрования, в которой для каждой буквы открытого текста существует единственная сопоставленная ей буква шифртекста. Само шифрование заключается в замене букв согласно таблице. Для расшифровки достаточно иметь ту же таблицу, либо знать алгоритм, по которой она генерируется.
Симметричное шифрование (шифрование с закрытым ключом) – методы обратимого преобразования данных, в которых используется один и тот же ключ, который обе стороны информационного обмена должны хранить в секрете от противника. Все известные из истории шифры, например, шифр Цезаря – это шифры с закрытым ключом.
Пропорциональные или монофонические шифры – методы замены, в которых уравнивается частота появления зашифрованных знаков.
Шифры замены (подстановки) основаны на том, что символы исходного текста, обычно разделенные на блоки и записанные в одном алфавите, заменяются одним или несколькими символами другого алфавита в соответствии с принятым правилом преобразования.
Шифр многоалфавитной замены (или подстановки) – группа методов шифрования подстановкой, в которых для замены символов исходного текста используется не один, а несколько алфавитов по определенному правилу.
Шифры перестановки основаны на том, что входной поток исходного текста делится на блоки, в каждом из которых выполняется перестановка символов. Ключом такого шифра является используемая при шифровании перестановочная матрица или вектор, указывающий правило перестановки.
Гаммирование – метод шифрования, основанный на "наложении" гамма-последовательности на открытый текст. Обычно это суммирование в каком-либо конечном поле (суммирование по модулю). Например, в поле GF(2) такое суммирование принимает вид обычного "исключающего ИЛИ". При расшифровке операция проводится повторно, в результате получается открытый текст.
Одноалфавитная замена
Одним из важных подклассов методов замены являются одноалфавитные (или моноалфавитные) подстановки, в которых устанавливается однозначное соответствие между каждым знаком ai исходного алфавита сообщений A и соответствующим знаком ei зашифрованного текста E. Одноалфавитная подстановка иногда называется также простой заменой, так как является самым простым шифром замены.
Примером одноалфавитной замены является шифр Цезаря, рассмотренный ранее. В рассмотренном ранее примере первая строка является исходным алфавитом, вторая (с циклическим сдвигом на k влево) – вектором замен.
В общем случае при одноалфавитной подстановке происходит однозначная замена исходных символов их эквивалентами из вектора замен (или таблицы замен). При таком методе шифрования ключом является используемая таблица замен.
Подстановка может быть задана с помощью таблицы, например, как показано на рис. 1.
Рис. 1. Пример таблицы замен для двух шифров
В таблице на рис. 1 на самом деле объединены сразу две таблицы. Одна (шифр 1) определяет замену русских букв исходного текста на другие русские буквы, а вторая (шифр 2) – замену букв на специальные символы. Исходным алфавитом для обоих шифров будут заглавные русские буквы (за исключением букв "Ё" и "Й"), пробел и точка.
Зашифрованное сообщение с использованием любого шифра моноалфавитной подстановки получается следующим образом. Берется очередной знак из исходного сообщения. Определяется его позиция в столбце "Откр. текст" таблицы замен. В зашифрованное сообщение вставляется шифрованный символ из этой же строки таблицы замен.
Попробуем зашифровать сообщение "ВЫШЛИТЕ ПОДКРЕПЛЕНИЕ" c использованием этих двух шифров (рис. 2). Для этого берем первую букву исходного сообщения "В". В таблице на рис. 2.3 в столбце "Шифр 1" находим для буквы "В" заменяемый символ. Это будет буква "О". Записываем букву "О" под буквой "В". Затем рассматриваем второй символ исходного сообщения – букву "Ы". Находим эту букву в столбце "Откр. текст" и из столбца "Шифр 1" берем букву, стоящую на той же строке, что и буква "Ы". Таким образом получаем второй символ зашифрованного сообщения – букву "Н". Продолжая действовать аналогично, зашифровываем все исходное сообщение (рис. 2).
Рис. 2. Пример шифрования методом прямой замены
Полученный таким образом текст имеет сравнительно низкий уровень защиты, так как исходный и зашифрованный тексты имеют одинаковые статистические закономерности. При этом не имеет значения, какие символы использованы для замены – перемешанные символы исходного алфавита или таинственно выглядящие знаки.
Зашифрованное сообщение может быть вскрыто путем так называемого частотного криптоанализа. Для этого могут быть использованы некоторые статистические данные языка, на котором написано сообщение.
Известно, что в текстах на русском языке наиболее часто встречаются символы О, И. Немного реже встречаются буквы Е, А. Из согласных самые частые символы Т, Н, Р, С. В распоряжении криптоаналитиков имеются специальные таблицы частот встречаемости символов для текстов разных типов – научных, художественных и т.д.
Криптоаналитик внимательно изучает полученную криптограмму, подсчитывая при этом, какие символы сколько раз встретились. Вначале наиболее часто встречаемые знаки зашифрованного сообщения заменяются, например, буквами О. Далее производится попытка определить места для букв И, Е, А. Затем подставляются наиболее часто встречаемые согласные. На каждом этапе оценивается возможность "сочетания" тех или иных букв. Например, в русских словах трудно найти четыре подряд гласные буквы, слова в русском языке не начинаются с буквы Ы и т.д. На самом деле для каждого естественного языка (русского, английского и т.д.) существует множество закономерностей, которые помогают раскрыть специалисту зашифрованные противником сообщения.
Возможность однозначного криптоанализа напрямую зависит от длины перехваченного сообщения. Посмотрим, с чем это связано. Пусть, например, в руки криптоаналитиков попало зашифрованное с помощью некоторого шифра одноалфавитной замены сообщение:
ТНФЖ.ИПЩЪРЪ
Это сообщение состоит из 11 символов. Пусть известно, что эти символы составляют целое сообщение, а не фрагмент более крупного текста. В этом случае наше зашифрованное сообщение состоит из одного или нескольких целых слов. В зашифрованном сообщении символ Ъ встречается 2 раза. Предположим, что в открытом тексте на месте зашифрованного знака Ъ стоит гласная О, А, И или Е. Подставим на место Ъ эти буквы и оценим возможность дальнейшего криптоанализа (рис.3):
Рис. 3. Варианты первого этапа криптоанализа
Все приведенные варианты замены могут встретиться на практике. Попробуем подобрать какие-нибудь варианты сообщений, учитывая, что в криптограмме остальные символы встречаются по одному разу (рис.4).
Рис. 4. Варианты второго этапа криптоанализа
Кроме представленных на рис.4 сообщений можно подобрать еще большое количество подходящих фраз. Таким образом, если нам ничего не известно заранее о содержании перехваченного сообщения малой длины, дешифровать его однозначно не получится.
Если же в руки криптоаналитиков попадает достаточно длинное сообщение, зашифрованное методом простой замены, его обычно удается успешно дешифровать. На помощь специалистам по вскрытию криптограмм приходят статистические закономерности языка. Чем длиннее зашифрованное сообщение, тем больше вероятность его однозначного дешифрования.
Интересно, что если попытаться замаскировать статистические характеристики открытого текста, то задача вскрытия шифра простой замены значительно усложнится. Например, с этой целью можно перед шифрованием "сжимать" открытый текст с использованием компьютерных программ-архиваторов.
Пропорциональные шифры.
К одноалфавитным методам подстановки относятся пропорциональные или монофонические шифры, в которых уравнивается частота появления зашифрованных знаков для защиты от раскрытия с помощью частотного анализа. Для знаков, встречающихся часто, используется относительно большое число возможных эквивалентов. Для менее используемых исходных знаков может оказаться достаточным одного или двух эквивалентов. При шифровании замена для символа открытого текста выбирается либо случайным, либо определенным образом (например, по порядку).
При использовании пропорционального шифра в качестве замены символам обычно выбираются числа. Например, поставим в соответствие буквам русского языка трехзначные числа, как указано на рис. 5.
Рис. 5. Таблица замен для пропорционального шифра
В этом случае сообщение
БОЛЬШОЙ СЕКРЕТ
может быть зашифровано следующим образом:
101757132562103213762751800761754134130759
В данном примере варианты замен для повторяющихся букв (например, "О") выбирались по порядку.
Интересно, что шифры, в которых производится замена букв несколькими символами, пропорционально встречаемости в открытом тексте, описывали итальянские ученые еще в XIV-XV веках.
Пропорциональные шифры более сложны для вскрытия, чем шифры простой одноалфавитной замены. Однако, если имеется хотя бы одна пара "открытый текст – шифротекст", вскрытие производится тривиально. Если же в наличии имеются только шифротексты, то вскрытие ключа, то есть нахождение таблицы замен, становится более трудоемким, но тоже вполне осуществимым.
Многоалфавитные подстановки
В целях маскирования естественной частотной статистики исходного языка применяется многоалфавитная подстановка, которая также бывает нескольких видов. В многоалфавитных подстановках для замены символов исходного текста используется не один, а несколько алфавитов. Обычно алфавиты для замены образованы из символов исходного алфавита, записанных в другом порядке.
Примером многоалфавитной подстановки может служить схема, основанная на использовании таблицы Вижинера. Этот метод, известный уже в XVI веке, был описан французом Блезом Вижинером в "Трактате о шифрах", вышедшем в 1585 году.
В этом методе для шифрования используется таблица, представляющая собой квадратную матрицу с числом элементов NxN, где N — количество символов в алфавите (рис. 6). В первой строке матрицы записывают буквы в порядке очередности их в исходном алфавите, во второй — ту же последовательность букв, но с циклическим сдвигом влево на одну позицию, в третьей — со сдвигом на две позиции и т. д.
Рис. 6. Подготовка таблицы шифрования
Для шифрования текста выбирают ключ, представляющий собой некоторое слово или набор символов исходного алфавита. Далее из полной матрицы выписывают подматрицу шифрования, включающую первую строку и строки матрицы, начальными буквами которых являются последовательно буквы ключа (например, если выбрать ключ "весна", то таблица шифрования будет такой, как на рис. 7.
Рис. 7. Первый этап шифрования – составление подматрицы шифрования
В процессе шифрования (рис.8) под каждой буквой шифруемого текста записывают буквы ключа, повторяющие ключ требуемое число раз, затем шифруемый текст по таблице шифрования (рис.7) заменяют буквами, расположенными на пересечениях линий, соединяющих буквы текста первой строки таблицы и буквы ключа, находящейся под ней.
Например, под первой буквой исходного текста "М" записана буква "В" ключа. В таблице кодирования находим столбец, начинающийся с "М" и строку, начинающуюся с "В". На их пересечении располагается буква "О". Она и будет первым символом зашифрованного сообщения (на рис.8 эта буква выделена прямоугольной рамочкой). Следующая буква исходного сообщения – "Е", символ ключа – тоже "Е". Находим пересечение строки, начинающейся с "Е", и столбца, начинающегося с "Е". Это будет буква"Л" – второй символ зашифрованного сообщения.
Рис. 8. Механизм шифрования многоалфавитной заменой
Особенность данного метода многоалфавитной подстановки заключается в том, что каждый из символов ключа используется для шифрования одного символа исходного сообщения. После использования всех символов ключа, они повторяются в том же порядке. Если используется ключ из десяти букв, то каждая десятая буква сообщения шифруется одним и тем же символом ключа. Этот параметр называется периодом шифра. Если ключ шифрования состоит из одного символа, то при шифровании будет использоваться одна строка таблицы Вижинера, следовательно, в этом случае мы получим моноалфавитную подстановку, а именно шифр Цезаря.
С целью повышения надежности шифрования текста можно использовать подряд два или более зашифрования по методу Вижинера с разными ключами (составной шифр Вижинера).
На практике кроме метода Вижинера использовались также различные модификации этого метода. Например, шифр Вижинера с перемешанным один раз алфавитом. В этом случае для расшифрования сообщения получателю необходимо кроме ключа знать порядок следования символов в таблице шифрования.
Еще одним примером метода многоалфавитной подстановки является шифр с бегущим ключом или книжный шифр. В этом методе один текст используется в качестве ключа для шифрования другого текста. В эпоху "докомпьютерной" криптографии в качестве ключа для шифра с бегущим ключом выбирали какую-нибудь достаточно толстую книгу; от этого и произошло второе название этого шифра. Периодом в таком методе шифрования будет длина выбранного в качестве ключа произведения.
Методы многоалфавитной подстановки, в том числе и метод Вижинера, значительно труднее поддаются "ручному" криптоанализу. Для вскрытия методов многоалфавитной замены разработаны специальные, достаточно сложные алгоритмы. С использованием компьютера вскрытие метода многоалфавитной подстановки возможно достаточно быстро благодаря высокой скорости проводимых операций и расчетов.
В первой половине ХХ века для автоматизации процесса выполнения многоалфавитных подстановок стали широко применять роторные шифровальные машины. Главными элементами в таких устройствах являлись роторы – механические колеса, используемые для выполнения подстановки. Роторная шифровальная машина содержала обычно клавиатуру и набор роторов. Каждый ротор содержал набор символов (по количеству в алфавите), размещенных в произвольном порядке, и выполнял простую одноалфавитную подстановку. После выполнения первой замены символы сообщения обрабатывались вторым ротором и так далее. Роторы могли смещаться, что и задавало ключ шифрования. Некоторые роторные машины выполняли также и перестановку символов в процессе шифрования. Самым известным устройством подобного класса являлась немецкая шифровальная роторная машина Энигма (лат. Enigma — загадка), использовавшаяся во время второй мировой войны. Выпускалось несколько моделей Энигмы с разным числом роторов. В шифрмашине Энигма с тремя роторами можно было использовать 16900 разных алфавитов, и все они представляли собой различные перестановки символов.
Методы гаммирования
Еще одним частным случаем многоалфавитной подстановки является гаммирование. В этом способе шифрование выполняется путем сложения символов исходного текста и ключа по модулю, равному числу букв в алфавите. Если в исходном алфавите, например, 33 символа, то сложение производится по модулю 33. Такой процесс сложения исходного текста и ключа называется в криптографииналожением гаммы.
Пусть символам исходного алфавита соответствуют числа от 0 (А) до 32 (Я). Если обозначить число, соответствующее исходному символу, x, а символу ключа – k, то можно записать правило гаммирования следующим образом:
z = x + k (mod N),
где z – закодированный символ, N - количество символов в алфавите, а сложение по модулю N - операция, аналогичная обычному сложению, с тем отличием, что если обычное суммирование дает результат, больший или равный N, то значением суммы считается остаток от деления его на N. Например, пусть сложим по модулю 33 символы Г (3) и Ю (31):
3 + 31 (mod 33) = 1,
то есть в результате получаем символ Б, соответствующий числу 1.
Наиболее часто на практике встречается двоичное гаммирование. При этом используется двоичный алфавит, а сложение производится по модулю два. Операция сложения по модулю 2 часто обозначается 
, то есть можно записать:
Операция сложения по модулю два в алгебре логики называется также "исключающее ИЛИ" или по-английски XOR.
Рассмотрим пример. Предположим, нам необходимо зашифровать десятичное число 14 методом гаммирования с использованием ключа 12. Для этого вначале необходимо преобразовать исходное число и ключ (гамму) в двоичную форму: 14(10)=1110(2), 12(10)=1100(2). Затем надо записать полученные двоичные числа друг под другом и каждую пару символов сложить по модулю два. При сложении двух двоичных знаков получается 0, если исходные двоичные цифры одинаковы, и 1, если цифры разные:
Сложим по модулю два двоичные числа 1110 и 1100:
Исходное число 1 1 1 0
Гамма 1 1 0 0
Результат 0 0 1 0
В результате сложения получили двоичное число 0010. Если перевести его в десятичную форму, получим 2. Таким образом, в результате применения к числу 14 операции гаммирования с ключом 12 получаем в результате число 2.
Каким же образом выполняется расшифрование? Зашифрованное число 2 представляется в двоичном виде и снова производится сложение по модулю 2 с ключом:
Зашифрованное число 0 0 1 0
Гамма 1 1 0 0
Результат 1 1 1 0
Переведем полученное двоичное значение 1110 в десятичный вид и получим 14, то есть исходное число.
Таким образом, при гаммировании по модулю 2 нужно использовать одну и ту же операцию как для зашифрования, так и для расшифрования. Это позволяет использовать один и тот же алгоритм, а соответственно и одну и ту же программу при программной реализации, как для шифрования, так и для расшифрования.
Операция сложения по модулю два очень быстро выполняется на компьютере (в отличие от многих других арифметических операций), поэтому наложение гаммы даже на очень большой открытый текст выполняется практически мгновенно.
Благодаря указанным достоинствам метод гаммирования широко применяется в современных технических системах сам по себе, а также как элемент комбинированных алгоритмов шифрования.
Сформулируем, как производится гаммирование по модулю 2 в общем случае:
- символы исходного текста и гамма представляются в двоичном коде и располагаются один под другим, при этом ключ (гамма) записывается столько раз, сколько потребуется;
- каждая пара двоичных знаков складывается по модулю два;
- полученная последовательность двоичных знаков кодируется символами алфавита в соответствии с выбранным кодом.
На рис. 9 показано, как применяется гаммирование к тексту с русскими символами. Символы кодируются в соответствии с принятой кодировкой, а затем производится сложение по модулю 2.
При использовании метода гаммирования ключом является последовательность, с которой производится сложение – гамма. Если гамма короче, чем сообщение, предназначенное для зашифрования, гамма повторяется требуемое число раз. Так в примере на рис. 9 длина исходного сообщения равна двенадцати байтам, а длина ключа – пяти байтам. Следовательно, для зашифрования гамма должна быть повторена 2 раза полностью и еще один раз частично.
Рис. 9. Механизм гаммирования
Чем длиннее ключ, тем надежнее шифрование методом гаммирования. На практике длина ключа ограничена возможностями аппаратуры обмена данными и вычислительной техники, а именно выделяемыми объемами памяти под ключ, временем обработки сообщения, а также возможностями аппаратуры подготовки и записи последовательностей ключей. Кроме того, для использования ключа вначале необходимо каким-либо надежным способом доставить его обеим сторонам, обменивающимся сообщениями. Это приводит к возникновению проблемы распределения ключей, сложность решения которой возрастает с увеличением длины ключа и количества абонентов в сети передачи сообщений.
Методы перестановки
При использовании шифров перестановки входной поток исходного текста делится на блоки, в каждом из которых выполняется перестановка символов. Перестановки в классической "до компьютерной" криптографии получались в результате записи исходного текста и чтения шифрованного текста по разным путям геометрической фигуры.
Простейшим примером перестановки является перестановка с фиксированным периодом d. В этом методе сообщение делится на блоки по d символов и в каждом блоке производится одна и та же перестановка. Правило, по которому производится перестановка, является ключом и может быть задано некоторой перестановкой первых d натуральных чисел. В результате сами буквы сообщения не изменяются, но передаются в другом порядке.
Например, для d=6 в качестве ключа перестановки можно взять 436215. Это означает, что в каждом блоке из 6 символов четвертый символ становится на первое место, третий – на второе, шестой – на третье и т.д. Пусть необходимо зашифровать такой текст:
ЭТО_ТЕКСТ_ДЛЯ_ШИФРОВАНИЯ
Количество символов в исходном сообщении равно 24, следовательно, сообщение необходимо разбить на 4 блока. Результатом шифрования с помощью перестановки 436215 будет сообщение
_ОЕТЭТ_ТЛСКДИШР_ЯФНАЯВОИ
Теоретически, если блок состоит из d символов, то число возможных перестановок d!=1*2*...*(d-1)*d. В последнем примере d=6, следовательно, число перестановок равно 6!=1*2*3*4*5*6=720. Таким образом, если противник перехватил зашифрованное сообщение из рассмотренного примера, ему понадобится не более 720 попыток для раскрытия исходного сообщения (при условии, что размер блока известен противнику).
Для повышения криптостойкости можно последовательно применить к шифруемому сообщению две или более перестановки с разными периодами.
Другим примером методов перестановки является перестановка по таблице. В этом методе производится запись исходного текста построкам некоторой таблицы и чтение его по столбцам этой же таблицы. Последовательность заполнения строк и чтения столбцов может быть любой и задается ключом.
Рассмотрим пример. Пусть в таблице кодирования будет 4 столбца и 3 строки (размер блока равен 3*4=12 символов). Зашифруем такой текст:
ЭТО ТЕКСТ ДЛЯ ШИФРОВАНИЯ
Количество символов в исходном сообщении равно 24, следовательно, сообщение необходимо разбить на 2 блока. Запишем каждый блок в свою таблицу по строчкам (рис. 10).
Рис. 10. Шифрование методом перестановки по таблице
Затем будем считывать из таблицы каждый блок последовательно по столбцам:
ЭТТТЕ ОКД СЛЯФА РНШОИИВЯ
Можно считывать столбцы не последовательно, а, например, так: третий, второй, первый, четвертый:
ОКДТЕ ЭТТ СЛШОИ РНЯФАИВЯ
В этом случае порядок считывания столбцов и будет ключом.
В случае, если размер сообщения не кратен размеру блока, можно дополнить сообщение какими-либо символами, не влияющими на смысл, например, пробелами. Однако это делать не рекомендуется, так как это дает противнику в случае перехвата криптограммы информацию о размере используемой таблицы перестановок (длине блока). После определения длины блока противник может найти длину ключа (количество столбцов таблицы) среди делителей длины блока.
Посмотрим, как зашифровать и расшифровать сообщение, имеющее длину, не кратной размеру таблицы перестановки. Зашифруем слово
ПЕРЕМЕНКА
Количество символов в исходном сообщении равно 9. Запишем сообщение в таблицу по строкам (рис. 11), а последние три ячейки оставим пустыми.
Рис. 11. Шифрование неполного блока методом перестановки по таблице
Затем будем считывать из таблицы последовательно по столбцам:
ПМАЕЕРНЕК
Для расшифрования вначале определяют число полных столбцов, то есть количество символов в последней строке. Для этого делятразмер сообщения (в нашем примере – 9) на количество столбцов или размер ключа (в примере – 4). Остаток от деления будет числом полных столбцов: 9 mod 4 = 1. Следовательно, в нашем примере был 1 полный столбец и три коротких. Теперь можно поставить буквы сообщения на свои места и расшифровать сообщение. Так как ключом при шифровании было число 1234 (столбцы считывались последовательно), то при расшифровании первые три символа (ПМА) записываются в первый столбец таблицы перестановки, следующие два (ЕЕ) – во второй столбец, следующие два (РН) – в третий, и последние два (ЕК) – в четвертый. После заполнения таблицы считываем строки и получаем исходное сообщение ПЕРЕМЕНКА.
Существуют и другие способы перестановки, которые можно реализовать программным и аппаратным путем. Например, при передаче данных, записанных в двоичном виде, удобно использовать аппаратный блок, который перемешивает определенным образом с помощью соответствующего электрического монтажа биты исходного n-разрядного сообщения. Так, если принять размер блока равным восьми битам, можно, к примеру, использовать такой блок перестановки, как на рис. 12.
Рис.12. Аппаратный блок перестановки
УЧЕНЬЕ - СВЕТ, А НЕУЧЕНЬЕ - ЧУТЬ СВЕТ И НА РАБОТУ!
