# ECE 458 Assignment 2: Exercises for Topic 2 solution

\$30.00

Original Work
Category:

## 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
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
)?