VE475 Introduction to Cryptography Homework 4 Solved
Ex. 1 - Euler's totient
Let ϕ be Euler's totient function.
1. Prove that for any prime p, ϕ(pk) = pk−1(p − 1).
2. Prove that for any two coprime integers m and n, ϕ(mn) = ϕ(m)ϕ(n).
3. Using the previous results prove that for any integer n 1, we have
ϕ(n) = n (1 − 1) p
pin
4. What are the three last digits of 7803
Ex. 2 - AES
Supposed a round 0 AES key is composed of 128 1.
1. What is the key used for round 1 ?
2. Observe K(5) and express it in term of K(4).
3. Prove that K(10) = K(8) and K(11) = K(9).
Note: x denotes the complement of x, that is Os become 1s and 1s become Os. Ex. 3 - Simple questions
1. A plaintext is split into blocks and then encrypted. If one block is corrupted during transmission show that the number of plaintext decrypted incorrectly is one for the ECB mode and two for CBC.
2. Show that using CBC mode with an IV incremented by 1 each time, instead of being random, results in schemes that are not CPA secure.
3. Prove that 2 is a generator of U(Z/29Z).
4. Determine
(8191] .
5. Let a, b, c be three integers and p be an odd prime not dividing a. Prove that the number of solutions mod p to the equation ax2 + bx + c = 0 is 1 + (b2−4ac).
p
6. Let p and q be two primes such that p q 2 and q−1 divides p−1. Show that if gcd(n, pq) = 1, then np−1 ≡ 1 mod pq.
7. Let p be an odd prime. Prove that (−3) = 1 if and only if p ≡ 1 mod 3.
p
8. Let p be a prime. Prove that if (a) = 1, then a is not a generator of F∗p.
p
Ex. 4 — Prime vs. irreducible
In a commutative ring R, a non-zero, non-invertible element p is said to be prime if for any x, y ∈ R,
pl(x.y) implies pix or ply. (∗)
The goal of this exercise is to prove that this definition generalizes the definition of primality for integers, i.e., p ∈ Z is prime if
p 1 and a I p implies a = 1 or a = p. (∗∗)
1. Prove that in an integral domain, i.e. a commutative ring in which the product of two nonzero elements is nonzero, any prime element (in the sense of (∗)) is irreducible.
2. Prove that in Z any irreducible integer is prime in the classical sense (∗∗).
3. Prove that for p ∈ Z, (∗∗) implies (∗).
4. Conclude that (∗) and (∗∗) are equivalent for integers.
