Last active
April 2, 2021 10:06
-
-
Save schas002/757c0b948b469cd591c24f27eb16edf0 to your computer and use it in GitHub Desktop.
A Blum Blum Shub implementation in JavaScript.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
*** 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; | |
} |
@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
@Francois-Laberge-Bose, really it's easy to understand, and not so hard.
The formula
g ^ N mod p = r
, can return abijective transfromation
some value of indexN
, into resultr
.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, thenphi(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 uniqueN
on input.This formula, seems, like a
Blum-Blum-Shub PRNG-algorithm
, too, because any value ofr
, can be extracted directly,without need to compute all previous values, on
PRNG
, and then - justskip
it all, to extract thatN-th r-value
.Computing of power by modulus, can be processed fastly, by using fast
modPow (powmod)
-algorithm.This
PRNG
, likeblum-blum-shub algo
, have aseed
too,and this is not reversive, because to compute
N
byr
, need to resolve adiscrete-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, andnow, think about the
number of primitive roots
,g
by modulop
...If some value
p
have at least one primitive rootg
,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 thanphi(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 as2
(yeap, because
(p-1)
is even value, such as prime is odd)and
some another prime
.If this
some another prime
is abig prime nubmer
, then number of primitive roots by modulop
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