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 de clave pública probabilístico 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 simple inicial. Para demostrar las propiedades de seguridad del criptosistema, Goldwasser y Micali propusieron la definición ampliamente utilizada de seguridad semántica .
El criptosistema GM es semánticamente seguro en base a la supuesta intratabilidad del problema de residuosidad cuadrática módulo un compuesto N = pq donde p, q son primos grandes . Esta suposición establece que dado ( x , N ) es difícil determinar si x es un residuo cuadrático módulo N (es decir, x = y 2 mod N para algún y ), cuando el símbolo de Jacobi para x es +1. El problema de residuos cuadráticos se resuelve fácilmente dada la factorización de N , mientras que nuevos residuos cuadráticos pueden ser generados por cualquier parte, incluso sin conocimiento de esta factorización. El criptosistema GM aprovecha esta asimetría al cifrar bits de texto simple individuales como residuos cuadráticos aleatorios o no residuos módulo N , todos con símbolo de residuo cuadrático +1. Los destinatarios usan la factorización de N como una clave secreta y descifran el mensaje probando la residuosidad cuadrática de los valores de texto cifrado recibidos.
Debido a que Goldwasser–Micali produce un valor de tamaño aproximado de | N | para cifrar cada bit de un texto simple, el cifrado GM da como resultado una expansión sustancial del texto cifrado . Para evitar ataques de factorización , se recomienda que | N | sea de 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 y demostrablemente seguros como ElGamal .
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.
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 cuadrado módulo N , dada la factorización ( p , q ) de N. Esto se puede lograr utilizando el siguiente procedimiento:
El módulo utilizado en el cifrado GM se genera de la misma manera que en el criptosistema RSA . (Consulte RSA , generación de claves para obtener más detalles).
La clave pública consta de ( x , N ). La clave secreta es la factorización ( p , q ).
Supongamos que Bob desea enviar un mensaje m a Alice:
Bob envía el texto cifrado ( c 1 , ..., c n ).
Alice recibe ( c 1 , ..., c n ). Puede recuperar m utilizando el siguiente procedimiento:
Alice emite el mensaje m = ( m 1 , ..., m n ).
Hay una reducción simple de romper este criptosistema al problema de determinar si un valor aleatorio módulo N con símbolo de Jacobi +1 es un residuo cuadrático. Si un algoritmo A rompe el criptosistema, entonces para determinar si un valor dado x es un residuo cuadrático módulo N , probamos A para ver si puede romper el criptosistema usando ( 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" simplemente será 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 aleatorio auto-reducible , lo que garantiza que para un N dado , cada clave pública es tan segura como cualquier otra clave pública.
El criptosistema GM tiene propiedades homomórficas , en el sentido de que si c 0 , c 1 son los cifrados de los bits m 0 , m 1 , entonces c 0 c 1 mod N será un cifrado de . Por este motivo, el criptosistema GM se utiliza a veces en primitivas criptográficas más complejas.
