Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / C++
Article

CBBS: A Pseudo Random Number Generator

Rate me:
Please Sign up or sign in to vote.
4.04/5 (9 votes)
13 Jul 20076 min read 57.7K   2.5K   23   7
A C++ class implementation of the pseudorandom number generator Blum Blum Shub (BBS)

Introduction

CBBS is an implementation in C++ (no MFC) of the Blum Blum Shub pseudorandom number generator. Sometimes you may need some random data and having truly strong and unpredictable random data is hard to get. This kind of data cannot be generated by a computer, von Neumann says, "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin." So, why make a pseudorandom generator to get "random" data from arithmetical methods? To be honest, this algorithm does not "generate" random data. Rather, it is intended to expand a small amount of real random data.

You can take real random data from the mouse movements of the user, his key strike delays, some radioactive source connected to your computer or whatever you want. However, you cannot ask the user to type a novel and move his mouse around two hours a day to get enough data for use with a stream cipher and crypt your favourite DVD movie.

Here comes the mighty pseudorandom generator! (Put a good music here to magnify the effect.) So, if you need to generate a large amount of random data, just take a small amount of real random data, pass it to your generator and you get it. The generator uses the data you provide as a seed. Using the same seed X times will generate the same data. Here is the main interest of a pseudorandom generator; you only need to generate a limited amount of real random data.

Some mathematics: the Blum Blum Shub algorithm

The main formula of BBS is: Xn+1 = (Xn)2 mod M

Where M = pq. p and q are two large prime numbers, both congruent to 3 (mod 4). So we need seeds for p and q to calculate M. In addition, we need a seed to make the initial X, called X0. The greatest common divisor from X and M must be 1. One interesting part of this algorithm is that you can take the value of the X of your choice.

Screenshot - CBBS2.png

This formula shows how to get Xi, where i is the number of X starting from X0. The security of BBS is based in the difficulty of computing integer factorization. For each X, we can take a limited amount of bit. This limit is defined by:

log(log(M))

That's enough mathematics for now. If you need more information on BBS, read this.

The class himself

Code dependencies

I've implemented the algorithm as a class, a pure C++ class with no MFC or anything else. However, you will need two libraries to compile the code. You can download the code with precompiled libraries at the top of this article. Here is a description:

  • The GMP library is required to work on big numbers.
  • The MPFR library is used only for the log2() function on big numbers.

For me in production, a big number means a prime of 4096 bit length. (Even more is required if you plan to rule the world.) Needless to say, you can't compute this with C standard functions. GMP is easy and fast. Here are the versions I use:

The demo project

I wrote a very small and brief demo application to demonstrate how to use the class. This project is not cryptographically secure because it generate seeds from *random* data sent by the Windows rand() function. These are really bad numbers, as I say everywhere in my code. Do NOT use the rand() generator in your production application. Generate your seeds with real random data. Here is some output of the demo application:

Initializing the generator... OKK

p is 309 decimal digits length and 1024 bit length
q is 309 decimal digits length and 1024 bit length
M is 617 decimal digits length and 2048 bit length
X is 617 decimal digits length and 2047 bit length
With these numbers we can take a max of 10 bits from each X

A random bit: 0
A random byte: f1
A random int: 4208186245
A random hex string: 3e53d963b9eeee3866918472a2d94431
A random binary data of length: 1024 (not printed obviously)
The random bit was: 0
The last bit at X4208186245 is: 1

Enter a number to get all bits generated from Xn
Just enter 0 to exit

Enter a number: 1
The 10 bits at X1 is: 0111100010
Enter a number: 0
Appuyez sur une touche pour continuer...

Usage of the class

1. Create a new instance

First of all, you need to initialise the class just in case. You can use CBBS or pCBBS. The first is a normal instance and the second is a pointer to the instance of the class.

C++
pCBBS BBS;      // BBS is a pointer to the instance of the class CBBS
BBS = new CBBS; // New instance of CBBS

2. Initialise the pseudorandom number generator

C++
BBS->Init(Seedp, Seedq, Seedx, SEED_LEN); 
    // Provide the seedss

// OR 

BBS->Init(); 
    // Let rand() generate the seeds /!\ONLY FOR TESTING/!\

3. Use it as you wish

Many functions are provided to get the random data in the format you need. Here, I list them all. Each bit is taken from the current X, starting at the least significant bit and going to the most significant bit. When we get the max number of bits, we can take the current X from the application. We can then compute the next X and continue from LSB to MSB. Remember the log(log(M)) rule. GetRndBit() returns a single Boolean value, either true or false. I hesitate to make it return an integer with only 1 bit set for performance reasons, but I think that this function is not very useful, so it has no need to be fast.

C++
bool  GetRndBit(); 
    // A bit, alone, all naked

GetRndByte() returns a byte (8 bits). I used the unsigned char type instead of the unsigned short type. This is because I think it will be more likely be used to generate binary data to be written to a file or sent through a network.

C++
unsigned char GetRndByte(); 
    // A byte, maked by 8 bit

GetRndInt() returns an int. The size of the int depends on the system. Most of the time, this will be 32 bits.

C++
unsigned int GetRndInt(); 
    // An int, depending on int length for the sys (generally 32bit)

GetRndBin(unsigned char *rnd, unsigned long Len) puts some random data into rnd. unsigned char *rnd must be a valid pointer to a string of size Len. unsigned long Len is the length of data that rnd can hold, including the ending zero. Len is given in bytes, so if you want 16 byte random data (128 bits), set Len to 17 for the ending zero.

C++
int  GetRndBin(unsigned char *rnd, unsigned long Len); 
    // Some random binary data

GetRndBinHex(char *rnd, unsigned long Len) is the same function as GetRndBin(), but it returns a hexadecimal string, which is more readable. unsigned char *rnd must be a valid pointer to a string of size Len. unsigned long Len is the length of the data that rnd can hold, including the ending zero. Len is the number of hexadecimal digits that will be printed to rnd. The random binary data will be Len/2. For example: 17 means 16 hexadecimal digits representing 8 bytes or 64 bits. Never forget the ending zero.

C++
int  GetRndBinHex(char *rnd, unsigned long Len);  
    // Random binary data, printed in hex readable format

GetRndBitAt(unsigned long i, int offset = 0) is the cool one. It returns the bit at offset (LSB to MSB) from the Xi. unsigned long i is the number of the X to get the bit from. See the "Some mathematics" section for more details. int offset is the optional offset of the bit as counted from LSB to MSB. offset must be smaller than MaxBit. See GetMaxBit().

C++
bool  GetRndBitAt(unsigned long i, int offset = 0);  
    // Return the bit at offset from Xi

4. Some useless but essential functions

The next four functions return the length of a value in the base you ask. Say that p = 307 = 1 0011 0011. GetpLen(2) will return 9 while GetpLen(10) will return 3.

C++
unsigned long GetpLen(int b);    // The length of p
unsigned long GetqLen(int b);    // The length of q
unsigned long GetMLen(int b);    // The length of M
unsigned long GetXLen(int b);    // The length of X

GetMaxBit() returns the number of bits we can take from an X before computing the next X. Again, remember the log(log(M)) thing.

C++
unsigned long  GetMaxBit(); 
    // Return MaxBit

GetMaxPeriod() is dangerous. It computes the next X until X0 = X. This means that the generator is back to its initial state and it starts to loop. When it does, it returns the number of X needed to accomplish the loop. This is the period of the generator. Dot NOT make this with a number bigger than 16 bits (2 bytes). It will take a LOT of time.

C++
unsigned long  GetMaxPeriod();        
    // Calculate the max period before loop,
    // don't use with numbers bigger than 2 byte.

5. Clean

After usage, you will need to clean it. Don't leave the numbers in memory too long after use.

C++
BBS->Clear();      
    // Clear all the data, zero all values and numbers.

History

  • 13 July, 2007 -- First version, to be improved if some thing constructive is submitted either here or by emailing me.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


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

Comments and Discussions

 
GeneralBlum Micali in C# Pin
Cryptonite25-Sep-14 11:31
Cryptonite25-Sep-14 11:31 
QuestionC# .NET version? Pin
turbine417-Nov-12 16:00
turbine417-Nov-12 16:00 
Thanks for sharing the implementation and article.

After some searching I've not yet been able to find a C# version of Blum Blum Shub. I could probably translate/implement it, but that has its own risks and time-cost, so I figured if I'm asking, others have probably wondered the same.

Cheers.
-T
GeneralGood one. Pin
Karthik_Balaguru22-Jun-09 3:51
Karthik_Balaguru22-Jun-09 3:51 
GeneralFYI: Boost.Random Pin
Stephen Hewitt15-Jul-07 14:15
Stephen Hewitt15-Jul-07 14:15 
GeneralRe: FYI: Boost.Random Pin
Alexandre Ravey15-Jul-07 20:54
Alexandre Ravey15-Jul-07 20:54 
GeneralA small (hopefully constructive) comment [modified] Pin
Garth J Lancaster14-Jul-07 2:17
professionalGarth J Lancaster14-Jul-07 2:17 
GeneralRe: A small (hopefully constructive) comment Pin
Alexandre Ravey15-Jul-07 20:42
Alexandre Ravey15-Jul-07 20:42 

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.