The Blum Micali Algorithm and Cryptographically Secure PRNGs (CSPRNGs)

• Download source - 35.4 KB
• Download results - 12.4 KB

Introduction

The Blum-Micali algorithm is a fascinating and useful way of producing cryptographically safe pseudo random numbers. Why are they cryptographically safe? In order to reproduce the number sequence, you will have to have the original values used when seeding the algorithm. The values in the sequence cannot be reproduced (if the seed values are large enough) without admitting that we have indeed solved the discrete log problem (DLP).

Here is the equation: X_i+1 = G^X_i % P

According to the formula, you must supply a primitive root and use it as a generator (G) over the prime modulus (P). Although it's relatively simple to discover a prime via Rabin-Miller testing, finding a primitive root of that prime group might be difficult if not just plain impossible.

So what do we do now? To get around this, we strategically decide to use a special kind of safe prime. A safe prime is a prime (P) that is also a prime where (P-1)/2. We will use a special safe prime that has either residue 3 or 7 (modulo 8) which has the special property that the primitive root is equal to +2 or -2 over the prime modulus group.

In other words, we need to find a positive integer (P) which satisfies these conditions:

1. P % 8 = 3 or 7
2. P is prime
3. (P - 1) / 2 is prime

Background

I've often wondered about the deterministic nature of PRNGs and whether or not any of them could be used as a symmetric cipher (such as in a one-time pad). It appears that the Blum-Micali algorithm might be able to generate such numbers in a very reproducible manner (supposing that we cannot solve the discrete log problem and providing that the initial seed values are kept secret).

Using the Code

You will need to initialize the RandBlumMicali class with the appropriate seed values. Calling "GetRandomBytes" will return the requested number of bytes.

blummicali = new RandBlumMicali(someValue, safePrime, generator);
var bts = blummicali.GetRandomBytes(200).ToList();

First few values returned when clicking "Generate":

164,151,204,77,83,15,147,154,175,96,130,52,94,190,227,159,12,47,8,19,26,140,226,120,165,71....

Points of Interest

1. It takes a really, really, really long time to generate random values from the given algorithm when using such large integers (in fact, there may be a way of speeding it up using the Chinese Remainder Theorem).
2. The algorithm passed every DIEHARD test (see the blummicali_diehard_results.txt) when using 20 digit primes.
3. This is a deterministic algorithm (as opposed to nondeterministic methods).

Some Reference Materials

• http://en.wikipedia.org/wiki/Safe_prime
• http://en.wikipedia.org/wiki/Primitive_root_modulo_n
• http://en.wikipedia.org/wiki/Blum%E2%80%93Micali_algorithm
• http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
• http://number.subwiki.org/wiki/Safe_prime_has_plus_or_minus_two_as_a_primitive_root