1. Caesar Substitution Cipher. Recall that a Caesar shift cipher identifies (A, B,... , Z) with Z₂₆ = (00, 011 ... 25) and enciphers using a shift x → (x + k) mod 26 for some private key k. Knowing this, decipher

HSS PZ MHPY PU SVCL DHY HUK JYFWAVNYHWOF

2. RSA Cryptosystem. An RSA cryptosystem has public key (1050958331,1019). It enciphers text in 3-character (9-digit) blocks, with each text character identified with its 3-digit ASCII code (see pg 3 of our handout Common Alphabetic Substitution Codes). For example, the 3-character plaintext string "Abz" is identified with the 9-digit string 065098122 of ciphertext, which is then enciphered using the RSA public key.

You intercept the message 652557294 075733184 encrypted with this public key. Can you decipher it?

(Hint: This problem will require some computer calculations. WolframAlpha has a "Phi(n)" function, and the modular arithmetic calculator site given on Assignment 4 can also be used.)

3. Suppose C ⊆ F_q⁽ⁿ⁾ is a linear code of length n over Fq. The automorphism group of the code C is

Aut(C) = {g E G L(n, q) : gC = C}.

(a) Prove that Aut(C) is a group.

(b) Find the automorphism group of the repetition code {000,111} of length 3 over F₂.

4. Recall that the nonlinear S-boxes in AES make use of a natural bijection between the field F28 and the group algebra F2 C8 which has no algebraic realization.

(a) Prove that F₂C₈ is not a field.

(b) How much can be said about the algebraic structure of F₂C₈ using the CRT for polynomials?

5. A cyclic linear code of length 6 over F₅ has generator polynomial g(x) = x³ + 2x² + 2x + 1. Text characters are encoded using the base 5 representation of their standard ASCII decimal number. For example B = 66 = 231 base 5 is identified with the message m(x) = 2x² + 3x + 1, then encoded as g(x)m(x).

Suppose you receive the two character message

2x⁵ + 3x⁴ + x² + 3, 2x⁴ + 2x³ + 3x² + 4x + 4.

(a) Show that the first character in the received message is most likely error-free, and decode it.

(b) Show that the second character of the received message contains errors. Find the most likely error, decode it, and obtain the 2-character message.

6. One technique for creating regular LDPC codes is to use the incidence matrix of the Cayley graph of a group G with a relatively small generating set of involutions S. Vertices are the elements of the group, and there is an edge between x and y if x = ys for some s ∈ S.

(a) Recall that the dihedral group D₁₀ is generated by two involutions a, b satisfying a² = b² = e and (ab)⁵ = a Draw the Cayley graph associated with (D₁₀, {a, b}). Find the 5 x 10 parity check matrix H for the LDPC code associated with this graph.

(b) In the LDPC code associated with the Cayley graph (D₁₀, {a, b}), the message nodes are, f₁, ....... f₅ where f_i = (ab)ⁱ, i = 1,......5, and the check nodes are c_i = f_i,a i = 1,.......5. For a message to be valid, the value of each message node should be the sum modulo 2 of the values at the check nodes that are connected to it.

In the LDPC decoding algorithm, the values of message nodes and check nodes are passed back and forth and adjusted to the most likely state at each stage. First the values of the h's are used to determine a list of likely values for each of their check nodes, then check nodes are adjusted to their most likely value, and then the new values of these ci's are used to adjust the values of the fi's.

If the received values are f₁f₂f₃f₄f₅c₁c₂c₃c₄c₅ = 0101100110, find the most likely actual message after one pass back and forth through the LDPC graph decoding algorithm. Use the parity check matrix to verify that this is a code-word.

7. Reed-Solomon Code. An RS-(7,3,5) code has length 7 and dimension 3 over F₂³ = F₂(ζ), where (ζ³ = ζ + 1. The code has designated distance 5, so the generating polynomial is g(x) (x + ζ) (x + ζ²) (x + ζ³)(x + ζ⁴) F23 [x]. 8-bit hexadecimal ASCII symbols are first encoded as 9-bit strings by adding a check digit:

For example: N = 4E in 8-digit ASCII becomes 010011100 as a 9-bit string, which is represented as the message polynomial m(x) = (x2+((+1)x-F(2. It is desirable in transmission that the first part of the transmitted message contains the actual message. The first three blocks of the transmitted message is x4m(x), and the last four blocks are the remainder r(x) of x4m(x) divided by g(x).

Calculate the transmitted message c(x) = x⁴m(x) + r(x) that would be associated with the plaintext symbol ± = B1 in extended ASCII, and write this as a 21-bit binary string.

8. RS decoding. In the RS-(7,3,5) code of exercise 7, the 21-bit string 001010100111000001011 is received. Determine the most likely intended plain-text message symbol. How many bit errors occurred? How many symbol errors?