Review Questions
7.1 What is the difference between statistical randomness and unpredictability?
Get 7.1 exercise solution
7.2 List important design considerations for a stream cipher.
Get 7.2 exercise solution
7.3 Why is it not desirable to reuse a stream cipher key?
Get 7.3 exercise solution
7.4 What primitive operations are used in RC4?
Get 7.4 exercise solution
Problems
7.1
If we take the linear congruential algorithm with an additive component
of 0, Xn+1 = (aXn) mod m Then it can be shown that if m is prime and if
a given value of a produces the maximum period of m - 1, then ak will
also produce the maximum period, provided that k is less than m and that
k and m - 1 are relatively prim
e. Demonstrate this by using X0 = 1 and m = 31 and producing the sequences for ak = 3, 32, 33, and 34.
Get 7.1 exercise solution
7.2
a. What is the maximum period obtainable from the following generator? Xn+1 = (aXn) mod 24
b. What should be the value of a?
c. What restrictions are required on the seed?
Get 7.2 exercise solution
7.3
You may wonder why the modulus m = 231 - 1 was chosen for the linear
congruential method instead of simply 231, because this latter number
can be represented with no additional bits and the mod operation should
be easier to perform. In general, the modulus 2k - 1 is preferable to
2k. Why is this so?
Get 7.3 exercise solution
7.4
With the linear congruential algorithm, a choice of parameters that
provides a full period does not necessarily provide a good
randomization. For example, consider the following two generators: Xn+1 =
(6Xn) mod 13 Xn+1 = (7Xn) mod 13 Write out the two sequences to show
that both are full perio
d. Which one appears more random to you?
Get 7.4 exercise solution
7.5
In any use of pseudorandom numbers, whether for encryption, simulation,
or statistical design, it is dangerous to trust blindly the random
number generator that happens to be available in your computer’s system
library. [PARK88] found that many contemporary textbooks and programming
packages make use of flawed algorithms for pseudorandom number
generation. This exercise will enable you to test your system. The test
is based on a theorem attributed to Ernesto Cesaro (see [KNUT98] for a
proof), which states the following: Given two randomly chosen integers, x
and y, the probability that gcd(x, y) = 1 is 6/p2. Use this theorem in
a program to determine statistically the value of p. The main program
should call three subprograms: the random number generator from the
system library to generate the random integers; a subprogram to
calculate the greatest common divisor of two integers using Euclid’s
Algorithm; and a subprogram that calculates square roots. If these
latter two programs are not available, you will have to write them as
well. The main program should loop through a large number of random
numbers to give an estimate of the aforementioned probability. From
this, it is a simple matter to solve for your estimate of p. If the
result is close to 3.14, congratulations! If not, then the result is
probably low, usually a value of around 2.7. Why would such an inferior
result be obtained?
Get 7.5 exercise solution
7.6
Suppose you have a true random bit generator where each bit in the
generated stream has the same probability of being a 0 or 1 as any other
bit in the stream and that the bits are not correlated; that is the
bits are generated from identical independent distribution. However, the
bit stream is biase
d. The probability of a 1 is 0.5 + 0 and the
probability of a 0 is n, where 0 6 0 6 0.5. A simple deskewing algorithm
is as follows: Examine the bit stream as a sequence of nonoverlapping
pairs. Discard all 00 and 11 pairs. Replace each 01 pair with 0 and each
10 pair with 1.
a. What is the probability of occurrence of each pair in the original sequence?
b. What is the probability of occurrence of 0 and 1 in the modified sequence?
c. What is the expected number of input bits to produce x output bits?
d.
Suppose that the algorithm uses overlapping successive bit pairs
instead of nonoverlapping successive bit pairs. That is, the first
output bit is based on input bits 1 and 2, the second output bit is
based on input bits 2 and 3, and so on. What can you say about the
output bit stream?
Get 7.6 exercise solution
7.7
Another approach to deskewing is to consider the bit stream as a
sequence of nonoverlapping groups of n bits each and output the parity
of each group. That is, if a group contains an odd number of ones, the
output is 1; otherwise the output is 0.
a. Express this operation in terms of a basic Boolean function.
b.
Assume, as in the preceding problem, that the probability of a 1 is 0.5
+ 0. If each group consists of 2 bits, what is the probability of an
output of 1?
c. If each group consists of 4 bits, what is the probability of an output of 1?
d. Generalize the result to find the probability of an output of 1 for input groups of n bits.
Get 7.7 exercise solution
7.8
What RC4 key value will leave S unchanged during initialization? That
is, after the initial permutation of S, the entries of S will be equal
to the values from 0 through 255 in ascending order.
Get 7.8 exercise solution
7.9
RC4 has a secret internal state which is a permutation of all the
possible values of the vector S and the two indices i and j.
a. Using a straightforward scheme to store the internal state, how many bits are used?
b. Suppose we think of it from the point of view of how much information is represented by the stat
e.
In that case, we need to determine how may different states there are,
then take the log to base 2 to find out how many bits of information
this represents. Using this approach, how many bits would be needed to
represent the state?
Get 7.9 exercise solution
7.10
Alice and Bob agree to communicate privately via email using a scheme
based on RC4, but they want to avoid using a new secret key for each
transmission. Alice and Bob privately agree on a 128-bit key k. To
encrypt a message m, consisting of a string of bits, the following
procedure is use
d. 1. Choose a random 80-bit value v 2. Generate the ciphertext c = RC4(v}k) ⊕ m 3. Send the bit string (v}c)
a. Suppose Alice uses this procedure to send a message m to Bo
b. Describe how Bob can recover the message m from (v}c) using k.
b.
If an adversary observes several values (v1}c1), (v2}c2), . . .
transmitted between Alice and Bob, how can he/she determine when the
same key stream has been used to encrypt two messages?
c.
Approximately how many messages can Alice expect to send before the same
key stream will be used twice? Use the result from the birthday paradox
described in Appendix 11A [Equation (11.7)].
d. What does this imply about the lifetime of the key k (i.e., the number of messages that can be encrypted using k)?
Get 7.10 exercise solution
