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

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

Введение

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

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

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

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

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

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]:

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

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