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

В Криптосистема Бенало является продолжением Криптосистема Голдвассера-Микали (GM) создана в 1985 году Джошем (Коэном) Бенало. Основное улучшение криптосистемы Benaloh по сравнению с GM заключается в том, что более длинные блоки данных могут быть зашифрованы одновременно, тогда как в GM каждый бит шифруется индивидуально.^[1][2][3]

Определение схемы

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

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

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

1. Выберите большие простые числа п и q такой, что ${displaystyle rvert (p-1), имя оператора {gcd} (r, (p-1) / r) = 1,}$ и ${displaystyle operatorname {gcd} (r, (q-1)) = 1}$
2. Набор ${displaystyle n = pq, phi = (p-1) (q-1)}$
3. выбирать ${displaystyle yin mathbb {Z} _ {n} ^ {*}}$ такой, что ${displaystyle y ^ {phi / r} или эквивалент 1mod n}$.

Примечание: Если р является составным, как указали Fousse et al. в 2011^[4] что вышеуказанные условия (то есть те, которые указаны в исходной статье) недостаточны, чтобы гарантировать правильное дешифрование, то есть гарантировать, что ${displaystyle D (E (m)) = m}$ во всех случаях (как и должно быть). Чтобы решить эту проблему, авторы предлагают следующую проверку: пусть ${displaystyle r = p_ {1} p_ {2} dots p_ {k}}$ быть простым разложением р. выбирать ${displaystyle yin mathbb {Z} _ {n} ^ {*}}$ так что для каждого фактора ${displaystyle p_ {i}}$, это тот случай, когда ${displaystyle y ^ {phi / p_ {i}} eq 1mod n}$.

1. Набор ${displaystyle x = y ^ {phi / r} mod n}$

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

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

Чтобы зашифровать сообщение ${displaystyle min mathbb {Z} _ {r}}$:

1. Выберите случайный ${displaystyle uin mathbb {Z} _ {n} ^ {*}}$
2. Набор ${displaystyle E_ {r} (m) = y ^ {m} u ^ {r} mod n}$

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

Расшифровать зашифрованный текст ${displaystyle cin mathbb {Z} _ {n} ^ {*}}$:

1. Вычислить ${displaystyle a = c ^ {phi / r} mod n}$
2. Выход ${displaystyle m = log _ {x} (a)}$, т.е. найти м такой, что ${displaystyle x ^ {m} Equiv amod n}$

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

${Displaystyle а = (с) ^ {фи / г} экв (у ^ {м} и ^ {г}) ^ {фи / г} экв (у ^ {м}) ^ {фи / г} (и ^ { г}) ^ {фи / г} эквив (у ^ {фи / г}) ^ {м} (и) ^ {фи} экв (х) ^ {м} (и) ^ {0} эквив х ^ {м } мод n}$

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

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

Безопасность этой схемы основана на Проблема более высокой остаточности, в частности, учитывая z,р и п где факторизация п неизвестно, вычислить невозможно, чтобы определить, z является рмод остатка п, т.е. если существует Икс такой, что ${displaystyle zequiv x ^ {r} mod n}$.

Рекомендации