Неретин А.Д., Быков Д.В.

Волгоградский государственный технический университет, Россия

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

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

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

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

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

Для решения подобных проблем повышения производительности в настоящее время используются параллельные и/или конвейерные системы на базе сопроцессоров, в качестве которых могут использоваться графические процессоры (GPU), либо программируемые логические интегральные схемы (ПЛИС). До недавнего времени разработка под архитектуру ПЛИС была трудоемкой задачей, которая требовала дополнительных знаний, как в программировании, так и в схемотехнике. Однако, с выходом стандарта OpenCL 2.0 в июле 2013 года, а так же добавлением его поддержки компанией Altera для работы с их платами, разработка приложений под ПЛИС становится крайне актуальной задачей.

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

Одной из методик, позволяющих быстро, просто и эффективно рассчитать оценку прироста производительности реализации алгоритмов на ПЛИС является Reconfigurable Amenability Test (RAT), предложенная в 2009 году B. Holland, K. Nagarajan и A. D. George в [1]. Прогнозируемое время выполнения алгоритма определяется исходя из двух показателей: времени обмена данными между CPU и сопроцессором и времени непосредственных вычислений. Время обмена данными учитывает объём данных и скорости чтения и записи, время непосредственных вычислений - опять же объём данных, количество операций над ними, частоту и количество одновременно выполняемых сопроцессором операций. Кроме того, при вычислении времени выполнения алгоритма предлагается учитывать использование одиночной или двойной буферизации. Двойная буферизация подразумевает одновременное осуществление передачи данных и непосредственных вычислений [2]. Расчетные формулы и более подробная информация о методике приведена в [1]

Были произведены расчеты для аппаратных реализаций алгоритмов генерации случайных последовательностей предложенных компанией Altera, а именно Linear Feedback Shift Register (LFSR), C Library Random Number Generator (CLRNG), Race Condition-Based True Random Numbers (RCBTRN) и Word Stream Scrambling (WSS). Был произведен расчет для плат Altera серии Cyclone V в сравнении с Intel Core i7 920 @ 2.67 GHz. В результате расчетов было выявлено, что все алгоритмы кроме LFSR могут дать значительный прирост производительности, а именно: для CLRNG было получено ускорение в 11.6 раз, для WSS – в 14.8 раза и для RCBTRN – в 18.9 раз. На основе этих данных была проведена симуляция остальных алгоритмов в системе Quartus II, в результате которой было подтверждено, что конвейерная реализация этих алгоритмов под архитектуру ПЛИС на самом деле дает значительный прирос производительности, различие с теоретической оценкой в среднем составило 5%.

Таким образом, можно сделать два вывода: во-первых, использование методики RAT для оценки прироста производительности дает возможность на ранней стадии отказаться от разработки под архитектуру ПЛИС, и во-вторых, реализация алгоритмов генерации случайных последовательностей на OpenCL позволит получить позволит получить значительный прирост производительности по сравнению с традиционными ЭВМ.

Литература:

1. Holland B. RAT: RC Amenability Test for Rapid Performance Prediction [Электронный ресурс] / Brian Holland, Karthik Nagarajan, Alan D. George. – URL: http://www.cse.sc.edu/~jbakos/reading_list/trets_rat_final.pdf

2. Андреев, А. Е. Прогнозирование производительности при реализации алгоритмов на гибридных архитектурах с сопроцессорами [Электронный ресурс] / А. Е. Андреев, И. М. Силкин, Ю. В. Шафран // Журнал «Современные проблемы науки и образования». – 2012. – №3. – URL: http://www.science-education.ru/103