Click here to Skip to main content
15,867,851 members
Articles / Security / Cryptography
Tip/Trick

The Blum Micali Algorithm and Cryptographically Secure PRNGs (CSPRNGs)

Rate me:
Please Sign up or sign in to vote.
5.00/5 (7 votes)
23 Sep 2014CPOL2 min read 23.3K   514   10   6
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.

C#
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionPrimitive root generator Pin
Member 115794009-May-15 7:23
Member 115794009-May-15 7:23 
AnswerRe: Primitive root generator Pin
Cryptonite11-May-15 19:11
Cryptonite11-May-15 19:11 
QuestionValue of X sub 1 Pin
robertclark017-Jan-15 15:44
robertclark017-Jan-15 15:44 
AnswerRe: Value of X sub 1 Pin
Cryptonite18-Jan-15 8:07
Cryptonite18-Jan-15 8:07 
GeneralRe: Value of X sub 1 Pin
robertclark018-Jan-15 9:09
robertclark018-Jan-15 9:09 
GeneralRe: Value of X sub 1 Pin
Cryptonite18-Jan-15 10:11
Cryptonite18-Jan-15 10:11 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.