CS 426, Spring, 2008, HW 8 (part II). (HW7 is part I, which is at hw7.html).
Due April 14, 2008, 5: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 the following pseudorandom number generators: /dev/urandom in linux
Read about (a) from http://en.wikipedia.org/wiki/Urandom and references
if interested more.
A random number can be generated by reading /dev/urandom. Read 64 bits (8 bytes) from
urandom.
Assignments
1. Use C. Generate 2^20 (1 million) random
numbers.
In order to take care of plotting process: each time after generating 256 number
s, 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 bl
ock. 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 (these many numbers are chosen through random sampling as above).
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.
First find a mechanism about how to add two 64-bit numbers: (using double in gcc?)
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^20.
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).
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, 6 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 a different analysis for urandom. 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.
6. Compare the degree of random-ness between urandom and Java
(in HW7) by the count
of 0's and 1's. Turn in your analysis.
Which one would you choose for random generation - urandom or Java?