Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Very Slow Random Number Generation using dev/urandom on Mac OS 10.8

I am writing a program that uses Paillier Cryptosystem to encrypt a matrix. To encrypt a 50 x 50 matrix it takes about 12 seconds! That's painfully long considering I intend to encrypt matrices of sizes 5000 x 5000 and above. Profiling the program on Xcode I figured out that this paillier_get_rand_devurandom() is the culprit.

This is the call trace snapshot :

enter image description here

Here's the source code of this particular Paillier C library function

    void paillier_get_rand_devurandom( void* buf, int len )
    {
          paillier_get_rand_file(buf, len, "/dev/urandom");
    }  


    void paillier_get_rand_file( void* buf, int len, char* file )
   {
         FILE* fp;
         void* p;

         fp = fopen(file, "r");

         p = buf;
         while( len )
         {
             size_t s;
             s = fread(p, 1, len, fp);
             p += s;
             len -= s;
         }

        fclose(fp);
    }

And in case,

    <http://www.en.wikipedia.org/wiki/Paillier_cryptosystem>
    Paillier Cryptosytem C library : <http://acsc.cs.utexas.edu/libpaillier/> 

I have read that random number generation using dev/random is slow whereas with dev/urandom its much faster. In my case both are equally slow. Can this random number generation be made faster?

EDIT: Here's an example

    #include <stdio.h>
    #include <stdlib.h>
    #include <gmp.h>
    #include<paillier.h>


   int main(void)
   {

       paillier_pubkey_t* pub;//The public key
   paillier_prvkey_t* prv;//The private key 


       paillier_keygen(1024, &pub, &prv,paillier_get_rand_devurandom);


      paillier_ciphertext_t* ca;
      paillier_ciphertext_t* cb;
      paillier_ciphertext_t* res;


      paillier_plaintext_t* a;
      paillier_plaintext_t* b;
      paillier_plaintext_t* sum;



     a=paillier_plaintext_from_ui(45);
     b=paillier_plaintext_from_ui(100);


     //This is the encryption function 
     ca=paillier_enc(0, pub, a, paillier_get_rand_devurandom);
     cb=paillier_enc(0, pub, b, paillier_get_rand_devurandom);


     res=paillier_create_enc_zero();


     paillier_mul(pub, res,ca, cb);

     sum=paillier_dec(0, pub, prv, res);


     gmp_printf("The sum is : %Zd\n",sum);


     return 0;

   }

And this is the encryption function signature

    /*
Encrypt the given plaintext with the given public key using
randomness from get_rand for blinding. If res is not null, its
contents will be overwritten with the result. Otherwise, a new
paillier_ciphertext_t will be allocated and returned.
    */
    paillier_ciphertext_t* paillier_enc( paillier_ciphertext_t* res,
                                           paillier_pubkey_t* pub,
                        paillier_plaintext_t* pt,
                         paillier_get_rand_t get_rand );

Sorry this question is only getting longer

 The actual scale_encrypt_T()

 void scale_encrypt_T(char *scaledTfile)
{
    ...
    ...

//Printing scaled and then encrypted T[][] in a file 
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {
        void *buf2;

        //T[][] is the 50 x 50 matrix 
        temp=(int)(T[i][j]*pow(10,6));  //Scale factor q = 10 to the power of 6

        p0=paillier_plaintext_from_ui(temp);

        //c0 is the cipher text
         /***So this is where its taking so long***/
        c0=paillier_enc(0, pub, p0, paillier_get_rand_devurandom);


        buf2=paillier_ciphertext_to_bytes(PAILLIER_BITS_TO_BYTES(pub->bits)*2, c0);

        fwrite(buf2, 1, PAILLIER_BITS_TO_BYTES(pub->bits)*2, fpt);
        free(buf2);

    }

}
like image 902
segmentation_fault Avatar asked May 29 '13 19:05

segmentation_fault


People also ask

Why is Dev random so slow?

On most Linux systems, /dev/random is powered from actual entropy gathered by the environment. If your system isn't delivering a large amount of data from /dev/random , it likely means that you're not generating enough environmental randomness to power it.

Does Mac Have Dev urandom?

So the answer is Yes, it is still valid to use /dev/urandom/ for generating key material on macOS Catalina ( 10.15.

How do I get a random number from Dev urandom?

You can use /dev/urandom to generate pseudo-random numbers on the command line like this. Commands like this that pull data from /dev/urandom and use od to process it can generate nearly random numbers. Run the same command numerous times and you'll see that you get a range of numbers.

What is the difference between Dev random and Dev urandom?

'Urandom' is used where there is constant need of random numbers and its randomness is not much important while 'random' is used where there is a security concern and its randomness should be reliable as it blocks outputting random numbers if entropy is not up to the mark.


1 Answers

Supposing that n is 50, your code is doing 2500 separate encryptions. Each encryption may require some random data.

It will be more efficient to do one encryption by encrypting the entire array in one call to paillier_enc. I am not familiar with the libpaillier API, but it looks like you would do this by arranging for all the data of the 50-by-50 array to be in contiguous memory, then use paillier_plaintext_from_bytes to package the entire array into a paillier_plaintext_t object, then use pallier_enc with that object.

like image 138
Eric Postpischil Avatar answered Oct 26 '22 23:10

Eric Postpischil