Криптосистема Бенало

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

Разработана Джошем Бенало в 1988 году. Получила применение в системах электронного голосования.

Система является частично гомоморфной. Как и во многих криптосистемах с открытым ключом, эта система работает в группе $\mathbb{(}Z/n\mathbb{Z}{)}^{\ast <!--\; \ast \; -->}$$\mathbb {(} {Z}/n\mathbb {Z} )^{*}$ , где $n$$n$ — произведение двух простых чисел.

Описание алгоритмаПравить

Генерация ключаПравить

1. Выбираются блок размера $r$$r$  и два больших различных простых числа $p$$p$  и $q$$q$ , удовлетворяющие следующим условиям:
   1. $r$$r$  и $(p-<!--\; -\; -->1)/r$$(p-1)/r$  — взаимно простые ;
   2. $r$$r$  и $q-<!--\; -\; -->1$$q-1$  — взаимно простые.
2. Вычисляется $n=p\times <!--\; \times \; -->q$$n=p\times q$ , $\mathrm{\varphi <!--\; \varphi \; -->}=(p-<!--\; -\; -->1)(q-<!--\; -\; -->1)$$\phi =(p-1)(q-1)$ ;
3. Выбирается $y\in <!--\; \in \; -->{\mathbb{Z}}_n^{\ast <!--\; \ast \; -->}$$y\in \mathbb {Z} _{n}^{*}$  так, что $y^{\mathrm{\varphi <!--\; \varphi \; -->}/r}\not\equiv 1\mathrm{mod}n$$y^{\phi /r}\not \equiv 1\mod n$ .
   Замечание: если $r$$r$  составное, то вышеуказанные условия не являются достаточными для обеспечения правильной расшифровки, то есть для того, чтобы всегда выполнялось $D(E(m))=m$$D(E(m))=m$ . Чтобы избежать подобного, предлагается выполнять следующую проверку: пусть $r=p_1{p}_2\dots <!--\; \dots \; -->p_k$$r=p_{1}p_{2}\dots p_{k}$ . Тогда $y$$y$  выбирается таким образом, чтобы для каждого $p_i$$p_{{i}}$  выполнялось $y^{\mathrm{\varphi <!--\; \varphi \; -->}/p_i}\ne <!--\; \ne \; -->1\mathrm{mod}n$$y^{\phi /p_{i}}\neq 1\mod n$  .
4. Пусть $x=y^{\mathrm{\varphi <!--\; \varphi \; -->}/r}\mathrm{mod}n$$x=y^{\phi /r}\mod n$ ;

Тогда открытым ключом является $(y,r,n)$$(y,r,n)$ , а секретным ключом — $(\mathrm{\varphi <!--\; \varphi \; -->},x)$$(\phi ,x)$ .

ШифрованиеПравить

Шифрование сообщения $m\in <!--\; \in \; -->{\mathbb{Z}}_r$$m\in {\mathbb {Z} }_{r}$ :

1. Выбирается произвольное $u\in <!--\; \in \; -->{\mathbb{Z}}_n^{\ast <!--\; \ast \; -->}$$u\in {\mathbb {Z} _{n}^{*}}$ ;
2. Тогда $E_r(m)=y^m{u}^r\mathrm{mod}n$$E_{r}(m)=y^{m}u^{r}\mod n$ .

РасшифрованиеПравить

Для начала заметим, что для любых $m\in <!--\; \in \; -->{\mathbb{Z}}_r$$m\in {\mathbb {Z} }_{r}$  и $u\in <!--\; \in \; -->{\mathbb{Z}}_n^{\ast <!--\; \ast \; -->}$$u\in {\mathbb {Z} }_{n}^{*}$  выполняется: $a=(c{)}^{\mathrm{\varphi <!--\; \varphi \; -->}/r}\equiv <!--\; \equiv \; -->(y^m{u}^r{)}^{\mathrm{\varphi <!--\; \varphi \; -->}/r}\equiv <!--\; \equiv \; -->(y^m{)}^{\mathrm{\varphi <!--\; \varphi \; -->}/r}(u^r{)}^{\mathrm{\varphi <!--\; \varphi \; -->}/r}\equiv <!--\; \equiv \; -->(y^{\mathrm{\varphi <!--\; \varphi \; -->}/r}{)}^m(u{)}^{\mathrm{\varphi <!--\; \varphi \; -->}}\equiv <!--\; \equiv \; -->(x{)}^m(u{)}^0\equiv <!--\; \equiv \; -->x^m\mathrm{mod}n$$a=(c)^{\phi /r}\equiv (y^{m}u^{r})^{\phi /r}\equiv (y^{m})^{\phi /r}(u^{r})^{\phi /r}\equiv (y^{\phi /r})^{m}(u)^{\phi }\equiv (x)^{m}(u)^{0}\equiv x^{m}\mod n$ 

Таким образом, чтобы вычислить $m$$m$ , зная $a$$a$ , проводится операция дискретного логарифмирования из $a$$a$  по основанию $x$$x$ . Если число $r$$r$  небольшое, возможно нахождение $m$$m$  через исчерпывающий перебор, то есть проверкой выполнения равенства $x^i\equiv <!--\; \equiv \; -->a\mathrm{mod}n$$x^{i}\equiv a\mod n$  для всех $0\dots <!--\; \dots \; -->(r-<!--\; -\; -->1)$$0\dots (r-1)$ . При больших значениях $r$$r$ , нахождение $m$$m$  можно проводить с помощью алгоритма Гельфонда — Шенкса (алгоритм больших и малых шагов), получив временную сложность расшифрования $O(\sqrt{r})$$O({\sqrt {r}})$ .

Расшифрование шифртекста $c\in <!--\; \in \; -->{\mathbb{Z}}_n^{\ast <!--\; \ast \; -->}$$c\in {\mathbb {Z} }_{n}^{*}$ :

1. Вычисляется $a=c^{\mathrm{\varphi <!--\; \varphi \; -->}/r}\mathrm{mod}n$$a=c^{\phi /r}\mod n$ ;
2. Подбирается $m={\log }_x<!--\; \; -->(a)$$m=\log _{x}(a)$ , то есть такое $m$$m$  , что $x^m\equiv <!--\; \equiv \; -->a\mathrm{mod}n$$x^{m}\equiv a\mod n$ 

Свойства криптосистемыПравить

ГомоморфизмПравить

Криптосистема Бенало гомоморфна относительно операции сложения:

$\mathcal{E}(x_1)\cdot <!--\; \cdot \; -->\mathcal{E}(x_2)=(g^{x_1}{u}_1^r)(g^{x_2}{u}_2^r)=g^{x_1+x_2}(u_1{u}_2{)}^r=\mathcal{E}(x_1+x_{2}modr)$${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{x_{1}}u_{1}^{r})(g^{x_{2}}u_{2}^{r})=g^{x_{1}+x_{2}}(u_{1}u_{2})^{r}={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}r)$ , где $\mathcal{E}(x)$${\mathcal {E}}(x)$  является функцией шифрования от сообщения $x$$x$ 

СтойкостьПравить

Стойкость криптосистемы Бенало основана на труднорешаемой задаче о вычетах высокой степени. Зная размер блока $r$$r$ , модуль $n$$n$  и шифртекст $E(M)$$E(M)$ , где разложение на множители числа $n$$n$  неизвестно, — определить открытый текст вычислительно сложно.

ЛитератураПравить

1. А. И. Трубей «Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор)»
2. Benaloh, Josh (1994) "Dense Probabilistic Encryption"