SIT281 PROBLEM-BASED LEARNING B

Instructions

This is an individual assignment. The aim of the assignment is that the student applies concepts and methods studied in weeks 3-5 to solve problems on number theory, the RSA cryptosystem, and lfsr sequences.

The assignment has a value of 115 points and is worth 20% of the unit marks. It consists of six problems that are to be solved. Question 3 is perhaps more difficult than the others. Thus, Question 3 should be completed after you have completed the other questions.

Submission

Students must submit the assignment in clear handwriting. The solutions should be clear enough so that a fellow student can understand all their steps; and they should demonstrate the student’s understanding of all procedures used to solve the problems. No marks will be awarded for answers without workings.

The assignment is due on Monday 30 August 2021 (Week 7) at 8pm. The student should submit the assignment electronically through the Could unit site by the due date and time.

Only one pdf file must be submitted. You will lose 5% of the marks if you submit a file or files that do not follow this instruction. It is your responsibility to ensure your file is not corrupted and can be read by a standard .pdf viewer. Failure to comply will result in zero marks.

References

Learning materials of Weeks 3-5 of the SIT281 Unit site on CloudDeakin.

Trappe and Washington, Introduction to cryptography with coding theory 3e.

Problems

This question is about quadratic equations.

Solve the quadratic equation: x2 ≡ 534 (mod 1517) (12 marks).

Use the Legendre symbol to determine whether the following congruence has a solution: x2 ≡ 1093 (mod 65537). Give an answer.

Note: You don’t have to solve the quadratic equation, only to determine if it has a solution or not.

Verify the answer of each equation in sagemath. (2+2 marks)

12+10+4=26 marks

Part (a)

The student receives 12 marks if all the steps of the computation are correct and he/she gives an answer. This includes 2 marks for transforming the equation into four systems of linear equations, 2 marks for solving each of the four systems, and 1 mark for giving a final answer. Also, the student gets 1 mark for applying at least once the extended Euclidean algorithm.

For different level of correctness the students receives between 4 and 0 marks.

—

Part (b)

The student receives 1 mark for each correctly justified step in his/her an- swer. The final answer is worth 1 mark.

—

Part (c)

The student receives 2 marks if a correct sagemath code is provided. For different levels of correctness, the student receives between 1 and 0 marks.

Alice and Bob has designed an RSA algorithm based on n = 9797. Bob chooses the public key eB = 17.

Find the private key dB of Bob. Justify each step.

What should Alice do to send the message 1234567890 to Bob? What message Bob receives?

What should Bob do to decrypt the message he received from Alice?

Alice doesn’t know which public key eA and private key dA to choose. She is thinking of eA = 100. Is this a good idea? Give an answer and justify it.

Verify the answer of Parts (a),(b),(c) in sagemath. (2+2+2 marks)

5+10+6+2+6=28 marks

Part (a)

The student receives 5 marks if all the steps of the computation are correct and he/she has quoted the correct theorems and results. This includes 1 mark for the computation of the Euler φ function, 1 mark for the Euclidean algorithm, 1 mark for the extended Euclidean algorithm, and 1 mark for the value of dB. For different level of correctness the students receives between 4 and 0 marks.

—

Part (b)

The student receives 3 marks for correctly breaking the message into smaller messages, 6 marks for encrypting the message, and 1 mark for stating the message that Bob receives. For different level of correctness the students receives between 9 and 0 marks.

—

Part (c)

The student receives 6 marks for decrypting each small message.

—

Part (d)

The student receives 1 mark for a correct answer ( Yes or No), and 1 mark for the justification.

—

Part (e)

In each case, the student receives 2 marks if a correct sagemath code is provided. For different levels of correctness, the student receives between 1 and 0 marks.

Eve wants to break a version of the RSA algorithm designed by Alice, Bob, and Jerry. Alice, Bob, and Jerry have chosen a number n, and two public keys e1 and e2 that are relatively prime. There are also two private keys d1, d2, corresponding to the public keys e1 and e2, respectively. Alice, Bob, and Jerry agree that every message sent to them needs to be encrypted twice, each time with a different public key. That, is, if Tom wants to send a message m to Alice, Bob, and Jerry, then he should send ciphertexts c1 and c2 computed as follows:

c1 ≡ me1 (mod n), c2 ≡ me2 (mod n).

After receiving Tom’s ciphertexts, Alice, Bob, and Jerry made public n, e1, e2, c1, c2.

Eve has announced that she has broken the algorithm of Alice, Bob, and Jerry without knowing the private keys d1 and d2. Guillermo has seen the workings of Eve and has confirmed that Eve is right. Please explain how Eve broke the algorithm. Your solution cannot be based on factoring n; solutions that are based on the factorisation on n won’t be accepted.

(b) For the tuple n = 11021, e1 = 5, e2 = 19, c1 = 3302, and c2 = 9049, Use Eve’s idea to find the message m that Tom sent.

Note: This problem is harder than the other problems, and so you should attempt it after you have completed the other problems.

8+10=18 marks

Part (a)

The student receives 8 marks for a correct general analysis that will work for every tuple n, e1, e2, c1, c2, with each step well justified. For different levels of correctness, the student receives between 7 and 0 marks.

—

Part (b)

The student receive 10 marks for correctly computing the message m. This includes 5 marks for applications of the Euclidean algorithm followed by the extended Euclidean algorithm, and 2 marks for the computation of a relevant inverse, and 2 marks for giving m. For different levels of correctness, the student receives between 9 and 0 marks.

This problem investigates the factorisation of large numbers.

You are told that 71722 ≡ 602 (mod 14351). Use this information to factor 14351. Justify each step.

(b) You are told that 5945 ≡ 1768 (mod 1891) and 51890 ≡ 1 (mod 1891). Use this information to factor 1891. Justify each step.

6+6=12 marks

Part (a)-(b)

For each part, the student receives 6 marks for a correct factorisation of the relevant number, using only the information given in the question. For different levels of correctness, the student receives between 6 and 0 marks.

This question deals with the finite field GF (24). GF (24) is obtained as Z2[x]

(mod x4 + x3 + 1). Note that in some parts, you may need to use long division of

polynomials. And in the the last question, you will learn of the extended Euclidean algorithm for polynomials. A brief description of this algorithm is given below.

Compute the following elements of Z2[x] (mod x4 + x3 + 1).

(a) (x3 + x2 + 1)(x3 + x + 1).

(b) (x2 + 1)(x2 + x)

(e) (x2 + x)(x3 + 1)−1.

For the last part, you need to compute inverses in GF (24). For instance, to compute (x3 + 1)−1, we proceed as in the case of integers.

Step 1. First compute the gcd(x3 + 1, x4 + x3 + 1). Here use the Euclidean algorithm for polynomials. Each step in the Euclidean algorithm is a long division of polynomials with remainder. Just make sure that the remainder has degree less than that of the divisor at every step.

Step 2. As in the case of integers, trace your steps back and find polynomials

s(x) and t(x) such that

(x3 + 1)s(x) + (x4 + x3 + 1)t(x) = gcd(x3 + 1, x4 + x3 + 1).

3+3+3+3+7=19 marks

Part (a)-(d)

For each part, the student receives 3 marks for a correct computation of the part. This requires the correct utilisation of the long division with remainder, when necessary. For different levels of correctness, the student receives between 2 and 0 marks.

—

Part (e)

The student receive 4 marks for correctly applying the Euclidean algorithm and extended Euclidean algorithm to the polynomials x3 + 1 and x4 + x3 + 1. Two extra marks are giving for carrying out appropriate long divisions. The answer for the product (x2 + x)(x3 + 1)−1 is worth 1 mark. For different levels of correctness, the student receives between 6s and 0 marks.

This question explores lfsr sequences.

Consider the sequence starting x1 = 1, x2 = 0, x3 = 1 and defined by the length 3 recurrence

xn+3 ≡ xn + xn+1 + xn+2 (mod 2).

This sequence can also be given by a length 2 recurrence. Determine this length 2 recurrence by setting up and solving the appropriate matrix equa- tions.

Suppose we build an LFSR-type machine that works mod 2. It uses a recur- rence of length 2 of the form

xn+2 ≡ c0xn + c1xn+1 + 1 (mod 2).

to generate the sequence 1, 1, 0, 0, 1, 1, 0, 0. Find c0 and c1.

6+6=12 marks

Part (a)-(b)

For each part, the student receives 6 marks for a correct computation of the part. This includes 2 marks for the correct values of c0 and c1, 1 mark for the final recurrence, and 3 marks for the analysis. For different levels of correctness, the student receives between 5s and 0 marks.

The post 2 SIT281 PROBLEM-BASED LEARNING B 3 Instructions This is an individual assignment. appeared first on PapersSpot.