Исследование алгоритмов восстановления пароля по SHA1-хешу

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

КУРСОВАЯ РАБОТА

Исследование алгоритмов восстановления пароля по SHA1-хешу

Введение

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

? неавторизованный доступ к информации;

? неавторизованное изменение информации;

? неавторизованный доступ к сетям и другим сервисам;

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

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

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

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

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

1. Анализ технического задания

1.1 Выбор метода шифрования

Любая ценная информация, которая распространяется на разнообразных носителях, или по каналам связи в локальных и глобальных сетях, может быть модифицирована по некоторым правилам, с целью сохранения ее конфиденциальности и целостности.

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

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

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

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

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

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

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

В данной работе будет реализовано аппаратное шифрование, потому что этот метод:

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

- исключает какое-либо вмешательство в процесс шифрования.

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

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

1.2 Обзор аналогов разрабатываемого устройства

защита шифрование аппаратный микроконтроллер

Большая часть устройств для аппаратного шифрования реализована в виде PCI плат расширения или приборов типа USB-ключ. Производителями подобных продуктов являются, в основном, Россия, США и Япония.

1.2.1 «Криптон»

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

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

- осуществлять электронную цифровую подпись файлов, проверяя их целостность и авторство;

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

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

- создавать системы защиты информации от несанкционированного доступа и разграничения доступа к компьютеру.

Основные технические данные и характеристики

Алгоритм шифрования ГОСТ 28147-89

Размерность ключа шифрования, бит 256 Количество уровней ключевой системы 3

Датчик случайных чисел аппаратный (аттестован экспертной организацией)

Шина PCI (Bus Master, Target)

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

Скорость шифрования, Кбайт/с до 8500

Носители ключей дискеты, смарт-карты

1.2.2 «ruToken»

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

1. Аутентификация - замена парольной защиты при доступе к БД, Web-серверам, VPN-сетям и security-ориентированным приложениям на программно-аппаратную аутентификацию; ? защищенные соединения при доступе к почтовым серверам, серверам баз данных, Web-серверам, файл-серверам, аутентификации при удаленном доступе.

2. Защита данных ? защита информации (шифрование по ГОСТ 28147-89); ? защита электронной почты (ЭЦП, шифрование); ? защита доступа к компьютеру (авторизация пользователя при входе в операционную систему).

Общие технические характеристики ruToken:

- Аппаратное шифрование по ГОСТ 28147-89;

- Файловая система по ISO 7816;

- 8, 16 или 32 Кбайт энергонезависимой памяти;

- Поддержка PC/SC, PKCS#11, MS CryptoAPI, X.509.

- Базируется на защищенном микроконтроллере;

- Интерфейс USB (USB 1.1 / USB 2.0);

- EEPROM память 8, 16 и 32 Кб;

- 2-факторная аутентификация (по факту наличия ruToken и по факту предъявления PIN-кода;

- 32-битовый уникальный серийный номер;

- Поддержка стандартов ISO/IEC 7816, PC/SC, ГОСТ 28147-89, MS CryptoAPI и MS SmartcardAPI;

- Возможность интеграции в любые smartcard-ориентированные программные продукты (e-mail-, internet-, платежные системы и т.п.).

1.3 Аспекты создания устройства для аппаратного шифрования

1.3.1 Структура аппаратного шифратора

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

Блок управления, служит для управления работой всего шифратора. Обычно он реализован на базе микроконтроллера. Шифропроцессор представляет собой специализированную микросхему или микросхему программируемой логики (PLD - Programmable Logic Device), которая выполняет шифрование данных. Для генерации ключей шифрования в устройстве предусмотрен аппаратный датчик случайных чисел (ДСЧ), вырабатывающий статистически случайный и непредсказуемый сигнал, преобразуемый затем в цифровую форму. Обмен командами и данными между шифратором и компьютером обеспечивается контроллером. Для хранения программного обеспечения микроконтроллера необходима энергонезависимая память, реализованная на одной или нескольких микросхемах. Это же внутреннее ПЗУ используется для записи журнала операций и других целей.

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

Помимо функций шифрования информации, каждый шифратор должен обеспечивать:

- выполнение различных операций с ключами шифрования: их загрузку в шифропроцессор и выгрузку из него, а также взаимное шифрование ключей;

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

- генерацию случайных чисел по запросу.

1.3.2 Ключевые схемы и процесс шифрования файлов

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

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

Трехуровневую схему лучше всего иллюстрирует упрощенный пример процесса шифрования файла (Рисунок 1.1). На этапе начальной загрузки в ключевую ячейку №3 заносится главный ключ. Сеансовый ключ генерируется в результате запроса к ДСЧ шифратора на получение случайного числа, которое загружается в ключевую ячейку №1, соответствующую сеансовому ключу. С его помощью шифруется содержимое файла и создается новый файл, хранящий зашифрованную информацию.

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

Рис. 1.1 - Шифрование файла

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

Преимущества многоуровневой ключевой схемы:

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

- при смене долговременного ключа можно быстро перешифровать файл: достаточно перешифровать сеансовый ключ со старого долговременного на новый.

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

1.3.3 Хэширование паролей

При разработке любого криптоалгоритма следует учитывать, что в половине случаев конечным пользователем системы является человек, а не автоматическая система. Необходимо принимать во внимание тот факт, что пользователю придется запоминать ключ длиной до 4096 битов (512 ASCII символов), а предел запоминаемости чисел человеческим мозгом лежит на границе 12-15 символов.

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

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

- бесконечная область определения;

- конечная область значений;

- необратимость;

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

Эти свойства позволяют подавать на вход хэш-функции пароли произвольной длины и, ограничив область значений функции диапазоном 0..2^N-1, где N - длина ключа в битах, получать на выходе достаточно равномерно распределенные по области значения блоки информации - ключи. Размер пароля ограничен исключительно используемым алгоритмом хэширования. Например, при использовании хэш-функции SHA2, с длиной результата в 384 бита, на вход можно подавать число меньшее бита. Если пароль - строка ASCII символов, то длина пароля в этом случае ограничена символами. Это значит, что паролем могут быть строки текста, цитаты или стихотворения, что значительно улучшает запоминание пароля.

1.3.4 Длина ключа, используемого в криптосистеме

Любой шифровальный алгоритм с использованием ключа, может быть вскрыт методом перебора всех значений ключа. Если ключ подбирается методом грубой силы (brute force), требуемая мощность компьютера растет экспоненциально с увеличением длины ключа. Ключ длиной в 32 бита требует для вскрытия шагов. Системы с 40-битным ключом требуют шагов. Системы с 56-битными ключами могут быть легко вскрыты с помощью специальной аппаратуры (используя суперкомпьютер стоимостью 250 тыс. долларов, сотрудники RSA Laboratory «взломали» утвержденный правительством США алгоритм шифрования данных DES менее чем за три дня. Полный перебор ключа длиной 64 бита для RC5 в настоящее время продолжается. Ключи длиной 80 бит могут в будущем стать уязвимыми. Ключи длиной 128 бит вероятно останутся недоступными для вскрытия методом грубой силы в обозримом будущем. Можно использовать и более длинные ключи.

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

В 2007 году, группа Швейцарских ученых под руководством Арьена Ленстра осуществила факторизацию 700 битного ключа. Арьен Ленстра считает, что взлом 1024 битного RSA шифра станет возможным через 5-10 лет. Ключи длиной в 2048 и 4096 бит, криптоаналитики считают надежными на десятилетия.

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

1.3.5 Проблемы, возникающие при шифровании файлов

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

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

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

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

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

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

1.4 Выбор алгоритма шифрования

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

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

Ограниченные алгоритмы непригодны при современных требованиях, предъявляемых к шифрованию, потому что:

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

- невозможно применение готового оборудования и стандартных программ;

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

В криптографии, описанные проблемы решаются при помощи использования ключа, который обозначается буквой «К» (от английского слова key). Ключ должен выбираться среди значений, принадлежащих множеству, которое называется ключевым пространством. И функция шифрования «Е», и функция расшифровки «D» зависят от ключа. Этот факт выражается присутствием «К» в качестве подстрочного индекса у функций «Е» и «D»:

Е к (Р) = С (1.1)

D к (С) = Р (1.2)

Справедливо следующее тождество:

D k (E k (P)) = P (1.3)

Некоторые алгоритмы шифрования используют различные ключи для шифрования и расшифровки. Это означает, что ключ шифрования «К₁» отличается от ключа расшифровки «К₂». В этом случае справедливы следующие соотношения:

Е _k1 (P) = С (1.4)

D _k2 (С) = Р (1.5)

D _k2 (E _k1 (Р)) = Р (1.6)

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

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

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

1.4.1 Симметричные алгоритмы шифрования

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

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

Блочные алгоритмы

Тройной DES

Базовый алгоритм DES был разработан фирмой IBM в середине 1970-х годов. Через несколько лет, DES был принят в качестве государственного стандарта шифрования США. Тройной DES - это вариация DES, в которой базовый алгоритм выполняется трижды на одном блоке данных. Длина общего ключа - 168 бит (в DES - 56 бит). Алгоритм оперирует 64-битовыми блоками данных. Расчётная стойкость такого алгоритма к лобовой атаке составляет 112 бит.

AES

«Улучшенный стандарт шифрования» (Advanced Encryption Standard). Алгоритм принят национальным институтом стандартов и технологий (NIST) США в 1999 году в качестве стандарта шифрования важных несекретных коммуникаций. Пришел на смену устаревшему DES. Авторское название - Rijndael («Рэндал»). Это блочный шифр со 128-, 192- или 256-битовым размером ключа и 128-битовым блоком.

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

CAST

Представляет собой шифр со 128-битовым ключом и 64-битовым блоком. Дизайн основан на формальной архитектуре DES с доказанной стойкостью. Не имеет слабых ключей. Алгоритм совершенно устойчив к линейному и дифференциальному криптоанализу. Может быть взломан только методом прямого перебора.

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

Twofish

Один из пяти финалистов на звание AES. Группу разработчиков возглавлял Брюс Шнайер. В реализации использует 256-битовый ключ и 128-битовый блок данных.

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

Blowfish

Автором алгоритма является Брюс Шнайер. Алгоритм представляет собой блочный шифр с ключом переменной длины (вплоть до 448 бит), оперирующий на 64-битовых блоках.

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

Автор алгоритма, Брюс Шнайер, рекомендует использовать Blowfish во встраиваемых системах анализа, обработки и преобразования данных.

Потоковые шифры

RC4

Это потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколе SSL и для шифрования паролей в Windows NT). Шифр разработан компанией RSA Security Inc. Для его использования требуется лицензия.

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

В США длина ключа для использования внутри страны рекомендуется равной 128 битов. Алгоритм имеет специальный статус, который означает, что разрешено экспортировать реализации RC4 с длинной ключа до 40 бит.

RC4 в 10 раз быстрее DES и устойчив к криптоанализу. S-блок медленно изменяется при использовании.

WAKE

Алгоритм WAKE (Word Auto Key Encryption) выдаёт поток 32-битных слов, которые с помощью XOR могут быть использованы для получения шифротекста. Для генерации следующего слова ключа используется предыдущее слово шифротекста. Это быстрый алгоритм. Алгоритм использует S блок из 256 32-битовых значений. Этот S-блок обладает одним особым свойством: старший байт всех элементов представляет собой перестановку всех возможных байтов, а 3 младших байта случайны.

Самым ценным качеством WAKE является его скорость. WAKE чувствителен к вскрытию с выбранным открытым текстом или выбранным шифротекстом.

1.4.2 Алгоритмы шифрования с открытым ключом

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

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

RSA

Это криптографическая система с открытым ключом, обеспечивающая оба механизма защиты: шифрование и цифровую подпись. Криптосистема RSA была разработана в 1977 году и названа в честь авторов: Рональда Ривеста, Ади Шамира и Леонарда Адельмана.

Принцип действия RSA состоит в следующем. Для начала сгенерируем пару ключей:

1. Возьмём два больших случайных простых числа p и q (т.е. числа делящихся только на себя и на 1) приблизительно равной разрядности, и вычислим их произведение

n = p•q (1.7)

2. Выберем число e, взаимно простое с произведением (p-1)*(q-1). Взаимно простыми называют числа, у которых нет общих множителей кроме 1 (например, 15 и 28 - являются, 15 и 27 - нет: кроме 1 их общий множитель - 3).

3. Вычисляется число d, взаимно простое с n.

d = e^-1mod((p-1)•(q-1)) (1.8)

Числа e и n становятся открытым ключом. Число d - закрытым. Чтобы создать шифротекст c из сообщения m, необходимо выполнить:

c = m^e mod n (1.9)

Чтобы расшифровать полученный шифротекст, необходимо выполнить:

m = c^d mod n (1.10)

Пока не найдены эффективные методы разложения чисел на множители, невозможно факторизовав n получить p и q, а, следовательно, и показатель закрытого ключа d. Таким образом, надежность криптосистемы RSA базируется на трудноразрешимой задаче разложения n на множители. Несмотря на фактическую сложность разложения больших чисел на множители, научно не доказано, что факторизация является трудной, или NP-полной, задачей. Доказательств обратного тоже никто не представил.

1.4.3 Выбор алгоритма шифрования

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

- Криптостойкость. Алгоритм должен быть тщательно проанализирован мировым криптографическим сообществом в течение длительного времени (не менее пяти лет лет) [1] и признан криптостойким к различным видам атак;

- Длина ключа. Ключ, используемый в алгоритме шифрования, должен быть не короче 256 бит для алгоритмов симметричного шифрования и 2048 бит для алгоритмов с открытым ключом. Это сделано для того, чтобы шифр невозможно было вскрыть методом прямого перебора (грубой силой) в ХХI веке;

- Скорость шифрования. Предполагается взаимодействие устройства с компьютером через полноскоростной интерфейс USB2.0. (12 Мбит/сек). Поэтому скорость шифрования данных по выбранному алгоритму должна быть настолько высокой, чтобы не возникало простоев при передаче данных на максимальной скорости.

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

Выбор осуществлялся из следующего набора алгоритмов: RC6, Rijndael (Рэндал), Serpent и Twofish, потоковые шифры RC4 и WAKE, алгоритм Blowfish, разработанный известным криптоаналитиком Брюсом Шнайером, а также алгоритм с открытым ключом - RSA.

Все вышеперечисленные алгоритмы в различной степени отвечают предъявляемым к ним требованиям. Для реализации RSA, необходимы операции (возведение в степень) над большими числами, для быстрого выполнения которых в проекте придется применять специализированные микросхемы. Алгоритмы с открытым ключом не применимы из-за низкой скорости. Потоковые шифры лучше не использовать. Они лучше подходят для шифрования потока информации. Например, пакетов информации в компьютерных сетях, либо разговоров по телефонной линии.

Поскольку разрабатываемое устройство предназначено для шифрования файлов, необходимо использовать блочный шифр, а не потоковый. Два кандидата на эту роль - Rijndael и Blowfish. Создатель Blowfish, Брюс Шнайер рекомендует этот шифр для использования в системах, построенных на основе микроконтроллера. Длина ключа используемого в Blowfish переменная, с верхним пределом 448 бит (в Rijndael максимум - 256 бит). К тому же на алгоритм Blowfish отсутствует лицензия и его можно свободно использовать. Поэтому в устройстве будет реализован алгоритм Blowfish.

1.5 Описание алгоритма Blowfish

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

- Скорость. Blowfish шифрует данные на 32-битовых микропроцессорах со скоростью 26 тактов на байт.

- Компактность. Blowfish может работать менее, чем в 5 Кбайт памяти.

- Простота. Blowfish использует только простые операции: сложение, XOR и выборка из таблицы по 32-битовому операнду. Анализ его схемы несложен, это уменьшает количество ошибок при реализации.

- Настраиваемая безопасность. Длина ключа Blowfish переменна и может достигать 448 битов.

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

Blowfish представляет собой 64-битовый блочный шифр с ключом переменной длины. Алгоритм состоит из двух частей: развертывание ключа и шифрование данных. Развертывание ключа преобразует ключ длиной до 448 битов в несколько массивов подключей, общим объемом 4168 байтов.

Шифрование по алгоритму Blowfish состоит из функции преобразования данных, последовательно выполняемой 16 раз. Каждый этап состоит из зависимой от ключа перестановки и зависимой от ключа и данных подстановки. Используются только сложения и XOR 32-битовых слов. Единственными дополнительными операциями на каждом этапе являются четыре извлечения данных из индексированного массива.

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

P-массив состоит из 18-ти 32-битовых подключей:

Каждый из четырех 32-битовых S-блоков содержит 256 элементов:

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

Blowfish является сетью Фейстела (Feistel), состоящей из 16 этапов. На вход подается 64-битовый элемент данных x.

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

- Элемент x разбивается на две 32-битовых половины: и ;

- Для этапов с первого по шестнадцатый, выполняется:

Рис. 1.2 - Алгоритм Blowfish

(1.11)

(1.12)

Переставить и (кроме последнего этапа);

- В последнем этапе, производится:

(1.13)

(1.14)

- Объединяются элементы и _;



Рис. 1.3 - Функция F

Функция F (рис. 1.8) представляет собой последовательность следующих действий:

- Разделить на четыре 8-битовых части: a, b, c и d;

- Выполнить над a, b, c, d:

(1.15)

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

В реализациях Blowfish, для которых требуется очень большая скорость, цикл должен быть развернут, а все ключи должны храниться в КЭШе данных.

Подключи рассчитываются с помощью специального алгоритма. Вот какова точная последовательность действий.

1. Сначала P-массив, а затем четыре S-блока по порядку инициализируются фиксированной строкой. Эта строка состоит из шестнадцатеричных цифр .

2. Выполняется XOR P₁ с первыми 32 битами ключа, XOR P₂ со следующими 32 битами ключа, и так далее для всех битов ключа (до P₁₈). Используется циклически, пока для всего P-массива не будет выполнена операция XOR с битами ключа.

3. Используя подключи, полученные на этапах (1) и (2), алгоритмом Blowfish шифруется строка из одних нулей.

4. P₁ и P₂ заменяются результатом этапа (3).

5. Результат этапа (3) шифруется с помощью алгоритма Blowfish и измененных подключей.

6. P₃ и P₄ заменяются результатом этапа (5).

7. Далее в ходе процесса все элементы P-массива и затем по порядку все четыре S-блока заменяются выходом постоянно меняющегося алгоритма Blowfish.

Серж Воденэ (Serge Vaudenay) исследовал Blowfish с известными S-блоками и r этапами. Дифференциальный криптоанализ может раскрыть P-массив с помощью 2^8r+1 выбранных открытых текстов. Для некоторых слабых ключей, которые генерируют плохие S-блоки (вероятность выбора такого ключа составляет 1 к 2¹⁴), это же вскрытие раскрывает P-массив с помощью всего 2^4r+1. При неизвестных S-блоках это вскрытие может обнаружить использование слабого ключа, но не может определить сам ключ (ни S-блоки, ни P-массив). Это вскрытие эффективно только против вариантов с уменьшенным числом этапов и совершенно бесполезно против 16-этапного Blowfish.

Слабым является ключ, для которого два элемента данного S-блока идентичны. До выполнения развертывания ключа невозможно определить, является ли он слабым.

В устройстве осуществляется проверка ключей на принадлежность к классу слабых. Слабые ключи не используются.

В устройстве реализован Blowfish c количеством этапов, равным 16.

До сих пор неизвестно об успешном криптоанализе Blowfish.

1.6 Выбор функции для хэширования паролей

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

1.6.1 MD4

MD4 - это однонаправленная хэш-функция. MD обозначает Message Digest (краткое изложение сообщения). Алгоритм для входного сообщения выдает 128-битовое хэш-значение. MD4 подходит для высокоскоростных программных реализаций. Она основана на простом наборе битовых манипуляций с 32-битовыми операндами.

После первого появления алгоритма Берт Боер и Антон Босселаерс (Antoon Bosselaers) осуществили криптоанализ последних двух из трех этапов алгоритма. Эли Бихам рассмотрел использование дифференциального криптоанализа против первых двух этапов MD4.

1.6.2 MD5

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

Алгоритмы MD4 и MD5 в проектах лучше не использовать. Существует возможность вычисления коллизий этих функций.

1.6.3 SHA

Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA), разработан для стандарта цифровой подписи (Digital Signature Standard).

Для любого входного сообщения длиной меньше 2⁶⁴ битов SHA выдает 160-битовый результат, называемый кратким содержанием сообщения. SHA является криптостойким алгоритмом и разработан так, чтобы было невозможно найти сообщение, соответствующее данному краткому содержанию сообщения. Любые изменения, произошедшие при передаче сообщения, с очень высокой вероятностью приведут к изменению краткого содержания сообщения.

12.08.2004 найдена полная коллизия SHA-0. На это потребовалось 50 000 часов машинного времени [1].

1.6.4 SHA1

Алгоритм разработан в 1995 году в качестве замены более слабого SHA. Длина результата 160 бит.

Группе китайских ученых удалось найти коллизии в SHA1 меньше чем за 2⁶⁹ операций хеширования (для вскрытия грубой силой не обходимо произвести 2⁸⁰ операций). В связи с этим NIST рекомендует пока пользоваться SHA2 - алгоритм, похожий на тот, что используется в SHA1, но с длиной выходного сообщения 256, 384 и 512 бит. Это делает SHA2 более устойчивым к вскрытию полным перебором.

1.6.5 SHA2

Алгоритм представляет собой вариант SHA1, с большей длиной выходного сообщения. Существуют варианты SHA-256, SHA-384, SHA-512. Об успешных атаках на SHA2 пока неизвестно.

В устройстве используется хэш-функция SHA2-384, так как:

- это одна из немногих криптостойких функций хэширования на сегодняшний день;

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

1.7 Выбор генератора случайных чисел

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

1.7.1 Методы получения случайных чисел

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

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

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

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

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

1.7.2 Линейные конгруэнтные генераторы

Линейные конгруэнтные генераторы являются генераторами псевдослучайных чисел, которые вычисляются по формуле:

X_n = (a•X_n-1 + b) mod m (1.16)

в которых X_n - это n-ый член последовательности, а X_n-1 - предыдущий член последовательности. Переменные a>0, b>0 и m>0 целочисленные константы: a - множитель, b- инкремент, и m - модуль.

Получаемая последовательность зависит от выбора стартового числа X₀ и при разных его значениях получаются различные последовательности случайных чисел.

Период такого генератора не больше, чем m. Если a, b и m выбраны правильно, то генератор будет генератором с максимальным периодом и его период будет равен m.

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

Линейные конгруэнтные генераторы нельзя использовать в криптографии, так как они предсказуемы. Впервые линейные конгруэнтные генераторы были взломаны Джимом Ридсом (Jim Reeds), а затем Джоан Бояр (Joan Boyar).

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

1.7.3 Алгоритм Блюма-Блюма-Шуба (Blum Blum Shub, BBS)

Алгоритм представляет собой генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюм и Майклом Шубом.

Алгоритм BBS выглядит так:

x_n+1 = (x_n)² mod M, (1.17)

где M=p•q является произведением двух больших простых чисел p и q. На каждом шаге алгоритма выходные данные получаются из x_n путем взятия либо бита четности, либо нескольких наименее значимых бит из x_n.

Алгоритм Блюма-Блюма-Шуба рекомендуется использовать только в криптографии. Этот метод имеет необычно высокую стойкость, которая обеспечивается качеством генератора исходя из вычислительной сложности задачи факторизации чисел. Вычисление выходных бит настолько же трудно, как и факторизация M [1].

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

1.7.4 Генератор, используемый в разрабатываемом устройстве

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

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

1.8 Структурная схема разрабатываемого устройства

Проанализировав техническое задание, составим структурную схему устройства:

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

- Устройство будет производить шифрование данных с большой скоростью (до 12 Мбит/сек). Поэтому основой устройства должен быть высокопроизводительный 32-х разрядный микроконтроллер.

- Устройство связано с компьютером через интерфейс USB на скорости 12 Мбит/сек. Поэтому микроконтроллер, используемый в устройстве, должен быть оснащен full-speed USB контроллером.

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

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

- Необходимо предусмотреть индикацию подачи питания на устройство и индикацию нормальной работы устройства.

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

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

Структурная схема устройства для аппаратного шифрования информации, которая соответствует приведенным выше требованиям.

3. Разработка схемотехнической реализации аппаратного шифратора

3.1 Выбор элементной базы для шифратора

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

3.1.1 Выбор микроконтроллера

Согласно техническому заданию, устройство должно поддерживать USB. Следовательно, нужен контроллер с поддержкой этого интерфейса.

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

Наиболее подходящими контроллерами являются Atmel AT91SAM7S64, Atmel AT89C5131, Philips LPC2141, Philips LPC2142.

Таблица 2.1 - Параметры микроконтроллеров

Микроконтроллер	Быстродействие, MIPS	Объем flash, Кб	Объем ОЗУ, Кб	Цена, USD
AT91SAM7S64	50	64	16	5
AT89C5131	4	32	1	8
LPC2141	55	32	8	5
LPC2142	55	64	16	7
Коэф. важности	0,2	0,15	0,15	0,5

Выберем один из них по матрице параметров:

1) ;

2) Составим матрицу приведенных параметров:

- если большее значение параметра соответствует лучшему качеству ИМС, то ;

- если параметр не удовлетворяет этому условию, то .

;

3) Составим матрицу нормированных параметров A:

,

где - максимальное значение j-го параметра.

;

4) Вычислим оценочную функцию :

;

Т.к. наименьшее, то AT91SAM7S64 будет оптимальным выбором.

1.1..1. Технические характеристики микроконтроллера AT91SAM7S64.

Характеристики микроконтроллера [2]:

- Содержит ядро процессора ARM7TDMI® ARM® Thumb®;

- Высокопроизводительная 32-разр. RISC-архитектура;

- Обширный набор 16-разр. инструкций;

- Лидер по соотношению производительность / энергопотребление;

- Встроенное ядро внутрисхемной эмуляции с отладочным коммуникационным каналом;

- Внутренняя высокоскоростная флэш-память размером 64 кбайт и организацией 512 страниц по 128 байт в каждой

- Однотактный доступ при частотах до 30 МГц. Упреждающий буфер оптимизирует выполнение Thumb-инструкций при максимальном быстродействии;

- Время программирования страниц: 4 мс, в т.ч. автоматическое стирание страницы; время полного стирания: 10 мс;

- 10,000 циклов записи, 10-летний срок хранения данных, функции защиты секторов, бит защиты флэш-памяти;

- Интерфейс быстрого программирования флэш-памяти для серийного производства;

- 16 кбайт внутреннего высокоскоростного СОЗУ, однотактный доступ при максимальном быстродействии;

- Контроллер памяти (MC)

- Встроенный контроллер флэш-памяти, определение некорректного доступа и формирование статуса ошибки;

- Контроллер сброса (RSTC)

- Состоит из схемы сброса при подаче питания и схемы детектора снижения напряжения питания с откалиброванным в заводских условиях порогом;

- Выполняет обработку внешнего сигнала сброса и формирует информацию об источнике сброса;

- Тактовый генератор (CKGR)

- Маломощный RC-генератор, встроенный генератор частот от 3 до 20 МГц;

- Одна схема ФАПЧ;

- Контроллер управления энергопотреблением (PMC)

- Возможность программной оптимизации энергопотребления, в т.ч. с использованием режимов пониженного быстродействия (Slow Clock), возможно снижение частоты до 500 Гц) и режим холостого хода (Idle);

- Три программируемых внешних тактовых сигнала;

- Усовершенствованный контроллер прерываний (AIC)

- Индивидуальное маскирование, восемь уровней приоритетов, векторизованные источники прерываний;

- Два внешних источника прерывания + один внешний источник прерывания с быстрым реагированием, защита от ложных прерываний;

- Блок отладки (DBGU);

- 2-пров. УАПП + поддержка прерывания по отладочному коммуникационному каналу, программируемое предотвращение доступа со стороны внутрисхемного эмулятора;

- Интервальный таймер (PIT);

- 20-разр. программируемый счетчик + 12 разр. счетчик интервалов;

- Сторожевой таймер (WDT)

- 12-разр. программируемый счетчик с защитой ключом;

- Выполняет сброс или генерирует запрос на прерывание системы;

- Счетчик может быть остановлен, когда процессор находится в состоянии отладки или в режиме холостого хода;

- Таймер реального времени (RTT)

- 32-разр. циклический счетчик с сигнализатором;

- Работает от внутреннего RC-генератора;

- Один контроллер параллельного ввода / вывода (PIOA)

- 42 программируемые линии ввода-вывода, мультиплексированные с двумя встроенными периферийными модулями;

- Возможность генерации прерывания по изменению на входе любой линии ввода-вывода;

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

- 11 канальный контроллер периферийных данных (PDC);

- Один полноскоростной контроллер USB 2.0 (12 Мбит/сек), режим устройства;

- Встроенный трансивер, встроенные конфигурируемые буферы FIFO емкостью 328 байт каждый;

- Один синхронный последовательный контроллер (SSC);

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

- Поддержка аналогового интерфейса I2S, поддержка временного уплотнения;

- Возможность высокоскоростной непрерывной передачи потока данных в 32-разр. формате;

- Два универсальных синхронных / асинхронных приемопередатчика (УСАПП)

- Раздельные генераторы скорости связи, инфракрасная модуляция / демодуляция (IrDA);

- Поддержка смарт-карт ISO7816 T0/T1, аппаратное подтверждение связи, поддержка RS485;

- Полный интерфейс модема на УСАПП1;

- Последовательный периферийный интерфейс SPI с режимами ведущий / подчиненный

- Программируемая длина данных от 8 до 16 бит, четыре внешних выхода выбора микросхем;