Cryptography and Computer Security - Exercise 4
Subject: RC4 + Modular Arithmetic
Submission deadline: 15/12/2010

Questions

1. A "resolving" IV combination is one that, after 3 swaps of the KSA, puts the RC4 S array into a state in which: (a) S[1] < 3 and (b) S[1] + S[S[1]] = 3. In class we saw that IVs of the form (3, 255, x) are resolving. Find a resolving IV that starts with the decimal number made from the last 2 digits of your 9-digit ID number.

2. Consider the field GF(2⁸) of polynmials with degree 0$\le$d$\le$7 over $\mathbb {Z}$₂, modulo the irreducible polynomial f (x) = x⁸ + x⁴ + x³ + x + 1. Each polynomial is specified by 8 bits (its coefficients), which we represent by 2 hex digits. E.g., the polynomial x⁷ + x⁵ + x is represented by the hex number `a2'. Let z(x) be the polynomial represented by the last 2 digits of your 9-digit ID treated as hex digits (e.g., if your ID number ends with `45' then your z(x) = x⁶ + x² + 1). Using the extended Euclid algorithm, compute z^-1(x), i.e., find a(x) such that a(x)z(x) = 1(mod f (x)).

Submission instructions

1. Send your results via email to crypto-netsec@eng.tau.ac.il.
2. The subject should be: ex4. Do NOT put a dash ("-") between the "x" and the "4" as it confuses the mailer.
3. The body of the email should contain 4 lines, including the leading keywords and the ":=" symbols:

      TZ  := your "Teudat Zehut" number (9 digits)
      Q1  := resolving IV as 3 comma-separated decimal numbers, e.g., 45,127,200
      Q2  := the polynomial a(x) as 2 hex digits, e.g., a3
   

4. Send plain ASCII email. In particular:
   1. No attachments
   2. No HTML email
   3. Be extra careful with Microsoft mailers which by default send the text encapsulated in an attachment called "winmail.dat".
   4. When in doubt, use a Unix text-based mailer like "mail" or "pine".