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 
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 
ω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
Get Computer Security and Cryptography now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
