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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Данный алгоритм представляет из себя так же блочный шифр, но с одной отличительной особенностью - переменной длиной ключа и блоков. Длина может принимать значения 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 разбиты на байты. Эти байты, благодаря взаимно однозначному отображению, можно рассматривать как элементы вышеуказанного поля. Итак, рассмотрим функции:

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

,

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

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

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

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

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

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

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

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

.1 Понятие нейронной сети

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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