Project Management Professional Practice Quiz 1. This practice quiz contains 20 questions, provided by Whizlabs Software. Which of the following is a tool used to secure expert ... A. Drop the alternative approach. B. Work out a mitigation plan. C. P
The greatest of richness is the richness of the soul. Prophet Muhammad (Peace be upon him)
Idea Transcript
Introduction to Cryptography
Practice Questions for Quiz 1
Problem 1 (9 points) For each term below, give (i) a brief definition and (ii) a small example. (a) chosen plaintext attack (b) greatest common divisor (c) Euler’s ϕ function Problem 2 (6 points) ∗ . Evaluate the following to obtain a element of Z11 (a) (7 × 6) mod 11 (b) (7−1 × 6) mod 11 (c) (1043210 ) mod 11 Problem 3 (5 points) Notice that the bottom row of the ×11 table is the reverse of the top. Use a bit of algebra to prove: For each n ≥ 2, the bottom row of the ×n table is the reverse of the top row (i.e., that the bottom row’s i-th entry is n − i).
Math Facts Fermat’s Little Lemma (FLL). If p is prime & gcd( a, p) = 1, then a p−1 ≡ 1 (mod p). Euler’s Theorem. If n > 1 & gcd( a, n) = 1, then a ϕ(n) ≡ 1 (mod n). ∗ The multiplication table for Z11
×11 1 2 3 4 5 6 7 8 9 10
Page 1
1 1 2 3 4 5 6 7 8 9 10
2 2 4 6 8 10 1 3 5 7 9
3 3 6 9 1 4 7 10 2 5 8
4 4 8 1 5 9 2 6 10 3 7
5 5 10 4 9 3 8 2 7 1 6
6 6 1 7 2 8 3 9 4 10 5
7 7 3 10 6 2 9 5 1 8 4
8 8 5 2 10 7 4 1 9 6 3
9 9 7 5 3 1 10 8 6 4 2
10 10 9 8 7 6 5 4 3 2 1
September 20, 2017
Introduction to Cryptography
Practice Questions for Quiz 1
Answers for Problem 1 (a) Def: The attacker chooses what plaintext is to be encrypted. Ex: Suppose the cipher used a a cyclic shift. If the attacker chooses ”a” as the plaintext, he can read of the shift from the ciphertext. (b) Def: gcd( a, b) = the largest natural number dividing both a and b. Ex: gcd(20, 35) = 5. (c) Def: ϕ(n) = Card({ k ∈ Zn | gcd(k, n) = 1 }). Ex: ϕ(5) = 4. Answers for Problem 2 (a) By the ×11 table, 7 ×13 6 = 9. (b) By the ×11 table, 7 ×11 8 = 1.
So: 7−1 ×11 6 = 8 ×13 6 = 4.
∗ . (c) By FLL, k10 (mod 11) ≡ 1 for all k ∈ Z11
So:
1043210 ≡ 104321·10 ≡ (1010 )4321 ≡ (1)4321 ≡ 1 (mod 11). Answer for Problem 3 The number in the i-column of the bottom row is (n − 1) · i (mod n). So:
( n − 1) · i = n · i − i ∼ = −i (mod n) ∼ = n − i (mod n).