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

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

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

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

No credit card required