Статистическое исследование аффинного шифра

Размещено на http://www.allbest.ru/

СТАТИСТИЧЕСКОЕ ИССЛЕДОВАНИЕ АФФИННОГО ШИФРА

Д. Бахаев, В. А. Ефремов, А. Д. Лаврентьев, М. Г. Семериков

Иркутский Государственный Технический Университет

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

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

Шифр - это какая-либо система преобразования текста с ключом для обеспечения секретности и аутентичности (аутентичность информации -- свойство, гарантирующее, что субъект или ресурс идентичны заявленным передаваемой информации).

Рассматриваемый нами аффинный шифр относится к классу симметричных шифров [1]. Симметричные шифры - это такие шифры, которые используют один и тот же ключ для шифрования и дешифрования. Существуют также ассиметричные шифры, в которых для шифрования и дешифрования используются разные ключи. То есть тот, кто владеет только ключом шифровки, не может расшифровать даже те данные, которые он зашифровал сам. В математике найдены функции, именующиеся односторонними, которые позволяют это реализовать.

Симметричные шифры подразделяются на блочные и поточные шифры. Отличительная особенность блочных шифров состоит в том, что они обрабатывают за одну итерацию сразу несколько байт (обычно по 8 или 16) открытого текста в отличие от потоковых шифров, которые обрабатывают по 1 байту (или биту). Аффинный шифр относится к поточным шифрам.

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

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

Представим, что у нас есть текст, зашифрованный шифром простой однозначной замены - то есть каждый символ заменяется каким-то другим символом по определенному закону. В качестве примера приведем шифр Цезаря: каждая буква смещается на 4 позиции вправо согласно алфавиту. Слово «мышь» шифруется следующим образом: буква «м» заменяется на «р», буква «ы» заменяется на «я» (сдвиг на 4 позиции вправо), и так далее. Результат такой замены показан на рис.1.

Получаем «ряыа». Ключом в данном случае является знание направления и количества смещения буквы.

Рис.1 Результат применения шифра Цезаря к слову «мышь».

Перейдем к самому алгоритму аффинного шифра. Для этого нужно определить несколько понятий. Мультипликативная группа - это множество чисел, в котором перемножение любых элементов, принадлежащих этому множеству, по модулю m дает элемент этого же множества [2]. Умножение/сложение некоторых чисел по модулю m (также используется обозначение «mod m») - это остаток от деления на m произведения/суммы чисел. Таблица Кэли - это квадратная матрица размерности m, в которой каждый элемент такой, что:

a_i,j = i*j(mod m);

C помощью таблицы Кэли находят мультипликативную группу.

Рис. 2 Таблица Кэли для умножения по модулю 10.

Числа, дающие при умножении по модулю m единицу, образуют мультипликативную группу.

Формула шифрования выглядит следующим образом [1]:

y = E(x) = (б x (mod m) + mod m;

формула дешифрования:

x = D(y) = б^-1((y - в) mod m)mod m;

где x - исходный, y - зашифрованный символ, должно принадлежать мультипликативной группе; в может быть любым целым числом, не превышающим размер алфавита программы (все символы, которые программа распознает и зашифрует). б^-1- это число из мультипликативной группы, такое, что:

(б б^-1)mod m = 1;

Из таблицы Кэли видно, что числа 1,3,7,9 из мультипликативной группы, соответственно 3 и 7 - обратные друг другу по mod 10.

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

Следующим этапом работы является исследование частотного анализа.

Частотный анализ текста - это статистика встречаемости букв в тексте по отношению к другим буквам. Мы реализовали на языке С++ программу - статистический анализатор, которая позволяет вывести статистику для заданного текстового файла.

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

Рис. 3 Гистограммы частотности букв главы №1 романа «Евгений Онегин».

Как видно, наиболее встречаемые буквы в этой главе - о, и, н, а, е.

Если мы зашифруем эту же главу аффинным шифром, то график частотности не изменится - буквы «поменяются» своей встречаемостью. В русском языке, согласно исследованиям лингвистов [3], буква «о» встречается чаще других (что, кстати, подтверждает наша программа). Соответственно, самую встречаемую букву в зашифрованном тексте можно условно заменить на «о» (при условии, что текст достаточно большой); исходя из этого, мы можем распознать в зашифрованном тексте короткие слова с «о», например «но», «об», «то» и т.д.

Однако стоит заметить, что частотная характеристика для текстов разных типов (например, художественное произведение и юридический документ) несколько различна. Статистика для Федерального закона Российской Федерации от 27 июля 2006 г. N 149-ФЗ «Об информации, информационных технологиях и о защите информации» изображена на рис.4.

Рис.4 Гистограмма частотности букв Федерального закона Российской Федерации от 27 июля 2006 г. N 149-ФЗ «Об информации, информационных технологиях и о защите информации»

Мы реализовали аффинный шифр на языках С++ и Python. Зашифруем ту же главу «Евгения Онегина». Пусть б = 3, в =4. б и в. Результат шифрования (фрагмент):

hАc AАos ksЛ so g)YУkУA)IхН NА)Iх oАПУЫПMН AУЗosЗАIхН

FАЯMЗУAБIхН ЯАEIАЗ)Iх ЗУA)IхН hАЯАIхEБ kAАвoсkН )ЯoсЗАIхН

ЁЗgБIхEБ ЛsAПсk ) wsEgMёoсkН Мo)kАIУgхoсk )gх AАЗosПMёoсka

hАc Iskos Дсg so ksgвАg)ЗН cAАEosAУв)ЗН

М EУAПУвoсU w)EхkАU cАc oУДAУЫУoa xПo)k ПсёАН sПos gэДБН

hАc so MkУg ЯАДсIх EУДБa hАc ЗЯsA УЛs Дсg ДсEIA ) oУЫУoН

JIсПg)З ) ПУAЯscН А wsAs? Иg)EIАg wsEgMёosэ EgУЯs?a

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

Рис. 5 Гистограммы частотности букв главы №1 романа «Евгений Онегин».

Рис. 6 Гистограммы частотности букв зашифрованной главы №1 романа «Евгений Онегин» (б = 3, в =4).

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

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

Рис. 7 Гистограммы частотности букв главы №1 романа «Евгений Онегин», б, в выбираются случайно после каждого слова.

Рис. 8 Гистограммы частотности букв зашифрованной главы №1 романа «Евгений Онегин» (б = 3, в =4).

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

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

информация криптология шифрование защита

Литература

1. Алферов А.П., Зубов А.Ю. Основы криптографии. М.: Гелиос АРВ, 2005.

2. Нечаев В.И. Элементы криптографии. М.: Высшая школа, 1999.

Размещено на Allbest.ru