Список обозначений

Семейство перестановок RSA

rSA collection of permutations

Пусть $(\mathfrak Q_n\,|\, n\in\mathbb N)$ — полиномиально конструируемое семейство распределений вероятностей на множестве пар вида $(\{p,q\},e)$, где $p$ и $q$ — различные простые числа, а $e$ — целое число, большее $3$ и взаимно простое с $\varphi(pq)=\#\mathbb Z^{\star}_{pq}=(p-1)(q-1)$. Положим $I=\{(pq,e)\,|\,(\{p,q\},e)\in\mathop{\mathrm{supp}}\mathfrak Q_n,\, n\in\mathbb N\}$. Для каждого $n\in\mathbb N$ распределение вероятностей $\mathfrak G_n$ определяется как распределение на множестве всех пар $((pq,e),d)$, где $(\{p,q\},e)\leftarrow\mathfrak Q_n$ и $d=e^{-1}\bmod\varphi(pq)$.

Пусть $(m,e)\in I$. Определим перестановку $\mathop{\mathrm{RSA}}_{m,e}$ множества $\mathbb Z^{\star}_m$ равенством $\mathop{\mathrm{RSA}}_{m,e}(x)=x^e\bmod m$ ($x\in\mathbb Z^{\star}_m$), а в качестве $\mathfrak X_{m,e}$ выберем равномерное распределение на $\mathbb Z^{\star}_m$. Очевидно, что если $((m,e),d)\in\mathop{\mathrm{supp}}\mathfrak G_n$ ($n\in\mathbb N$), то $\mathop{\mathrm{RSA}}_{m,e}^{-1}(x)=x^d\bmod m$ для любого $x\in\mathbb Z^{\star}_m$. Семейство $(\mathop{\mathrm{RSA}}_i\,|\, i\in I)$ называется семейством перестановок RSA. Название семейства происходит от первых букв фамилий авторов статьи [1], в котором оно было определено. Необходимым условием для того, чтобы это семейство было семейством перестановок с секретом относительно семейств распределений вероятностей $(\mathfrak G_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$, является трудность задачи факторизации чисел $pq$ при известном $e$, где $(\{p,q\},e)\leftarrow\mathfrak Q_n$. Это условие формализуется следующим образом: для любого полиномиального вероятностного алгоритма $\mathcal F$ величина $\Pr(\mathcal F(1^n,pq,e)=\{p,q\})$, где $(\{p,q\},e)\leftarrow\mathfrak Q_n$, пренебрежимо мала как функция от $n\in\mathbb N$. Однако неизвестно, является ли данное условие или какое либо другое стандартное криптографическое предположение достаточным для того, чтобы семейство перестановок RSA при подходящем выборе $(\mathfrak Q_n\,|\, n\in\mathbb N)$ было семейством перестановок с секретом относительно указанных семейств распределений вероятностей. См. также [2] [3].

Литература

  • [1] Rivest, R. and Shamir, A. and Adleman, L. «A method for obtaining digital signatures and public key cryptosystems» 1978
  • [2] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [3] Luby, M. «Pseudorandomness and cryptographic applications» 1996

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна