Bias tee: Difference between revisions
en>Hmainsbot1 m AWB general fixes and delink dates per WP:DATELINK, WP:YEARLINK and MOS:UNLINKYEARS using AWB (8097) |
en>Matthias Buchmeier +Category:Microwave technology |
||
Line 1: | Line 1: | ||
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 encryption|deterministic]], and hence is not [[semantic security|semantically secure]]. This system also lacks [[provable security]]. | |||
==System Overview== | |||
This system is based on a type of [[knapsack problem]]. Specifically, the underlying problem is this: given integers ''c'',''n'',''p'' and ''v''<sub>0</sub>,...,''v''<sub>''n''</sub>, find a vector <math>x \in \{0,1\}^n</math> such that | |||
:<math>c \equiv \prod_{i=0}^n v_i^{x_i} \mod p</math> | |||
The idea here is that when the ''v''<sub>''i''</sub> 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 number|prime]] modulus ''p''. | |||
*Pick a positive integer ''n'' and for ''i'' from 0 to ''n'', set ''p''<sub>''i''</sub> to be the ''i''th prime, starting with ''p''<sub>0</sub> = 2 and such that <math>\prod_{i=0}^np_i < p</math>. | |||
*Pick a secret integer ''s'' < ''p''-1, such that gcd(''p''-1,''s'') = 1. | |||
*Set <math>v_i = \sqrt[s]{p_i} \mod p</math>. | |||
The public key is then ''p'',''n'' and ''v''<sub>0</sub>,...,''v''<sub>''n''</sub>. The private key is ''s''. | |||
===Encryption=== | |||
To encrypt an ''n''-bit long message ''m'', calculate | |||
:<math>c = \prod_{i=0}^n v_i^{m_i} \mod p</math> | |||
where ''m''<sub>''i''</sub> is the ''i''th bit of the message ''m''. | |||
===Decryption=== | |||
To decrypt a message ''c'', calculate | |||
:<math>m = \sum_{i=0}^n \frac{2^i}{p_i-1} \times \left( \gcd(p_i,c^s \mod p) -1 \right)</math> | |||
This works because the fraction | |||
:<math>\frac{ \gcd(p_i,c^s \mod p) - 1 }{p_i - 1}</math> | |||
is 0 or 1 depending on whether ''p''<sub>''i''</sub> divides ''c''<sup>''s''</sup> mod ''p''. | |||
==See also== | |||
*[[Merkle–Hellman knapsack cryptosystem]] | |||
*[[Graham–Shamir knapsack cryptosystem]] | |||
==References== | |||
*[http://www.di.ens.fr/~stern/data/St63.pdf Original Paper] | |||
*[http://eprint.iacr.org/2008/119.pdf Recent bandwidth improvement] | |||
{{Cryptography navbox | public-key}} | |||
{{DEFAULTSORT:Naccache-Stern knapsack cryptosystem}} | |||
[[Category:Public-key encryption schemes]] |
Revision as of 21:45, 16 January 2014
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.
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.
Key Generation
To generate a public/private key pair
- Pick a large prime modulus p.
- Pick a positive integer n and for i from 0 to n, set pi to be the ith prime, starting with p0 = 2 and such that .
- Pick a secret integer s < p-1, such that gcd(p-1,s) = 1.
- Set .
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
where mi is the ith bit of the message m.
Decryption
To decrypt a message c, calculate
This works because the fraction
is 0 or 1 depending on whether pi divides cs mod p.