• GMP
  • Introduzione e librerie
  • CSPRNG Blum Blum Shub
• Crittografia
• Sicurezza

CSPRNG Blum Blum Shub

PRNG e CSPRNG

Prima di tutto: cos'è un PRNG? È un generatore di numeri pseudo-casuali, vale a dire una funzione che genera una sequenza di numeri apparentemente non correlati tra di loro. L'"apparentemente" è dovuto al fatto che i microprocessori sono sistemi deterministici, mentre l'effettiva casualità è caratteristica dei sistemi non deterministici. In altre parole numeri davvero casuali sono ottenibili solo tramite processi fisici (ad es.: decadimento di isotopi radioattivi, rumore elettronico o termico), mentre qualunque algoritmo se si conoscono le sue variabili interne, produrrà sempre la stessa sequenza di numeri.

In realtà in questa sede sarebbe più corretto parlare di PRBG, cioè di sistemi che generano bit casuali. Un PRBG può facilmente essere "trasformato" in un PRNG generando ⌊lg n⌋+1 bit e considerando la sequenza come un numero espresso in base 2. Se tale numero eccede n si scarta la sequenza e se ne genera un'altra. Qui utilizzerò il termine PRNG, ma lo si può considerare come un sinonimo di PRBG (tecnicamente il Blum-Blum-Shub è un PRBG, ma a noi interessa generare numeri casuali, dei singoli bit ce ne facciamo poco).

I PRNG hanno ampi impieghi in molti campi (in primis le simulazioni numeriche di tutti i tipi) e praticamente tutti i linguaggi di programmazione prevedono funzioni per la generazione di numeri casuali. Ma non tutti i PRNG sono uguali: prima di tutto non necessariamente generano sequenze di numeri distribuite uniformemente nell'intervallo stabilito dall'utilizzatore (ad. es.: [0; 1]), ma possono simulare distribuzioni gaussiane, poissoniane o altre ancora, dal punto di vista dell'implementazione si va da semplici operatori aritmetici, all'utilizzo di registri a scorrimento, all'aritmetica modulare.

Fin qui abbiamo evitato una domanda di base: quando una sequenza di numeri è casuale? La teoria della probabilità e la statistica evitano accuratamente di fare affermazioni assolute in proposito, e preferiscono piuttosto esprimere tutto in termini di probabilità che affermazioni relative a sequenze di eventi casuali siano vere o meno. Dare una risposta a questa domanda è molto difficile se si decide di affrontarla da un punto di vista strettamente matematico. Per chi volesse approfondire consiglio di leggere The Art of Computer Programming – Seminumerical Algorithms, volume 2, di D. E. Knuth, che contiene un'approfondita discussione sulla nozione di "casualità" e di alcuni noti algoritmi per la realizazzazione di PRNG. Per i nostri scopi è sufficiente la definizione intuitiva, citata dallo stesso Knuth:

La definizione di Lehmer coglie alcuni punti fondamentali:

• Una sequenza appare casuale se non è possibile prevedere il prossimo elemento della sequenza senza conoscere l'algoritmo che li genera.
• Una sequenza pseudo-casuale riesce a superare una serie di test che ne determinano il grado di "casualità"
• Le sequenze casuali adatte per un utilizzo possono non essere adatte per un altro.

È facile fare un esempio che chiarisca questi il primo concetto. Data la sequenza 0, 9, 9, 4, 6, 5, 7, 6, 4, 0, sapreste dire qual è il prossimo numero? Ve lo dico io: è 7. Sembrano casuali? Sì, ma non lo sono affatto: sono le cifre dalla 2000^a in poi di π. Per quanto riguarda il secondo punto sarebbe necessario parlare dei metodi con cui si determina la qualità dei numeri generati dai PRNG, argomento che esula dagli scopi di questo documento, mi limiterò a un piccolo esempio. Un test classico che si fa su un generatore di bit (cioè un generatore di numeri che sputa fuori o 1 o 0) è cercare di comprimere un file il cui contenuto è la sequenza di bit casuali. Se la sequenza di bit è effettivamente casuale, il file sarà al limite non comprimibile per nulla. Anche una comunissima immagine in formato .gif supera questo test, ma altri test mostrano come il contenuto di un file .gif sia non casuale. Per chi volesse approfondire le metodologie di test suggerisco di leggere il documento FIPS-PUB-140-1, i sorgenti del programma Diehard di George Marsaglia e ENT di John Walker, l'articolo A Statistical Test Suite for Random and Pseudorandom Number Generators in NIST Special Publication 800-22.

Veniamo al terzo punto, fondamentale dal nostro punto di vista. Esistono molti PRNG (ad. es.: Mersenne Twister, linear feedback shift register, linear congruential generator), ma molti di questi soffrono di un difetto che, se non inficia sulla loro utilità in altri campi più "classici", li rende inutilizzabili per applicazioni crittografiche. Il problema è che un osservatore esterno, conoscendo l'algoritmo utilizzato e una certa quantità di numeri generati, può risalire allo stato interno del sistema e predire quali saranno i prossimi numeri della sequenza. Siamo arrivati al punto cruciale dei CSPRNG: questa categoria di PRNG resiste al next-bit test (test del prossimo bit).

Si dice che un PRNG passa il next-bit test se non esiste alcun algoritmo eseguibile in tempo polinomiale che ricevendo in input i primi l bit di una sequenza s generata dal PRNG, possa predire il (l+1)° bit con una possibilità di successo significativamente superiore a ¹/₂.

CSPRNG

Un CSPRNG per essere definito tale deve passare il next-bit test. Nel 1982 Andrew Yao ha dimostrato che un PRNG può superare il next-bit test se e solo se passa tutti i test statistici eseguibili in tempo polinomiale.

Un'altra caratteristica desiderabile di un CSPRNG è che resista a una compromissione dello stato; vale a dire che se parte o tutto lo stato interno dell'algoritmo viene rivelato (o correttamente indovinato), deve essere impossibile per un attaccante ricostruire la sequenza dei numeri casuali generati prima della compromissione. Inoltre, se viene aggiunta entropia durante il funzionamento del CSPRNG, dovrebbe essere impossibile usare le informazioni dello stato interno per predire lo stato del sistema.

Esistono fondamentalmente due categorie di CSPRNG: quelli basati su primitive crittografiche e quelli su problemi della teoria dei numeri ritenuti "computazionalmente ardui". La prima categoria è sicuramente quella pi� popolata, tra i tanti ricordiamo:

• ANSI X9.17-1985 Appendix C.
• ANSI X9.31-1998 Appendix A.2.4.
• Yarrow.
• Fortuna (successore di Yarrow).
• ISAAC, che recentemente ha ceduto a un attacco di crittanalisi di Marina Pudovkina, che ha ridotto la complessità di un attacco riportandolo a un valore inferiore alla radice quadrata di tutti i possibili stati iniziali, passando da 10²⁴⁶⁶ a "solo" 4.67×10¹²⁴⁰. ISAAC è strutturalmente simile all'algoritmo di crittazione RC4.
• CryptGenRandom, funzione che fa parte delle CryptoAPI di Microsoft, di cui si parlerà in seguito.

Per il secondo gruppo citiamo:

• RSA PRNG, che è un CSPRNG se e solo se il problema di RSA è intrattabile (condizione supposta ma non dimostrata). Il problema RSA è il seguente: dati un intero positivo n risultante dal prodotto di due numeri primi dispari, un intero positivo e tale che MCD(e, (p-1)(q-1))=1 e un intero c, trovare un intero m tale che m^e≡c mod n.
• Micali-Schnorr PRNG: è più efficiente del RSA PRNG sia per la quantità di bit generati che per il minor numero di operazioni richieste. Tale algoritmo è crittograficamente sicuro se è vera l'assunzione per cui la distribuzione di x^e mod n partendo da un x lungo r bit scelti a caso è indistinguibile da tutti i test statistici eseguibili in tempo polinomiale da una distribuzione uniforme di interi nell'intervallo [0, n-1] (condizione più ristretta dell'intrattabilità di RSA).
• Blum-Blum-Shub PRNG, di cui qui si tratta.

Blum-Blum-Shub PRNG

L'algoritmo Blum-Blum-Shub PRNG, detto anche BBS PRNG o generatore x² mod n, fu proposto nel 1986 da Lenore Blum, Manuel Blum e Michael Shub (anche se era già stata pubblicata una prima bozza nel 1983), che dimostrarono come fosse un CSPRNG sotto l'assunzione dell'intrattabilità del problema dei resti quadratici, vale a dire della difficoltà dell'estrazione delle radici quadrate nell'aritmetica modulare. Nel 1984 Umesh V. Vazirani e Vijay V. Vazirani dimostrarono come il BBS fosse un PRNG sotto la condizione più debole dell'intrattabilità del problema della fattorizzazione degli interi (se il problema dei resti quadratici e della fattorizzazione degli interi siano equivalenti è una domanda ancora aperta).

Una dimostrazione del perché il BBS sia un CSPRNG sarebbe molto tediosa e pochissimo utile (e probabilmente sbagliata, visto che IANAM), per chi volesse approfondire consiglio Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator di Pascal Junod. Passiamo quindi all'algoritmo vero e proprio:

1. Si generino due numeri interi positivi p e q segreti e distinti, ognuno congruente a 3 modulo 4, e si calcoli n=pq. n è un cosiddetto "numero di Blum". Si legga la nota sotto per la scelta di p e q
2. Si selezioni un numero intero segreto s (detto seme o seed) nell'intervallo [1, n-1] tale che MCD(s, n)=1 e si calcoli x₀←s² mod n.
3. Per i che va da 1 a l si esegua:
   1. x_i←x²_i-1 mod n.
   2. z_i← il bit meno significativo di x_i.
4. I bit casuali sono la sequenza z₁, z₂, ..., z_l.

Come già detto il BBS genera bit, quindi a questo punto è sufficiente utilizzare poche operazioni logiche per raggruppare i bit in byte e ottenere così i dati casuali.

Un'interessante proprietà di BBS è quella per cui è possibile calcolare direttamente qualunque i-esimo valore tramite la formula x_i=(x₀^{2i mod ((p-1)(q-1))}) mod n.

L'estrazione di un singolo bit richiede un elevamento al quadrato modulare. L'efficienza dell'algoritmo può essere migliorata estraendo da x_i gli ultimi j bit, dove j = c lg lg n. Non è attualmente noto un intervallo esplicito entro cui può variare c per cui il BBS rimanga crittograficamente sicuro.

imbbsprng

Personalmente ho sviluppato il (semplicissimo) codice in Windows utilizzando Dev-C++, ma è tutto C standard, quindi non dovrebbe esserci alcun problema nel compilarlo e utilizzarlo in qualunque altri sistema operativo (e infatti ho anche testato il codice sotto Linux). Se dovessero esserci richieste eventualmente scriverò una versione più elaborata per il pinguino, che poi si ridurrebbe a scrivere un opportuno makefile che renda la compilazione più semplice, dato che l'ossatura c'è già.

Inizializzazione

Il problema di come inizializzare l'algoritmo è sufficientemente interessante da meritare un paragrafo a sé. Stiamo programmando un PRNG, che ha bisogno di bit casuali per poter iniziare a funzionare. Ottenere tali bit che forniscono l'entropia necessaria per l'algoritmo, è tutt'altro che banale. Si possono distinguere fondamentalmente due sorgenti di entropia: quelle hardware e quelle software. Sorgenti hardware possono essere contatori geiger che rilevano l'emissione di particelle durante un processo di decadimento radioattivo (come è stato fatto nel progetto HotBits da John Walker), rumore proveniente da un microfono o da un CCD (come nel progetto LavaRnd di London C. Noll, Simon Cooper e Mel Pleasant), misurando i tempi di latenza nell'accesso ai file in un hard disk a causa delle turbolenze d'aria sui piatti (About Random Bits di Martin Geisler, Mikkel Krøigård e Andreas Danielsen), rumore termico su un diodo o un resistore, un oscillatore instabile e così via. Sorgenti software di entropia possono essere l'orologio di sistema, gli intervalli tra gli input dell'utente, statistiche di sistema.

Scrivere un programma che utilizzi queste tecniche è ampiamente al di fuori degli scopi di questo testo. Ricorriamo quindi agli strumenti messi a disposizione dal sistema operativo.

Su sistemi Windows sono presenti le cosiddette CryptoAPI (contrazione di Cryptographic Application Programming Interface), che mettono a disposizione del programmatore delle API che consentono di implementare con (relativa) facilità funzionalità crittografiche. Di particolare interesse per noi è la funzione CryptGenRandom che per generare i bit casuali utilizza l'ID del processo e del thread corrente, l'orologio di sistema, dei contatori a alta risoluzione di sistema, dati sullo stato della memoria, il numero di cluster liberi su disco, l'hash MD4 delle variabili d'ambiente dell'utente. Questi dati vengono dati come input all'hash SHA-1 e il risultato è utilizzato come chiave in uno stream che utilizza l'algoritmo di crittazione RC4, il cui l'output è restituito come stream di bit casuali.

Su sistemi unix e unix-like sono disponibili i file fittizi /dev/random e /dev/urandom: il primo restituisce bit casuali finchè l'algoritmo interno stima che l'entropia presente nei pool di bit utilizzati per generare i bit casuali sia sufficientemente alta, mentre il secondo utilizza l'entropia dei pool per inizializzare un PRNG. Le informazioni utilizzate dal kernel Linux per i pool di entropia sono i numeri degli interrupt IRQ e l'istante in cui effettuano una chiamata, informazioni sull'hard disk, i tasti digitati e l'istante in cui sono stati premuti, i movimenti del mouse. Di base /dev/random ha una struttura simile a quella del CSPRNG Yarrow, utilizza una versione (errata) di SHA-1 e MD5 (e utilizza delle versioni ridotte di MD4 per la generazione dei numeri di sequenza e di altre informazioni per i pacchetti IP e TCP). Nonostante alcune scelte di design non proprio felicissime, tutto sommato è possibile ritenere /dev/random un'ottima sorgente di bit casuali. È possibile tuttavia migliorarlo, ed è disponibile una patch per sostituire l'algoritmo utilizzato con un'architettura molto simile a quella prevista da Fortuna (il CSPRNG progettato da Ferguson e Schneier). Per ulteriori informazioni vi rimando a http://jlcooke.ca/random/.

Finalmente arriviamo al primo codice: ci serve una funzione a cui, dando in pasto un buffer e il numero di byte necessari, lo riempia di bit casuali. Per i sistemi unix-like l'operazione è semplicissima:

unsigned int unsecurerand(char *rndbuf, size_t nbytes)
{
   FILE *devrnd;
   int nread;
   if ((devrnd=fopen(RANDOMDEV, "r")) == NULL)
      return 0;
   nread = fread(rndbuf, 1, nbytes, devrnd);
   fclose(devrnd);
   return nread;
}

Dove RANDOMDEV è una costante definita in un header che specifica il file da utilizzare. Si noti che in generale /dev/random non è esattamente velocissimo nel generare byte casuali, per cui se siete disposti a sacrificare un minimo di sicurezza per un (enorme) aumento di velocitè, vi consiglio di dare un'occhiata al file imbbsprng.h (contenuto nei sorgenti scaricabili) e modificarlo in modo che RANDOMDEV sia "/dev/urandom".

Su Windows le cose sono, neanche a dirlo, più complesse. Per chi volesse dare un'occhiata a un esempio completo è possibile consultare il programmino C su MSDN: Example C Program: Using CryptAcquireContext. Quello che bisogna fare, in sostanza, è ottenere un handle per un cryptographic service provider (CSP), che è un oggetto che mette a disposizione i servizi delle CryptoAPI. Una volta ottenuto l'handle, possiamo utilizzare la funzione CryptGenRandom, che restituirà i byte casuali richiesti, dopodichè si deallocano le risorse utilizzate:

unsigned int unsecurerand(char *rndbuf, size_t nbytes)
{
   // handle del CSP
   HCRYPTPROV hcp;
   // flag che identificano quello che vogliamo fare:
   // CRYPT_VERIFYCONTEXT: vuol dire che non ci interessa accedere a chiavi persistenti del sistema
   // CRYPT_MACHINE_KEYSET: vuol dire che le chiavi che vogliamo utilizzare non appartengono all'utentema alla macchina, quindi non vanno associate a alcun utente
   DWORD flags = CRYPT_VERIFYCONTEXT | CRYPT_MACHINE_KEYSET;
  // proviamo ad acquisire un CSP (in questo caso che supporti RSA)
   if (!CryptAcquireContext(&hcp, NULL, NULL, PROV_RSA_FULL, flags))
   {
      // se la chiamata ha fallito con errore NTE_BAD_KEYSET, seguiamo il suggerimendo dell'sdk e utilizziamo anche il flag CRYPT_NEWKEYSET
      if (GetLastError()==NTE_BAD_KEYSET) {
         flags |= CRYPT_NEWKEYSET;
         if (!CryptAcquireContext(&hcp, NULL, NULL, PROV_RSA_FULL, flags))
	    // se la chiamata fallisce ancora, siamo riusciti a generare 0 byte e restituiamo tale valore
            return 0;
         } else
         // se la chiamata ha fallito per qualunque altro motivo, restituiamo 0
         return 0;
   }
   // ottenuto l'handle del CSP, chiediamo nbytes byte casuali da mettere in rndbuf
   if (!CryptGenRandom(hcp, nbytes, rndbuf))
   {
      // se la chiamata fallisce rilasciamo l'handle del CSP e restituiamo 0
      CryptReleaseContext(hcp, 0);
      return 0;
   }
   // abbiamo i nostri byte casuali, possiamo rilasciare l'handle
   CryptReleaseContext(hcp, 0);
   // restituiamo nbytes
   return nbytes;
}

Abbiamo così la funzione che si occupa di generare byte casuali che ci consentiranno di inizializzare il nostro PRNG. Per utilizzare correttamente il codice a seconda che ci si trovi su un sistema Windows o unix-like, � sufficiente utilizzare la direttiva per il precompilatore #ifdef _WIN32.

Implementazione

Una prima funzione che ci tornerà molto utile è quella che utilizza unsecurerand e che usa i byte generati per creare un numero intero casuale lungo un certo numero di bit (attenzione, non byte) a nostra scelta. Il tipo definito da GMP per i numeri interi è mpz_t. GMP specifica una funzione che consente di impostare il valore di una variabile mpz_t utilizzando un semplice array. La funzione da utilizzare è mpz_import, la cui signature è:

void mpz_import(mpz_t rop, size_t count, int order, int size, int endian, size_t nails, const void *op)

Questa funzione imposta il valore di rop importando il valore da *op. In particolare la funzione si aspetta che l'array *op contenga count elementi, ognuno lungo size byte. order deve essere impostato a 1 se si vuole indicare che il primo elemento è il più significativo, altrimenti deve essere impostato a -1. Per ogni elemento viene considerata l'endianess, cioè quale byte è il più significativo. Questo valore deve essere 1 per indicare che il primo byte è il più significativo, -1 per indicare che il primo byte è il meno significativo e 0 per utilizzare l'endianess nativa della CPU. Da ogni elemento vengono ignorati i primi nails bit.

Con queste informazioni è molto semplice scrivere il codice che ci siamo prefissi, stando attenti a trattare il primo elemento dell'array in modo che abbia il giusto numero di bit a 0 all'inizio, in modo che l'intero sia lungo esattamente quanto vogliamo (generalmente si sceglieranno lunghezze multiple di 8, ma better safe than sorry:

void unsecurerand_mpz(mpz_t dest, size_t bitlength) {
   byte *buff;
   size_t bytesize;
   unsigned int nullbits;

   // bytesize è l'intero che ci dice quanti byte casuali dobbiamo generare (è l'arrotondamento verso l'alto della lunghezza in bit diviso 8)
   bytesize=ceil(bitlength / 8.0);
   //buff è il buffer che contiene i byte casuali
   buff = malloc(bytesize);

   // cerchiamo di generare i byte casuali che vogliamo
   if (unsecurerand(buff, bytesize)!=bytesize) {
      // se falliamo impostiamo dest a 0
      mpz_set_d(dest, 0);
   } else {

      // nullbits è il numero di bit a 0 che ci devono essere all'inizio del primo byte affinchè l'intero ottenuto sia lungo esattamente
      // bitlength bit
      nullbits = (bitlength % 8) ? 8-(bitlength % 8) : 0;

      // impostiamo a 0 i primi nullbits bit del primo byte (che sarà il più significativo mettendolo in and logico con 0xFF opportunamente
      // shiftato a destra
      buff[0] &= 0xFF >> nullbits;

      // se ad es. vogliamo un intero di 4 bit, il 4o bit da destra (contando da 1) deve essere impostato a 1 eseguiamo quindi l'operazione
      // qui riportata di or logico
      buff[0] |= 1 << (7-nullbits);

      // possiamo ora importare l'array come numero intero
      mpz_import(dest, bytesize, 1, 1, 1, 0, buff);
   }

   // liberiamo il buffer
   free(buff);
}

Possiamo ora passare all'implementazione vera e propria del BBS. Possiamo individuare tre funzioni fondamentali: una per inizializzare l'algoritmo, una per generare i byte casuali e una per liberare le risorse allocate. Dall'algoritmo vediamo che per generare i numeri casuali in un qualunque momento abbiamo bisogno di sole due informazioni: la x_i e la n. Creiamo quindi una struttura adatta a contenere questi dati:

typedef struct {
   mpz_t xi;
   mpz_t n;
} BBS_CONTEXT;

Deallocare le risorse è sicuramente la parte più semplice: per farlo si richiama la funzione mpz_clear, che ha come unico argomento l'intero di GMP da deallocare:

void bbs_free(BBS_CONTEXT *ctx)
{
   mpz_clear(ctx->xi);
   mpz_clear(ctx->n);
}

Passiamo ora alla procedura di inizializzazione. Avremo bisogno delle variabili p, q e s (mentre xi e n saranno accessibili nella struttura precedentemente dichiarata) e di una variabile intera reps che indicherà il numero di volte per cui andrà effettuato il test di Miller-Rabin per determinare la pseudoprimaltà delle variabili utilizzate nell'algoritmo. Il test di Miller-Rabin è un test che consente di individuare numeri probabilmente primi. Questo vuol dire che se un numero non lo passa è sicuramente composto, ma se lo passa non necessariamente è primo. Più volte un numero passa il test di Miller-Rabin, più probabilmente è primo. Dichiariamo quindi le nostre variabili:

void bbs_init(BBS_CONTEXT *ctx, size_t bitlength)
{
   unsigned int reps;
   mpz_t p, q, s;

Come sappiamo p e q devono essere lunghi (in bit) la metà di n, questo vuol dire che la lunghezza in bit che ci viene richiesta deve essere un numero pari. Se non lo è, la dobbiamo incrementare di uno (si ricordi che l'operatore % indica il calcolo del modulo):

   if (bitlength % 2)
      bitlength++;

Inizializziamo ora le variabili di tipo mpz_t, utilizzando la funzione mpz_init2, che accetta come argomento la lunghezza in bit della variabile: ciò consente di allocare subito la memoria necessaria, evitando successive eventuali costose operazioni di riallocazione (si ricordi che lo shift a destra di un bit equivale alla divisione per 2 - in realtà gcc è sufficientemente furbo da effettuare da sé questa piccolissima ottimizzazione, ma a me viene di riflesso farla a mano):

   mpz_init2(p, bitlength>>1);
   mpz_init2(q, bitlength>>1);
   mpz_init2(s, bitlength);
   mpz_init2(ctx->n, bitlength);
   mpz_init2(ctx->xi, bitlength);

Impostiamo ora il numero di volte per cui effettuare il test Miller-Rabin. La probabilità che un numero di k bit passi un certo numero t di volte il test pur essendo composto, è una funzione decrescente, cioè più è lungo il numero, meno volte va eseguito il test per determinare se sia probabilmente primo. Indicando con p_k,_t tale probabilità i valori qui scelti sono tali per cui p_k,_t < 0.5⁸⁰ (≈ 10^-24).

   if (bitlength/2<100)
      reps=30;
   else if (bitlength/2<150)
      reps=20;
   else if (bitlength/2<250)
      reps=15;
   else if (bitlength/2<600)
      reps=10;
   else
      reps=4;

(So che è codice bruttissimo, voglio solo essere chiaro: i test vanno effettuati su p e q, che hanno lunghezza pari alla metà della lunghezza in bit passata come parametro).

Passiamo ora all'individuazione di p e q. Grazie alla funzione unsecurerand_mpz scritta prima, ottenere i valori casuali da cui iniziare è facilissimo. Partendo da questi valori possiamo individuare i numeri primi successivi con la funzione mpz_nextprime. Una volta verificato che p e q siano congruenti a 3 modulo 4, li moltiplichiamo e controlliamo che la n così ottenuta sia lunga esattamente il numero di bit che desideriamo (non è difficile che moltiplicando due numeri di 256 bit si ottenga un risultato di 511 bit), in caso contrario generiamo altri due p e q; memorizziamo n nella struttura BBS_CONTEXT che ci è stata passata come parametro. Il codice è il seguente:

   do {
      // generiamo p e q casuali
      unsecurerand_mpz(p, bitlength>>1);
      unsecurerand_mpz(q, bitlength>>1);

      // cerchiamo un p ≈ 3 mod 4 e effettuiamo un numero appropriato di test
      // di Miller-Rabin per sincerarci della sua primalità
      do {
         mpz_nextprime(p, p);
      } while (!(mpz_congruent_ui_p(p, 3, 4) && mpz_probab_prime_p(p, reps)));

      // idem per q
      do {
         mpz_nextprime(q, q);
      } while (!(mpz_congruent_ui_p(q, 3, 4) && mpz_probab_prime_p(q, reps)));

      // mettiamo nel campo n della struttura ctx il prodotto p*q
      mpz_mul(ctx->n, p, q);

   } while (mpz_sizeinbase(ctx->n, 2)!=bitlength);
   // ripetiamo la ricerca di altri p e q se n non è lungo il numero di bit desiderati

In realtà il codice che potete scaricare è leggermente diverso, perché tiene conto del fatto che la chiamata a mpz_nextprime comporta già di per sé l'esecuzione di cinque test di Miller-Rabin, per cui effettuare altri test per i numeri più lunghi di 600 bit è sostanzialmente solo una perdita di tempo.

Si passa ora a cercare il seed casuale s. Come sappiamo s deve essere minore di n e deve avere massimo comun divisore 1 con n (gcd(s, n)==1)), vale a dire che deve essere diverso da p e da q. Il codice che realizza tali operazioni è immediato:

   do {
      unsecurerand_mpz(s, bitlength);
   } while ((mpz_cmp(s, p)==0) || (mpz_cmp(s, q)==0) || (mpz_cmp(s, ctx->n)>=0));

mpz_cmp è una funzione per effettuare comparazioni tra variabili intere e dà gli stessi risultati della funzione strcmp: 0 se i due argomenti sono uguali, un numero negativo se il primo è minore del secondo, un numero positivo altrimenti.

Si può ora calcolare x₀=s² mod n, tramite la funzione mpz_powm_ui, che effettua un'elevazione a potenza con modulo. Il suffisso "_ui" indica che l'argomento dell'esponente è un semplice intero senza segno standard del C, e non un intero introdotto da GMP.

   mpz_powm_ui(ctx->xi, s, 2, ctx->n);

Abbiamo effettuato tutti i calcoli necessari, provvediamo quindi a liberare le risorse allocate:

   mpz_clear(p);
   mpz_clear(q);
   mpz_clear(s);
}

Terminata la procedura di inizializzazione, possiamo scrivere la funzione che genera i numeri casuali. Il suo funzionamento è molto semplice: prima di tutto si azzera il buffer di destinazione, poi si effettuano due cicli annidati - quello esterno serve per contare i byte generati, quello interno genera gli 8 bit necessari per ogni byte effettuando l'elevazione a potenza modulare prevista dall'algoritmo. Per generare i bit si utilizza la funzione mpz_tstbit che restituisce 1 o 0 concordemente con lo stato del bit che gli viene richiesto. Tale risultato, opportunamente shiftato, viene messo in or logico con il byte che si sta generando:

void bbs_random(BBS_CONTEXT *ctx, char *dest, size_t count) {
   unsigned long int i, j;
   memset(dest, 0, count);
   for (i=0; i<count; i++)
      for (j=0; j<8; j++) {
         mpz_powm_ui(ctx->xi, ctx->xi, 2, ctx->n);
         dest[i] |= (char)(mpz_tstbit(ctx->xi, 0) << j);
      }
}

Download

Clicca qui per iniziare il download

Potete scaricare da qui i sorgenti completi del generatore casuale (che include tra l'altro una funzione bbs_random_mpz che genera interi casuali di tipo mpz_t) comprendente una semplice applicazione che genera un file di 1 MiB contenenti byte casuali utilizzando il Blum-Blum-Shub. I sorgenti comprendono il progetto da aprire con Dev-C++ e il binario già compilato (che non necessita della dll di gmp in quanto è linkato staticamente con il suo codice), ma può essere compilato senza alcun problema anche su sistemi Linux su cui sia stata installata la GMP utilizzando il comando:

ippatsuman@akane$ gcc main.c imbbsprng.c -lm -lgmp -o imbbsprng_demo

Per ulteriori informazioni contattatemi pure.