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.6 CRYPTANALYSIS OF THE MERKLE–HELLMAN KNAPSACK SYSTEM (MODULAR MAPPING) [SHAMIR, 1982]

UCSB has been the site of a meeting dealing with current topics in cryptography starting with CRYPTO ’81 in 1981. Adi Shamir electrified the attendees at CRYFTO ’82 by presenting an analysis of the Merkle–Hellman cryptosystem. A program running on an Apple during his lecture illustrated the solution technique that we now describe.

The mapping Tω−1,m: s = (s0, s1, …, sn−1) → a = (a0, a1, …, an−1) from the super-increasing to the public knapsack vector is nonlinear and this was the basis for believing that the Merkle–Hellman scheme provided a secure public-key encipherment scheme.

For image define the modular mapping (function) ϕa,m(w) for 0 ≤ a, w < m (Fig. 11.1) by

image

  • The continuous representation of the discrete-valued function ϕa,m(w) consists of straight-line segments with slope image
  • ϕa, m (w) has minima nearly equal to 0 at the points image with i = 0, 1, …, a − 1; the distance between consecutive minima is larger than 1.

Write

Figure 11.1 The modular mapping function.

where kj is an integer <m. According ...

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