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

Постановка

В криптографии под семейством псевдослучайных функций понимают набор функций (которые могут быть эффективно вычислены за полиномиальное время), обладающих следующим свойством: злоумышленник не может эффективно найти какое-либо существенное различие между поведением функции из данного семейства и истинной случайной функции . Пусть ${\displaystyle p}$ — это ${\displaystyle n}$ - битное простое число , ${\displaystyle l}$ — простое число , являющееся делителем ${\displaystyle p-1}$ , а ${\displaystyle g\in {\mathbb {F} }_{p}^{*}}$ , — некоторый элемент с мультипликативным порядком ${\displaystyle l}$ по модулю ${\displaystyle p}$ . Тогда функция Наора — Рейнгольда ${\displaystyle f_{a}(x)}$ определяется некоторым ${\displaystyle (n+1)}$ -мерным вектором ${\displaystyle a=(a_{0},a_{1},...,a_{n})\in ({\mathbb {F} }_{l})^{n+1}}$ над полем ${\displaystyle \mathbb {F} _{l}}$ и равна:

${\displaystyle f_{a}(x)=g^{a_{0}\cdot a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}\in \mathbb {F} _{p}}$

где ${\displaystyle x=x_{1},...,x_{n}}$ — это двоичное представление целого числа ${\displaystyle x,}$ ${\displaystyle 0\leq x<2^{n}}$ , с добавлением ведущих нулей, если это необходимо .

Пример

Пусть ${\displaystyle p=7}$ и ${\displaystyle l=3}$ . В качестве ${\displaystyle g\in \mathbb {F} _{7}^{*}}$ с мультипликативным порядком ${\displaystyle 3}$ можно выбрать ${\displaystyle g=4}$ . Тогда при ${\displaystyle n=3}$ , ${\displaystyle a=(1,1,3,1)}$ и ${\displaystyle x=5}$ функция ${\displaystyle f_{a}(5)}$ вычисляется как

${\displaystyle f_{a}(x)=g^{a_{0}\cdot a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}=4^{1\cdot 1^{1}3^{0}1^{1}}=4^{1}=4\in \mathbb {F} _{7}}$

Так как двоичное представление числа ${\displaystyle 5}$ — это ${\displaystyle (1,0,1)}$ .

Вычислительная сложность

Построение псевдослучайной функции Наора — Рейнгольда требует ${\displaystyle n}$ умножений по модулю ${\displaystyle l}$ и одно возведение в степень по модулю ${\displaystyle p}$ , которое может быть сделано за ${\displaystyle O\left({\frac {n}{\log n}}\right)}$ умножений по этому модулю .

Для данной функции было показано, что существует такой полином ${\displaystyle p(x)}$ , что для любого ${\displaystyle a=(a_{0},a_{1},...,a_{n})\in ({\mathbb {F} }_{l})^{n+1}}$ , ${\displaystyle f_{a}(x)}$ может быть реализована схемой из пороговых элементов глубины ${\displaystyle d}$ и размера, не превышающего ${\displaystyle p(n)}$ . Это означает, что функции Наора — Рейнгольда принадлежит в терминах .

Применение

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

Также было показано, что данная функция может быть использована в :

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

Безопасность

Псевдослучайная функция Наора — Рейнгольда имеет высокую криптографическую стойкость . Пусть злоумышленнику известны значения функции в нескольких точках: ${\displaystyle f_{a}(1)=g^{a_{0}a_{1}},f_{a}(2)=g^{a_{0}a_{2}},\dots ,f_{a}(k)=g^{a_{0}a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}}$ и ему необходимо вычислить ${\displaystyle f_{a}(k+1)}$ . Если ${\displaystyle x_{1}=0}$ , то чтобы получить ${\displaystyle f_{a}(k+1)=g^{a_{0}a_{1}a_{2}^{x_{2}}\dots a_{n}^{x_{n}}}}$ , злоумышленнику необходимо решить для ${\displaystyle f_{a}(1)=g^{a_{0}a_{1}}}$ и ${\displaystyle f_{a}(k)=g^{a_{0}a_{2}^{x_{2}}...a_{n}^{x_{n}}}}$ . Но по не существует эффективного алгоритма, способного решить данную задачу .

Поток чисел, генерируемый псевдослучайной функцией , также должен быть непредсказуемым, то есть, он должен быть неотличим от совершенно случайного набора чисел. Пусть ${\displaystyle {\mathcal {A}}^{f}}$ обозначает алгоритм, имеющий доступ к оракулу , который вычисляет ${\displaystyle f_{a}(x)}$ . Предположим, что выполняется для ${\displaystyle \mathbb {F} _{p}}$ . Тогда для любого вероятностного полиномиального алгоритма ${\displaystyle {\mathcal {A}}}$ и достаточно большого ${\displaystyle n}$ выполнено :

${\displaystyle |{\text{Pr }}[{\mathcal {A}}^{f_{a}(x)}(p,g)=1]-{\text{Pr }}[{\mathcal {A}}^{R}(p,g)=1]|<\epsilon }$ , где ${\displaystyle \epsilon (n)}$ — пренебрежимо мало.

Первая вероятность равна доле наборов ${\displaystyle s=(p,g,a)}$ , на которых алгоритм выдаёт единицу, а вторая получается из случайного выбора пары ${\displaystyle (p,g)}$ и функции ${\displaystyle R_{a}(x)}$ среди множества всех функций ${\displaystyle \{0,1\}^{n}\to {\mathbb {F} }_{p}}$ .

Линейная сложность

Одним из естественных показателей того, насколько последовательность может быть полезной для криптографических целей, является её линейная сложность. Линейная сложность ${\displaystyle n}$ -элементной последовательности ${\displaystyle W(x),\;x=0,\dots ,n-1}$ , над кольцом ${\displaystyle {\mathcal {R}}}$ — это длина ${\displaystyle l}$ кратчайшего линейного рекуррентного соотношения ${\displaystyle W(x+l)=A_{l-1}W(x+l-1)+\dots +A_{0}W(x),\;x=0,\dots ,n-(l-1)}$ , где ${\displaystyle A_{0},\dots ,A_{l-1}\in {\mathcal {R}}}$ . Для функции Наора — Рейнгольда было показано, что существуют такие ${\displaystyle \gamma >0}$ и ${\displaystyle n\geqslant (1+\gamma )\log l}$ , что для любого ${\displaystyle \delta >0}$ и достаточно большого ${\displaystyle l}$ линейная сложность ${\displaystyle L_{a}}$ последовательности ${\displaystyle f_{a}(x)}$ , ${\displaystyle 0\leq x<2^{n}}$ , удовлетворяет следующему неравенству :

${\displaystyle L_{a}\geqslant {\begin{cases}l^{1-\ \delta \,\!}&{\text{, если }}\gamma \,\!\geqslant 2\\l^{\left({\tfrac {\ \gamma \,\!}{2-\ \delta \,\!}}\right)}&{\text{, если }}\gamma \,\!<2\end{cases}}}$

для всех, кроме не более чем ${\displaystyle 3(l-1)^{n-\delta }}$ векторов ${\displaystyle a\in (\mathbb {F} _{l})^{n+1}}$ .

Равномерность распределения

Статистическое распределение ${\displaystyle f_{a}(x)}$ экспоненциально близко к равномерному распределению почти для всех векторов ${\displaystyle a\in ({\mathbb {F} }_{l})^{n+1}}$ :

пусть ${\displaystyle {\mathbf {D} }_{a}}$ — множества ${\displaystyle \{f_{a}(x)|0\leq x<2^{n}\}}$ или, другими словами, отклонение распределения значений псевдослучайной функции от равномерного распределения . Было показано, что если ${\displaystyle n=\log p}$ — это битовая длина ${\displaystyle p}$ , тогда для всех векторов ${\displaystyle a}$ ∈ ${\displaystyle (\mathbb {F} _{l})^{n+1}}$ справедливо неравенство ${\displaystyle {\mathbf {D} }_{a}\leq \Delta (l,p)}$ , где :

${\displaystyle \Delta (l,p)={\begin{cases}p^{\left({\tfrac {1-\ \gamma \,\!}{2}}\right)}l^{\left({\tfrac {-1}{2}}\right)}\log ^{2}p&{\text{ если }}l\geqslant p^{\gamma \,\!}\\p^{\left({\tfrac {1}{2}}\right)}l^{-1}\log ^{2}p&{\text{ если }}p^{\gamma \,\!}>l\geqslant p^{\left({\tfrac {2}{3}}\right)}\\p^{\left({\tfrac {1}{4}}\right)}l^{\left({\tfrac {-5}{8}}\right)}\log ^{2}p&{\text{ если }}p^{\left({\tfrac {2}{3}}\right)}>l\geqslant p^{\left({\tfrac {1}{2}}\right)}\\p^{\left({\tfrac {1}{8}}\right)}l^{\left({\tfrac {-3}{8}}\right)}\log ^{2}p&{\text{ если }}p^{\left({\tfrac {1}{2}}\right)}>l\geqslant p^{\left({\tfrac {1}{3}}\right)}\\\end{cases}}}$

и ${\displaystyle \gamma =2,5-\log 3\approx 0,9150\dots }$ .

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

Последовательности на эллиптической кривой

Анализ этой функции на эллиптической кривой позволяет улучшить криптографическую стойкость соответствующей системы. Пусть ${\displaystyle p>3}$ — простое число и ${\displaystyle E}$ — эллиптическая кривая над ${\displaystyle \mathbb {F} _{p}}$ . Тогда любой вектор ${\displaystyle a=(a_{0},a_{1},\dots ,a_{n})\in ({\mathbb {F} }_{l}^{*})^{n+1}}$ определяет конечную последовательность ${\displaystyle f_{a}(x)=(a_{0}a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G\in \mathbb {F} _{p}^{2}}$ в циклической группе ${\displaystyle \langle G\rangle }$ , где ${\displaystyle x=x_{1}\dots x_{n}}$ — битовое представление ${\displaystyle x,\;0\leq x<2^{n}}$ , ${\displaystyle G\in \mathbb {F} _{p}^{2}}$ , — некоторый элемент на ${\displaystyle E}$ с мультипликативным порядком ${\displaystyle l}$ , а ${\displaystyle (a_{0}a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G}$ — это операция возведения элемента ${\displaystyle G}$ в степень ${\displaystyle a_{0}a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}}}$ относительно групповой операции в абелевой группе ${\displaystyle \mathbb {F} _{p}}$ -рациональных точек эллиптической кривой . В таких обозначениях последовательность Наора — Рейнгольда на эллиптической кривой определяется как ${\displaystyle u_{k}=X(f_{a}(k))\;}$ , где ${\displaystyle X(P)}$ обозначает абсциссу точки ${\displaystyle P\in E}$ .

Если предположение Диффи — Хеллмана выполнено, то индекса ${\displaystyle k}$ не достаточно для вычисления ${\displaystyle u_{k}}$ за полиномиальное время. Для эллиптической кривой Наора — Рейнгольда было показано, что существуют такие ${\displaystyle \gamma >0}$ и ${\displaystyle n\geqslant (1+\gamma )\log l}$ , что для любого ${\displaystyle \delta >0}$ и достаточно большого ${\displaystyle l}$ линейная сложность ${\displaystyle L_{a}}$ последовательности ${\displaystyle (u_{k})_{k=0}^{2^{n}-1}}$ удовлетворяет следующему неравенству :

${\displaystyle L_{a}\geqslant \min \left(l^{{\frac {1}{3}}-\delta },{\frac {l^{(\gamma -3\delta )}}{\log ^{2}l}}\right)}$

для всех, кроме не более чем ${\displaystyle O((l-1)^{n-\delta })}$ векторов ${\displaystyle a\in (\mathbb {F} _{l}^{*})^{n+1}}$ .

См. также

• Симметричные криптосистемы
• Конечное поле
• Инверсный конгруэнтный метод
• Криптосистема с открытым ключом

Примечания