El criptosistema BG es semánticamente seguro basado en la supuesta intratabilidad de la factorización de enteros ; específicamente, factorizar un valor compuesto dónde son números primos grandes . BG tiene múltiples ventajas sobre los esquemas de cifrado probabilístico anteriores, como el criptosistema Goldwasser-Micali . Primero, su seguridad semántica se reduce únicamente a la factorización de enteros, sin requerir ningún supuesto adicional (por ejemplo, la dureza del problema de residuosidad cuadrática o el problema de RSA ). En segundo lugar, BG es eficiente en términos de almacenamiento, induciendo una expansión de texto cifrado de tamaño constante independientemente de la longitud del mensaje. BG también es relativamente eficiente en términos de cálculo y le va bien incluso en comparación con criptosistemas como RSA (dependiendo de la longitud del mensaje y las opciones de exponente). Sin embargo, BG es muy vulnerable a los ataques de texto cifrado de elección adaptativa (ver más abajo).
Debido a que el cifrado se realiza mediante un algoritmo probabilístico, un texto plano determinado puede producir textos cifrados muy diferentes cada vez que se cifra. Esto tiene ventajas significativas, ya que evita que un adversario reconozca los mensajes interceptados comparándolos con un diccionario de textos cifrados conocidos.
Operación
El criptosistema Blum-Goldwasser consta de tres algoritmos: un algoritmo de generación de claves probabilísticas que produce una clave pública y una privada, un algoritmo de cifrado probabilístico y un algoritmo de descifrado determinista.
Generación de claves
Las claves públicas y privadas se generan de la siguiente manera:
Elija dos números primos grandes y distintos y tal que y .
Calcular . Este será el mismo valor que se utilizó en el cifrado (ver prueba a continuación). luego se puede utilizar para calcular la misma secuencia de valores que se utilizaron en el cifrado para descifrar el mensaje, como se indica a continuación.
Para de 1 a
Calcular .
Calcular el menos significativo pedazos de .
Calcular .
Finalmente, vuelva a ensamblar los valores en el mensaje .
Ejemplo
Dejar y . Luego y . Para cifrar el mensaje de seis bits, lo dividimos en dos bloques de 3 bits , entonces . Seleccionamos al azar y calcular . Ahora calculamos el valores de la siguiente manera:
Entonces el cifrado es .
Para descifrar, calculamos
Se puede ver que tiene el mismo valor que en el algoritmo de cifrado. Por tanto, el descifrado procede de la misma forma que el cifrado:
Prueba de corrección
Debemos demostrar que el valor calculado en el paso 6 del algoritmo de descifrado es igual al valor calculado en el paso 4 del algoritmo de cifrado.
En el algoritmo de cifrado, por construcción es un módulo de residuo cuadrático . Por lo tanto, también es un módulo de residuo cuadrático., como todos los demás valores obtenidos de ella al elevar al cuadrado. Por tanto, según el criterio de Euler ,. Luego
Similar,
Elevando la primera ecuación a la potencia obtenemos
Repitiendo esto veces, tenemos
Y con un argumento similar podemos demostrar que .
Finalmente, desde , podemos multiplicar por y obten
a partir del cual , modulo ambos y , y por lo tanto .
Seguridad y eficiencia
El esquema Blum-Goldwasser es semánticamente seguro basado en la dureza de predecir los bits del flujo de claves dado solo el estado final de BBS y la clave pública . Sin embargo, los textos cifrados de la formason vulnerables a un ataque de texto cifrado elegido adaptativo en el que el adversario solicita el descifrado de un texto cifrado elegido . El descifrado del texto cifrado original se puede calcular como .
Dependiendo del tamaño del texto sin formato, BG puede ser más o menos costoso computacionalmente que RSA. Debido a que la mayoría de las implementaciones de RSA utilizan un exponente de cifrado fijo optimizado para minimizar el tiempo de cifrado, el cifrado RSA normalmente superará a BG para todos los mensajes excepto los más cortos. Sin embargo, como el exponente de descifrado RSA se distribuye aleatoriamente, la potenciación modular puede requerir un número comparable de cuadraturas / multiplicaciones al descifrado BG para un texto cifrado de la misma longitud. BG tiene la ventaja de escalar de manera más eficiente a textos cifrados más largos, donde RSA requiere múltiples cifrados separados. En estos casos, BG puede ser significativamente más eficiente.
Referencias
^ RFC 4086 sección "6.2.2. El generador de secuencia de Blum Blum Shub"
M. Blum, S. Goldwasser, "Un esquema de cifrado de clave pública probabilista eficiente que oculta toda la información parcial", Actas de avances en criptología - CRYPTO '84 , págs. 289-299, Springer Verlag, 1985.
Menezes, Alfred; van Oorschot, Paul C .; y Vanstone, Scott A. Manual de criptografía aplicada . CRC Press, octubre de 1996. ISBN 0-8493-8523-7