Псевдослучайные функции (ПСФ) постоянно расширяют сферу своего применения, занимая прочные позиции, начиная от имитационного моделирования до криптографии. При этом к таким функциям предъявляются довольно высокие требования, как с точки зрения их устойчивости к атакующим алгоритмам, так и к скорости вычисления конечного результата. Поэтому вопросам разработки алгоритмов быстрого вычисления псевдослучайных функций повышенной эффективности в настоящее время уделяется значительное внимание.
Цель исследования. Эффективность применения псевдослучайных функций зависит не только от их криптографической стойкости, но и от скорости их вычислений. Для обеспечения высокой степени защиты от несанкционированного доступа (НСД) требуется использование больших модулей, с помощью которых происходит синтез ПСФ. Однако это приводит к снижению скорости вычисления ПСФ. Решить данную проблему можно за счет использования модулярных кодов, которые обладают свойством кольца и поля. Поэтому целью работы является повышение скорости синтеза псевдослучайной функции, обладающей требуемым уровнем криптостойкости, за счет использования модулярной технологии, в частности кодов системы остаточных классов.
Материалы и методы исследования
Для разработки псевдослучайных функций, как правило, используют генераторы псевдослучайных последовательностей (ПСП) [7]. Благодаря довольно простой структуре классических генераторов ПСП на основе линейных регистров сдвига с обратной связью, двоичные псевдослучайные последовательности используются для решения задач, среди которых можно выделить: помехоустойчивое кодирование; защита информации; встроенное техническое диагностирование компонентов компьютерных систем (КС); системы электронных платежей; обеспечение целостности передаваемого сообщения; генерация ключей из некоторого секретного значения (например, мастер-ключа); аутентификация пользователей.
Во всех вышеперечисленных случаях ПСФ используются либо непосредственно, либо на их основе строятся алгоритмы хеширования информации. В последних двух случаях качество операций генерации псевдослучайных функций и хеширования определяется в первую очередь эффективностью ПСФ. Таким образом, именно от свойств псевдослучайных функций, особенно в тех случаях, когда необходимо обеспечить устойчивую работу КС при наличии случайных и умышленных деструктивных воздействий, в значительной степени зависит надежность процессов сбора, обработки, хранения и передачи информации. Кроме того, к техническим реализациям алгоритмов вычисления ПСФ предъявляются высокие требования с точки зрения обеспечения высоких скоростных показателей. Поэтому получение высокоэффективных ПСФ в реальном масштабе времени является актуальной задачей.
Анализ работ [3–6] показал, что в настоящее время известно несколько алгоритмов, позволяющих получать довольно хорошие псевдослучайные функции. Так, в работе [6] была представлена ПСФ Наора-Рейнголда, стойкость которой была выведена из сложности решения проблемы принятия решения Диффи-Хеллмана (DDH). Алгоритм вычисления такой ПСФ определяется следующим образом: на ее вход поступают m-битная строка 
и секретный ключ 
, результатом работы является
, (1)
где 
.
Вычислительная сложность этой функции составляет m-1 модулярных умножений для вычисления w и одно заключительное возведение в степень.
Однако алгебраическая конструкция ПСФ Наора-Рейнголда, несмотря на то, что она лежит в основе многих криптографических схем и даже таких алгебраических конструкций, как верифицируемые случайные функции рассеянные и распределенные ПСФ, обладает недостатками, среди которых можно выделить – большой размер секретного ключа и довольно низкое быстродействие ее технической реализации [3,4].
С целью устранения данных недостатков в работе [1] была разработана алгебраическая ПСФ, имеющая точно такой же размер области определения, как ПСФ Наора-Рейнголда и Бонеха-Монтгомери-Рагунатана (БМР ПСФ), но использующая более короткий секретный ключ по сравнению с ПСФ Наора-Рейнголда. Рассмотрим особенности построения такой псевдослучайной функции. Данная ПСФ на вход принимает входную последовательность вместе с ключом 
и на выход выдает
, (2)
где 
.
Для области определения размером 2m значение 
, вследствие чего при вычислении данной функции требуется в 
раз меньше умножений, но на 
больше возведений в степень по сравнению с (1) для вычисления значения w. В общей сумме нам необходимо 
умножений для вычисления значения w. Основным преимуществом данной ПСФ является использование меньшего объема памяти для вычисления значения функция, так как она использует ключ в 
раз меньший размером по сравнения с ПСФ Наора-Рейнголда. Стойкость ПСФ основывается на предположении о сложности решения λ-DDH проблемы. Применение разработанной ПСФ в системах электронных платежей показано в работе [1].
Применение каскадной реализации позволяет повысить производительность вычисления псевдослучайной функции, однако для дальнейшего повышения скоростных характеристик генератора ПСФ целесообразно использовать систему остаточных классов. В данном случае система остаточных классов задается набором простых чисел 
, называемых модулями. Тогда динамический диапазон такой системы будет определяться
. (3)
Для любого целого числа 
задается единственным образом через n–кортеж остатков
, (4)
где 
.
Модулярное число со знаком определяется в диапазоне 
. Вычисления над n-кортежем независимы от целого числа. Таким образом, существует изоморфизм между кольцом целых чисел по модулю 
и прямой суммой колец 
, а арифметические операции в Z(P) отражены на соответствующих операциях с остатками. Для 
справедливо
(5)
где 
представляет сложение, вычитание или умножение по модулю.
Выражение (5) отражает основные характеристики модулярной арифметики: любая система, состоящая из большого числа сложений, вычитаний и умножений может быть представлена несколькими независимыми каналами, работающими параллельно. При этом разрядность обрабатываемых данных будет определяться выбранным модулем pi, характеризующегося относительно небольшой разрядностью. В результате этого увеличивается производительность системы. Необходимо отметить, что каждая цифра модулярной арифметики независима и равнозначна, поэтому нет необходимости распространения сигнала переноса между кольцами. Таким образом, арифметические операции сложения, вычитания и умножения выполняются без переносов в отличие от обычного позиционного представления чисел и для каждого значения модуля pi арифметические операции выполняются с парой соответствующих вычетов параллельно, при этом вычеты имеют гораздо меньшую разрядность, чем исходные операнды A и B. Введение метрики в кольце по модулю p позволяет рассматривать его как метрическое конечномерное пространство векторов конечной размерности.
Восстановление числа А по его модулярному коду основано на фундаментальном положении, лежащем в основе модулярного представления числа – Китайской теореме об остатках (КТО) [8]. На основании известного представления числа в СОК 
КТО делает возможным определение числа в ПСС 
, если наибольший общий делитель любой пары модулей равен 1. Тогда
, (6)
где 
Из (6) видно, что из КТО получаем 
, а не само A. Если известно, что A находится между 0 и 
, то можно записать
, для 
(7)
В некоторых случаях желательно иметь вид КТО, где сумма появляется без оператора по модулю P. Это можно сделать путем определения вспомогательной функции 
, так, чтобы
(8)
где 
, 
– ранг числа A.
Тогда вычисление ПСФ с использованием модулярной технологии будет определяться выражением
,(9)
где 
.
Результаты исследования и их обсуждение
Рассмотрим пример вычисления псевдослучайной функции повышенной эффективности в кодах СОК. Пусть заданы модули p1 = 11 и р2 = 13. В этом случае диапазон СОК равен
.
Для восстановления числа вычисляем ортогональные базисы:
,
где m1 – вес первого ортогонального базиса, удовлетворяющий условию
;
,
где m2 – вес второго ортогонального базиса, удовлетворяющий условию
.
В качестве первообразного элемента выбираем h = 2. Предположим, что в качестве секретного ключа выбирается число X = 810, которое принадлежит мультипликативной группе. В качестве входного значения выбираем число U = 1010. Представим эти значения в двоичном коде. В результате преобразований имеем следующие значения^
U = 1010 = 10102 ;
X = 810 = 10002.
Полученные значения, представленные 4-битовым блоком. Разобьем эти значения на m = 2 блока, по 2 бит каждый. В результате этого имеем
u1= 102=210; u2 = 102 = 210; x1 = 102 = 210; x2 = 002 = 010.
Для вычисления ПСФ повышенной эффективности по модулю р1 =11 используем (9). Тогда
Для вычисления ПСФ повышенной эффективности по модулю р2 =13 используем (9). Тогда
Тогда, согласно китайской теореме об остатках, получаем значение ПСФ
Проведем сравнительную оценку времени вычисления ПСФ согласно алгоритма, задаваемого выражением (2) и алгоритма, реализованного в кодах системы остаточных классов вычетов (9). Анализ этих выражений показывает, что основным фактором, от которого будет зависеть время вычисления ПСФ, будет вычисления показателя степени. Из выражения (1) наглядно видно, чтобы реализовать эту процедуру необходимо выполнить m умножений данных размером 
. При использовании выражения (9) число умножений остается таким же, но разрядность обрабатываемых операндов сокращается до значений 
. Таким образом, очевидно, что применение модулярных кодов, в частности кодов СОК, позволяет повысить быстродействие вычисления псевдослучайной функции повышенной эффективности.
Заключение
В статье проведена разработка нового подхода, позволяющего за счет использования модулярных технологий повысить скорость вычисления ПСФ. Применение кодов системы остаточных классов позволяет перейти к параллельным вычислениям псевдослучайной функции. При этом скорость синтеза значений ПСФ обуславливается тем, что при выполнении m умножений в алгоритме (2) используются операнды размером 
. При переходе к кодам СОК, согласно (9), разрядность обрабатываемых операндов сокращается до значений 
. Очевидно, что при увеличении размерности позиционной ПСФ, эффективность применения модулряных технлогий возрастает при сохранеии требуемого уроня защиты от НСД.