SIT281 PROBLEM-BASED LEARNING-B ON NUMBER THEORY AND THE RSA CRYPTOSYSTEM

GUILLERMO PINEDA-VILLAVICENCIO

Instructions

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

The assignment has a value of 81 points and is worth 15% of the unit marks. It consists of four problems that are to be solved.

Submission

Students must submit the assignment in clear handwriting or typeset. 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 prob- lems. No marks will be awarded for answers without workings.

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

Note 1: The student is solving the assignment by hand, and then (after that) he/she is verifying the answers of some questions with sagemath. Sagemath code should be provided only when the question asks the student to do so.

Note 2: 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.

Note 3: Only one submission is allowed. Students should submit the assign- ment when they are sure of their answers.

References

• Learning materials of Weeks 3-6 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: x² ≡ 531 (mod 2021) (12 marks).
  • Use the Legendre or Jacobi symbol to determine whether the following con- gruence has a solution: x² ≡ 1097 (mod 65539). Give an answer.

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

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

12+10+2=24 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 student receives between 11 and 0 marks. — Part (b) The student receives 1 mark for each correctly justified step in his/her an- swer, up to ten steps. The final answer is worth 1 mark. For different level of correctness the student receives between 9 and 0 marks. — Part (c) The student receives 1 mark if a correct sagemath code is provided.

• Alice and Bob has designed an RSA algorithm based on n = 152416431947009. Bob chooses the public key e_B = 11. Every exponentiation and square root can be computed with  sagemath;  every  other  operation  must  be  done by hand.
  • Find the private key d_B of Bob so that 0 < d_B. Justify each step.
  • What should Alice do to send the message 123456789 to Bob? What message Bob receives?
  • What should Bob do to decrypt the message he receives from Alice?
  • Verify the answer of Parts (a),(b),(c) in sagemath. (1+1+1 marks)
  • (D grade question) Eve managed to access n and φ(n). She claims she can compute the primes p and q so that n = pq. Is this true? Justify your answer.

6+4+4+3+6=23 marks

Part (a)

The student receives 6 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 2 marks for the value of d_B. For different level of correctness the student receives between 5 and 0 marks.

—

Part (b)

The student receives 3 marks for encrypting the message, and 1 mark for stating the message that Bob receives. For different level of correctness the student receives between 3 and 0 marks.

—

Part (c)

The student receives 3 marks for decrypting the ciphertext, and 1 mark for stating the plaintext that Bob receives. For different level of correctness the student receives between 3 and 0 marks.

—

Part (d)

In each case, the student receives 1 mark if a correct sagemath code is provided.

—

Part (e)

The student receives 6 marks if all the steps of the computation are correct and he/she has quoted the correct theorems and results. For different level of correctness the student receives between 5 and 0 marks.

• (D grade question) This problem investigates the factorisation of large numbers. Every exponentiation and gcd can be computed with sagemath;  every other operation must be done by hand.
  • You are told that 159238479574729 ≡ 529 (mod 38592041). Use this infor- mation to factor 38592041. Justify each step.

(b) You are told that 11^481516095 ≡ 493836216 (mod 3852273587) and 11^963032190 ≡ 1 (mod 3852273587). Use this information to factor 3852273587. 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 5 and 0 marks.

• This question deals with the finite field GF (2⁸), which can be obtained as Z₂[x] (mod  x⁸ + x⁴ + x³ + x + 1).  This is the polynomial the AES cryptosystem uses, but it is not the only polynomial that gives GF (2⁸) (see the last part of this question). In this question, you will learn the extended Euclidean algorithm for polynomials. A brief description of this algorithm is given below.

Compute the following elements of Z₂[x] (mod x⁸ + x⁴ + x³ + x + 1); your

polynomials must be polynomials of degree at most 7.

(a) (x⁶ + x⁵ + x⁴ + x²)(x³ + x + 1). (b) (x⁵ + x² + 1) + (x⁵ + x²)

(c) (x² + x + 1) − (x⁷ + x + 1).

• (x² + x)(x³ + 1)⁻¹ (I could have also written this as (x² + x)/(x³ + 1)). To compute (x³ + 1)⁻¹ in GF (2⁸), we proceed as in the case of integers.

Step 1. First compute the gcd(x³+1, x⁸+x⁴+x³+x+1). Here use the Euclidean algorithm for polynomials. Each step in the Euclidean algorithm is a long division of polynomials with remainder. At every step, just make sure that the remainder has a degree less than that of the divisor.

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

s(x) and t(x) such that

(x³ + 1)s(x) + (x⁸ + x⁴ + x³ + x + 1)t(x) = gcd(x³ + 1, x⁸ + x⁴ + x³ + x + 1).

• GF (2⁸) can also be obtained as Z₂[x] (mod x⁸ + x⁷ + x⁶ + x + 1). Under this new polynomial, compute again Parts (a) and (c).

4+3+3+7+(3+2)=22 marks

Get expert help for SIT281 PROBLEM-BASED LEARNING-B ON NUMBER THEORY AND THE RSA CRYPTOSYSTEM and many more. 24X7 help, plag free solution. Order online now!