## Description

Exercise 1∗

. LFSR generators.

(a) There 6 LFSRs of degree 5 which generate m-sequences with period 31. We associate

a feedback function f(x0, · · · , xn−1) = c0x0 + · · · + cn−1xn−1 with a polynomial f(x) =

x

n + cn−1x

n−1 + · · · + c1x + c0, ci ∈ {0, 1}. These 6 primitive polynomials are given as

follows.

f(x)

x

5 + x

3 + x

2 + x + 1

x

5 + x

4 + x

3 + x + 1

x

5 + x

2 + 1

x

5 + x

4 + x

2 + x + 1

x

5 + x

3 + 1

x

5 + x

4 + x

3 + x

2 + 1

You may pick one of these which is not the one in (b), and generate an m-sequence of

period 31.

(b) Let

a = {ai} = 0000101101010001110111110010011

generated by the primitive polynomial f(x) = x

5 + x

3 + x

2 + x + 1. Thus a is an msequence of period 31. Calculate the 0-1 distribution, the run distribution of the sequence,

and autocorrelation. What is the initial state of the LFSR which generates this sequence?

Sketch the LFSR.

(c) For the LFSR which generates the m-sequence given in (b), if we want to generate a

pseudorandom number of 5 bits, how many different numbers the LFSR could generate?

Exercise 2∗

. Correlation attack. Let a combinatorial generator be given as follows (note

that this design is similar as the example given on slide 6 Lecture 9).

@G. Gong, ECE 458, Computer Security, Spring 2020 2

Suppose it is used as a key stream generator and a 10-bit key is loaded as initial states of

three LFSRs. An attacker obtains the 40 consecutive bits of the outputs of this generator:

s

40 = (1001110111110100101001001001111100001101).

(a) From the Lecture 9, the output is correlated with the first LFSR and the third LFSR. Let

the initial states for the first and third LFSRs be (a0, a1) = (1, 1) and (c0, c1, c2, c3, c4) =

(1, 1, 1, 1, 1). What are their respective outputs of these two LFSRs?

(b) Find the 10-bit key, i.e., the initial state of each LFSR used to generate the key stream

bits using the correlation attack.

(c) Compare the complexity of (c) with the exhaustive search.

(Hint. You should write a small program to compute the correlation.)

Exercise 3. Cipher design.

(a) Explain why IV is needed for both stream cipher and block cipher.

(b) Use a credit card with cryptographic protections for the bank transaction as an example to

explain some consequence of confidentiality or integrity and authenticity of a transaction

is lost when there is no IV and they key is repeated in use for multiple transactions.

Exercise 4. The core nonlinear part of the permutations in AES is the S-box, which is the

8-bit inverse function. Let a simplified AES 4-bit S-box, denoted by E(x) given as follows.

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

E(x) 0 1 9 14 13 11 7 6 15 2 12 5 10 4 3 8

@G. Gong, ECE 458, Computer Security, Spring 2020 3

Let k = 0011 be the symmetric key shared by two communication entities, say Alice and Bob.

(We assume that the right most bit is the least significant bit.) The encryption is defined as

follows:

c = E(k + m)

where the addition is bitwise addition. For example, if the message m = 0101, since k + m =

0011 + 0101 = 0110, look at the table, for input x = 0110 = 2 + 22 = 6, then the cipher text

is given by

c = E(k + m) = E(6) = 7 = 0111.

Find the cipher text for the plaintext m = 110001010 using CBC encryption.

Exercise 5. SHA

(a) What is the size of the output of SHA1, and each case of SHA2?

(b) What are SHA-3’s parameters? What are their respective collision probabilities by a

random guess for SHA1, SHA2 and SHA3?

(c) List SHA1, SHA2 and SHA3’s respective security levels according to the time-memory

trade-off attack.

Exercise 6. Security of public-key systems.

(a) What are their definitions of a one-way function and one-way trapdoor function, respectively? Provide an example to explain those concepts.

(b) Explain how the security of public-key cryptosystems are evaluated.

Exercise 7∗

. DH protocol under authentic channel. In a small fantasy world computing

the discrete logarithm in GF(p) is computational infeasible even for p being an n-bit prime

number when n ≈ 6. So, we could choose the domain parameters (p, g) = (47, 5).

(a) Verify that p = 47 is a 6-bit prime number, and g = 5 is a primitive element in GF(p).

(b) For three users in the system, say, Alice, Bob and Carol, they use Gen to generate their

private keys

xA = 3, xB = 11, xC = 7.

Compute their respective public-keys for each of them.

(c) Compute shared key for each pair of users using the results in (b).

(d) ∗∗ Optional. If you do this correctly, then you will receive one bonus mark.

@G. Gong, ECE 458, Computer Security, Spring 2020 4

(1) If one of three users, say user Alice, has got an attack and the attacker retrieved its

private-key. Explain how the attacker can impersonate the other users.

(2) Identify a scenario in the real world where the above attack could happen and determine the harmful consequence of the attack.

Exercise 8. Bob will use RSA signature scheme to sign messages. Let p = 11, q = 23,

n = pq, hash function h(x) = 2x mod n.

(a) Generate Bob’s private and public key pair.

(b) Bob will sign the message m = 2, generate a digital signature for the message m = 2.

Generate Bob’s signature over m = 2.

(c) Show the verification process of Bob’s signature.

(d) Explain why the timing side-channel attack can be used to recover the secret exponent d

when Bob is generating a signature or decrypting a ciphertext.

Hint. We omit the certificate step here. Since n = 11 × 23 = 253, φ(n) = (p − 1)(q − 1) =

10 × 22=220. For your convenience, here we list the first ten numbers which are coprime with

220, and their inverses modulo 220.

e 3 7 9 13 17 19 21 23 27 29

d = e

−1mod 220 147 63 49 17 13 139 21 67 163 129

Exercise 9 . Solve the following problems for DSS.

(a) What happens if the random number k used in creating DSS signature is compromised?

(b) DSS specifies that if the signature-generation process results in value of s = 0, a new

random number k should be generated and the signature should be recomputed? Why?

(c) What happens if the hash function is not secure in DSS (this means that for a = h(m),

one can easily find another m0

such that a = h(m0

)?