O'Reilly logo

Computer Security and Cryptography by Alan G. Konheim

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

11.4 TRAP-DOOR KNAPSACKS

In their important paper. Merkle and Hellman [1978] published the first example of a trap-door public-key cryptosystem. They define a transformation relating

  • A knapsack problem K{s, t} with a knapsack vector s that is super-increasing and
  • A knapsack problem K{a, b, m} modulo m with a seemingly general knapsack vector a.

It was intended that the transformation K{s, t} → K{a, b, m} satisfy three properties:

  1. K{a, b, m} and K{s, t} are equivalent, meaning they have a common solution;
  2. It is computationally infeasible to find a solution to K{a, b, m};
  3. It is easy to find a solution to K{s, t}.

We develop their ideas in this section.

Let SUPn[m] be the subset of SUPn that satisfies the size condition

image

TABLE 11.3 The Knapsack Multipliers for m = 14

image

Let image denote the set of integers, referred to as knapsack multipliers, which are relatively prime to the modulus m. Each ω m has a multiplicative inverse ω−1 m; that is, 1 = ωω−1 (modulo m).

Note that the modulus m is not required to be a prime number.

Example 11.8

Table 11.3 lists the knapsack multipliers from m = 14.

Example 11.9

Table 11.4 lists the knapsack multipliers for m = 13. When ω is relatively prime to ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required