Применение параллельных вычислений при решении задач защиты информации

Применение параллельных вычислений при решении задач защиты информации

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

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

Для асимметричных криптосистем также существует достаточно большое разнообразие методов. Среди них наиболее известны такие методы как метод Гельфонда, «giant step-baby step», метод встречи на случайном дереве, метод базы разложения, метод решета числового поля, метод Ферма, метод непрерывных дробей, метод квадратичного решета и др. Однако если при анализе симметричных криптосистем различные методы используют различные приемы, такие как линеаризация, рассмотрение пар текстов, составление систем переопределенных уравнений, то при анализе асимметричных криптосистем все методы сводятся к решению двух задач различными способами — задачи дискретного логарифмирования и задачи факторизации больших чисел.

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

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

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

Рассмотрим различные криптографические алгоритмы с использованием PMB.

Анализ симметричных алгоритмов шифрования На основе разработанных алгоритмов проведения дифференциального криптоанализа DES была реализована программа, позволяющая осуществлять анализ любого числа раундов шифрования с помощью РМВ. С помощью данной программы был проверен алгоритм анализа 6 раундов шифра DES с использованием наиболее вероятных дифференциалов. Экспериментальные данные показали, что анализ 6-раундового алгоритма DES всегда дает правильный результат. Время анализа на 2-процессорной системе в среднем занимает 7,5 минут, на 16-процессорной — 56 секунд. Второе проводимое испытание — это полный анализ алгоритма DES, состоящего из 8, 10, 12, 14 и 16 раундов на 2-х, 3-х, 4-х и 5-ти процессорной системе с частотой процессоров 2,67 ГГц. Результаты анализа алгоритма шифрования DES показали, что при увеличении числа процессоров, принимающих участие в вычислениях, наблюдается практически линейное уменьшение времени анализа.

Для 8 раундов.

Для 16-процессорного кластера с частотой процессоров 1,41 ГГц время работы программы для полного 16-раундового алгоритма DES составило 24 часа 13 минут.

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

Не всегда большее число процессоров приводит к снижению времени расчетов. Однако при использовании 16 процессоров для анализа с помощью статического распределения данных время вычислений сокращается в 2,88 раза, с помощью динамического — в 4,4 раза по сравнению с такими же расчетами на двухпроцессорной системе.

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

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

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

шифр секретный ассиметричный.

[1] Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. — СПб: БХВ-Петербург, 2002.

[2] Biham E., Shamir A. Differential Cryptanalysis of the Full 16-round DES/Crypto'92/ - Springer-Velgar, 1998, — P. 487.

[3] Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems. Extended Abstract // Crypto'90. — Springer-Velgar, 1998. — P. 2.

[4] Панасенко С. Алгоритмы шифрования. Специальный справочник. — СПб.:БХВ-Петербург, 2009. — 576 с.

[5] Бабенко Л. К. Ищукова Е.А. Современные алгоритмы блочного шифрования и методы их анализа. — М.: Гелиос АРВ, 2006.

[6] Бабенко Л. К., Ищукова Е. А. Анализ современных криптографических систем с помощью метода дифференциального криптоанализа. Актуальные аспекты защиты информации в Южном федеральном университете. Монография. — Таганрог: Изд-во ТТИ ЮФУ, 2011. — С. 102−181.

[7] Бабенко Л. К. Ищукова Е.А. Применение рекурсивного алгоритма поиска в Б-деревьях для дифференциального криптоанализа алгоритма шифрования ГОСТ 28 147–89 // Материалы IХ Международной научно-практической конференции «ИБ». Ч. 2. — Таганрог, Изд-во: ТТИ ЮФУ, 2007. — С. 92−97.

[8] Маховенко Е. Б. Теоретико-числовые методы в криптографии: Учебное пособие. — М.: Гелиос АРВ, 2006. — 320 с.

[9] Ростовцев А. Г., Маховенко Е. Б. Теоретическая криптография. — СПб.: АНО НПО «Профессионал», 2005. — 480 с.

[10] Бабенко Л. К., Сидоров И. Д. Параллельные алгоритмы криптоанализа асимметричных систем. Актуальные аспекты защиты информации в Южном федеральном университете. Монография. — Таганрог: Изд-во ТТИ ЮФУ, 2011. — С. 207−252.