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 seguro de manera probada 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 probar las propiedades de seguridad del criptosistema, Goldwasser y Micali propusieron la definición ampliamente utilizada de seguridad semántica .
Base
El criptosistema GM es semánticamente seguro basado en la supuesta intratabilidad del problema de residuosidad cuadrática módulo a 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 residuo cuadrático módulo N (es decir, x = y 2 mod N para alguna 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 conocimiento de esta factorización. El criptosistema GM aprovecha esta asimetría encriptando bits de texto plano individuales como residuos cuadráticos aleatorios o no residuos módulo 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 residuosidad 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 plano, el cifrado GM da como resultado una expansión sustancial del texto cifrado . Para prevenir ataques de factorización , se recomienda que | N | ser 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 .
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.
Definición de esquema
Goldwasser – Micali consta de tres algoritmos: un algoritmo probabilístico de generación de claves 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 mediante el siguiente procedimiento:
- Calcule x p = x mod p , x q = x mod q .
- Si y , Entonces x es un cuadrática residuo mod N .
Generación de claves
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).
- Alice genera dos distintos gran números primos p y q , aleatoria e independiente de la otra.
- Alice calcula N = pq .
- Luego encuentra un no-residuo x tal que los símbolos de Legendre satisfaceny de ahí el símbolo de Jacobi es +1. El valor x se puede encontrar, por ejemplo, seleccionando valores aleatorios y probando los dos símbolos de Legendre. Si p , q = 3 mod 4 (es decir, N es un entero de Blum ), entonces se garantiza que el valor N - 1 tiene 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:
- Bob primero codifica m como una cadena de bits ( m 1 , ..., m n ).
- Por cada pedacito , Bob genera un valor aleatorio del grupo de unidades módulo N , o. Él emite el valor.
Bob envía el texto cifrado ( c 1 , ..., c n ).
Descifrado de mensajes
Alice recibe ( c 1 , ..., c n ). Ella puede recuperar m utilizando el siguiente procedimiento:
- 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 envía el mensaje m = ( m 1 , ..., m n ).
Propiedades de seguridad
Hay una simple reducción 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" será simplemente un residuo cuadrático aleatorio, por lo que A no puede ser correcto más de la mitad de las veces. Además, este problema es auto-reducible al azar , lo que asegura 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 0 , c 1 son las encriptaciones de los bits m 0 , m 1 , entonces c 0 c 1 mod N será una encriptación de. Por esta razón, el criptosistema GM se utiliza a veces en primitivas criptográficas más complejas.
Referencias
- S. Goldwasser, S. Micali (1982). "Cifrado probabilístico y cómo jugar al póquer mental manteniendo en secreto toda la información parcial". Proc. 14º Simposio de Teoría de la Computación : 365–377. doi : 10.1145 / 800070.802212 .
- S. Goldwasser, S. Micali (1984). "Cifrado probabilístico". Revista de Ciencias de la Computación y Sistemas . 28 (2): 270–299. doi : 10.1016 / 0022-0000 (84) 90070-9 .