Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A Blum Blum Shub implementation in JavaScript.
/**
*** blum_blum_shub.js ***
An implementation of the Blum Blum Shub pseudorandom number generator proposed
in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from
Michael O. Rabin's oblivious transfer mapping.
Blum Blum Shub takes the form
2
x = x mod M
n+1 n
where M = pq is the product of two large primes p and q. At each step of the
algorithm, some output is derived from x[n+1]; the output is commonly either
the bit parity of x[n+1] or one or more of the least significant bits of
x[n+1].
The seed x[0] should be an integer that is co-prime to M (i.e. p and q are not
factors of x[0]) and not 1 or 0.
The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees
that each quadratic residue has one square root which is also a quadratic
residue) and gcd(phi(p - 1), phi(q - 1)) should be small (this makes the cycle
length large).
In this implementation, p = 5651 and q = 5623.
This software is licensed under the zlib/libpng license:
Copyright (c) 2016 Andrew Zyabin
This software is provided 'as-is', without any express or implied warranty. In
no event will the authors be held liable for any damages arising from the use
of this software.
Permission is granted to anyone to use this software for any purpose, including
commercial applications, and to alter it and redistribute it freely, subject to
the following restrictions:
1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software in a
product, an acknowledgment in the product documentation would be
appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/
var p = 5651;
var q = 5623;
var M = p * q;
var x = undefined;
/** Get the gcd of two numbers, A and B. */
function gcd(a, b) {
while(a != b) {
if(a > b) {
a = a - b;
} else {
b = b - a;
}
}
return a;
}
/** Seed the random number generator. */
function seed(s) {
if(s == 0) {
throw new Error("The seed x[0] cannot be 0");
} else if(s == 1) {
throw new Error("The seed x[0] cannot be 1");
} else if(gcd(s, M) != 1) {
throw new Error("The seed x[0] must be co-prime to " + M.toString());
} else {
x = s;
return s;
}
}
/** Get next item from the random number generator. */
function next() {
var cachedx = x;
cachedx = cachedx * x;
cachedx = cachedx % M;
x = cachedx;
return x;
}
@seflless
Copy link

seflless commented Jul 24, 2016

@schas002 I'm obsessing with PRNGs this weekend, was looking for a PRNG that is random access, as in:

generator(0) = <random-number>
generator(1) = <random-number>
generator(2) = <random-number>
generator(3) = <random-number>

It seems that this algorithm supposedly is able to be evaluated like that but the math is beyond me. Was wondering if you knew more about how I might translate this to Javascript.

See: https://en.wikipedia.org/wiki/Blum_Blum_Shub:

An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any xi value directly (via Euler's theorem)...

@username1565
Copy link

username1565 commented May 2, 2019

@francoislaberge

<script>
/** Get next item from the random number generator. */
function next() {
	var cachedx = x;
	cachedx = cachedx * x;
	cachedx = cachedx % M;
	x = cachedx;
	return x;
}

//fast modPow
function powmod( base, exp, mod ){
  if (exp == 0) return 1;
  if (exp % 2 == 0){
    return Math.pow( powmod( base, (exp / 2), mod), 2) % mod;
  }
  else {
    return (base * powmod( base, (exp - 1), mod)) % mod;
  }
}

//least common multiple.
function lcm(A)	//A - array with numbers (for example: [57,0,-45,-18,90,447])
{   
    var  n = A.length, a = Math.abs(A[0]);
    for (var i = 1; i < n; i++)
     { var b = Math.abs(A[ i ]), c = a;
       while (a && b){ a > b ? a %= b : b %= a; } 
       a = Math.abs(c*A[ i ])/(a+b);
     }
    return a;
}

function generate(n){	//n-th number from generator, without calculating previous:
	return (powmod( x0, powmod( 2, n, lcm([(p-1), (q-1)]) ), M ));
}

//start generator
p = 7;
q = 19;
M = p * q;	//update M

var x0 = 53;				//p = 7, q = 19, x0 = 53; 	(53, 16, 123, 100, 25...)
x = x0;					//x0 as start nubmer, seed.

var n = 1;	//Just to display n in console
//generate numbers. See this in console.log(F12 button)
console.log(
	'next(4 numbers): '+		//16 123 100 25 ...
	'\n'+(n++)+' = '+next()+
	'\n'+(n++)+' = '+next()+
	'\n'+(n++)+' = '+next()+
	'\n'+(n++)+' = '+next()+
	'\n...'
);

var n = 3;	//show n-th number
console.log(
	//'lcm(p-1, q-1) = ', lcm([(p-1), (q-1)]),	//test lcm = 18, true
	'\n'+n+'-th number = ', generate(n)		//return 25 and this is 4-th number.
);
</script>

@Francois-Laberge-Bose
Copy link

Francois-Laberge-Bose commented May 2, 2019

Awesome, thank you! I'm super busy lately, but would love to get back to try this as soon as I can. Does this have the property that all integers will generate unique random numbers? I'm trying to make sure that is true for all of my algorithms.

@username1565
Copy link

username1565 commented Sep 23, 2020

Oww, @Francois-Laberge-Bose... I did not saw your message. Maybe needed to quote my username, to let me receive email from you.
You wrote:

Awesome, thank you! I'm super busy lately, but would love to get back to try this as soon as I can. Does this have the property that all integers will generate unique random numbers? I'm trying to make sure that is true for all of my algorithms.

I do not know, need to test it.

But I know, that, if you want to get [unique integers] by modulo n, in range [from 0 up to φ(n)-1],
and get it from consecutive numbers [from 0 up to φ(n)-1],
you can use fast modPow-function, and primitive root by modulo n.
φ(n) - means Euler function from n.

Here is described this property (Russian language): http://kaf401.rloc.ru/Criptfiles/primroots.htm
where:
grey values - primitive roots a, by modulo n,
green values - consecutive integers, on input in range [from 0 up to φ(n)-1],
blue values - unique integers in range [from 0 up to φ(n)-1].

@Francois-Laberge-Bose
Copy link

Francois-Laberge-Bose commented Sep 23, 2020

@username1565 No worries. I'm now too busy to try to understand your answer. Will sometime though. Thanks!

@username1565
Copy link

username1565 commented Sep 24, 2020

@Francois-Laberge-Bose, really it's easy to understand, and not so hard.

The formula g ^ N mod p = r, can return a bijective transfromation some value of index N, into result r.

Now, look again, at this simply formula, but in the details:
r = g ^ N mod p,
and here:
p - this is a some prime number,
g - primitive root,
N - some index of Nth r-number,
r - result number.

When p is a prime number, then phi(p) = (p-1), and this value is easy to compute.
So, this formula, can return the transformation of this some value of index - N in range [1, ..., (p-1)],
into some Nth-number r in range [1, ... (p-1)].
This transformation is bijective transformation (as you requested),
and all r-values, are unique values, for each unique N on input.

This formula, seems, like a Blum-Blum-Shub PRNG-algorithm, too, because any value of r, can be extracted directly,
without need to compute all previous values, on PRNG, and then - just skip it all, to extract that N-th r-value.
Computing of power by modulus, can be processed fastly, by using fast modPow (powmod)-algorithm.

This PRNG, like blum-blum-shub algo, have a seed too,
and this is not reversive, because to compute N by r, need to resolve a discrete-logarithm (this is so hard task).
So, this formula seems, like seeded hash-function,
because while g can have a small value, and it can be public,
the value of p, can be a hidden secret value.

Also, g, can be some any primitive root, and
now, think about the number of primitive roots, g by modulo p...
If some value p have at least one primitive root g,
then total number of primitive roots is equal of phi(phi(p)) different primitive roots by modulo p.
While p is a prime number, and phi(p) = (p-1) for prime number,
the value of phi(phi(p)) can be more lesser than phi(p)-value,
because phi(p)/2 can be easy factorized.
But if phi(p)/2 = prime ((p-1)/2 = prime) and this is a prime number too,
then this can not be factorized, and number of primitive roots is a large number, then.
While phi(p) = (p-1), phi(p) can be factorized as 2
(yeap, because (p-1) is even value, such as prime is odd)
and some another prime.
If this some another prime is a big prime nubmer, then number of primitive roots by modulo p is,
maybe, big number too (but I'm not sure, and need to test it... UPD: And after tests, this seems, like (p-1)/2 primitive roots, in this case).

For your free time, you can also see the details, and comments in this source code:
https://github.com/username1565/BigInteger.js/blob/master/Diffie_Hellman_Key_Exchange_BigInteger.html
Onilie version - here:
https://username1565.github.io/BigInteger.js/Diffie_Hellman_Key_Exchange_BigInteger.html

@username1565
Copy link

username1565 commented Nov 28, 2020

@Francois-Laberge-Bose!
This all was been so interested for me, and I did implemented BRAPRNG, and Blum-Blum-Shub-algo here: https://github.com/username1565/BigInteger.js/blob/2b2057db04a32996247f2d1182511b6f2fe82395/BigInteger.js#L2161
in this commit: username1565/BigInteger.js@2b2057d
Also, added RSABigInteger. You can see the source code for your free time.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment