CS 426, Spring, 2008, HW 7 (part I). (HW8 is part II, which is at hw8.html).
Due April 02, 2008, 11:30 PM.
The purpose of this PSO is to experiment with cryptographically secure
random numbers
and pseudo-random number generators. Random numbers are of great
importance in cryptography,
so is of importance to this lab. Partner
with a friend over this project - in order to reduce the load on the
machines.
One turn-in per group of two. Mention your partner's e-mail id and Name in README.
What you need to turnin: The program(s) (preferably, one) for both 1 and 2,
a Makefile, and four plots - two for 1 and 2 for 2. And answers in README.
Experiments to be done on: pod
machines, with linux. If 2^20 does not work with your
implementation, use 2^15.
We would use pseudorandom number generator: Java
1.5 SecureRandom.
Read about (b) from
http://java.sun.com/j2se/1.4.2/docs/api/java/security/SecureRandom.html
and
http://java.sun.com/javase/6/docs/technotes/guides/security/crypto/CryptoSpec.html#SecureRandom.
A random number can be generated by using an object
of SecureRandom and its nextDouble API to generate randoms.
The numbers are in 0 to 1.
For Java SecureRandom, do not set any seed explicitly.
Assignments
1. Use Java (of course) for
SecureRandom. Generate 2^20 (1 million) random numbers.
In order to take care of plotting process: each time after generating 256 numbers, choose one of them as follows. This number becomes the representative number.
For numbers 0 through 255 (or 256 through 511 and so on), choose x = r mod 256; where r is the number at position (0, 256, 512, ...)
beginning that block. Choose the x'th random number in that group. This number would be used for plotting in (a).
(a) Plot the random numbers with X-axis as the index of the random
number -
1 to 2^12.
An index of the i'th random number is i. The Y-axis is the value
of the random number.
(b) For each random number, count the number of 1's and 0's it
has.
Take an average of the number of 1's (number of 0's) for a group
of 2^8 consecutive random numbers generated.
Plot the average number of
1's and average number of 0's for with respect
to the X-axis (the index of the group).
2. Objective is to generate order-preserving random numbers as
follows.
Generate a random number s.
Let r(i) be the i'th random number.
r(1) = s.
for (i=2 to 2^20) {
generate a random number s.
r(i) = r(i-1) + s.
}
Each time 256 numbers are generated in this way, choose one number from them randomly as in (1). Use it for plotting.
(a) Plot the random numbers with X-axis as the index of the
random number -
1 to 2^12.
An index of the i'th random number is i. The Y-axis is the value
of the random number.
(b) For each random number, count the number of 1's and 0's it
has.
Take an average of the number of 1's (number of 0's) for a group
of 2^8 consecutive random numbers generated.
Plot the average number of
1's and average number of 0's for with respect
to the X-axis (the index of the group).
Plot the random numbers with X-axis as the index of the random
number - 1 to 2^20.
An index of the i'th random number is i. The Y-axis is the value
of the random number.
For each random number, count the number of 1's and 0's it has.
Plot the number of 1's and number of 0's for each number with respect
to the X-axis
(the index of the random number).
Plotting is such that: the points are
fit into a curve. There is no need to show each point on the plot
separately.
Turn-ins
Turn in the
plots in "pdf" file. "doc"
or Excel files will be rejected.
The following answers to 3, 4, 5 are to be turned in.
3. Turn in the
program(s) and Makefile.
4. Compare the random-ness between random numbers generated by
1 and 2
(by the same generator); which one is more
random? Turn in an analysis
for Java. Is there another way to generate order preserving random
numbers? Is
that better than 2?
5.
Analyze the degree of random-ness by the count
of 0's and 1's.
If the number of 0's and 1's, is same or around same, then the degree
of randomness is "not bad". Turn in your analysis.