Part - Problem Solving Questions

Q1) Affine Cipher

(a) You are given a plaintext: "exam", encrypt it using the affine function 5 x + 2 (mod26). (b)Work out the decryption formula and use it to decrypt the ciphertext obtained from Part (a). (c)Explain why the affine function 13x + 2 (mod 26) cannot be used for encryption.

Q2) Hill Cipher

(a) You have found out that the exam is easy, and wanted to tell your friends. Encrypt the plaintext "easy" using the matrix M =

(b) What is the decryption matrix M^-1?

Q3) LFSR
Consider the linear recursion relation x_n+2 = c₀x_n+1 + c₁x_n + c₂ ( mod 2) that generates the sequence: 0, 1, 1, 0, 1, . . .

(a) Find the value of the coefficients c₀, c₁, and c₂.

(b) Find the next 3 elements of the sequence, and determine the period of the recursion relation.

Q4) Extended Euclidean Algorithm

Apply the Extended Euclidean Algorithm to:

(a) find the value of gcd(242 , 129); and
(b) solve 242 x + 129y = gcd(242, 129) for integers x and y.

Q5) Chinese Remainder Theorem and Euler's Theorem

(a) Given that x = 5 (mod 13) and x ≡ 7 (mod 11), solve for x by hand using the Chinese Remainder Theorem.

(b) Now use Maple to solve for x, if x = 1 (mod 19) and x ≡ 17 (mod 31)

(c) The Euler's Theorem states that: If gcd( a, n) = 1, then a^φ(n) ≡ 1 mod n. Use it to find, by hand, the value of:

11⁷²² mod 225.

Q6. Modulus Arithmetic

(i) Express 113 in binary, using the method for base conversion you have learned in SIT192.

(ii) Hence express 3¹¹³ as a product of powers of 3 from the set (3¹, 3², 3⁴, 3⁸, 3¹⁶, 3³², 3⁶⁴).

(iii) Determine each of 3¹, 3², 3⁴, 3⁸, 3¹⁶, 3³², 3⁶⁴( mod 217), using only the +, -, ×, ÷ functions on a calculator. Show all intermediate steps.

(iv) Hence determine 3¹¹³( mod 217), again using only the +, -, ×, ÷ functions on a calculator. Show all intermediate steps.

(v) Confirm your final answer using Wolfram Alpha. Show your query given to Wolfram Alpha.