Naccache-Stern knapsack cryptosystem
From Wikipedia, the free encyclopedia
Note: this is not to be confused with the Naccache-Stern cryptosystem based on the higher residuosity problem.
The Naccache-Stern Knapsack Cryptosystem is a 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 |
[edit] 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 
such that
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.
[edit] 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](../../../math/8/c/5/8c52072f9a41d5a10d60c9783820d82a.png)
. Note: these roots can be calculated using the Pohlig-Hellman algorithm.
The public key is then p,n and v0,...,vn. The private key is s.
[edit] Encryption
To encrypt an n-bit long message m, calculate
where mi is the ith bit of the message m.
[edit] Decryption
To decrypt a message c, calculate
This works because the fraction
is 0 or 1 depending on whether pi divides cs mod p.
