meditationatae

Just another WordPress.com site

Implementing the Blum-Blum-Shub cryptographic pseudo-random bit generator in PARI/gp

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” …

Advertisements

Written by meditationatae

November 17, 2013 at 5:10 pm

Posted in History

Tagged with ,

%d bloggers like this: