HW1
1.
We consider the ring ℤ4. Construct a table which describes the addition of all elements in the ring with each other:
(1) Construct the multiplication table for ℤ4.
(2) Construct the addition and multiplication tables for ℤ5.
(3) Construct the addition and multiplication tables for ℤ6.
(4) There are elements in ℤ4 and ℤ6 without a multiplicative inverse. Which elements are these? Why does a multiplicative inverse exist for all nonzero elements in ℤ5?
2.
This problem explores the use of a one-time pad version of the Vigenere cipher. In this scheme, the key is a stream of random numbers between 0 and 26. For example, if the key is 3 19 5…, then the first letter of plaintext is encrypted with a shift of 3 letters, the second with a shift of 19 letters, and so on.
a.
Encrypt the plaintext sendmoremoney with the key stream 9 0 1 7 23
15 21 14 11 11 2 8 9.
b.
Using the ciphertext produced in part a, find a key so that the ciphertext
decrypts to the plaintext cashnotneeded.
HW2
Q1
: Why is DES called block cipher? What is the size/length of the block? What
is the effective key length of DES?
Q5
: Multiplication in GF(24): Compute A(x)B(x) mod P(x) in GF(24) using the
irreducible polynomial P(x) = x4 + x + 1.
a) A(x) = x2 + 1, B(x) = x3 + x2 + 1
b) A(x) = x2 + 1, B(x) = x + 1
HW3
3.1
Using the basic form of Euclid’s algorithm, compute the greatest common divisor
of
1. 7469 and 2464
2. 2689 and 4001
3.2
With the Euclidean algorithm we finally have an efficient algorithm for finding the multiplicative inverse in Zm that is much better than exhaustive search. Find the inverses in Zm of the following elements a modulo m:
- a = 7, m = 26 (affine cipher)
- a = 19, m = 999
Note that the inverses must again be elements in Zm and that you can easily verify your answers.
