Naccache–Stern knapsack cryptosystem

Naccache–Stern knapsack cryptosystem

Note: this is not to be confused with the Naccache–Stern cryptosystem based on the higher residuosity problem.

The Naccache–Stern Knapsack Cryptosystem is an atypical public-key cryptosystem developed by David Naccache and Jacques Stern in 1997. This cryptosystem is deterministic, and hence is not semantically secure. This system also lacks provable security.

Contents

System Overview

This system is based on a type of knapsack problem. Specifically, the underlying problem is this: given integers c,n,p and v0,...,vn, find a vector x \in \{0,1\}^n such that

c \equiv \prod_{i=0}^n v_i^{x_i} \mod p

The idea here is that when the vi are relatively prime and much smaller than the modulus p this problem can be solved easily. It is this observation which allows decryption.

Key Generation

To generate a public/private key pair

  • Pick a large prime modulus p.
  • Pick a positive integer n.
  • For i from 0 to n, set pi to be the ith prime, starting with p0 = 2.
  • Pick a secret integer s < p-1, such that gcd(p-1,s) = 1.
  • Set v_i = \sqrt[s]{p_i} \mod p.

The public key is then p,n and v0,...,vn. The private key is s.

Encryption

To encrypt an n-bit long message m, calculate

c = \prod_{i=0}^n v_i^{m_i} \mod p

where mi is the ith bit of the message m.

Decryption

To decrypt a message c, calculate

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

This works because the fraction

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

is 0 or 1 depending on whether pi divides cs mod p.

See also

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Naccache-Stern knapsack cryptosystem — Note: this is not to be confused with the Naccache Stern cryptosystem based on the higher residuosity problem.The Naccache Stern Knapsack Cryptosystem is an atypical Public Key Cryptosystem developed by David Naccache and Jacques Stern in 1997.… …   Wikipedia

  • Naccache–Stern cryptosystem — Note: this is not to be confused with the Naccache–Stern knapsack cryptosystem. The Naccache–Stern cryptosystem is a homomorphic public key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was… …   Wikipedia

  • Naccache-Stern cryptosystem — Note: this is not to be confused with the Naccache Stern knapsack cryptosystem.The Naccache Stern cryptosystem is a homomorphic Public key cryptosystem whose security rests on the higher residuosity problem.The Naccache Stern cryptosystem was… …   Wikipedia

  • Merkle–Hellman knapsack cryptosystem — The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.[1] Although its ideas are elegant, and far simpler than RSA, it has been broken.[2] Contents 1… …   Wikipedia

  • Knapsack (disambiguation) — The word knapsack can refer to: * a backpack * Knapsack, Germany, a locality of Hürth, Rhine Erft district, North Rhine Westphalia * the knapsack problem, a math problem:* the subset sum problem, a special case of the above:* Naccache Stern… …   Wikipedia

  • Jacques Stern (Kryptologe) — Jacques Stern (* 21. August 1949 in Paris) ist ein französischer Kryptologe, Informatiker und Mathematiker. Jacques Stern Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • David Naccache — (2011) David Naccache is a cryptographer, currently a professor at the Pantheon Assas Paris II University and member of the École normale supérieure s Computer Laboratory. He is also a visiting professor at Royal Holloway University of London s… …   Wikipedia

  • Jacques Stern — (born 1949) is a cryptographer, currently a professor at the École Normale Supérieure, where he is Director of the Computer Science Laboratory. He received the 2006 CNRS Gold Medal. His notable work includes the cryptanalysis of numerous… …   Wikipedia

  • Niederreiter cryptosystem — In cryptography, the Niederreiter cryptosystem is a variation of the McEliece Cryptosystem developed in 1986 by Harald Niederreiter [1]. It applies the same idea to the parity check matrix H of a linear code. Niederreiter is equivalent to… …   Wikipedia

  • Задача о ранце в криптографии — (англ. Knapsack problem)  это задача, на основе которой американские криптографы Ральф Меркл (англ.) и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом. Он носит название криптосистема Меркла Хеллмана. Для… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”