Криптосистема Benaloh

Криптосистема Benaloh является расширением криптосистемы Goldwasser-Micali (GM) создан в 1985 году Джошем (Коэном) Бенало. Основное улучшение криптосистемы Benaloh по сравнению с GM заключается в том, что более длинные блоки данных могут быть зашифрованы одновременно, тогда как в GM каждый бит шифруется индивидуально.

• 1 Определение схемы
  • 1.1 Генерация ключа
  • 1.2 Шифрование сообщений
  • 1.3 Расшифровка сообщений
  • 1.4 Безопасность
• 2 Ссылки

Как и многие криптосистемы с открытым ключом, эта схема работает в группе $(Z\; /\; n\; Z)\; \ast \; \{\backslash \; displaystyle\; (\backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\})\; ^\; \{*\}\}$, где n - произведение двух больших простых чисел. Эта схема гомоморфна и, следовательно, податлива.

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

Учитывая размер блока r, пара открытого / закрытого ключей генерируется следующим образом:

1. Выберите большие простые числа p и q такие, что $r\; |\; (п\; -\; 1),\; НОД\; \; (г,\; (п\; -\; 1)\; /\; г)\; знак\; равно\; 1,\; \{\backslash \; Displaystyle\; г\; \backslash \; верт\; (р-1),\; \backslash \; OperatorName\; \{НОД\}\; (г,\; (р-1)\; /\; г)\; =\; 1,\}$и $gcd\; \; (r,\; (q\; -\; 1))\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{gcd\}\; (r,\; (q-1))\; =\; 1\}$
2. Установить $n\; =\; pq,\; \varphi \; =\; (p\; -\; 1)\; (q\; -\; 1)\; \{\backslash \; displaystyle\; n\; =\; pq,\; \backslash \; phi\; =\; (p-1)\; (q-1)\}$
3. Выбрать $y\; \in \; Z\; n\; \ast \; \{\backslash \; displaystyle\; y\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; \_\; \{n\}\; ^\; \{*\}\}$так, что $y\; \varphi \; /\; r\; \not\equiv \; 1\; mod\; n\; \{\backslash \; displaystyle\; y\; ^\; \{\backslash \; phi\; /\; r\}\; \backslash \; not\; \backslash \; Equiv\; 1\; \backslash \; mod\; n\}$.

Примечание: Если r составное, на это указали Fousse et al. в 2011 году, что вышеуказанные условия (т. е. те, которые указаны в исходной статье) недостаточны для гарантии правильного дешифрования, т. е. чтобы гарантировать, что $D\; (E\; (m))\; =\; m\; \{\backslash \; displaystyle\; D\; (E\; (m))\; =\; m\}$во всех случаях (как и должно быть). Чтобы решить эту проблему, авторы предлагают следующую проверку: пусть $r\; =\; p\; 1\; p\; 2\dots \; pk\; \{\backslash \; displaystyle\; r\; =\; p\_\; \{1\}\; p\_\; \{2\}\; \backslash \; dots\; p\_\; \{k\}\}$будет факторизация числа r на простые множители. Выберите $y\; \in \; Z\; n\; \ast \; \{\backslash \; displaystyle\; y\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; \_\; \{n\}\; ^\; \{*\}\}$так, чтобы для каждого множителя $pi\; \{\backslash \; displaystyle\; p\_\; \{i\; \}\}$, это случай, когда $y\; \varphi \; /\; pi\; \ne \; 1\; mod\; n\; \{\backslash \; displaystyle\; y\; ^\; \{\backslash \; phi\; /\; p\_\; \{i\}\}\; \backslash \; neq\; 1\; \backslash \; mod\; n\}$.

1. Set $x\; =\; y\; \varphi \; /\; r\; mod\; n\; \{\backslash \; displaystyle\; x\; =\; y\; ^\; \{\backslash \; phi\; /\; r\}\; \backslash \; mod\; n\}$

Тогда открытый ключ $y,\; n\; \{\backslash \; displaystyle\; y,\; n\}$, а закрытый ключ - $\varphi ,\; x\; \{\backslash \; displaystyle\; \backslash \; phi,\; x\}$.

Шифрование сообщения

Для шифрования сообщения $m\; \in \; Z\; r\; \{\backslash \; displaystyle\; m\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; \_\; \{r\}\}$:

1. Выберите случайный $u\; \in \; Z\; n\; \ast \; \{\backslash \; displaystyle\; u\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; \_\; \{n\}\; ^\; \{*\}\}$
2. Установить $E\; r\; (m)\; =\; ymur\; mod\; n\; \{\backslash \; displaystyle\; E\_\; \{r\}\; (m)\; =\; y\; ^\; \{m\}\; u\; ^\; \{r\}\; \backslash \; mod\; n\}$

Расшифровка сообщения

Для расшифровки зашифрованный текст $c\; \in \; Z\; n\; \ast \; \{\backslash \; displaystyle\; c\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; \_\; \{n\}\; ^\; \{*\}\}$:

1. Compute $a\; =\; c\; \varphi \; /\; r\; mod\; n\; \{\backslash \; displaystyle\; a\; =\; c\; ^\; \{\backslash \; phi\; /\; r\}\; \backslash \; mod\; n\}$
2. Вывод $m\; =\; log\; x\; \; (a)\; \{\backslash \; displaystyle\; m\; =\; \backslash \; log\; \_\; \{x\}\; (a)\}$, т.е., найдите m такое, что $xm\; \equiv \; a\; mod\; n\; \{\backslash \; displaystyle\; x\; ^\; \{m\}\; \backslash \; equi\; va\; \backslash \; mod\; n\}$

Чтобы понять расшифровку, сначала обратите внимание, что для любого $m\; \in \; Z\; r\; \{\backslash \; displaystyle\; m\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; \_\; \{r\}\}$и $u\; \in \; Z\; n\; \ast \; \{\backslash \; displaystyle\; u\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; \_\; \{n\}\; ^\; \{*\}\}$имеем:

$a\; =\; (c)\; \varphi \; /\; r\; \equiv \; (ymur)\; \varphi \; /\; р\; \equiv \; (ym)\; \varphi \; /\; r\; (ur)\; \varphi \; /\; r\; \equiv \; (y\; \varphi \; /\; r)\; m\; (u)\; \varphi \; \equiv \; (x)\; m\; (u)\; 0\; \equiv \; xm\; mod\; n\; \{\backslash \; displaystyle\; a\; =\; (c)\; ^\; \{\; \backslash \; phi\; /\; r\}\; \backslash \; эквив\; (у\; ^\; \{м\}\; и\; ^\; \{г\})\; ^\; \{\backslash \; фи\; /\; г\}\; \backslash \; экв\; (у\; ^\; \{м\})\; ^\; \{\backslash \; фи\; /\; г\}\; (и\; ^\; \{г\})\; ^\; \{\backslash \; phi\; /\; r\}\; \backslash \; Equiv\; (y\; ^\; \{\backslash \; phi\; /\; r\})\; ^\; \{m\}\; (u)\; ^\; \{\backslash \; phi\}\; \backslash \; Equiv\; (x)\; ^\; \{m\}\; (u)\; ^\; \{0\}\; \backslash \; Equiv\; x\; ^\; \{m\}\; \backslash \; mod\; n\}$

Чтобы восстановить m из a, мы берем дискретный журнал по основанию x. Если r мало, мы можем восстановить m с помощью исчерпывающего поиска, т. Е. Проверки того, $xi\; \equiv \; a\; mod\; n\; \{\backslash \; displaystyle\; x\; ^\; \{i\}\; \backslash \; Equiv\; a\; \backslash \; mod\; n\}$для всех $0\dots \; (r\; -\; 1)\; \{\backslash \; displaystyle\; 0\; \backslash \; dots\; (r-1)\}$. Для больших значений r алгоритм гигантского шага младенца может использоваться для восстановления m в $O\; (r)\; \{\backslash \; displaystyle\; O\; (\{\backslash \; sqrt\; \{r\}\})\}$время и пространство.

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

Безопасность этой схемы основана на проблеме более высокой остаточности, в частности, при заданных z, r и n, где факторизация n неизвестна, это вычисляется невозможно определить, является ли z r-м остатком по модулю n, т. е. существует ли x такой, что $z\; \equiv \; xr\; mod\; n\; \{\backslash \; displaystyle\; z\; \backslash \; Equiv\; x\; ^\; \{r\}\; \backslash \; mod\; n\}$.