Криптосистема Наккаша – Стерна - Naccache–Stern cryptosystem

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

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

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

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

Выберите семью из k маленький отчетливый простые числа п₁,...,п_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}}$
Выберите большие простые числа а и б так что оба п = 2au+1 и q=2bv+1 - простые.
Набор п=pq.
Выберите случайный грамм мод п такой, что грамм имеет порядок φ (п)/4.

Открытый ключ - это числа σ,п,грамм а закрытый ключ - это пара п,q.

Когда k= 1 это по сути Криптосистема Бенало.

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

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

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

потом Эм) это шифрование сообщения м.

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

Чтобы расшифровать, мы сначала находим м мод п_я для каждого я, а затем применяем Китайская теорема об остатках вычислять м мод ${displaystyle sigma}$ .

Учитывая зашифрованный текст c, чтобы расшифровать, вычисляем

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

{displaystyle {egin {matrix} c ^ {phi (n) / p_ {i}} & Equiv & x ^ {sigma phi (n) / p_ {i}} g ^ {mphi (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 nend {матрица}}}

куда ${displaystyle m_ {i} Equiv mmod p_ {i}}$ .

С п_я выбрано маленьким, м_я можно восстановить с помощью исчерпывающего поиска, т. е. сравнения ${displaystyle c_ {i}}$ к ${displaystyle g ^ {jphi (n) / p_ {i}}}$ за j от 1 до п_я-1.
Один раз м_я известен каждому я, м может быть восстановлен прямым применением китайской теоремы об остатках.

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

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