Криптография и симметричное шифрование

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

Введение

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

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

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

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

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



1. Криптография и симметричное шифрование

1.1 Зарождение и развитие криптографии

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

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

Следующий метод носит название «стеганография», полученное сочетанием греческих и латинских слов, и переводящийся как «тайнопись». Данный метод подразумевает под собой сокрытие самого факта существования информации. В прошлых веках очень распространенным использованием данного метода были симпатические чернила, проявляющиеся только при определенных манипуляциях. Так же довольно интересный пример «стеганографии» приводит древнегреческий историк Геродот в своих записях [2]. Он описывает процесс, когда голову раба брили налысо, и наносили на нее текст письма. По истечении некоторого времени, когда волосы отрастали заново, раба посылали к адресату, который снова брил голову раба и таким образом мог прочесть письмо. Очевидно, что реализации данного метода ограничены лишь воображением, и при этом имеют огромные проблемы с защищенностью от множества факторов. Таким образов в наше время данные методы в большинстве своем остались лишь в виде развлечений, хотя всегда найдутся люди, использующие данный метод и для чего-то важного.

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

Один из самых старых известных способов шифрования был найден в Месопотамии [2]. Это был рецепт изготовления глазури для глиняных изделий, и в системе шифровки использовались редко употребляемые знаки клинописи, игнорировались некоторые гласные и согласные буквы и вместо имен употреблялись цифры.

Чаще всего в древности для шифров использовались методы замены и перестановки. Одним из наиболее известных методов замены является шифр Цезаря. Это было собственное изобретение Цезаря, и он использовал этот шифр для своих переписок. Алгоритм шифрования заключался в сдвиге алфавита на 3 буквы влево. Рассмотрим его на примере русского алфавита. Сначала записывается обычный алфавит, затем под ним записывался этот же алфавит, сдвинутый на три символа влево (рис.1):

Рис. 1 - Таблица сдвига алфавита на 3 символа влево

Соответственно при шифровке буква А заменялась на Г, Б на Д, и т д. Например зашифрованное таким образом слово

будет выглядеть как

Обратная дешифровка происходила по нижней строке, буквы в ней сопоставлялись с буквами верхней. Ключом к данному шифру является число 3. Любопытно, что преемник Юлия Цезаря, Цезарь Август, использовал этот шифр со сдвигом на 4 буквы.

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

Для шифрования выберем число 7. В данной фразе 40 символов, не считая пробелов, таким образом разделить ее на группы по 7 символов не получится, поэтому дополним ее символами «ЪЬ» и полученные 42 символа разделим на 6 групп по 7 символов

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

Рис. 2 - Перестановка для группы при шифровании

В каждой группе производим эту перестановку, то есть для группы «МОСКОВС» переставим 1 и 2 символы, 2 и 4 и т д. Получим «ОКВСМСО». Вся фраза будет выглядеть так

Запишем ее без пропусков

Понять, что тут написано, стало невозможно.

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

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

С наступлением Нового времени криптография получила вторую жизнь, главным образом за счет бурного развития дипломатии. Во множестве государств при дворе появилась должность «секретаря по шифрам», чьей работой было составлять различные методы шифрования для «своих» и взламывать и расшифровывать чужие сообщения. Криптография в это время развивалась стремительными темпами так же и потому, что многие ученые люди довольно часто использовали ее в своих работах - Леонардо да Винчи, Франсуа Виет, Готфрид Лейбниц, Исаак Ньютон и многие другие развивали эту науку. Единственным препятствием ее развития была большая секретность. После этого большого скачка, в развитии криптографии снова образовался застой - большинство разработанных шифров использовались повсеместно и не требовались в доработке, а особо важные сообщения все равно так или иначе взламывались. И так продлилось до середины 20 века, когда потребности Второй Мировой войны и развитие ЭВМ позволили этой науке расцвести в то, какой мы ее знаем сейчас. Так же в 20 веке стали развиваться способы механического шифрования, при помощи специально разработанных механизмов и машин [6]. При этом методы механической шифровки были довольно просты, поэтому ручное шифрование использовалось повсеместно.

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

Во время Второй Мировой войны криптография получила широчайшее развитие в основном за счет разработки немецких криптоаналитиков. Этой разработкой была криптографическая машина «Энигма» [6], которая была одновременно механическим шифратором и дешифратором с достаточно большой стойкостью. При этом «Энигма» постоянно усложнялась механически, что делало возможность ее взлома еще более призрачной. Однако за счет того, что несколькими польскими учеными до начала войны были разработаны методы дешифровки «Энигмы», которые позже были переданы британской разведке, а так же за счет захваченных во время войны моделей, разведке ужалось добиться немалых успехов. Британские криптографические службы, расположенные в Блэтчли Парк, занимались дешифровкой и взломом «Энигмы» день и ночь. За счет постоянного механического усложнения, взлом был очень долгим до тех пор, пока Алан Тьюринг не разработал ЭВМ под названием «Колосс» [6], которая была специализирована для взлома шифров «Энигмы». Благодаря этому теперь криптоаналитики могли меньше чем за день взломать любой шифр, поскольку разработка «Энигмы» велась с учетом того, что взлом будет производиться вручную, а не при помощи ЭВМ. При всем при том, даже «Колосс» был бессилен перед взломом шифров, передаваемых не из армии, а из немецких криптографических центров. Однако, по сути, лишь цепочка ошибок немецких операторов и случайностей позволила разведке получить данные об «Энигме» и взломать ее шифры.

В это время стали появляться криптосистемы, основанные на строгом математическом обосновании их стойкости. Развились разделы математики, напрямую связанные с криптографией: теория вероятностей и математическая статистика, теория чисел, теория алгоритмов, кибернетика, теория информации. Одним из основных прорывов того времени стала работа Клода Шеннона «Теория связи в секретных системах», опубликованная в 1949 году [7]. В этой книге были сформулированы теоретические принципы шифрования и защиты информации, а так же была обоснована возможность создания криптосистемы сколь угодно большой стойкости.

С появлением по-настоящему мощных ЭВМ появилась возможность реализовывать криптосистемы со стойкостью, превосходящей стойкость ручных и механических на несколько порядков. В 1978 году был принят американский стандарт шифрования DES, благодаря которому было создано множество новых видом криптоанализа, реализация которых опять же была возможна лишь при больших вычислительных мощностях ЭВМ. Позже появились ассиметричные криптосистемы, ставшие настоящим прорывом в области шифрования, поскольку они не требовали передачи секретного ключа между сторонами. Одной из первых самых известных ассиметричных криптосистем была система RSA, которая позволила развить криптографию в целый перечень различных направлений, в том числе систему электронной цифровой подписи и электронных денег [8]. Дальше криптография развивается семимильными шагами и на сегодня является одной из самых востребованных и обширных математических наук.

1.2 Симметричное шифрование и его особенности

Рассмотрим формальное определение криптосистемы. Криптографическая система должна состоять из следующих компонентов [3]:

Пространство исходных сообщений, то есть множество строк над некоторым алфавитом;

Пространство зашифрованных текстов, то есть множество всех возможных полученных шифров;

Пространство ключей зашифрования и пространство ключей расшифровки, то есть множество всех возможных ключей зашифрования и расшифровки;

Эффективный алгоритм генерации ключей;

Эффективный алгоритм шифрования;

Эффективный алгоритм расшифровки;

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

Симметричные криптосистемы основываются на нескольких базовых классах [4]:

1) Моноалфавитные и многоалфавитные подстановки;

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

2) Перестановки;

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

3) Блочные шифры;

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

4) Гаммирование;

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

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

Рассмотрим самые известные алгоритмы симметричного шифрования. Первым из них безусловно является алгоритм DES, что расшифровывается Data Encryption Standard [3]. Этот алгоритм был первым одобренным международным сообществом и он и его модификации были стандартами для шифрования открытых данных (то есть не государственной секретной информации, имеющей отношение к национальной безопасности) вплоть до 2002 года, когда на смену ему пришел AES [3].

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

Рассмотрим работу этого алгоритма. Ее можно разделить на три шага:

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

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

Рис. 3 - Общая схема перестановок блоков при раундах шифрования (где Li и Ri - левая и правая части блока соответственно)

3) Далее, с результатом 16 раунда проводится еще одна перестановка, являющаяся обратной к перестановке, проводимой на первом шаге.

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

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

Споры о стойкости данного алгоритма начались почти сразу после принятия его, как стандарта. Все они в общем сводились к тому, что этот алгоритм использует слишком короткий ключ, что является слабым местом. Атаки на это слабое место заключались в полном переборе ключей и называются «атака в лоб». Однако такая атака не считается реальной и для вычислительных мощностей 70-х годов этот алгоритм является весьма стойким. Но к 90-м годам этот алгоритм перестал быть безопасным. В 1993 году было продемонстрировано, что стоимость машины, способной взломать алгоритм DES, составляет всего 1 миллион долларов, и взлом займет всего лишь три с половиной часа при известной паре «исходный текст - зашифрованный текст». Дальше, в 1998 году группа исследователей из коалиции компаний Cryptography Research, Advanced Wireless Technology и Electronic Frontier Foundation создали машину DES-Cracker стоимостью всего лишь 250 тысяч долларов, которой удалось взломать этот шифр за 56 часов [3]. Стало понятно, что для вычислительных мощностей этого времени 56-битный ключ действительно слишком короток.

В 1997 году Национальный институт стандартов и технологий США начал разработку алгоритма, призванного заменить стандарт DES. Этот алгоритм назвали AES, что расшифровывается как Advanced Encryption Standard. Причем его разработка в отличие от DES не была засекречена и широко освещалась. В 1998 году был представлен набор из 15 алгоритмов. Подходящих на роль AES. Они были собраны со всего мира и они были подвергнуты глубокому исследованию во всех областях. Исследования длились 2 года и в 2000 году было объявлено, что победил алгоритм, носивший название Rijndael, разработанный двумя бельгийскими криптографами - Дааменом(Daemen) и Рийменом(Rijmen) [3].

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

Как и большинство симметричных блочных шифров, AES состоит из нескольких раундов, для минимального случая 128 бит число раундов равно 10, но оно может увеличиваться. Каждый раунд можно описать функцией Round(State, RoundKey), которая получает на вход матрицу State (в первом раунде это исходный текст, в промежуточных - его преобразования и в заключительном раунде на выходе State является зашифрованным текстом) и матрицу RoundKey, являющуюся ключом раунда, при помощи которого и происходит преобразование переменной State. Сама функция Round состоит из четырех подфункций, которые и производят преобразования. Эти функции: SubBytes(State), ShiftRows(State), MixColumns(State) и AddRoundKey(State, RoundKey). Последний раунд называется FinalRound(State, RoundKey) и совпадает по своему выполнению с одним из промежуточных раундов без функции MixColumns(), что делает его похожим на заключительный раунд алгоритма DES. Для возможности расшифровки все функции раундов и их подфункции являются обратимыми. Рассмотрим действие внутренних функций каждого раунда. Все функции определены на конечном поле, состоящем из полиномов по модулю данного неприводимого полинома

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

1) SubBytes(State) - данная функция выполняет подстановку каждого байта в переменной State. Происходило это при помощи такого преобразования:

,

где х - это значение байта, А - некоторая обратимая матрица 8х8, b - вертикальный вектор, у - полученная подстановка байта. Если число х является нулевым байтов, то в результате получим .

За счет обратимости матрица А вся функция так же является обратимой;

2) ShiftRows() - данная функция применяется к матрице State построчно. Происходит операция перестановки, которая для каждой i-ой строки сдвигает ее циклически на n-i позиций вправо, где n - количество строк. Так как данный перестановочный шифр меняет лишь элементы строк, эта функция является обратимой;

3) MixColumns() - данная функция применяется к каждому столбцу матрицы State. Каждый столбец в нашем случае состоит из 4 элементов (вся матрица 4х4). Столбец преобразуется в полином третьей степени, где элементы столбца - коэффициенты полинома. Операцией с этим столбцом является домножение полученного полинома на некоторый полином третьей степени по модулю . Такое преобразование можно считать полиалфавитной подстановкой с известным ключом. Это преобразование так же является обратимым;

4) AddRoundKey() - данная функция производит сложение элементов переменных State и RoundKey байт за байтом и бит за битом. Очевидно, что данная функция так же является обратимой;

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

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



2. Нейронные сети

2.1 Понятие нейронной сети

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

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

2.2 Нейронная сеть и области ее использования

Согласно определению нейронной сети, это «громадный распределенный процессор, состоящий из элементарных единиц обработки информации, накапливающих экспериментальные знания и предоставляющих их для последующей обработки»[1]. Нейронная сеть имеет два критерия, по которым она схожа с человеческим мозгом:

1) Нейронная сеть обучается путём получения знаний из окружающей среды;

2) Знания накапливаются при помощи синаптических связей между нейронами (синаптические веса);

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

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

Выделяют несколько важных свойств нейронных сетей:

1) Нелинейность - чрезвычайно важное свойство, позволяющее решать нестандартные задачи и дающее большую гибкость при их выполнении;

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

3) Адаптивность - возможность нейронной сети перестраиваться при изменениях параметров окружающей среды. Например, нейронные сети, созданные для работы в одной среде, достаточно легко переобучить под работу в другой. Так же можно создать нейронную сеть, меняющую синаптические веса в реальном времени в зависимости от изменений среды. Однако нужно осторожно пользоваться этим свойством, поскольку слишком часто перестраивающаяся нейронная сеть теряет в производительности и может быть выведена из равновесия посторонними возбуждениями;

4) Очевидность ответа - нейронная сеть имеет возможность проверять достоверность того или иного ответа, что впоследствии может повысить продуктивность сети путем исключения сомнительных ответов;

5) Контекстная информация - каждый нейрон может подвергнуться влиянию любого другого нейрона, за счет чего знания в нейронной сети представляются путем ее состояния активации;

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

7) Масштабируемость - за счет параллельности позволяет значительно ускорить выполнение некоторых задач;

8) Единообразие анализа и проектирования - нейронные сети имеют универсальную структуру, и одно и то же проектное решение можно использовать в абсолютно разных областях.

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

2.3 Основные составляющие нейронной сети

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

Рассмотрим основную составляющую нейронной сети - нейрон. Нейрон является единицей обработки информации в нейронной сети. На Рис.4 показана модель нейрона, используемого в искусственных нейронных сетях.



Рис. 4 - Общая схема искусственного нейрона

На рисунке можно выделить три основных элемента нейрона:

1) Набор синапсов - множество входных сигналов, характеризуемых весом. Каждый из сигналов х умножается на свой вес w. Значения весов могут быть как положительные, так и отрицательные (в отличие от синапсов мозга);

2) Сумматор - ячейка нейрона, в которой происходит сложение входных сигналов. Эту операцию еще называют линейной комбинацией;

3) Функция активации - регулирует выходной сигнал нейрона. Обычно значение сигнала варьируется от 0 до 1 или же от -1 до 1.

Функция активации является одной из основных составляющих нейрона. Существует три основных типа функции активации [1]:

1) Функция единичного скачка или пороговая функция - это функция, которая может принимать значения 0 или 1, в зависимости от поступившей переменной. Записать ее можно так:

2) Кусочно-линейная функция - эту функцию чаще всего рассматривают, как аппроксимацию нелинейного усилителя. Она так же принимает значения в зависимости от входной переменной, но кроме 0 и 1 она может принимать значение самой переменной, взятой по модулю.

3) Сигмоидальная функция - это монотонновозрастающая функция, график которой напоминает букву S. Чаще всего именно эту функцию используют в нейронных сетях. Она имеет множество видов, например логистическая функция:

где а - параметр наклона кривой

Описанная выше модель нейрона является детерминистской моделью. Однако чаще полезно использовать стохастическую модель, которая отличается тем, что нейрон может переключаться между двумя состояниями: -1 и 1.



3. Постановка задачи

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

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

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



4. Математическая модель нейронной сети на базе базисно-радиальных функций

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

Рис. 5 - Схема гиперсферы, и накладываемые ограничения

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



4.1 Структура базисной радиальной нейронной сети

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

Рис. 6 - Структура радиально-базисной нейронной сети

(где xi - входы сети, y - выход сети, - функция активации, - веса) а функция преобразования нейронной сети выглядит так

где сi - центры в функции Гаусса, xp - элементы обучающей выборки от 1 до р

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

4.2 Построение нейронной сети

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

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

4.3 Математическая формализация

Теоретическую основу подхода построения радиально-базисных нейронных сетей представляет теорема Ковера о разделимости множеств. Она утверждает следующее:

«Нелинейное преобразование сложной задачи классификации образов в пространство более высокой размерности повышает вероятность линейной разделимости образов.»

Данная теорема базируется на двух моментах:

1) Задание нелинейной скрытой функции , где х - входной вектор, i=1…, - размерность скрытого пространства.

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

Ковер доказал, что любое множество образов, размещенных на некотором пространстве, тем более разделимо, чем больше это пространство в сравнении с первоначальным пространством этих образов. Если задать , как вероятность разделимости, то:

,

где определяется формулой .

Так же из теоремы Ковера можно сформулировать, что если вектор радиальных функций в N-мерном входном пространстве обозначить , то это пространство является нелинейно -разделяемым на два пространственных класса X+ и X- тогда, когда существует такой вектор весов, что

граница между этими классами определяется уравнением

Увеличение размерности скрытого слоя позволяет увеличить вероятность линейной разделимости, однако для некоторых случаев достаточно простого нелинейного преобразования без увеличения размерности. Чаще всего при преобразовании T различных векторов необходимо использовать T нейронов скрытого слоя. За счет этого в контексте задачи разработки алгоритма симметричного шифрования, следует использовать столько нейронов скрытого слоя, сколько имеется кластеров для шифруемых символов.

В качестве функции активации в радиально-базисной нейронной сети чаще всего используют функцию Гаусса:

где r=x-ci - расстояние от данной точки до центра ci гипершара, у - ширина функции

Центр гипершара и значение у определяются в процессе обучения сети. Радиальная сеть с функцией Гаусса выглядит так (рис.7):

Рис. 7 - Радиально-базисная нейронная сеть на основе функций Гаусса

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



5. Алгоритм симметричного шифрования данных на основе базисной радиальной сети

5.1 Алгоритм шифрования

Реализация алгоритма шифрования состоит из нескольких основных этапов:

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

далее следует построение самой нейронной сети - выбор типа используемой нейронной сети, определение ее структуры и обучение (получение значений весовых коэффициентов);

и наконец, основной этап, на котором происходит сам процесс шифрования.

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

На Рис.8 показана основная схема работы алгоритма:

Рис. 8 - Общая схема работы алгоритма шифрования



5.2 Предварительный этап

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

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

1) Для каждого символа генерируется количество областей с учетом частоты вхождения символов, и получается вектор количества областей , где - количество различных символов, - число областей для каждого класса.

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

В качестве примера рассмотрим такое шифруемое сообщение: «jerome k. jerome. three men in a boat (to say nothing of the dog). there were four of us - george, and william samuel harris, and myself, and montmorency.». Очевидно, что частота использования символов не равномерна. Например пробел встречается 28 раз, «e» - 17 раз, символы «k, b, c, (, )» - по одному разу. Рассмотрим основные статистические показатели текста:

Общее количество символов в сообщении: 154

Размер алфавита: 27

Среднее значение частоты появления символа: 0,037

Минимальное значение частоты появления символа: 0,0065

Максимальное значение частоты появления символа: 0,1818

На Рис.9 показано сравнение частоты использования символов во входной последовательности и распределения точек по пространству шифрования с соответствующими классами входной последовательности.

Рис. 9 - Сравнение частотности символов в сообщении и точек в кластерах

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

5.3 Построение нейронной сети

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

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

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

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

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

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



5.4 Обучение нейронной сети

Процесс обучения радиально-базисной нейронной сети сводится к двум действиям:

1) Подбору центров ci и значений у в базисной функции. Для этого чаще всего используют алгоритмы без учителя;

2) Распределению весов нейронов выходного слоя. Для этого чаще всего используют алгоритмы с учителем.

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

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

Рассмотрим процесс обучения подробнее:

1) Самое первое действие - это предобработка данных. Каждый символ исходного текста двоично кодируется кодом bj. После производится анализ входного текста на частотность вхождения в него символов и составляется соотношение lj для символа, показывающее частотность каждого символа. Далее на основе этого соотношения производится создание поля кластеров, по которым будут распределены символы текста. Поле задается таким образом:

В двумерном пространстве размером N*k X N*k случайно распределяются N точек (где N - требуемое количество кластеров, равное i*M, где M - количество символов, i=1,2,3…), с единственным правилом - они должны быть не менее чем на 2*k удалены друг от друга от границ выбранного пространства;

Далее производится пошаговое увеличение их радиусов с одним требованием - скорость увеличения aj прямо зависит от lj каждого кластера;

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

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

2) Далее происходит создание набора данных для обучения нейронной сети. Набор создается путем выбора определенного количества точек z из каждого кластера и соотношения их с двоичным кодом b каждого символа. Наборы упорядочиваются и подготавливаются для обучения нейронной сети.

3) Третий шаг - создание скрытого слоя нейронной сети. Количество нейронов скрытого слоя равно N - количеству кластеров, заданных для символов. В каждом нейроне задается своя функция активации. В качестве функции активации используется функция Гаусса

где r=x-ci - расстояние от данной точки до центра ci гипершара, у - ширина функции

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

4) Далее созданная нейронная сеть обучается с помощью полученных ранее обучающих выборок. Корректировка весов выходов нейронов скрытого слоя происходит с использованием псевдообратной матрицы Грина G, в которой xi обозначает все обучающие выборки, а K - количество нейронов скрытого слоя

где x-входные данные, сi-центр кластера радиально-базисной функции, - радиально-базисная функция нейрона скрытого слоя

С использованием этой матрицы можно легко определить вектор весов скрытого слоя с использованием псевдоинверсии:

, где , d - вектор ожидаемых значений

5.5 Основной этап

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