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

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

Обзор системы

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

c\equiv \prod _{i=0}^{n}v_{i}^{x_{i}}\mod p

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

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

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

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

Открытый ключ тогда равен p , n и v ₀ ,..., v _n . Закрытый ключ — s .

Шифрование

Чтобы зашифровать n- битное сообщение m , вычислите

c=\prod _{i=0}^{n}v_{i}^{m_{i}}\mod p

где m _i — i -й бит сообщения m .

Расшифровка

Чтобы расшифровать сообщение c , вычислите

m=\sum _{i=0}^{n}{\frac {2^{i}}{p_{i}-1}}\times \left(\gcd(p_{i},c^{s}\mod p)-1\right)

Это работает, потому что дробь

{\frac {\gcd(p_{i},c^{s}\mod p)-1}{p_{i}-1}}

равно 0 или 1 в зависимости от того, pi _c ли делит ^с против п .

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

Безопасность функции люка зависит от сложности следующих задач: мультипликативная задача о рюкзаке : дано $c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\pmod {p}},$ восстановить $m_{i}$ . В отличие от аддитивных криптосистем на основе ранца, такие как Меркл-Хеллман , методы, подобные Евклиду редукция решетки не применима к этой проблеме.

Самая известная универсальная атака состоит в решении задачи дискретного логарифма для восстановления $s$ от $p,p_{i},v_{i}$ , что считается сложным для классического компьютера. Однако квантовый алгоритм Шора эффективно решает эту проблему. Более того, в настоящее время (2023 г.) нет никаких доказательств того, что метод Наккаше-Штерна рюкзак сводится к задаче дискретного логарифмирования.

Самая известная специфическая атака (в 2018 году) использует день рождения. теорема о частичном инвертировании функции, не зная лазейки, предполагая, что сообщение имеет очень низкий вес Хэмминга . ^{[ 1 ]}

Ссылки

^ Анастасиадис, М.; Чацис, Н.; Дразиотис, штат Калифорния (октябрь 2018 г.). «Атаки типа дня рождения на ранцевую криптосистему Наккаша – Штерна». Письма об обработке информации . 138 : 39–43. дои : 10.1016/j.ipl.2018.06.002 .

См. также

[1] Анастасиадис, М.; Чацис, Н.; Дразиотис, штат Калифорния (октябрь 2018 г.). «Атаки типа дня рождения на ранцевую криптосистему Наккаша – Штерна». Письма об обработке информации . 138 : 39–43. дои : 10.1016/j.ipl.2018.06.002 .

[ 1 ]