Solved–Assignment 3– Solution

Description

Problem 1 (Functions and matrices) [30 marks] Consider the set of or-dered pairs (x; y) where x are y are real numbers. Such a pair can be seen as a point in the plane equipped with Cartesian coordinates (x; y).
1. For each of the following functions F1; F2; F3; F4, determine a (2 2)-matrix A so that the point of coordinates (x y) is sent to the point (x0 y0 ) when we have
x0 = A x (1)
y0 y
where A = c d (2)
a b
(a) F1(x; y) = (2y; 3x)
(b) F2 (x; y) = (0; 0)
(c) F3 (x; y) = (y; y)
(d) F4 (x; y) = (y + x; y x)
2. Determine which of the above functions F1; F2; F3; F4 is injective? sur-jective? Justify your answer.

Problem 2 (Chinese Remaindering Theorem) [20 marks] Let m and n be two relatively prime integers. Let s; t 2 Z be such that s m + t n = 1. The Chinese Remaindering Theorem states that for every a; b 2 Z there exists c 2 Z such that
( x 2 Z ) x a mod m () x c mod m n(3)
8 x b mod n

where a convenient c is given by

c = a + (b a) s m = b + (a b)t n (4)

1. Prove that the above c satis es both c a mod m and c b mod n.

2. Let x 2 Z. Prove that if x c mod m n holds then x a mod m and x b mod n both hold as well.

3. Let x 2 Z. Prove that if both x a mod m and x b mod n hold then so does x c mod m n.

1

Problem 3 (Solving congruences) [30 marks]

1. Find all integers x such that 0 x < 77 and 5x + 9 = 10 mod 77. Justify your answer.

2. Find all integers x such that 0 x < 77, x 2 mod 7 and x 3 mod 11. Justify your answer.

3. Find all integers x and y such that 0 x < 77, 0 y < 77, x + y = 33 mod 77 and x y = 10 mod 77. Justify your answer.

Problem 4 (RSA) [20 marks] Let us consider an RSA Public Key Crypto System. Alice selects 2 prime numbers: p = 5 and q = 11. Alice selects her public exponent e = 3 and sends it to Bob. Bob wants to send the message M = 4 to Alice.

1. Compute the product n = p q and (n)

2. Is this choice for of e valid here?

3. Compute d , the private exponent of Alice.

4. Encrypt the plain-text M using Alice public exponent. What is the resulting cipher-text C?

5. Verify that Alice can obtain M from C, using her private decryption exponent.

2