Основные способы шифрования информации

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

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

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

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

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

Перестановки - несложный метод криптографического преобразования. Используется как правило в сочетании с другими методами.

Гаммирование - этот метод заключается в наложении на исходный текст некоторой псевдослучайной последовательности, генерируемой на основе ключа.

Блочные шифры представляют собой последовательность (с возможным повторением и чередованием) основных методов преобразования, применяемую к блоку (части) шифруемого текста. Блочные шифры на практике встречаются чаще, чем “чистые” преобразования того или иного класса в силу их более высокой криптостойкости, а также потому, что этот метод позволяет шифровать тексты практически любой длины, разбивая их на блоки. Российский и американский стандарты шифрования основаны именно на этом классе шифров.

2.1 Перестановочные шифры

Простой столбцевой перестановочный шифр

В данном виде шифра текст пишется на горизонтально разграфленном листе бумаги фиксированной ширины, а шифротекст считывается по вертикали. Дешифрирование заключается в записи шифротекста вертикально на листе разграфленной бумаги фиксированной ширины и затем считывании открытого текста горизонтально. Открытый текст: ВОЛОГОДСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

В О Л О Г О

Д С К И Й

Г О С У Д А

Р С Т В Е Н

Н Ы Й П Е

Д А Г О Г И

Ч Е С К И Й

У Н И В Е

Р С И Т Е Т

Зашифрованный текст: ВДГРНДЧ РОСОСЫАЕУСЛКСТЙГСНИОИУВ ОКИТГЙДЕПГИВЕО АНЕИЙЕТ

Перестановочный шифр с ключевым словом

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

Открытый текст: Прикладная математика Ключ: Шифр Ш и ф р

4 1 3 2

П р и к

л а д н

а я м а

т е м а

т и к а

Криптограмма: Раяеикнаааидммкплатт

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

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

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

2.2 Подстановочные шифры

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

Метод Цезаря

Метод Цезаря является самым простым вариантом шифрования.

Он назван по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита, сдвигая его на 3 символа вперед.

Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст -- шифрованный текст”.

Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки преобразуется в еюыолхиврсеюивцнгкгрлб.

Таблица 1.1: Применение подстановки Цезвря.

При своей несложности система легко уязвима. Если злоумышленник имеет

1) шифрованный и соответствующий исходный текст или

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

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

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

Метод Цезаря с ключевым словом

В данной разновидности метод Цезаря ключ задается числом k (0<=k<=n-1) и коротким ключевым словом или предложением. Выписывается алфавит, а под ним, начиная с k-й позиции, ключевое слово. Оставшиеся буквы записываются в алфавитном порядке после ключевого слова. В итоге мы получаем подстановку для каждой буквы. Требование, чтобы все буквы ключевого слова были различными не обязательно - можно записывать ключевое слово без повторения одинаковых букв. Количество ключей в системе Цезаря с ключевым словом равно n!.

Аффинная криптосистема Обобщением системы Цезаря является аффинная криптосистема. Она определяется двум числами a и b, где 0<=a,b<=n-1. n - как и раньше, является мощностью алфавита. Числа a и n должны быть взаимно просты. Соответствующими заменами являются:

Aa,b(j)=(a*j+b)(mod n)

A-1a,b(j)=(j-b)*a-1(mod n)

Обратную замену также можно получить, просто поменяв местами строки в таблице замен.

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

Шифр Полибия

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

АБВГДЕ

ААБВГДЕ

БЖЗИЙКЛ

ВМНОПРС

ГТУФХЦЧ

ДШЩЪЫЬЭ

ЕЮЯ.,-

Каждая буква может быть представлена парой букв, указывающих строку и столбец, в которых расположена данная буква. Так представления букв В, Г, П, У будут АВ, АГ, ВГ, ГБ соответственно, а сообщение ПРИКЛАДНАЯ МАТЕМАТИКА зашифруется как ВГВДБВБДБЕАААДВБААЕБЕЕВАААГААЕВАААГАБВБДААЕЕ

Системы шифрования Вижинера

Метод Вижинера является следствием подстановки Цезаря. В системе Вижинера задается некая конечная последовательность ключа

k = (k0 ,k1 ,...,kn),

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

Например, при ключе пользователя 15 8 2 10 11 4 18 рабочий ключ будет периодической последовательностью:

15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18 ...

Таким образом:

При длине пользовательского ключа R

1) исходный текст x делится на R фрагментов

xi = (xi , xi+r , ..., xi+r(n-1)), 0 Ј i < r;

2) i-й фрагмент исходного текста xi шифруется при помощи подстановки Цезаря в зависимости от пользовательского ключа :

(xi , xi+r , ..., xi+r(n-1)) ® (yi , yi+r , ..., yi+r(n-1)),

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

Пример. Преобразование текста с помощью подстановки Вижинера (r=4)

Исходный текст (ИТ1):

НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ

Ключ: КЛЮЧ

Разобьем исходный текст на блоки по 4 символа:

НЕ_С ЛЕДУ ЕТ_В ЫБИР АТЬ_ НЕСЛ УЧАЙ НЫЙ_ КЛЮЧ

и наложим на них ключ (используя таблицу Вижинера):

H+К=Ч, Е+Л=Р и т.д.

Получаем зашифрованный (ЗТ1) текст:

ЧРЭЗ ХРБЙ ПЭЭЩ ДМЕЖ КЭЩЦ ЧРОБ ЭБЮ_ ЧЕЖЦ ФЦЫН

Криптостойкость метода резко убывает с уменьшением длины ключа.

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

Гаммирование

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

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

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

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

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

2.3 Блочные шифры

Блочные шифры представляют собой последовательность (с возможным повторением и чередованием) основных методов преобразования, применяемую к блоку (части) шифруемого текста. Блочные шифры на практике встречаются чаще, чем "чистые" преобразования того или иного класса в силу их более высокой криптостойкости. Российский (ГОСТ 28147-89) и американский(Rijndael) стандарты шифрования основаны именно на этом классе шифров.

Режим электронной шифровальной книги

Режим электронной шифровальной книги (electronic codebook) - это наиболее очевидный способ использования блочного шифра: блок открытого текста заменяется блоком шифротекста. Так как один и тот же блок открытого текста заменяется одним и тем же блоком шифротекста, то теоретически возможно создать шифровальную книгу блоков открытого текста и соответствующих криптотекстов. Однако, если размер блока 64 бита, то кодовая книга будет состоять из 264 записей, что слишком много для предварительного вычисления и хранения (для каждого ключа понадобится отдельная шифровальная книга). Это самый легкий режим работы. Все блоки открытого текста шифруются независимо и, следовательно, нет необходимости в последовательном шифровании, что важно для баз данных с произвольным доступом. Кроме того, обработка может быть распараллелена, на несколько шифровальных процессоров, независимо обрабатывающих различные блоки. Проблемой данного режима является то, что если у криптоаналитика есть открытый текст и шифротекст для нескольких сообщений, то он может начать составлять шифровальную книгу, не зная ключа. В большинстве реальных ситуаций фрагменты сообщений могут повторяться. Особенно уязвимы начало и конец сообщения, где находится информация об отправителе, получателе, дате, формате файла, и т.п. Положительными чертами являются возможность шифровать несколько сообщений одним ключом без снижения безопасности и нераспространении ошибок - при повреждении неверно дешифрируется только испорченный блок.

Режим сцепления блоков шифра

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

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

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

3. Криптосистемы с открытым ключом