CSC 580: Cryptography and Security in Computing

A printable PDF is available.

Assignment 2 - Due Wednesday, February 12

This assignment is more straightforward than usual, covers only one chapter, and you only have one week. It will count only half as much as your normal assignments (it will be graded out of 50 points).

  1. Compute the following GCD's using the Euclidean algorithm presented in Section 4.2. Show each step and intermediate result.

    • (a) gcd(21703, 44850)
    • (b) gcd(215258, 71512)

  2. Compute gcd(612, 4931) using the Extended Euclidean algorithm given in Section 4.3. Show each step and intermediate result. Note that for inputs a and b, the Extended Euclidean algorithm finds not only gcd(a,b) but also values x and y so that ax+by=gcd(a,b) -- make sure you clearly mark x and y in your final answer.

  3. Prove that for any positive values a, b, c, and n,

    • (a) (a×b) mod n = [(a mod n)×(b mod n)] mod n
    • (b) (a×b×c) mod n = [(a×b) mod n]×c mod n

  4. For each of the following equations, find an integer x that satisfies the equation.

    • (a) 3x == 4 ( mod 5)
    • (b) 3x == 4 ( mod 7)
    • (c) 9x == 1 ( mod 11)

  5. For the following questions, use polynomial arithmetic over GF(2):

    • (a) What is the product of x7+x6+1 and x4+x3+x2?
    • (b) What are the quotient and remainder when x11+x8+x4+x3+x2 is divided by x8+x4+x3+x+1?
    • (c) What is the product of x7+x6+1 and x4+x3+x2 modulo x8+x4+x3+x+1?

  6. Part (c) in the previous question can be viewed as a field operation over GF(28) -- rewrite that operation and product using the hexadecimal notation described in Section 4.7 (you do not need to rework the calculation -- just re-write the result using hexadecimal notation).

  7. Calculate {16}×{64}, where these values are hexadecimal notation for elements of GF(28) -- use the AES modulus (x8+x4+x3+x+1).