Criptosistema Blum-Goldwasser

El criptosistema Blum-Goldwasser (BG) es un algoritmo de cifrado de clave asimétrica propuesto por Manuel Blum y Shafi Goldwasser en 1984. Blum-Goldwasser es un criptosistema probabilístico y semánticamente seguro con una expansión de texto cifrado de tamaño constante . El algoritmo de cifrado implementa un cifrado de flujo basado en XOR utilizando el generador de números pseudoaleatorios Blum-Blum-Shub (BBS) para generar la secuencia de claves . El descifrado se logra manipulando el estado final del generador BBS mediante la clave privada , con el fin de encontrar la semilla inicial y reconstruir la secuencia de claves.

El criptosistema BG es semánticamente seguro basado en la intratabilidad asumida de la factorización de enteros ; específicamente, factorizar un valor compuesto.${\displaystyle N=pq}$dónde${\displaystyle p,q}$son primos grandes . BG tiene múltiples ventajas sobre 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 ninguna suposición adicional (por ejemplo, la dificultad del problema de residuos cuadráticos o el problema RSA ). Segundo, 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 computación, y se desempeña bien incluso en comparación con criptosistemas como RSA (dependiendo de la longitud del mensaje y las elecciones de exponente). Sin embargo, BG es altamente vulnerable a ataques adaptativos de texto cifrado elegido (ver más abajo).

Dado que el cifrado se realiza mediante un algoritmo probabilístico, un texto plano determinado puede generar textos cifrados muy diferentes cada vez que se cifra. Esto ofrece ventajas significativas, ya que impide que un adversario reconozca los mensajes interceptados comparándolos con un diccionario de textos cifrados conocidos.

El criptosistema Blum-Goldwasser consta de tres algoritmos: un algoritmo probabilístico de generación de claves que produce una clave pública y una clave privada, un algoritmo de cifrado probabilístico y un algoritmo de descifrado determinista.

Dejar${\displaystyle p=19}$y${\displaystyle q=7}$. Entonces${\displaystyle n=133}$y${\displaystyle h=\lfloor log_{2}(log_{2}(133))\rfloor =3}$Para cifrar el mensaje de seis bits${\displaystyle 101001_{2}}$, lo dividimos en dos bloques de 3 bits${\displaystyle m_{1}=101_{2},m_{2}=001_{2}}$, entonces${\displaystyle t=2}$Seleccionamos un número aleatorio.${\displaystyle r=36}$y calcular${\displaystyle x_{0}=36^{2}{\bmod {1}}33=99}$. Ahora calculamos el${\displaystyle c_{i}}$valores como sigue:

${\displaystyle {\begin{aligned}x_{1}&=99^{2}{\bmod {1}}33=92=1011100_{2};\quad p_{1}=100_{2};\quad c_{1}=101_{2}\oplus 100_{2}=001_{2}\\x_{2}&=92^{2}{\bmod {1}}33=85=1010101_{2};\quad p_{2}=101_{2};\quad c_{2}=001_{2}\oplus 101_{2}=100_{2}\\x_{3}&=85^{2}{\bmod {1}}33=43\end{aligned}}}$

Entonces el cifrado es${\displaystyle (c_{1}=001_{2},c_{2}=100_{2},x_{3}=43)}$.

Para descifrar, calculamos

${\displaystyle {\begin{aligned}d_{p}&=5^{3}{\bmod {1}}8=17\\d_{q}&=2^{3}{\bmod {6}}=2\\u_{p}&=43^{17}{\bmod {1}}9=4\\u_{q}&=43^{2}{\bmod {7}}=1\\(r_{p},r_{q})&=(3,-8){\text{ since }}3\cdot 19+(-8)\cdot 7=1\\x_{0}&=1\cdot 3\cdot 19+4\cdot (-8)\cdot 7{\bmod {1}}33=99\\\end{aligned}}}$

Se puede observar que${\displaystyle x_{0}}$tiene el mismo valor que en el algoritmo de cifrado. Por lo tanto, el descifrado se realiza de la misma manera que el cifrado:

${\displaystyle {\begin{aligned}x_{1}&=99^{2}{\bmod {1}}33=92=1011100_{2};\quad p_{1}=100_{2};\quad m_{1}=001_{2}\oplus 100_{2}=101_{2}\\x_{2}&=92^{2}{\bmod {1}}33=85=1010101_{2};\quad p_{2}=101_{2};\quad m_{2}=100_{2}\oplus 101_{2}=001_{2}\end{aligned}}}$

Debemos demostrar que el valor${\displaystyle x_{0}}$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${\displaystyle x_{0}}$es un residuo cuadrático módulo${\displaystyle n}$. Por lo tanto, también es un residuo cuadrático módulo${\displaystyle p}$, como todos los demás${\displaystyle x_{i}}$valores obtenidos a partir de él elevándolo al cuadrado. Por lo tanto, según el criterio de Euler ,${\displaystyle x_{i}^{(p-1)/2}\equiv 1\mod {p}}$. Entonces

${\displaystyle x_{t+1}^{(p+1)/4}\equiv (x_{t}^{2})^{(p+1)/4)}\equiv x_{t}^{(p+1)/2}\equiv x_{t}(x_{t}^{(p-1)/2})\equiv x_{t}\mod {p}}$

Similarmente,

${\displaystyle x_{t}^{(p+1)/4}\equiv x_{t-1}\mod {p}}$

Elevando la primera ecuación a la potencia${\displaystyle (p+1)/4}$obtenemos

${\displaystyle x_{t+1}^{((p+1)/4)^{2}}\equiv x_{t}^{(p+1)/4}\equiv x_{t-1}\mod {p}}$

Repitiendo esto${\displaystyle t}$veces, tenemos

${\displaystyle x_{t+1}^{(p+1)/4)^{t+1}}\equiv x_{0}\mod {p}}$

${\displaystyle x_{t+1}^{d_{p}}\equiv u_{p}\equiv x_{0}\mod {p}}$

Y mediante un argumento similar podemos demostrar que${\displaystyle x_{t+1}^{d_{q}}\equiv u_{q}\equiv x_{0}\mod {q}}$.

Finalmente, dado que${\displaystyle r_{p}p+r_{q}q=1}$, podemos multiplicar por${\displaystyle x_{0}}$y obtener

${\displaystyle x_{0}r_{p}p+x_{0}r_{q}q=x_{0}}$

de cuál${\displaystyle u_{q}r_{p}p+u_{p}r_{q}q\equiv x_{0}}$, módulo ambos${\displaystyle p}$y${\displaystyle q}$y por lo tanto${\displaystyle u_{q}r_{p}p+u_{p}r_{q}q\equiv x_{0}\mod {n}}$.

El esquema Blum-Goldwasser es semánticamente seguro debido a la dificultad de predecir los bits de la secuencia de claves conociendo únicamente el estado final del BBS.${\displaystyle y}$y la clave pública${\displaystyle N}$Sin embargo, los textos cifrados de la forma${\displaystyle {\vec {c}},y}$son vulnerables a un ataque adaptativo de texto cifrado elegido en el que el adversario solicita el descifrado.${\displaystyle m^{\prime }}$de un texto cifrado elegido${\displaystyle {\vec {a}},y}$. El descifrado${\displaystyle m}$del texto cifrado original se puede calcular como${\displaystyle {\vec {a}}\oplus m^{\prime }\oplus {\vec {c}}}$.

Dependiendo del tamaño del texto plano, BG puede ser más o menos costoso computacionalmente que RSA. Dado 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 generalmente supera a BG para todos los mensajes, excepto los más cortos. Sin embargo, como el exponente de descifrado de RSA se distribuye aleatoriamente, la exponenciación modular puede requerir una cantidad comparable de elevaciones al cuadrado/multiplicaciones que el descifrado de 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.

1. M. Blum, S. Goldwasser, "Un esquema de cifrado de clave pública probabilístico eficiente que oculta toda la información parcial", Actas de Advances in Cryptology – CRYPTO '84 , págs.  289–299, Springer Verlag, 1985.
2. 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

• Menezes, Oorschot, Vanstone, Scott: Manual de criptografía aplicada (descargas gratuitas en PDF), véase el capítulo 8.