РЕАЛИЗАЦИЯ  И  ИССЛЕДОВАНИЕ  КРИПТОГРАФИЧЕСКИ  СТОЙКОГО  ГЕНЕРАТОРА  BLUM-BLUM-SHUB

Выборнова  Юлия  Дмитриевна

аспирант  Самарского  государственного  аэрокосмического  университета  имени  академика  С.П.  Королева,  РФ,  г.  Самара

Email: 

RESEARCH  AND  IMPLEMENTATION  OF  CRYPTOGRAPHICALLY  SECURE  PSEUDORANDOM  BLUM-BLUM-SHUB  GENERATOR

Yuliya  Vybornova

post-graduate  student,  Samara  State  Aerospace  University,  Russia,  Samara

АННОТАЦИЯ

Объектом  исследования  является  криптографически  стойкий  генератор  псевдослучайных  последовательностей  Blum-Blum-Shub.  Цель  работы  –  реализация  генератора  псевдослучайных  последовательностей  с  помощью  двух  различных  прикладных  криптографических  библиотек  языка  программирования  C++  и  сравнение  основных  характеристик  полученных  программных  модулей.  В  работе  проведен  анализ  основных  характеристик  полученного  генератора:  производительности  и  потребления  оперативной  памяти  при  генерации  последовательностей  большой  длины.  Сформированы  выводы  о  границах  применения  полученных  реализаций  генератора.

ABSTRACT

The  object  of  this  research  is  a  cryptographically  secure  pseudorandom  number  generator  called  Blum-Blum-Shub  generator.  The  main  objective  is  implementation  of  pseudorandom  number  generator  using  two  different  C++  applied  cryptography  libraries  and  comparison  of  software  modules  characteristics.  The  paper  analyzes  the  main  characteristics  of  the  resulting  generator:  performance  and  memory  consumption  in  case  of  generating  long  sequences.  Application  area  of  both  implementations  was  defined.

Ключевые  слова:  псевдослучайные  последовательности;  генератор  бинарных  последовательностей;  большие  числа;  скорость  алгоритма;  потребление  памяти.

Keywords:  binary  sequences;  pseudorandom  number  generator;  big  integers;  algorithm  speed;  memory  consumption.

Реализация  генератора.

Генераторы  псевдослучайных  последовательностей  –  это  алгоритмы,  которые  используют  математические  формулы  или  предварительно  вычисленные  таблицы,  чтобы  порождать  последовательности  псевдослучайных  чисел  [1,  с.  815–816].

В  1986  году  Ленор  Блюм,  Мануель  Блюм  и  Майкл  Шуб  опубликовали  алгоритм,  который  впоследствии  получил  название  генератора  Blum-Blum-Shub.  Генератор  основан  на  операции  возведения  в  квадрат  в  кольце  вычетов  по  модулю  большого  числа  N,  где  N  =  P  ×  Q,  при  условии,  что  P  и  Q  –  простые  числа  равной  длины,  сравнимые  с  3  по  модулю  4  [2,  с.  367–368].

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

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

Для  реализации  первой  версии  программного  генератора  Blum-Blum-Shub  было  решено  использовать  библиотеку  Crypto++  [3]. 

Для  реализации  второй  версии  программного  генератора  Blum-Blum-Shub  использовалась  библиотека  MPIR  (The  Multiple  Precision  Integers  and  Rationals  Library)  [4]. 

Также  для  детального  рассмотрения  была  выбрана  одна  из  существующих  реализаций  исследуемого  генератора  –  реализация  Ника  Галбрета  2005  года  [5].  Реализация  представляет  собой  библиотеку  на  языке  программирования  Java. 

Исследование  характеристик  генератора  Blum-Blum-Shub

Три  реализации  исследуемого  генератора  были  протестированы  на  трех  различных  операционных  системах  семейства  Windows:  Windows  7  Home  Basic  (64-битная),  Windows  8  Professional  (32-битная),  Windows  Vista  Ultimate  (32-битная).  Windows  7  является  основной  операционной  системой  персонального  компьютера,  на  котором  проводилось  исследование,  а  Windows  8  и  Windows  Vista  запускались  с  помощью  виртуальной  машины  Oracle  VM  VirtualBox.  Основные  характеристики  персонального  компьютера:  двухядерный  процессор  Intel  Pentium  P6100,  тактовая  частота  каждого  ядра  2  ГГц,  объем  оперативной  памяти  3  Гб. 

Результаты  представлены  в  таблицах  1–3.

Таблица  1. 

Среднее  время  выполнения  программы  при  генерации  1  миллиона  бит  псевдослучайной  последовательности,  [с]

Таблица  2. 

Средняя  скорость  потока  при  генерации  1  миллиона  бит  псевдослучайной  последовательности,  [бит/с]

Таблица  3. 

Средний  объем  потребляемой  оперативной  памяти  при  генерации  1  миллиона  бит  псевдослучайной  последовательности,  [Кбайт]

Исходя  из  результатов  тестирования  двух  рассмотренных  генераторов,  можно  сделать  вывод,  что  самой  быстрой  является  реализация  генератора  Blum-Blum-Shub  на  языке  программирования  Java.  Однако  следует  обратить  внимание  на  наличие  внешней  зависимости  и  ненормированное  потребление  памяти.  В  данном  случае  преимущество  по  скорости  не  играет  роли,  так  как  для  того  чтобы  изменить  границы  применения  генератора,  необходимо  увеличить  его  скорость  в  1000  раз  и  более,  а  в  данном  случае  реализация  на  языке  программирования  Java  быстрее  других  реализаций  не  более,  чем  в  16  раз.

Реализация  на  основе  библиотеки  MPIR  также  обладает  высокой  скоростью,  но  как  и  реализация  на  языке  программирования  Java  имеет  ненормированное  потребление  памяти,  поэтому  трудно  предсказать  поведение  данной  программы  при  генерации  очень  больших  последовательностей  (1  гигабайт  и  более).  Для  запуска  данной  реализации  требуется  наличие  динамической  библиотеки  mpir.dll.  Данная  библиотека  не  требует  установки  и  почти  не  занимает  места  на  диске,  поэтому  такая  зависимость  не  является  недостатком.

Реализация  на  основе  библиотеки  Crypto++  является  самой  медленной  и  для  генерации  очень  больших  последовательностей  потребуется  колоссальное  количество  времени.  Но  зато  данная  программа  отличается  стабильным  потреблением  памяти  и  отсутствием  каких-либо  внешних  зависимостей. 

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

Заключение. 

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

Список  литературы:

1. Neil  J.  Salkind.  Encyclopedia  of  Measurement  and  Statistics.  Sage  Publications,  2007. 
2. Blum  L.,  M.  Blum  and  M.  Shub.  A  Simple  Unpredictable  Pseudo-Random  Number  Generator.  Proceedings,  SIAM  Journal  on  Computing,  May  1986.
3. Crypto++.  [Электронный  ресурс].  –  Режим  доступа.  –  URL:  http://www.cryptopp.com/  (дата  обращения:  21.09.2015)
4. The  Multiple  Precision  Integers  and  Rationals  Library.  [Электронный  ресурс].  –  Режим  доступа.  –  URL:  http://mpir.org/  (дата  обращения:  16.10.2015)
5. A  collection  of  random  number  generators  in  java.  [Электронный  ресурс].  –  Режим  доступа.  –  URL:  https://code.google.com/p/javarng/  (дата  обращения:  19.10.2015)