The Naccache–Stern Knapsack cryptosystem is an atypical
public-key cryptosystem
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
developed by
David Naccache
David Naccache is a cryptographer, currently a professor at the École normale supérieure and a member of its Computer Laboratory. He was previously a professor at Panthéon-Assas University.
Biography
He received his Ph.D. in 1995 from the ...
and
Jacques Stern
Jacques Stern (born 21 August 1949) is a cryptographer, currently a professor at the École Normale Supérieure. He received the 2006 CNRS Gold medal. His notable work includes the cryptanalysis of numerous encryption and signature schemes, t ...
in 1997. This cryptosystem is
deterministic
Determinism is a philosophical view, where all events are determined completely by previously existing causes. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping motives and consi ...
, and hence is not
semantically secure. While unbroken to date, this system also lacks
provable security
Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.
Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...
.
System Overview
This system is based on a type of
knapsack problem
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit a ...
. Specifically, the underlying problem is this: given integers ''c'',''n'',''p'' and ''v''
0,...,''v''
''n'', find a vector
such that
:
The idea here is that when the ''v''
''i'' are
relatively prime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equival ...
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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
modulus ''p''.
*Pick a positive integer ''n'' and for ''i'' from 0 to ''n'', set ''p''
''i'' to be the ''i''th prime, starting with ''p''
0 = 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 ''v''
0,...,''v''
''n''. The private key is ''s''.
Encryption
To encrypt an ''n''-bit long message ''m'', calculate
:
where ''m''
''i'' is the ''i''th bit of the message ''m''.
Decryption
To decrypt a message ''c'', calculate
:
This works because the fraction
:
is 0 or 1 depending on whether ''p''
''i'' divides ''c''
''s'' mod ''p''.
See also
*
Merkle–Hellman knapsack cryptosystem The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems. It was published by Ralph Merkle and Martin Hellman in 1978. A polynomial time attack was published by Adi Shamir in 1984. As a result, the cryptosystem is ...
*
Graham–Shamir knapsack cryptosystem
References
Original PaperRecent bandwidth improvement
{{DEFAULTSORT:Naccache-Stern knapsack cryptosystem
Public-key encryption schemes