Click here to Skip to main content
12,999,081 members (49,209 online)
Click here to Skip to main content
Add your own
alternative version

Stats

9.4K views
336 downloads
9 bookmarked
Posted 23 Sep 2014

The Blum Micali Algorithm and Cryptographically Secure PRNGs (CSPRNGs)

, 23 Sep 2014
Rate this:
Please Sign up or sign in to vote.
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).

Some Reference Materials

License

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

Share

About the Author

Cryptonite
United States United States
No Biography provided

You may also be interested in...

Pro

Comments and Discussions

 
QuestionPrimitive root generator Pin
Member 115794009-May-15 7:23
memberMember 115794009-May-15 7:23 
AnswerRe: Primitive root generator Pin
Cryptonite11-May-15 19:11
memberCryptonite11-May-15 19:11 
QuestionValue of X sub 1 Pin
robertclark017-Jan-15 15:44
memberrobertclark017-Jan-15 15:44 
AnswerRe: Value of X sub 1 Pin
Cryptonite18-Jan-15 8:07
memberCryptonite18-Jan-15 8:07 
GeneralRe: Value of X sub 1 Pin
robertclark018-Jan-15 9:09
memberrobertclark018-Jan-15 9:09 
GeneralRe: Value of X sub 1 Pin
Cryptonite18-Jan-15 10:11
memberCryptonite18-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.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170622.1 | Last Updated 24 Sep 2014
Article Copyright 2014 by Cryptonite
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid