Knapsack Problem and Cryptanalyze

Knapsack Problem and Cryptanalyze

 Cryptography 

 Symmetric-key Cryptography

 Consider an encryption scheme consisting of the sets of encryption and decryption transformations {Ee : e ∈ K} and {Dd : d ∈ K}, respectively, where K is the key space. The encryption scheme is said to be symmetric-key if for each associated encryption/decryption key pair (e,d), it is easy to determine d knowing only e, and to determine e from d. Since e = d in most pratical symmetrickey encryption schemes, the term symmetric-key becomes appropriate. 9 

 Public-key Cryptography 

The concept of public-key encryption is simple and elegant, but has far-reaching consequences. Let {Ee : e ∈ K} be a set of encryption transformations, {Dd : d ∈ K} be the set of corresponding decryption transformations, where K is the key space. Assume that each pair of (Ee, Dd) has the property that knowing Ee, it is computationally infeasible, given a random ciphertext c ∈ C, to find the message m ∈ M such that Ee(m) = c. This property implies that given e ∈ K, it is infeable to determine the corresponding decryption key d ∈ K. Ee is being viewed here as a trapdoor one-way function with d being the trapdoor information necessary to compute the inverse function and hence allow decryption.This is unlike symetric-key ciphers where e and d are essentially the same. 

 Notion of complexity

Problems of decisions A problem of decision[4] is a problem whose the response is YES or NO 

 Class of complexity

• Classe of complexity P : is set the problems of decisions whose we can set a response within polynomial time. • Classe of complexity NP : is set the problems of decisions which the YES response can be obtain within polynomial time by a certificate. • Classe of complexity CO-NP : is set the problems of decisions which the NO response can be obtain within polynomial time by a certificate.

 Notion of reduction 

Let D1 and D2 two problems of decisions. D1 is called polynomialy reducible to D2( denoted by D1 ≤P D2 ) if exist an algorithm A1 to appeal to an algorithm A2 whose resolves D2 and checking the following conditions: 1. The number of appeal of A1 to A2 either increased by a polynomial. 2. The cost of appeal of A2 is polynomial. 11 Definition 1.2.2 NP-Complet A problem of decision D is NP-Complet if : 1. D ∈ NP 2. ∀ D1, D1 ≤P D, then D ∈ NP. Definition 

 NP-Hard A problem of decision D is NP-Hard if exist H NP-Complet such as H ≤P D. 

Groups, Ring and Lattices 

 Groups Structure of groups 

A group is an set G non-empty set provided with an internal composition law satisfying the following axioms • (A1) the law (∗) in G is associative, eg x ∗ (y ∗ z) = (x ∗ y) ∗ z ∀ x, y, z ∈ G. • (A2) the law (∗) assume a neutral element in G, ie ∃ e such as x∗e = e∗x = x • (A3) Every element of G is symmetrizable for the law (∗) ie ∀ x ∈ G,∃ x’∈ G such as x ∗ x’ = x’∗ x = e. If the law (∗) is commutative, we say that the group G is commutative (abelian), ie x ∗ y = y ∗ x, ∀ x, y ∈ G. Example: (R n , +), (Z n , +) are the abelians groups. Subgroup 1.3.1 Let G a group provided with an internal composition law (∗) and let H a non-empty subset of G.We say that H is a subgroup of G when the following two laws are checked: • H is stable for the law (∗), eg x ∗ y ∈ H, ∀ x , y ∈ H ; • H is stable for the reverse, eg x −1 ∈ H, ∀ x ∈ H ; In this case, the restriction of the law of G on H defines an internal composition law in H, for which H is itself a group Generator of subgroup 

Let G be a group and X a non-empty subset of G

The intersection of all subgroups of G containing X is a subgroup of G, called the subgroup of G genered by X, denoted hXi. It is the smallest (inclusion) subgroup containing X. If X = {e1, …, ed} then hXi = Pd i=1 Z.ei . 12 Discrete subgroup in R n 1.3.1 Let H be a subgroup of R n then H is discet ⇐⇒ 0 is isolated. Proof 1.3.1 Implication =⇒ is clear. Conversely assume that 0 is isolated. We can to fixe r > 0 such as B(0,r) ∩ G = 0. Let x ∈ G. For all y ∈ B(0,r) ∩ G, we have: • y – x ∈ G is a subgroup, • k y – x k < r so y – x ∈ B(0,r) Thus, y – x ∈ B(0,r) ∩ G = { 0 }; so y = x and B(x,r) ∩ G = { x }. Which by definition means that x is an isolated point G. 1.3.2 Rings Structure of Ring 1.3.1 Let A be a set non-empty provided with two internal of composition law (+), (∗). (A,+,∗) is said to, or simply that A is a ring if : • (A,+) is a abelian group. • The law ∗ is associative, eg ∀ x, y, z ∈ A: x ∗ (y ∗ z) = (x ∗ y) ∗ z • The law ∗ is distributive over +, eg. ∀ x, y, z ∈ A: x ∗ (y + z) = x ∗ y + x ∗ z et (y + z)∗ x = y ∗ x + z ∗ x . if more law ∗ is commutative, we say that the ring (A,+,∗) is commutative. If a ring (A,+,∗) has a neutral element for the law ∗, we say that ring A is unitaire. In the case, we denote 1A this element called A unit. Neutral element for the additive law is denoted by 0A.