انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

Ch5:Knapsack cipher , Public key digital signature algorithem.

          Knapsack cipher system is a public key system based on the so –called Knapsack problem . The Knapsack problem can be described as follows .The vector A = (a₁,a₂,a₃……..a_n) consist of positive integer .The elements of this vector are multiplied by a binary vector denoted by X=(x₁,x₂……x_n) in which every   x_i ; i= 1,……..,n is either 0 or 1 . This results is the sum s :

       S=

If X and A are given the value of S can be calculated with out any effort . However if S and A are given , it is considerably move difficult to calculate X. figure 5-3illustrates the knapsack problem . A Knapsack filled with a selection of object) from a large set , each object has a different weight (the elements of a correspond to the determine which items are in the Knapsack?

In other word is it possible to determine the elements of X ? when A is sufficiently large (more than 100 elements), it is almost impossible to calculate X from a given S and A.