Ранцевая криптосистема Наккаша – Штерна - Naccache–Stern knapsack cryptosystem

В Криптосистема Naccache – Stern Knapsack нетипичный криптосистема с открытым ключом разработан Дэвид Наккаш и Жак Стерн в 1997 году. Эта криптосистема детерминированный, и, следовательно, не семантически безопасный. Несмотря на то, что эта система не сломана на сегодняшний день, ей также не хватает доказуемая безопасность.

Системный Обзор

Эта система основана на типе проблема с рюкзаком. В частности, основная проблема заключается в следующем: заданные целые числа c,п,п и v₀,...,v_пнайти вектор ${displaystyle xin {0,1} ^ {n}}$ такой, что

{displaystyle cequiv prod _ {i = 0} ^ {n} v_ {i} ^ {x_ {i}} mod p}

Идея здесь в том, что когда v_я находятся относительно простой и намного меньше модуля п эту проблему легко решить. Именно это наблюдение позволяет дешифровать.

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

Чтобы создать пару открытого / закрытого ключей

Выберите большой основной модуль п.
Выберите положительное целое число п и для я от 0 до п, набор п_я быть яое простое число, начиная с п₀ = 2 и такой, что ${displaystyle prod _ {i = 0} ^ {n} p_ {i}$ .
Выберите секретное целое число s < п-1, такой что gcd (п-1,s) = 1.
Набор ${displaystyle v_ {i} = {sqrt [{s}] {p_ {i}}} mod p}$ .