Simulación de Sistemas Paralelo “C” Integrantes: Susana Guasha, Lorena Aguilar, Andrés Carrera
Algoritmo de Blum Blum Shub
Algoritmo #include <stdio.h>#include <stdlib.h>#include <string.h>#include “gmp.h” /****************************************************************************/ /* TEMA: Algoritmo Blum-Blum-Shub */ /* */ /* POR: Andres Carrera */ /* Susana Guasha */ /* Lorena Agilar */ /* */ /****************************************************************************/
#define BITS_MODULO 1024 void iniciarBBS(char *s); int bitBBS(void);int byteBBS(void); int main(int argc, char *argv[]){ int i, nBytes; unsigned char s[256]; FILE *fo; if (argc!=3) { printf(”——————————————————\n”); printf(” Generador de números pseudoaleatorios Blum-Blum-Shub.\n\n”); printf(” Uso: %s <n> <s>\n”,argv[0]); printf(” n: numero de bytes requeridos.\n”); printf(” s: semilla.\n”); printf(”——————————————————\n”); return 1; }
/* Línea de comandos */ nBytes=atoi(argv[1]); strncpy(s,argv[2],256); /* Convertir la cadena s en un entero */ for (i=0; i<strlen(s); i++) s[i]=(s[i]%10)+’0′; /* Inicializa generador y produce los bytes pedidos * guardándolos en bbs.out */ iniciarBBS(s); fo = fopen(”bbs.out”, “wb”); for (i=0; i<nBytes; i++) { fprintf(fo, “%c”, byteBBS()); } fclose(fo); puts(”Resultados en el fichero: bbs.out”); return 0; }
mpz_t x; /* Último valor aleatorio */ mpz_t n; /* Módulo para BBS */
/* * Inicia el generador de numeros aleatorios a partir de la cadena s * que contiene un entero en base 10 que sirve como semilla. */void iniciarBBS(char *s){ mpz_t p, q, tmp; gmp_randstate_t estado;
/* Inicializar rng de la librería gmp3 */ gmp_randinit_default(estado); mpz_set_str(tmp, s, 10); gmp_randseed(estado, tmp);
/* Inicializar enteros */ mpz_init(x); mpz_init(n); mpz_init(p); mpz_init(q);
/* generar n como producto * de dos grandes primos congruentes con 3 modulo 4 */ do { mpz_urandomb(p, estado, BITS_MODULO/2); mpz_mul_ui(p,p,4); mpz_add_ui(p,p,3); } while (mpz_probab_prime_p(p,25)==0); do { mpz_urandomb(q, estado, BITS_MODULO/2); mpz_mul_ui(q,q,4); mpz_add_ui(q,q,3);
} while (mpz_probab_prime_p(q,25)==0); mpz_mul(n,p,q);
/* Ahora se produce la primera x = s^2 (mod n) */ mpz_set_str(x,s,10); mpz_mod(x,x,n); mpz_mul(x,x,x); mpz_mod(x,x,n);
/* Limpiamos variables innecesarias en lo sucesivo */ mpz_clear(p); mpz_clear(q); return;} int bitBBS(void){ mpz_mul(x,x,x); mpz_mod(x,x,n); /* x = x^2 mod n */ return mpz_tstbit(x, 0);} int byteBBS(void){ int byte=0, i; for (i=0; i<8; i++) byte = byte*2 + bitBBS(); return byte; }
Descripción Es un método para generar números que no tienen un comportamiento predecible. Por ende Blum Blum Shub (BBS) es un generador pseudoaleatorio de números propuesto por Lenore Blum, Manuel Blum y Michael Shub en 1986. Al generar los números aleatorios, cuando se da un numero pequeño de bits es posible también generar secuencias largas de bits, los generadores mas utilizados contiene funciones, estructuras y fuertes encriptaciones como PRBG, RSA esta genera 5 módulos cuando se usan números exponenciales; todas ellas usan el algoritmo de BBS por su característica de congruencia y no lineal. Se construye a través de una ecuación recursiva.
X i+1 = ( X i 2 ) mod (m) i= 0,1,2,3,…n
M = pq es el producto de dos números primos muy grandes p y q. En cada paso del algorimo, se obtiene un resultado para xn; el resultado es por lo general o bien el bit de paridad de xn ó uno ó más de los bits menos significativos de xn. Los dos números primos, p y q, deben ser ambos congruentes a 3 (mod 4) (esto asegura que cada residuo cuadrático posee una raíz cuadrada que también es un residuo cuadrático) y mcd(φ(p-1), φ(q-1)) debe ser pequeña (esto hace que la longitud del ciclo sea extensa). Una característica interesante del generador BBS generator es la posibilidad de calcular todo valor xi en forma directa: Características Es confiable y desde el punto de vista de su seguridad, lo que se relaciona con la calidad del generador en cuanto a la complejidad computacional de la factorización de enteros. Funcionamiento Cuando se eligen los primos en forma adecuada, y los bits menos significativos O(log log M) de cada xn se eligen como resultado, entonces en el límite cuando M se hace muy grande, distinguir los bits resultado de una secuencia aleatoria será por lo menos tan dificil como factorizar M. Si la factorización de enteros es dificil (como es de esperar) entonces BBS con grandes M tendrán un resultado libre de todo patrón no aleatorio que puede ser descubierto mediante una cantidad razonable de cálculos. Esto hace que el método sea tan seguro como otras tecnologías de cifrado asociadas al problema de factorización, como por ejemplo la cifrado RSA. Aplicaciones: El generador BBS es apropiado para ser utilizado en criptografía mas que en simulaciones, porque no es muy rápido. Especialmente como políticas en la banca en línea, direccionamiento de saltos de los routers en la red Ejercicio:X i+1 = ( X i 2 ) mod (m) i= 0,1,2,3,…n Datos p=11 q=19 s=3 Desarrollo: Se obtener un ciclo largo para estos números pequeños, en cuanto mcd (φ ( p - 1), φ ( q – 1 ) ) = 2. El generador BBS evalua: x0 utilizando x -1=s Resultados Crea la sucesión x0, x1, x2,… x5= 9, 81, 82, 36, 42, 92. Utilizando l bit de paridad para definir el resultado, entonces los bits resultados son 0 1 1 0 1 0.
Ingresar un comentario
|