Ранцевая криптосистема Наккаша – Стерна

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

Обзор системы [ править ]

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

{\ Displaystyle с \ Equiv \ prod _ {я = 0} ^ {n} v_ {я} ^ {x_ {i}} \ mod p}

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

Генерация ключей [ править ]

Чтобы сгенерировать пару открытого и закрытого ключей

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