Implementing the Blum-Blum-Shub cryptographic pseudo-random bit
generator in PARI/gp: code, parameters and performance.
Please see:
http://en.wikipedia.org/wiki/Blum_Blum_Shub
for background on the Blum-Blum-Shub cryptographic PRNG.
===================================================================
N.B. The following is intented for the PARI/gp number-theory and
mathematical computations environment.
Objective: Generate seeded BBS crypto-bits using PARI/gp, and
write them to a file for further use.
Steps for Blum-Blum-Shub cryptographic PRNG bits “to file”:
– First, initialization via integer seed.
– Second, we iterate squaring, modulo mmm.
The least significant bit of the standard
representative of the residue class,
an integer in ]0, mmm[ ,
is the crypto-bit at each stage.
N.B. Below, a “double-slash”, “//”, precedes a text comment.
A line beginning with a “?” is input.
A line beginning with a “%” is output.
The ellipsis, “…” is added by the author, yours truely.
? f=Mod(a0,mmm) // Seeding, via the integer seed “a0”.
%261 = Mod(2781584729… , 3007945278… ) // value of “f”, a residue class, modulo ‘mmm’.
? for(Z=1,len, g=f*f; g2=lift(g); g3=Mod(g2,2); g4=lift(g3); if(g4>0, write(bintest01aa, 1));if(g4<1,write(bi
ntest01aa,0)) ;f=g;)
[ time = 1h, 29min, 7,082 ms. ] // timing of computations is ON.
? // No output to screen: output goes to the file “bintest01aa”.
======================================================================
parameters and performance:
? ispseudoprime(q6)
%263 = 1
? ispseudoprime(t45)
%264 = 1
? floor(1+log(q6)/log(2))
%267 = 2048 // q6 is a 2048-bit probable prime.
? floor(1+log(t45)/log(2))
%268 = 2047 // t45 is a 2047-bit probable prime.
? mmm – t45*q6
%269 = 0 // mmm is the product of q6 and t45.
? floor(1+log(mmm)/log(2))
%283 = 4095 // mmm is a 4095-bit composite modulus.
? lift(Mod(q6, 4))
%270 = 3 // q6 is congruent to 3, modulo 4.
? lift(Mod(t45, 4))
%271 = 3 // t45 is congruent to 3, modulo 4.
? len
%272 = 193200000 // number of crypto-bits written to file.
? floor(len/(7.082 + 3600+1740))
%281 = 36131 // THEREFORE, about 36000 crypto-bits per second
// written to file.
====================================================================
Reference to Blum-Blum-Shub generator:
http://en.wikipedia.org/wiki/Blum_Blum_Shub
Notes:
——-
(a)
Since mmm is a/the 4095-bit composite modulus, it is well-beyond
the best publicly known general-purpose factoring algorithms, on the
best publicly known hardware using best-possible implementations, in
any “reasonnable” time-frame (e.g. 2 years, 5 years, etc.).
(b)
The main difficulty I encountered in getting the PARI/gp code for the
one-liner “command” was the “output-to-file” part, in pseudo-code:
if(g4>0)
{
write(bintest01aa, 1);
}
if(g4<1)
{
write(bintest01aa, 0);
}
where the value of g4 is the current “crypto-bit” …
[david@localhost bbshub_PARI_gp]$
[david@localhost bbshub_PARI_gp]$ cat info_Nov15a_draft01a
Implementing the Blum-Blum-Shub cryptographic pseudo-random bit
generator in PARI/gp: code, parameters and performance.
Please see:
http://en.wikipedia.org/wiki/Blum_Blum_Shub
for background on the Blum-Blum-Shub cryptographic PRNG.
===================================================================
N.B. The following is intented for the PARI/gp number-theory and
mathematical computations environment.
Objective: Generate seeded BBS crypto-bits using PARI/gp, and
write them to a file for further use.
Steps for Blum-Blum-Shub cryptographic PRNG bits “to file”:
– First, initialization via integer seed.
– Second, we iterate squaring, modulo mmm.
The least significant bit of the standard
representative of the residue class,
an integer in ]0, mmm[ ,
is the crypto-bit at each stage.
N.B. Below, a “double-slash”, “//”, precedes a text comment.
A line beginning with a “?” is input.
A line beginning with a “%” is output.
The ellipsis, “…” is added by the author, yours truely.
? f=Mod(a0,mmm) // Seeding, via the integer seed “a0”.
%261 = Mod(2781584729… , 3007945278… ) // value of “f”, a residue class, modulo ‘mmm’.
? for(Z=1,len, g=f*f; g2=lift(g); g3=Mod(g2,2); g4=lift(g3); if(g4>0, write(bintest01aa, 1));if(g4<1,write(bintest01aa,0)) ;f=g;)
[ time = 1h, 29min, 7,082 ms. ] // timing of computations is ON.
? // No output to screen: output goes to the file “bintest01aa”.
======================================================================
parameters and performance:
? ispseudoprime(q6)
%263 = 1
? ispseudoprime(t45)
%264 = 1
? floor(1+log(q6)/log(2))
%267 = 2048 // q6 is a 2048-bit probable prime.
? floor(1+log(t45)/log(2))
%268 = 2047 // t45 is a 2047-bit probable prime.
? mmm – t45*q6
%269 = 0 // mmm is the product of q6 and t45.
? floor(1+log(mmm)/log(2))
%283 = 4095 // mmm is a 4095-bit composite modulus.
? lift(Mod(q6, 4))
%270 = 3 // q6 is congruent to 3, modulo 4.
? lift(Mod(t45, 4))
%271 = 3 // t45 is congruent to 3, modulo 4.
? len
%272 = 193200000 // number of crypto-bits written to file.
? floor(len/(7.082 + 3600+1740))
%281 = 36131 // THEREFORE, about 36000 crypto-bits per second
// written to file.
====================================================================
Reference to Blum-Blum-Shub generator:
http://en.wikipedia.org/wiki/Blum_Blum_Shub
Notes:
——-
(a)
Since mmm is a/the 4095-bit composite modulus, it is well-beyond
the best publicly known general-purpose factoring algorithms, on the
best publicly known hardware using best-possible implementations, in
any “reasonnable” time-frame (e.g. 2 years, 5 years, etc.).
(b)
The main difficulty I encountered in getting the PARI/gp code for the
one-liner “command” was the “output-to-file” part, in pseudo-code:
if(g4>0)
{
write(bintest01aa, 1);
}
if(g4<1)
{
write(bintest01aa, 0);
}
where the value of g4 is the current “crypto-bit” …
