Criptografía Blum-Goldwasser

Algoritmo de cifrado de clave asimétrica

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 , 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 el flujo de claves . El descifrado se logra manipulando el estado final del generador BBS utilizando la clave privada , para encontrar la semilla inicial y reconstruir el flujo de claves.

El criptosistema BG es semánticamente seguro basándose en la supuesta intratabilidad de la factorización de números enteros ; específicamente, factorizar un valor compuesto donde son primos grandes . BG tiene múltiples ventajas sobre los esquemas de cifrado probabilístico anteriores, como el criptosistema Goldwasser-Micali . En primer lugar, su seguridad semántica se reduce únicamente a la factorización de números enteros, sin requerir ningún supuesto adicional (por ejemplo, la dureza del problema de residuosidad cuadrática o el problema 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 computación, y se desempeña bien incluso en comparación con criptosistemas como RSA (dependiendo de la longitud del mensaje y las opciones de exponente). Sin embargo, BG es altamente vulnerable a ataques de texto cifrado elegido adaptativo (ver más abajo). ${\displaystyle N=pq}$ ${\displaystyle p,q}$

Como el cifrado se realiza mediante un algoritmo probabilístico, un texto simple determinado puede generar textos cifrados muy diferentes cada vez que se cifra. Esto tiene ventajas significativas, ya que impide 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ístico 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:

1. Elija dos números primos grandes y distintos tales que y . ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p\equiv 3{\bmod {4}}}$ ${\displaystyle q\equiv 3{\bmod {4}}}$
2. Calcular . ^[1] ${\displaystyle n=pq}$

Entonces es la clave pública y el par es la clave privada. ${\displaystyle n}$ ${\displaystyle (p,q)}$

Encriptación

Un mensaje se cifra con la clave pública de la siguiente manera: ${\displaystyle M}$ ${\displaystyle n}$

1. Calcular el tamaño del bloque en bits, . ${\displaystyle h=\lfloor log_{2}(log_{2}(n))\rfloor }$
2. Convertir a una secuencia de bloques , donde cada bloque tiene una longitud de bits. ${\displaystyle M}$ ${\displaystyle t}$ ${\displaystyle m_{1},m_{2},\dots ,m_{t}}$ ${\displaystyle h}$
3. Seleccione un número entero aleatorio . ${\displaystyle r<n}$
4. Calcular . ${\displaystyle x_{0}=r^{2}{\bmod {n}}}$
5. Para del 1 al ${\displaystyle i}$ ${\displaystyle t}$
   1. Calcular . ${\displaystyle x_{i}=x_{i-1}^{2}{\bmod {n}}}$
   2. Calcular los bits menos significativos de . ${\displaystyle p_{i}=}$ ${\displaystyle h}$ ${\displaystyle x_{i}}$
   3. Calcular . ${\displaystyle c_{i}=m_{i}\oplus p_{i}}$
6. Finalmente, calcule . ${\displaystyle x_{t+1}=x_{t}^{2}{\bmod {n}}}$

El cifrado del mensaje es entonces todos los valores más el valor final : . ${\displaystyle M}$ ${\displaystyle c_{i}}$ ${\displaystyle x_{t+1}}$ ${\displaystyle (c_{1},c_{2},\dots ,c_{t},x_{t+1})}$

Descifrado

Un mensaje cifrado se puede descifrar con la clave privada de la siguiente manera: ${\displaystyle (c_{1},c_{2},\dots ,c_{t},x)}$ ${\displaystyle (p,q)}$

1. Calcular . ${\displaystyle d_{p}=((p+1)/4)^{t+1}{\bmod {(p-1)}}}$
2. Calcular . ${\displaystyle d_{q}=((q+1)/4)^{t+1}{\bmod {(q-1)}}}$
3. Calcular . ${\displaystyle u_{p}=x^{d_{p}}{\bmod {p}}}$
4. Calcular . ${\displaystyle u_{q}=x^{d_{q}}{\bmod {q}}}$
5. Utilizando el algoritmo euclidiano extendido , calcule y tal que . ${\displaystyle r_{p}}$ ${\displaystyle r_{q}}$ ${\displaystyle r_{p}p+r_{q}q=1}$
6. 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, de la siguiente manera. ${\displaystyle x_{0}=u_{q}r_{p}p+u_{p}r_{q}q{\bmod {n}}}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{i}}$
7. Para del 1 al ${\displaystyle i}$ ${\displaystyle t}$
   1. Calcular . ${\displaystyle x_{i}=x_{i-1}^{2}{\bmod {n}}}$
   2. Calcular los bits menos significativos de . ${\displaystyle p_{i}=}$ ${\displaystyle h}$ ${\displaystyle x_{i}}$
   3. Calcular . ${\displaystyle m_{i}=c_{i}\oplus p_{i}}$
8. Por último, vuelva a ensamblar los valores en el mensaje . ${\displaystyle (m_{1},m_{2},\dots ,m_{t})}$ ${\displaystyle M}$

Ejemplo

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

${\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 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 x_{0}}$

${\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}}}$

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. ${\displaystyle x_{0}}$

En el algoritmo de cifrado, por construcción es un residuo cuadrático módulo . Por lo tanto, también es un residuo cuadrático módulo , al igual que todos los demás valores obtenidos a partir de él al elevarlo al cuadrado. Por lo tanto, por el criterio de Euler , . Entonces ${\displaystyle x_{0}}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}^{(p-1)/2}\equiv 1\mod {p}}$

${\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 obtenemos ${\displaystyle (p+1)/4}$

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

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

${\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 con un argumento similar podemos demostrar que . ${\displaystyle x_{t+1}^{d_{q}}\equiv u_{q}\equiv x_{0}\mod {q}}$

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

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

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

Seguridad y eficiencia

El esquema Blum–Goldwasser es semánticamente seguro en función de la dificultad de predecir los bits de la secuencia de claves dados únicamente el estado final de BBS y la clave pública . Sin embargo, los textos cifrados de la forma son 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 . ${\displaystyle y}$ ${\displaystyle N}$ ${\displaystyle {\vec {c}},y}$ ${\displaystyle m^{\prime }}$ ${\displaystyle {\vec {a}},y}$ ${\displaystyle m}$ ${\displaystyle {\vec {a}}\oplus m^{\prime }\oplus {\vec {c}}}$

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 generalmente superará a BG para todos los mensajes, excepto los más cortos. Sin embargo, como el exponente de descifrado RSA se distribuye aleatoriamente, la exponenciación modular puede requerir una cantidad comparable de elevaciones al cuadrado/multiplicaciones a la 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

1. RFC  4086 sección "6.2.2. El generador de secuencias Blum Blum Shub"

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 

Enlaces externos

• Menezes, Oorschot, Vanstone, Scott: Manual de criptografía aplicada (descargas gratuitas en PDF), consulte el Capítulo 8