1. Caesar Substitution Cipher. Recall that a Caesar shift cipher identifies (A, B, ... , Z) with Z26 = (00, 01, . . , 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 Cryptosystent. 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. 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?
3. Suppose C ⊆ Fq(n) is a linear code of length n over Fq. The automorphism group of the code C is
Aut(C) = {g ∈ GL(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 F2.
4. Recall that the nonlinear S-boxes in AES make use of a natural bijection between the field F28 and the group algebra F2C8 which has no algebraic realization.
(a) Prove that F2C8 is not a field.
(b) How much can be said about the algebraic structure of F2C8 using the CRT for polynomials?
5. A cyclic linear code of length 6 over F5 has generator polynomial g(x) = x3 + 2x2 + 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) = 2x2 + 3x + 1, then encoded as g(x)m(x).
Suppose you receive the two character message
2x5 + 3x4 + x2 + 3, 2x4 + 2x3 + 3x2 + 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 D10 is generated by two involutions a, b satisfying a2 = b2 = e and (ab)5 = e. Draw the Cayley graph associated with (D10, {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 (D10, {a, b}), the message nodes are f1, ..., f5 where fi = (ab)i, i =1, ... , 5, and the check nodes are ci = fia,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 L'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 f1f2f3f4f5c1c2c3c4c5 = 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 F23 = F2(ζ), where ζ3 = ζ + 1. The code has designated distance 5, so the generating polynomial is g(x) = (x + ζ)(x + ζ2)(x + ζ3)(x + ζ4) ∈ 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+ζ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) = x4m(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?