Reference no: EM133022660

SIT281 PROBLEM-BASED LEARNING-A ON NUMBER THEORY AND CLASSICAL CRYPTOSYSTEMS

GUILLERMO PINEDA-VILLAVICENCIO

PrOBLEMS
(1) Consider the pairs (54321, 50) and (1739, 29341).
(a) Compute the greatest common divisor (gcd) of each pair using the Euclidean algorithm.
(b) For each pair (a, b) in the question, use the extended Euclidean algorithm to find integers x and y such that ax + by = gcd(a, b)
(c) Verify the answer of each gcd and each use of the extended Euclidean algo- rithm equation in sagemath. This means writing sagemath code to answer each question.

(2) Consider the following problems in modular arithmetic. Justify every step in your solution.
(a) Evaluate the modular powers 217219 (mod 344) and 310003 (mod 101).
(b) Solve each of the following modular equations for x: (i) 342x + 448 ≡ 73 (mod 1003),
(ii) 35x ≡ 1 (mod 81).
The order of operations for modular arithmetic is the same as that of ordinary arithmetic; that is, the multiplication before addition.
(c) Verify the answer of each modular power and each equation in sagemath. This means writing sagemath code to answer each question.

(3) Use the Chinese remainder theorem to solve the following systems of equations.
(a) x ≡ 34 (mod 100) and x ≡ -1 (mod 51).
(b) 3x ≡ 8 (mod 10) and 2x + 4 ≡ 9 (mod 111).
(c) Verify the answer of each system in sagemath. This means writing sagemath code to answer each system.

(4) This questions deals with affine ciphers and shift ciphers. The alphabet is consid- ered modulo 26; that is, A=0,...,Z=25.
(a) The following ciphertext has been encrypted with a shift cipher with encryp- tion key (shift) 3 or 16:
c1=IUBBOEKHSQHVEHJUDJXEKIQDTTEBBQHI.
This means that from the plaintext we use the key 3 or 16 to obtain c1. Decrypt c1. Here you need to use both keys and give the message that makes more sense.
(b) Using an affine cipher c = 11p + 17 where p is the plaintext, encrypt the plaintext:
p=(STUDENT FIRST NAME), MEET ME AT THE NATIONAL GALLERY.
For instance, in my case, the plaintext reads

(i) Give the ciphertext c for the plaintext p (5 marks).
(ii) Show manually how to decrypt the affine cipher c (6 marks). This includes computing the function p = (c - 17) ∗ 11-1 (mod 26).
(iii) With the function you constructed in (ii), decrypt the ciphertext NWVASPFWRAQVRSYJRXBE
.
(c) Verify the answer of each question in sagemath. This means writing sagemath code to decrypt c1 in Part (a), to encrypt the plaintext of Part (b)-(i), and to decrypt the ciphertext of Part (b)-(ii).

Attachment:- Problem-based-learning.rar