BLOCK CIPHERS

MATH 195

Some other groups that we shall encounter in the following:

• ℤ/2ℤ, with group law + or ⊕ or XOR.

• (ℤ/2ℤ)^{3} = {(a_{1}, a_{2}, a_{3}) : a_{i} ∈ ℤ/2ℤ}. In general, the set (ℤ/nℤ)^{k} is an additive abelian group with respect to componentwise addition modulo n. This has the number of elements #(ℤ/nℤ)^{k} = n^{k}. For example, in (ℤ/2ℤ)^{3} we have (1, 0, 1) + (0, 1, 1) = (1, 1, 0).

Block Cipher

[Block ciphers are discussed in §3.2.]

Say your alphabet has n elements: e.g. n = 2 (bits), n = 26 (letters), n = 10 (digits). The message is a finite sequence of symbols from the alphabet. Since any given message is finite but they can be infinitely long, we pick a positive integer k (e.g. k = 1, 3, 64, 2000), and chop up your message in blocks of length k. For

example, we might have LET|USM|EET|TOM|ORR|OWX.

We then let our plaintext space be P be words of length k on your alphabet: we identify this with P = (ℤ/nℤ)^{k}. Each (plaintext) message is now a finite sequence (X_{1}, X_{2}, …, X_{ℓ}) of elements of P. Encrypt them using the same key K ∈ K, so that C = P. Then Alice sends (E_{K}(X_{1}), …, E_{K}(X_{ℓ})) to Bob, and Bob applies D_{K} to each of the E_{K}(X_{i}) to recover the X_{i}.

As an example, we consider the Vigenère cipher [§2.3]. It has n = 26,

A = 0, B = 1, …, Z = 25,

k = 9, P = C = (ℤ/26ℤ)^{9} = K, and E_{K}(X) = X + K (in the group (ℤ/26ℤ)^{9}). With

K =DISCOVERY= (3, 8, 18, 2, 14, 21, 4, 17, 24),

and

X =WEAREDISC= (22, 4, 0, 17, 4, 3, 8, 18, 2),

we have

E_{K}(X) = (25, 12, 18, 19, 18, 17, 24, 12, 9, 0) = ZMSTSRYMJA.

In this case, D_{K}(X) = X − K.

We can also use stream ciphers. [See §3.2.]

This is some of the material covered January 31, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.