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.10 KNAPSACK CRYPTOSYSTEM PROBLEMS

Problems 11.1 to 11.4 provide technical details used in Chapter 11. In each example, the integer m has the factorization into primes image

The ciphertext files cipherPr11.1-cipherPr11.12 may be downloaded from the following ftp address: ftp://ftp.wiley.com/public/sci_tech_med/computer_security.

PROBLEMS

11.1 Show how the principle of inclusion–exclusion can be used to derive the formula of Proposition 11.6 for the Euler totient function.

11.2 Prove that Ωm = {ω : 1 = gcd{ω, m}} is a group; that is,

11.2a ω1, ω2 ωm image ω1ω2 m;

11.2b 1 m;

11.2c If ω m, then ω−1 m.

11.3 Prove that the cardinality of |Ωm| is the value of the Euler totient functjon ϕ(m).

11.4 Calculate the cardinality of Γm(s) = {ωs : ω m}.

Problems 11.5 to 11.8 provide examples of Merkle–Hellman knapsack encipherment. They require two programs: the first to encipher ASCII character plaintext, and the second to decipher ciphertext.

The Merkle–Hellman encipherment program takes as parameters

• The number of knapsack lengths n,

• The vector of public knapsack lengths a = (a0, a1, …, an−1), and

• A string of N ASCII characters x = (x0), x1), …, x(N−1)),

and returns ciphertext formatted as in Section 11.5.

The Merkle–Hellman decipherment program ciphertext takes as parameters

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