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}*

**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* = (*a*_{0}, *a*_{1}, …, *a*_{n−1}), and

• A string of *N* ASCII characters *x* = (*x*^{0)}, *x*^{1)}, …, *x*^{(N−1)}),

and returns ciphertext formatted as in Section 11.5.

The Merkle–Hellman decipherment program ciphertext takes as parameters

Start Free Trial

No credit card required