CS 463/563: Cryptography for Cybersecurity
Fall 2024
Homework #2
Note: Modular arithmetic is fundamental to cryptography. In this system, you can only have integers. For example, in mod 14 system, the answer MUST be 0,1,2,3,…9,11,12,13. Non-integer values have no place in this arithmetic. If you have an answer which is a floating point, such as 12.5, then you are doing something wrong.
Question 1: Modular Arithmetic: Compute the following without a calculator. SHOW YOUR WORK.
i. 150 * 92 mod 14 (Hint: a*b mod c = ((a mod c) * (b mod c)) mod c)
((150 mod 14) * (92 mod 14)) mod 14 ((10) * (8)) mod 14
80 mod 14 = 10
Final answer is 10
ii. 6 * (4/11) mod 14 (Hint: In mod 14 system, a, a+14, a+28, a+42, a+56, etc. are all equivalent)
((6 mod 14) * (4/11 mod 14)) mod 14 ((6) * (4/11 mod 14)) mod 14
11x mod 14 = 4 mod 14 4 mod 14 = 4 (118) mod 14 = 4
((6) * (8)) mod 14 48 mod 14 = 6 Final answer is 6
iii. 24/17 mod 14 (Hint: First, simplify the numerator and denominator separately by applying the mod function independently, and then solve as in (ii) above)
24 mod 14 = 10
17 mod 14 = 3
3 x 5 = 15, and 15 mod 14 = 1
(24/17) mod 14 = (10 x 5) mod 14
50 mod 14 = 8
Final answer is 8
iv. 48 * 512 mod 14 (Hint: Try to compute the exponent in stages, each time simplifying it using the mod function. For example, to compute 48 mod 14, express 48 mod 14 = (42 mod 14)4 mod 14, compute the one in the parenthesis, and repeat this process)
4^8 mod 14
(4^2 mod 14)^4 mod 14
(16 mod 14)^4 mod 14
2^4 mod 14
16 mod 14
2
4^8 mod 14 = 2
5^12 mod 14
(5^2 mod 14)^6 mod 14
(25 mod 14)^6 mod 14
11^6 mod 14
(11^2 mod 14)^3 mod 14
(121 mod 14)^3 mod 14
9^3 mod 14
729 mod 14
1
5^12 mod 14 = 1
((4^8 mod 14)(5^12 mod 14)) mod 14
((2)(1)) mod 14
2 mod 14
2
Final answer is 2
v. 510 * 68 mod 14 (same as above)
5^10 mod 14
(5^2 mod 14)^5 mod 14
(25 mod 14)^5 mod 14
11^5 mod 14
161,051 mod 14
9
5^10 mod 14 = 9
6^8 mod 14
(6^2 mod 14)^4 mod 14
(36 mod 14)^4 mod 14
8^4 mod 14
(8^2 mod 14)^2 mod 14
(64 mod 14)^2 mod 14
8^2 mod 14
64 mod 14
8
6^8 mod 14 = 8
((5^10 mod 14) * (6^8 mod 14)) mod 14
((9) * (8)) mod 14
72 mod 14
2
The final answer is 2
Question 2: SHOW YOUR WORK. You may use EXCEL or a calculator.
i. Show the elements of groups Z13 and Z* (Note that 13 is a prime number)
Z13 = {0,1,2,3,4,5,6,7,8,9,10,11,12}
Z*13 = {1,2,3,4,5,6,7,8,9,10,11,12}
ii. Show the elements of groups Z18 and Z (Note that 18 is NOT a prime number)
Z18 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}
Z*18 = { 1, 5, 7, 11, 13, 17}
iii. Find the order of 5 in Z*13 (Hint: Order of an element in a finite group G is the smallest positive integer k such that ak =1 where 1 is the identity element of G)
5^1 = 5
5^2 = 25 = 12 mod 13
5^3 = 125 = 8 mod 13
5^4 = 625 = 1
iv. Find (if it exists) the multiplicative inverse of 5 ∈ Z13 (integer ring) (Hint: For a ∈ Zn, its multiplicative inverse, if it exists, is defined as a-1 such that a.a-1 ≡ 1 mod n)
5a = 1 mod 13
5a = 1
a= 5a mod 13 =
a=1 5 mod 13 = 5
a=2 10 mod 13 = 10
a=3 15 mod 13 = 2
a=4 20 mod 13 = 7
a=5 25 mod 13 = 12
a=6 30 mod 13 = 4
a=7 35 mod 13 = 9
a=8 40 mod 13 = 1
Final answer is the inverse of 5 is 8 in z13
v. Is Z*13 a cyclic group? If so, what is its order and the generator element? (Hint: group G which contains some element α with maximum order ord(α) = |G| is said to be cyclic. Elements with maximum order are called generators)
Yes Z13 is a cyclic group.
2^2 = 4 mod 13 = 4
2^3 = 8 mod 13 = 8
2^4 = 16 = 3 mod 13 = 3
2^5 = 2*2^4 = 2*3 = 6 mod 13 = 6
2^6 = 2*2^5 = 2*6 = 12 mod 13 = 12
2^7 = 2*2^6 = 2*12 = 24 = 11 mod 13 = 11
2^8 = 2*2^7 = 2*11 = 22 = 9 mod 13 = 9
2^9 = 2*2^8 = 2*9 = 18 = 5 mod 13 = 5
2^10 = 2*2^9 = 2*5 = 10 mod 13 = 10
2^11 = 2*2^10 = 2*10 = 20 = 7 mod 13 = 7
2^12 = 2*2^11 = 2*7 = 14 = 1 mod 13 = 1
12 is the smallest integer such that 2^12 = 1 mod 13 and thus the order of 2 is 12 in the group.
2 is also the element of maximum order and is thus the generator element of this group.