Русская Википедия:Криптосистема Бенало

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

Генерация ключа

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

Тогда открытым ключом является <math>(y,r,n)</math>, а секретным ключом — <math>(\phi,x)</math>.

Шифрование

Шифрование сообщения <math>m\in {\mathbb {Z}}_{r}</math>:

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

Расшифрование

Для начала заметим, что для любых <math>m\in {\mathbb {Z}}_{r}</math> и <math>u\in {\mathbb {Z}}_{n}^{*}</math> выполняется: <math>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</math>

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

Расшифрование шифртекста <math>c\in {\mathbb {Z}}_{n}^{*}</math>:

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

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

Гомоморфизм

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

<math>{\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)</math>, где <math>{\mathcal {E}}(x)</math> является функцией шифрования от сообщения <math>x</math>

Стойкость

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

Литература

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