Criptosistema de Goldwasser–Micali

El criptosistema Goldwasser-Micali (GM) es un algoritmo de cifrado de clave asimétrica desarrollado por Shafi Goldwasser y Silvio Micali en 1982. GM tiene la distinción de ser el primer esquema de cifrado probabilístico de clave pública que es demostrablemente seguro bajo supuestos criptográficos estándar. Sin embargo, no es un criptosistema eficiente, ya que los textos cifrados pueden ser varios cientos de veces más grandes que el texto sin formato inicial. Para demostrar las propiedades de seguridad del sistema criptográfico, Goldwasser y Micali propusieron la definición ampliamente utilizada de seguridad semántica .

Base

El criptosistema GM es semánticamente seguro en función de la supuesta intratabilidad del módulo de problema de residuos cuadrático un compuesto N = pq donde p, q son números primos grandes. Esta suposición establece que dado ( x, N ) es difícil determinar si x es un módulo de residuo cuadrático N (es decir, x = y ² mod N para algunos y ), cuando el símbolo de Jacobi para x es   +1. El problema de los residuos cuadráticos se resuelve fácilmente dada la factorización de N, mientras que cualquier parte puede generar nuevos residuos cuadráticos, incluso sin el conocimiento de esta factorización. El criptosistema GM aprovecha esta asimetría al encriptar bits de texto sin formato individuales como residuos cuadráticos aleatorios o módulos no residuales N, todos con símbolo de residuo cuadrático   +1. Los destinatarios utilizan la factorización de N como clave secreta y descifran el mensaje probando la residualidad cuadrática de los valores de texto cifrado recibidos.

Porque Goldwasser – Micali produce un valor de tamaño aproximadamente | N | Para cifrar cada bit de un texto sin formato, el cifrado de GM da como resultado una expansión sustancial de texto cifrado . Para evitar ataques de factorización, se recomienda que | N | ser varios cientos de bits o más. Por lo tanto, el esquema sirve principalmente como una prueba de concepto, y desde entonces se han desarrollado esquemas más eficientes con seguridad comprobable como Elgamal .

Debido a que el cifrado se realiza utilizando un algoritmo probabilístico, un texto plano dado 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 al compararlos con un diccionario de textos cifrados conocidos.

Definición del esquema

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

El esquema se basa en decidir si un valor dado x es un mod cuadrado N, dada la factorización ( p, q ) de N. Esto se puede lograr utilizando el siguiente procedimiento:

1. Calcule x _p = x mod p, x _q = x mod q .
2. Si $x_{p}^{(p-1)/2}\equiv 1{\pmod {p}}$ y $x_{q}^{(q-1)/2}\equiv 1{\pmod {q}}$, entonces x es un mod de residuo cuadrático   N.

Generación clave

El módulo utilizado en el cifrado GM se genera de la misma manera que en el criptosistema RSA . (Ver RSA, generación de claves para más detalles. )

1. Alice genera dos números primos grandes distintos p y q, aleatoriamente e independientemente uno del otro.
2. Alice calcula N = pq .
3. Luego encuentra algo que no deja residuos x, de modo que los símbolos Legendre satisfagan $\left({\frac {x}{p}}\right)=\left({\frac {x}{q}}\right)=-1$ y de ahí el símbolo de Jacobi $\left({\frac {x}{N}}\right)$ es   +1. El valor x se puede encontrar, por ejemplo, seleccionando valores aleatorios y probando los dos símbolos Legendre. Si p, q = 3 mod 4 (es decir, N es un número entero de Blum ), entonces el valor N   −   1 está garantizado para tener la propiedad requerida.

La clave pública consta de ( x,   N ) La clave secreta es la factorización.   ( p,   q ).

Cifrado de mensajes

Supongamos que Bob desea enviar un mensaje m a Alice:

1. Bob primero codifica m como una cadena de bits ( m ₁, ..., m _n ).
2. Por cada bit $m_{i}$, Bob genera un valor aleatorio $y_{i}$ del grupo de unidades módulo   N o $\gcd(y_{i},N)=1$ . Saca el valor $c_{i}=y_{i}^{2}x^{m_{i}}{\pmod {N}}$ .

Bob envía el texto cifrado ( c ₁, ..., c _n ).

Descifrado de mensajes

Alicia recibe ( c ₁, ..., c _n ). Ella puede recuperar m utilizando el siguiente procedimiento:

1. Para cada i, usando la factorización prima ( p, q ), Alice determina si el valor c _i es un residuo cuadrático; si es así, m _i = 0, de lo contrario m _i = 1.

Alice emite el mensaje m = ( m ₁, ..., m _n ).

Propiedades de seguridad

Hay una reducción simple de romper este criptosistema al problema de determinar si un módulo de valor aleatorio N con el símbolo de Jacobi +1 es un residuo cuadrático. Si un algoritmo A rompe el sistema criptográfico, para determinar si un valor dado x es un módulo de residuo cuadrático N, probamos A para ver si puede romper el sistema criptográfico utilizando ( x, N ) como clave pública. Si x no es un residuo, entonces A debería funcionar correctamente. Sin embargo, si x es un residuo, entonces cada "texto cifrado" será simplemente un residuo cuadrático aleatorio, por lo que A no puede ser correcto más de la mitad del tiempo. Además, este problema es auto-reducible al azar, lo que garantiza que para una N dada, cada clave pública sea tan segura como cualquier otra clave pública.

El criptosistema GM tiene propiedades homomórficas, en el sentido de que si c ₀, c ₁ son los cifrados de los bits m ₀, m ₁, entonces c ₀ c ₁ mod   N será un cifrado de $m_{0}\oplus m_{1}$ . Por esta razón, el criptosistema GM a veces se usa en primitivas criptográficas más complejas.

Referencias

• S. Goldwasser, S. Micali (1982). «Probabilistic encryption and how to play mental poker keeping secret all partial information». Proc. 14th Symposium on Theory of Computing: 365-377. doi:10.1145/800070.802212. 
• S. Goldwasser, S. Micali (1984). «Probabilistic encryption». Journal of Computer and System Sciences 28 (2): 270-299. doi:10.1016/0022-0000(84)90070-9. 

Véase también

• Blum – Goldwasser cryptosystem

• Datos: Q742758