13,003,589 members (62,107 online)
alternative version

#### Stats

41.9K views
22 bookmarked
Posted 13 Jul 2007

# CBBS: A Pseudo Random Number Generator

, 13 Jul 2007
 Rate this:
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:

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.

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:

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

```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

```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.

```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.

```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.

```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.

```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.

```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()`.

```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.

```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.

```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.

```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.

```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.

A list of licenses authors might use can be found here

## Share

 Web Developer Switzerland
No Biography provided

## You may also be interested in...

 Pro

 First Prev Next
 Blum Micali in C# Cryptonite25-Sep-14 11:31 Cryptonite 25-Sep-14 11:31
 C# .NET version? turbine417-Nov-12 16:00 turbine4 17-Nov-12 16:00
 Good one. Karthik_Balaguru22-Jun-09 3:51 Karthik_Balaguru 22-Jun-09 3:51
 FYI: Boost.Random Stephen Hewitt15-Jul-07 14:15 Stephen Hewitt 15-Jul-07 14:15
 A collection of random number generators can be found here http://www.boost.org/libs/random/[^] Steve
 Re: FYI: Boost.Random Alexandre Ravey15-Jul-07 20:54 Alexandre Ravey 15-Jul-07 20:54
 A small (hopefully constructive) comment [modified] Garth J Lancaster14-Jul-07 2:17 Garth J Lancaster 14-Jul-07 2:17
 Re: A small (hopefully constructive) comment Alexandre Ravey15-Jul-07 20:42 Alexandre Ravey 15-Jul-07 20:42
 Last Visit: 31-Dec-99 18:00     Last Update: 27-Jun-17 4:48 Refresh 1