Description:
Making a computer or any other electronic device to generate a truly random string of bits is much harder that it might appear. On the other hand, truly random strings of bits are indispensable for secure cryptographic systems. A primary use is to generate secret keys for classical cryptography, and private keys for public key cryptography. A poor random number generator used for this purpose may allow the attacker to optimize his exhaustive key-search attack by trying the most probable keys first. As a result, time necessary to find the correct key may be orders of magnitude shorter as compared to predicted time based on analysis of the algorithm itself. Some today's cryptoalgorithms, such as the American Digital Signature Standard (DSS), require even more random parameters, and predictability of these parameters may impose the same threat to the system security as revealing a secret or a private key. As a result, a number of vendors offer special hardware random-number generators based on various physical phenomena, such as thermal noise from a semiconductor diode, instability of a free-running oscillator, or radioactive decay. In purely software systems, such as public domain PGP or PEM, much simpler sources of randomness must be used. These include: measuring the time between successive keystrokes, mixing unpredictable multi-user system characteristics, etc. Your task is to develop a program that evaluates different random number generators on the basis of standard criteria [2]-[4], and then apply your program to test available software and hardware random number generators.
Literature:
Description:
Creating a pair of corresponding public and private keys for the RSA cryptosystem requires generation of two very large prime numbers. The minimum length of these primes used in today's RSA implementations is 256 bits, which corresponds to numbers in the range 10^75. Due to the fast progress in factorization algorithms used to break RSA, it is currently recommended to use 384, 512, or even 1024-bit primes. It may be therefore surprising, that generating such long primes takes only seconds on a SPARC or PC. This is possible by using fast probabilistic tests for primality. A single iteration of a probabilistic test indicates that either a tested number is a composite (for sure) or it is probably prime (with some probability). Several iterations of this test may decrease the probability of the test witnessing a composite number to be prime to 10^-20, 10^-40, or any other value chosen by the user. Since error probability of 10^-20, is still smaller than odds of winning the top prize in a U.S. state lottery and being killed by lightning in the same day, people usually do not worry about it. Two prime numbers used in the RSA cryptosystem are often required to have special properties that makes factorization of their product more difficult. A method for generating numbers with this properties, so called strong primes, takes only about 20% more time than generation of an arbitrary prime. Your task is to implement and optimize the procedure for generating strong primes using probabilistic Rabin-Miller, Lucas-Lehmer, and Frobenius-Grantham algorithms, and examine time taken by your programs to generate primes of different sizes.
Literature:
Description:
Testing whether a randomly selected number is prime is much easier than factoring (polynomial vs. subexponential complexity). Still, proving (with certainty 1.0) that a given large number is prime, is not easy and efficient enough to be used for generating keys in cryptographic applications. As a result two practical approaches were developed for generating random large prime numbers. First (see project SK-2) is to prove primality of a randomly chosen number with a small error probability acceptable to the user (e.g. 10^-20). Second approach is to construct a random prime number together with a certificate of primality, which gives an absolute certainty that the number is prime. Surprisingly, most efficient algorithms from both groups, probabilistic Miller-Rabin algorithm, and deterministic Maurer algorithm take approximately the same time to execute. Deterministic method developed by Maurer in 1989 is a recursive algorithm. The algorithm is based on the forgotten theorem due to Pocklington published as early as in 1914. The popularity of Maurer's algorithm is growing but still a vast majority of cryptographic products use probabilistic primality testing. Your task is to implement Maurer's method, and examine time taken by your program to generate primes of different sizes.
Literature: