El cifrado probabilístico es el uso de la aleatoriedad en un algoritmo de cifrado , de modo que al cifrar el mismo mensaje varias veces, en general, arrojará diferentes textos cifrados . El término "encriptación probabilística" se usa típicamente en referencia a algoritmos de encriptación de clave pública ; sin embargo, varios algoritmos de cifrado de claves simétricas logran una propiedad similar (por ejemplo, cifrados de bloque cuando se utilizan en un modo de encadenamiento como CBC ), y cifrados de flujo como Freestyle [1] que son inherentemente aleatorios. Ser semánticamente seguro , es decir, ocultar incluso información parcial sobre el texto sin formato., un algoritmo de cifrado debe ser probabilístico .
Historia
Shafi Goldwasser y Silvio Micali propusieron el primer esquema de cifrado probabilístico de clave pública demostrablemente seguro , basado en la dureza del problema de residuosidad cuadrática y tenía un factor de expansión de mensaje igual al tamaño de la clave pública. Los algoritmos de cifrado probabilístico más eficientes incluyen Elgamal , Paillier y varias construcciones bajo el modelo de oráculo aleatorio , incluido OAEP.
Seguridad
El cifrado probabilístico es particularmente importante cuando se utiliza criptografía de clave pública . Supongamos que el adversario observa un texto cifrado y sospecha que el texto sin formato es "SÍ" o "NO", o tiene la corazonada de que el texto sin formato podría ser "ATAQUE A CALAIS". Cuando se utiliza un algoritmo de cifrado determinista , el adversario puede simplemente intentar cifrar cada una de sus suposiciones con la clave pública del destinatario y comparar cada resultado con el texto cifrado de destino. Para combatir este ataque, los esquemas de cifrado de clave pública deben incorporar un elemento de aleatoriedad, asegurando que cada texto plano se mapee en uno de un gran número de posibles textos cifrados.
Un enfoque intuitivo para convertir un esquema de cifrado determinista en uno probabilístico es simplemente rellenar el texto sin formato con una cadena aleatoria antes de cifrar con el algoritmo determinista . Por el contrario, el descifrado implica aplicar un algoritmo determinista e ignorar el relleno aleatorio. Sin embargo, los primeros esquemas que aplicaron este enfoque ingenuo se rompieron debido a limitaciones en algunos esquemas de cifrado deterministas. Técnicas como el relleno de cifrado asimétrico óptimo (OAEP) integran el relleno aleatorio de forma segura mediante cualquier permutación de trampilla .
Ejemplos de
Ejemplo de cifrado probabilístico utilizando cualquier permutación de trampilla:
- x - texto plano de un solo bit
- f - permutación de trampilla (algoritmo de cifrado determinista)
- b - predicado de núcleo duro de f
- r - cadena aleatoria
Esto es ineficaz porque solo se cifra un bit. En otras palabras, el factor de expansión del mensaje es igual al tamaño de la clave pública.
Ejemplo de cifrado probabilístico en el modelo de oráculo aleatorio:
- x - texto sin formato
- f - permutación de trampilla (algoritmo de cifrado determinista)
- h : oráculo aleatorio (generalmente implementado usando una función hash especificada públicamente )
- r - cadena aleatoria
Ver también
Referencias
- ^ Puthuparambil, Arun Babu; Thomas, Jithin Jose (1 de diciembre de 2019). "Freestyle, una versión aleatoria de ChaCha para resistir ataques de diccionario y fuerza bruta fuera de línea". Revista de aplicaciones y seguridad de la información . 49 : 102396. arXiv : 1802.03201 . doi : 10.1016 / j.jisa.2019.102396 . ISSN 2214-2126 .
enlaces externos
- Shafi Goldwasser y Silvio Micali, cifrado probabilístico , número especial de Journal of Computer and Systems Sciences, vol. 28, núm. 2, páginas 270-299, abril de 1984
- Freestyle, una versión aleatoria de ChaCha para resistir ataques de diccionario y de fuerza bruta fuera de línea [1] .