Криптосистема Наккаш–Штерн

Криптосистема Наккаша–Стерна — это гомоморфная криптосистема с открытым ключом , безопасность которой основана на проблеме высшей остаточности . Криптосистема Наккаша–Стерна была открыта Дэвидом Наккашем и Жаком Стерном в 1998 году.

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

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

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

• Выберите семейство из k малых различных простых чисел p ₁ ,..., p _k .
• Разделите набор пополам и установите и . ${\displaystyle u=\prod _{i=1}^{k/2}p_{i}}$ ${\displaystyle v=\prod _{k/2+1}^{k}p_{i}}$
• Набор ${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i}}$
• Выберите большие простые числа a и b так, чтобы и p = 2 au +1, и q = 2 bv +1 были простыми.
• Положим n = pq .
• Выберите случайное g mod n такое, что g имеет порядок φ( n )/4.

Открытый ключ — это числа σ, n , g , а закрытый ключ — это пара p , q .

При k = 1 это по сути криптосистема Бенало .

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

Эта система позволяет шифровать сообщение m в группе . ${\displaystyle \mathbb {Z} /\sigma \mathbb {Z} }$

• Выберите случайный . ${\displaystyle x\in \mathbb {Z} /n\mathbb {Z} }$
• Рассчитать ${\displaystyle E(m)=x^{\sigma }g^{m}\mod n}$

Тогда E(m) — это шифрование сообщения m .

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

Чтобы расшифровать, мы сначала находим m mod p _i для каждого i , а затем применяем китайскую теорему об остатках для вычисления m mod . ${\displaystyle \sigma }$

Для расшифровки шифртекста c необходимо вычислить

• ${\displaystyle c_{i}\equiv c^{\phi (n)/p_{i}}\mod n}$. Таким образом

${\displaystyle {\begin{matrix}c^{\phi (n)/p_{i}}&\equiv &x^{\sigma \phi (n)/p_{i}}g^{m\phi (n)/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\&\equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}}$

где . ${\displaystyle m_{i}\equiv m\mod p_{i}}$

• Поскольку p _i выбрано малым, m _i можно восстановить с помощью полного перебора, т.е. путем сравнения с j от 1 до p _i -1. ${\displaystyle c_{i}}$ ${\displaystyle g^{j\phi (n)/p_{i}}}$
• Как только m _i станет известно для каждого i , m можно восстановить, применив китайскую теорему об остатках.

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

Семантическая безопасность криптосистемы Наккаш-Стерна основана на расширении проблемы квадратичных остатков, известной как проблема высших остатков .

Ссылки

Наккаш, Дэвид; Стерн, Жак (1998). «Новая криптосистема с открытым ключом, основанная на высших остатках». Труды 5-й конференции ACM по компьютерной и коммуникационной безопасности . CCS '98. ACM. стр. 59–66. doi : 10.1145/288090.288106 . ISBN 1-58113-007-4.