Способы шифрования информации: от шифра цезаря до современных криптографических алгоритмов Борзунова а. А., Борзунова т.Л.

Произведена попытка сравнения программных реализаций различных криптографических алгоритмов.

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

Шифр цезаря. Рассмотрим одну из простейших систем шифрования, которая носит имя "шифр Юлия Цезаря". Предполагается, что знаменитый римский император и полководец, живший в 1 веке до нашей эры, использовал этот шифр в своей переписке. Шифр Цезаря применительно к русскому языку состоит в следующем. Каждая буква сообщения заменяется на другую, которая в русском алфавите отстоит от исходной на три позиции дальше. Таким образом, буква A заменяется на Г , Б на Д и так далее вплоть до буквы Ь , которая заменялась на Я , затем Э на A , Ю на Б и, наконец, Я на В . Это не очень сложный метод, тем более что при шифровании сообщений из нескольких слов сразу становится понятным, сколько слов содержал исходный текст. Кроме того, можно получить некоторую информацию по анализу повторов букв в зашифрованном сообщении. Тем не менее, Цезарь вошел в историю криптографии, а "шифр Юлия Цезаря", как его до сих пор называют, служит примером одной из первых систем шифрования.

Классическая, или одноключевая криптография опирается на использование симметричных алгоритмов шифрования, в которых шифрование и расшифрование отличаются только порядком выполнения и направлением некоторых шагов. Эти алгоритмы используют один и тот же секретный элемент (ключ), и второе действие (расшифрование) является простым обращением первого (шифрования). Поэтому обычно каждый из участников обмена может как зашифровать, так и расшифровать сообщение. На передающей стороне имеются источник сообщений и источник ключей. Источник ключей выбирает конкретный ключ К среди всех возможных ключей данной системы. Этот ключ К передается некоторым способом принимающей стороне, причем предполагается, что его нельзя перехватить, например, ключ передается специальным курьером (поэтому симметричное шифрование называется также шифрованием с закрытым ключом). Источник сообщений формирует некоторое сообщение М, которое затем шифруется с использованием выбранного ключа. В результате процедуры шифрования получается зашифрованное сообщение Е (называемое также криптограммой). Далее криптограмма Е передается по каналу связи. Так как канал связи является открытым, незащищенным, например, радиоканал или компьютерная сеть, то передаваемое сообщение может быть перехвачено противником. На принимающей стороне криптограмму Е с помощью ключа расшифровывают и получают исходное сообщение М. Если М – сообщение, К – ключ, а Е – зашифрованное сообщение, то можно записать E=f(M,K),то есть зашифрованное сообщение Е является некоторой функцией от исходного сообщения М и ключа К. Используемый в криптографической системе метод или алгоритм шифрования и определяет функцию f в приведенной выше формуле алгоритм шифрования и определяет функцию f в приведенной выше формуле. По причине большой избыточности естественных языков непосредственно в зашифрованное сообщение чрезвычайно трудно внести осмысленное изменение, поэтому классическая криптография обеспечивает также защиту от навязывания ложных данных. Если же естественной избыточности оказывается недостаточно для надежной защиты сообщения от модификации, избыточность может быть искусственно увеличена путем добавления к сообщению специальной контрольной комбинации, называемой имитовставкой.

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

Одним из важных подклассов методов замены являются одноалфавитные (или моноалфавитные) подстановки, в которых устанавливается однозначное соответствие между каждым знаком a_i исходного алфавита сообщений A и соответствующим знаком e_i зашифрованного текста E. Одноалфавитная подстановка иногда называется также простой заменой, так как является самым простым шифром замены. Примером одноалфавитной замены является шифр Цезаря. Общем случае при одноалфавитной подстановке происходит однозначная замена исходных символов их эквивалентами из вектора замен (или таблицы замен). При таком методе шифрования ключом является используемая таблица замен. Зашифрованное сообщение может быть вскрыто путем так называемого частотного криптоанализа. Для этого могут быть использованы некоторые статистические данные языка, на котором написано сообщение. К одноалфавитным методам подстановки относятся пропорциональные или монофонические шифры, в которых уравнивается частота появления зашифрованных знаков для защиты от раскрытия с помощью частотного анализа. Для знаков, встречающихся часто, используется относительно большое число возможных эквивалентов. Для менее используемых исходных знаков может оказаться достаточным одного или двух эквивалентов. При шифровании замена для символа открытого текста выбирается либо случайным, либо определенным образом (например, по порядку).

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

Примером многоалфавитной подстановки может служить схема, основанная на использовании таблицы Вижинера. В этом методе для шифрования используется таблица, представляющая собой квадратную матрицу с числом элементов NxN, где N — количество символов в алфавите .В первой строке матрицы записывают буквы в порядке очередности их в исходном алфавите, во второй — ту же последовательность букв, но с циклическим сдвигом влево на одну позицию, в третьей — со сдвигом на две позиции и т. д. Для шифрования текста выбирают ключ, представляющий собой некоторое слово или набор символов исходного алфавита. Далее из полной матрицы выписывают подматрицу шифрования, включающую первую строку и строки матрицы, начальными буквами которых являются последовательно буквы ключа. В процессе шифрования под каждой буквой шифруемого текста записывают буквы ключа, повторяющие ключ требуемое число раз, затем шифруемый текст по таблице шифрования заменяют буквами, расположенными на пересечениях линий, соединяющих буквы текста первой строки таблицы и буквы ключа, находящейся под ней. Расшифровка текста выполняется в следующей последовательности над буквами шифрованного текста сверху последовательно записывают буквы ключа, повторяя ключ требуемое число раз; в строке подматрицы таблицы Вижинера для каждой буквы ключа отыскивается буква, соответствующая знаку шифрованного текста. Находящаяся над ней буква первой строки и будет знаком расшифрованного текста; полученный текст группируется в слова по смыслу.

Раскрыть шифр Вижинера, тем же способом, что и шифр одноалфавитной замены, невозможно, так как одни и те же символы открытого текста могут быть заменены различными символами зашифрованного текста. С другой стороны, различные буквы открытого текста могут быть заменены одинаковыми знаками зашифрованного текста. Особенность данного метода многоалфавитной подстановки заключается в том, что каждый из символов ключа используется для шифрования одного символа исходного сообщения. После использования всех символов ключа, они повторяются в том же порядке. Если используется ключ из десяти букв, то каждая десятая буква сообщения шифруется одним и тем же символом ключа. Этот параметр называется периодом шифра. Если ключ шифрования состоит из одного символа, то при шифровании будет использоваться одна строка таблицы Вижинера, следовательно, в этом случае мы получим моноалфавитную подстановку, а именно шифр Цезаря. Методы многоалфавитной подстановки, в том числе и метод Вижинера, значительно труднее поддаются "ручному" криптоанализу. Для вскрытия методов многоалфавитной замены разработаны специальные, достаточно сложные алгоритмы. С использованием компьютера вскрытие метода многоалфавитной подстановки возможно достаточно быстро благодаря высокой скорости проводимых операций и расчетов.

Еще одним частным случаем многоалфавитной подстановки является методы гаммирования. Гаммирование – это метод шифрования, основанный на "наложении" гамма-последовательности на открытый текст. Обычно это суммирование в каком-либо конечном поле (суммирование по модулю). Например, в поле GF(2) такое суммирование принимает вид обычного "исключающего ИЛИ". При расшифровке операция проводится повторно, в результате получается открытый текст. В этом способе шифрование выполняется путем сложения символов исходного текста и ключа по модулю, равному числу букв в алфавите. Если в исходном алфавите, например, 33 символа, то сложение производится по модулю 33. Такой процесс сложения исходного текста и ключа называется в криптографии наложением гаммы. Наиболее часто на практике встречается двоичное гаммирование. При этом используется двоичный алфавит, а сложение производится по модулю два, где нужно использовать одну и ту же операцию как для зашифрования, так и для расшифрования. Это позволяет использовать один и тот же алгоритм, а соответственно и одну и ту же программу при программной реализации, как для шифрования, так и для расшифрования. Благодаря указанным достоинствам метод гаммирования широко применяется в современных технических системах сам по себе, а также как элемент комбинированных алгоритмов шифрования.

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

Шифры замены (подстановки) основаны на том, что символы исходного текста, обычно разделенные на блоки и записанные в одном алфавите, заменяются одним или несколькими символами другого алфавита в соответствии с принятым правилом преобразования. В этом методе производится запись исходного текста по строкам некоторой таблицы и чтение его по столбцам этой же таблицы. Последовательность заполнения строк и чтения столбцов может быть любой и задается ключом. Группа методов шифрования подстановкой, в которых для замены символов исходного текста используется не один, а несколько алфавитов по определенному правилу известен как шифр многоалфавитной замены (подстановки). Шифры перестановки основаны на том, что входной поток исходного текста делится на блоки, в каждом из которых выполняется перестановка символов. Ключом такого шифра является используемая при шифровании перестановочная матрица или вектор, указывающий правило перестановки. Различают перестановки с фиксированным периодом d или перестановка по таблице. Шифр простой (или одноалфавитной) замены, простой подстановочный шифр, моноалфавитный шифр— группа методов шифрования, которые сводятся к созданию по определённому алгоритму таблицы шифрования, в которой для каждой буквы открытого текста существует единственная сопоставленная ей буква шифртекста. Само шифрование заключается в замене букв согласно таблице. Для расшифровки достаточно иметь ту же таблицу, либо знать алгоритм, по которой она генерируется.

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

Мы рассмотрели общую схему симметричного шифрования и классификацию простейших методов шифрования с закрытым ключом. Теперь рассмотрим принципы построения современных блочных алгоритмов. Будем предполагать, что противнику известен метод шифрования, но неизвестен ключ, перехватив сообщение, ему понадобится n-е количество попыток (при использовании метода полного перебора) для нахождения ключа. Таким образом, не более чем за t минут работы противник узнает ключ и сможет в дальнейшем расшифровывать все сообщения, закрытые тем же ключом. Если же анализ производится с использованием компьютера, для дешифрации и поиска ключа потребуется гораздо меньше времени. Чтобы усложнить задачу криптоаналитику, можно увеличивать размер периода перестановки, то есть блока, в котором переставляются символы, например, до тысячи знаков. Однако, во-первых, перебор сотен и тысяч знаков на современных компьютерах производится за доли минуты, а во-вторых, при этом до тысячи символов возрастет и размер ключа. Такой ключ уже достаточно трудно запомнить и использовать. Если пойти по другому пути и применить перед перестановкой в блоке из 6 символов простую замену по методу Цезаря, то действительно, таким образом полученный комбинированный шифр значительно сильнее отдельно выполненных замены и перестановки. Для затруднения криптоанализа статистическими методами можно использовать наш комбинированный шифр дважды с одним и тем же ключом. При этом пространство ключей шифра не изменилось, однако за счет двухкратного шифрования статистические закономерности исходного текста замаскировались сильнее. В реальных шифрах также используется комбинация нескольких простейших операций над цепочками или блоками знаков. Для повышения криптостойкости эти операции выполняются циклически несколько раз, образуя раунды или шаги. На стойкость шифра влияют такие факторы, как размер блока, размер ключа, количество раундов шифрования. Современные шифры с закрытым ключом обрабатывают только двоичные данные, поэтому в них помимо обычных замены и перестановки применяются некоторые другие специфичные для двоичных чисел операции.

Алгоритмы симметричного шифрования могут обрабатывать исходный текст блоками или потоком. В зависимости от этого различают блочные алгоритмы симметричного шифрования и поточные. Блок текста рассматривается как неотрицательное целое число либо как несколько независимых неотрицательных целых чисел. Длина блока всегда выбирается равной степени двойки, например, 64, 128, 256 бит. В алгоритмах блочного симметричного шифрования часто используются операции сложения по модулю 2, сложения по модулю 2¹⁶ или 2³², циклического сдвига, замены и перестановки. Эти операции циклически повторяются в алгоритме N раз, образуя так называемые раунды или шаги. Исходными данными для каждого раунда являются выход предыдущего раунда и ключ, который получен по определенному алгоритму из общего ключа шифрования K. Ключ раунда называется подключом К_i Блочные алгоритмы шифрования применяются к двоичным данным. В общем случае процедура блочного шифрования преобразовывает n-битный блок открытого текста в k-битный блок зашифрованного текста. Число блоков длины n равно 2ⁿ. Для того чтобы преобразование было обратимым, каждый из таких блоков должен преобразовываться в свой уникальный блок зашифрованного текста. Длина блока всегда выбирается равной степени двойки, например, 64, 128, 256 бит.

Сеть Фейштеля. Само преобразование данных выполняется в раундах или шагах шифрования. Раунд, организованный по сети Фейштеля имеет следующую структуру. Входной блок делится на несколько частей равной длины. Эти части блока называются ветвями. Так, например, если блок имеет длину 64 бита, используются две ветви по 32 бита каждая. Ветви обрабатываются по отдельности, после чего осуществляется циклический сдвиг всех ветвей влево. Функция F называется образующей. Каждый раунд состоит из вычисления функции F для одной ветви и побитового выполнения операции "сумма по модулю 2" результата F с другой ветвью. После этого ветви меняются местами. Число раундов может быть различным для разных алгоритмов. В некоторых алгоритмах рекомендуется от 8 до 32 раундов, в других – больше. В целом увеличение количества раундов увеличивает криптостойкость алгоритма. Возможно, эта особенность и повлияла на столь активное распространение сети Фейштеля, так как для большей криптостойкости достаточно просто увеличить количество раундов, не изменяя сам алгоритм. В последнее время количество раундов не фиксируется, а лишь указываются рекомендуемые пределы. В последнее время все чаще используются различные разновидности сети Фейштеля для 128-битного блока с четырьмя ветвями. Увеличение количества ветвей, а не размерности каждой ветви связано с тем, что наиболее популярными до сих пор остаются процессоры с 32-разрядными словами, следовательно, оперировать 32-разрядными словами эффективнее, чем с 64-разрядными. В блочных алгоритмах, построенных на основе сети Фейштеля, основной операцией является вычисление образующей функции F. Эта функция использует подключ раунда и одну ветвь входного блока для вычисления результата. Именно тем, как определяется функция F, системы шифрования и отличаются друг от друга. В некоторых алгоритмах введены также начальные преобразования входного блока данных, придающие некоторую "случайность" входному тексту (это называется рандомизацией данных.) Рандомизация производится для того, чтобы уменьшить естественную избыточность входного сообщения.

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

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

Шифр многоалфавитной замены – группа методов шифрования подстановкой, в которых для замены символов исходного текста используется не один, а несколько алфавитов по определенному правилу. Таким образом, при шифровании получаётся достаточно сложная последовательность, которую уже не так просто вскрыть, как один одноалфавитный шифр. Частным случаем многоалфавитной подстановки является гаммирование – метод шифрования, основанный на "наложении" гамма-последовательности на открытый текст. Обычно это суммирование в каком-либо конечном поле (суммирование по модулю длины алфавита). Самым важным эффектом, достигаемым при использовании многоалфавитного шифра, является маскировка частот появления тех или иных букв в тексте, на основании которой обычно очень легко вскрываются одноалфавитные шифры.

В симметричных блочных шифрах используется комбинация нескольких простейших операций над цепочками или блоками бит: сложения по модулю 2, сложения по модулю 2¹⁶ или 2³², циклического сдвига, замены и перестановки. Для повышения криптостойкости эти операции выполняются циклически несколько раз, образуя раунды или шаги. На стойкость шифра влияют такие факторы, как размер блока, размер ключа, количество раундов шифрования. Алгоритмы симметричного шифрования различаются способом, которым обрабатывается исходный текст. Возможно шифрование блоками или шифрование потоком. Блок текста рассматривается как неотрицательное целое число либо как несколько независимых неотрицательных целых чисел. Длина блока всегда выбирается равной степени двойки, например, 64, 128, 256 бит. Блочный алгоритм симметричного шифрования может иметь в своей основе сеть (схему) Фейштеля. В этом случае входной блок делится на несколько частей равной длины (ветви). Ветви обрабатываются по отдельности, после чего осуществляется циклический сдвиг всех ветвей влево.

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

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

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

    алфавит: abcdefghijklmnopqrstuvwxyz

    замена:  qazwsxedcrfvtgbyhnujmikolp

    замена2: poiuytrewqasdfghjklmnbvcxz

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

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