ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

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

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

Механизм хеширования известен уже достаточное количество времени, однако сам термин хеширование появился в печатных изданиях не так давно, в 1967 г. [1]. По словам Дональда Кнута [2], впервые идея и принципы хеширования были озвучены Г.П. Ланом в 1953 г. на внутреннем меморандуме IBM. Для разрешения коллизий хеш-адресов он предложил использовать метод цепочек. Жини Амдал — другой сотрудник IBM — предложила использовать открытую линейную адресацию. Арнольд Думи в 1956 г. впервые описал хеширование в открытой печати. Он предложил использовать в качестве хеш-адреса остаток от деления на простое число. Гораздо более основательное исследование хеш-функций было опубликовано в 1963 г. Вернером Букхольцом [3].

1. Актуальность темы

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

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

2. Цель и задачи исследования

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

Основные задачи исследования:

  1. Анализ существующих криптографических алгоритмов.
  2. Изучение методов SAT Solvers.
  3. Разработка алгоритма криптоанализа.

Объектом исследования являются алгоритмы шифрования данных.

Предметом исследования являются способы оптимизации алгоритмов шифрования данных.

3. Предполагаемая научная новизна

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

4. Обзор существующих криптографических алгоритмов

По классификации, предоставленной С. Панасенко [4], криптографические алгоритмы делятся на бесключевые, одноключевые и двухключевые.

Бесключевые — не используют каких-либо ключей в процессе криптографических преобразований.

Одноключевые — используют в своих вычислениях некий секретный ключ.

Двухключевые — на различных этапах вычислений применяются два вида ключей: секретные и открытые.

Более подробная классификация показана на рисунке 1.

Классификация криптографических алгоритмов

Рисунок 1 — Классификация криптографических алгоритмов

Некоторые из алгоритмов рассмотрены ниже.

4.1 Генераторы случайных чисел

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

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

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

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

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

4.2 Алгоритмы симметричного шифрования

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

В настоящее время имеется целый ряд алгоритмов симметричного шифрования. Среди них отметим DES (Data Encryption Standard — стандарт шифрования данных), IDEA (International Data Encryption Algorithm — международный алгоритм шифрования данных) — патентованный алгоритм, применяемый в PGP, и Blowfish — непатентованный алгоритм, применяемый в SSH.

С алгоритмами симметричного шифрования связано понятие стойкости шифра. Стойкость — это мера сопротивления криптоаналитическим атакам. Стойкость алгоритма определяется размером используемого ключа. В IDEA применяются 128-разрядные ключи. В алгоритме Blowfish размер ключа конфигурируется от 32 до 448 бит. Чем длиннее ключ, тем более стойкий шифр. В DES используются 56-разрядные ключи, поэтому данный алгоритм считается относительно слабым.

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

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

4.3 Алгоритмы асимметричного шифрования

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

Алгоритмы асимметричного шифрования возникли в связи с необходимостью передавать секретные ключи по незащищенным каналам. Первую систему такого рода разработал Ральф Меркл (Ralph Merkle) в 1974 году. Первым алгоритмом, завоевавшим широкую популярность, был алгоритм Диффи-Хеллмана, созданный Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) в 1976 году. В 1977 году Рон Ривест (Ron Rivest), Ади Шамир (Adi Shamir) и Лен Эйдельман (Len Adleman) разработали схожий алгоритм RSA.

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

4.3.1 Шифрование с закрытым ключом

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

Наиболее широко используемым алгоритмом с закрытым ключом является стандарт Data Encryption Standard (DES). Этот алгоритм, разработанный компанией IBM в семидесятых годах прошлого века, принят в качестве американского стандарта для коммерческих и несекретных правительственных коммуникаций. Современные скорости вычислений на порядок превышают скорости вычислений в семидесятых годах, поэтому алгоритм DES считается устаревшим как минимум с 1998 года.

Другие известные системы шифрования с закрытым ключом — это RC2, RC4, RC5, тройной DES (triple DES) и IDEA. Тройной DES-алгоритм обеспечивает достаточную степень защиты. Этот алгоритм использует тот же метод шифрования, что и DES, но применяет его трижды, используя при этом до трех разных ключей. Открытый текст шифруется с использованием первого ключа, дешифруется при помощи второго ключа, а затем шифруется с применением третьего ключа.

Схема алгоритма шифрования с закрытым ключом

Рисунок 2 — Схема алгоритма шифрования с закрытым ключом (анимация, 16 кадров, 5 повторений, 53,9 КБ)

Условные обозначения:
     М — сообщение;
     Н(М) — хэширование сообщения;
     Е — электронная цифровая подпись;
     К — секретный ключ;
     МЕ — не зашифрованное сообщение с ЭЦП;
     МЕК — зашифрованное сообщение с ЭЦП;

Явный недостаток алгоритмов с закрытым ключом состоит в том, что для отправки кому-то защищенного сообщения необходимо располагать безопасным способом передачи этому лицу закрытого ключа [7].

4.3.2 Шифрование с открытым ключом

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

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

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

Алгоритмы шифрования с открытым ключом используют так называемые необратимые или односторонние функции. Эти функции обладают следующим свойством: при заданном значении аргумента х относительно просто вычислить значение функции (x), однако, если известно значение функции y = f(x), то нет простого пути для вычисления значения аргумента x. Например, функция SIN. Зная x, легко найти значение SIN(x) (например, x = π, тогда SIN(π) = 0). Однако, если SIN(x) = 0, однозначно определить х нельзя, т.к. в этом случае х может быть любым числом, определяемым по формуле i * π, где i — целое число [8].

Выводы

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

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

Важное замечание

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2013 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

  1. Hellerman H., Digital Computer System Principles. McGraw-Hill, 1967.
  2. Кнут Д., Искусство программирования, т.3. М.: Вильямс, 2000.
  3. Buchholz W., IBM Systems J., 2 (1963), 86–111
  4. Панасенко С.П., Алгоритмы шифрования. Специальный справочник. – СПб.: БХВ-Петербург, 2009, - 576 с.: ил.
  5. Введение в криптографию [Электронный ресурс]. – Режим доступа: http://algolist.manual.ru/defence/...
  6. Симметричное шифрование [Электронный ресурс]. – Режим доступа: http://www.open-security.org/linux/...
  7. Шифрование с закрытым ключом [Электронный ресурс]. – Режим доступа: http://sevidi.ru/phpstroy/...
  8. Шифрование с открытым ключом [Электронный ресурс]. – Режим доступа: https://sites.google.com/site/...
  9. Litwin W., Proc. 6th International Conf. on Very Large Databases (1980), 212-223