12,999,081 members (49,209 online)
Tip/Trick
alternative version

#### Stats

9.4K views
9 bookmarked
Posted 23 Sep 2014

# The Blum Micali Algorithm and Cryptographically Secure PRNGs (CSPRNGs)

, 23 Sep 2014
 Rate this:
The Blum Micali algorithm provides for a cryptographically secure PRNG (pseudo random number generator).

## 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: Xi+1 = G^Xi % 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).

## Share

 United States
No Biography provided

## You may also be interested in...

 Pro

 First Prev Next
 Primitive root generator Member 115794009-May-15 7:23 Member 11579400 9-May-15 7:23
 Re: Primitive root generator Cryptonite11-May-15 19:11 Cryptonite 11-May-15 19:11
 Value of X sub 1 robertclark017-Jan-15 15:44 robertclark0 17-Jan-15 15:44
 Re: Value of X sub 1 Cryptonite18-Jan-15 8:07 Cryptonite 18-Jan-15 8:07
 Re: Value of X sub 1 robertclark018-Jan-15 9:09 robertclark0 18-Jan-15 9:09
 Re: Value of X sub 1 Cryptonite18-Jan-15 10:11 Cryptonite 18-Jan-15 10:11
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jun-17 22:13 Refresh 1