EE418- Assignment 1 Solved

1.    [Com] (Modulo Addition, 2 pts x 6 = 12 pts) Please find i) (a + b) (modm) and ii) a (modm), b (modm) and (a (modm) + b (modm)) (modm) for each values of a, b and m given below. You are allowed to use calculators or Python codes provided in the class. However, your answers must include the computaion steps as shown below.

e.g., a = 15, b = 28, and m = 10

Ans: (i) (15 + 28) (mod 10) = 43 (mod 10) = 3 (mod 10)

(ii) 15 (mod 10) + 28 (mod 10) = 5 (mod 10) + 8 (mod 10) = 13 (mod 10) = 3 (mod 10)

(a)    a = 35, b = 256 and m = 10

(b)    a = −300, b = −93 and m = 26

(c)    a = 10496, b = −5899 and m = 256

(d)   a = 771, b = 400375 and m = 1024

(e)    a = −37388, b = 509 and m = 4096

(f)     a = −25678, b = −895632 and m = 33558

2.    [Com] (Modulo Multiplication, 2 pts x 6 = 12 pts) Please find i) (a · b) (mod m) and ii) a (mod m), b (mod m) and (a (mod m) · b (mod m)) (mod m) for each values of a, b and m given below. You are allowed to use calculators or Python codes provided in the class. However, your answers must include the computaion steps as shown below.

e.g., a = 15, b = 28, and m = 10

Ans: (i) (15 · 28) (mod 10) = 420 (mod 10) = 0 (mod 10)

(ii) 15 · 28 (mod 10) = 5 (mod 10) · 8 (mod 10) = 40 (mod 10) = 0 (mod 10)

(a)    a = 432, b = 163 and m = 12

(b)    a = −531, b = −435 and m = 26

(c)    a = −2465, b = 8526 and m = 512

(d)   a = 1024, b = 400375 and m = 2048

(e)    a = −45599, b = 7999 and m = 8192

(f)     a = −4536783, b = −39632 and m = 47384

3.    (GCD and Modulo Inverse) Please answer the following questions.

(a)    [Pro] Please write a Python/MATLAB function to calculate gcd of three integers a, b, and c.

(b)    [Pro] Use the function you developed in part (a) to find the gcd of the following integer values a, b, and c.

•    a = −144, b = 2058, c = 302526

•    a = 3674160, b = −243, c = 51030

•    a = −733, b = −21379, c = 46782

(c)    [Com] (2 pts x 5 = 10 pts) Please find i) (a−1) (mod m) and ii) a (mod m) and

(a (mod m))−1 (mod m) for each values of a and m given below. You are allowed to use calculators or Python codes provided in the class. However, your answers must include the computaion steps as shown below.

e.g., a = 33 and m = 10

Ans: gcd(33,10) = 1. Therefore, 33−1 (mod 10) exists.

(i)    33−1 (mod 10) = 7 (mod 10)

(ii)  (33 (mod 10))−1 (mod 10) = 3−1 (mod 10) = 7 (mod 10)

•    a = 777, and m = 26

•    a = −37, and m = 512

•    a = 24865, and m = 4096

•    a = −256789, and m = 56789

•    a = −1900757, and m = 770077

(d)   [Pro] Find out how much time is taken to calculate inverses in each of the cases in part c). For example if you are using “modulo inverse naive” python function provided in the “Mapping English Alphabet to Integers And Modulo Arithmetic” notebook, you may use the following code to calculate run time.

 

Figure 1: Sample python code for calculating run time associated with “modulo inverse naive” python function provided in the “Mapping English Alphabet to Integers And Modulo Arithmetic” notebook.

(e)    [Com] (5 pts) Do you observe any specific pattern in the run times computed in part d)? If so, briefly explain the reason for your observations in part d.

4.    [Com] (Modulo Arithmetic, 3 pts x 6 = 18 pts) Please find the answers for the following questions using the properties of modulo arithmetic. You are allowed to use calculators or Python codes provided in the class. However, your answers must include the computaion steps as shown below.

e.g., (33−1 · 12 − 142) (mod 10)

Ans: gcd(33,10) = 1. Therefore, 33−1 (mod 10) exists.

(33 (mod 10))−1 · 12 (mod 10) − (14 (mod 10))2 = (3−1 (mod 10)) · (2 (mod 10)) − 42 (mod 10) = (7 (mod 10)) · (2 (mod 10)) − 16 (mod 10) = 14 (mod 10) − 6 (mod 10) = 4 (mod 10) − 6 (mod 10) = −2 (mod 10) = 8 (mod 10).

(a)    (32 · (−71) + 782) (mod 7)

(b)    (−534 · (90 + 4382)) (mod 26)

(c)    ((−543 − 4652) · (−75 + 976)) (mod 256)

(d)   (31132 · (−782)) (mod 2048)

(e)    ((−5)4 · 2153−3) (mod 4096)

(f)     (((−35 · 3) + 7762)−7 · ((−5462)2 − (2161)−1)5) (mod 12235)

5.    (Permutation Cipher)

(a)    [Com] (5 pts) [(a)] Suppose that π is the following permutation of {1,...,8}:

x
1
2
3
4
5
6
7
8
π(x)
4
1
6
2
7
3
8
5
Compute the permutation π−1.

(b)    [Pro] [(b)] Write a Python/MATLAB function for permutation cipher decryption with m = 8. This function will take the ciphertext (y) and permutation key (π(x)) as inputs and output plaintext (x).

(c)    [Pro] [(c)] Decrypt the following ciphertext, for a Permutation Cipher with m = 8, which was encrypted using the key π:

T G E E M N E L N N T D R O E O A A H D O E T C S H A E I R L M

6.    [Pro] (Shift Cipher Decryption) Please answer the following questions.

(a)    Please write a Python/MATLAB function for shift cipher decryption. This function should take the ciphertext (Y ) and shift key (K) as inputs and output plaintext (x).

(b)    Use your function developed in part (a) to decrypt the provided cipher text file “sampleFICT.txt”. Use the shift key, K = 15.

i)             Write the decrypted text to a file name “# $ shift  output.txt”, where “#” and “$” should be replaced with your first name and last name, respectively.

ii)           Print the 30th to 39th ciphertext characters in the file “sampleFICT.txt” and their corresponding plaintext.